مسئله فرشته

منطقهٔ خط چین آبی خانه‌هایی که توسط فرشتهٔ با قدرت ۳ قابل دست رسی است، را نشان می‌دهد.

مسئله فرشته از مسائل نظریه بازی‌ها است که توسط هرتن کانوی پیشنهاد شد. این بازی معمولاً با نام فرشته‌ها شیاطین شناخته می‌شود. بازی دو بازیکن به نامهای فرشته و شیطان دارد و روی صفحهٔ شطرنج نا متناهی (یا به‌طور هم ارز نقاط روی صفحه مشبّک دوبعدی) بازی می‌شود. فرشته مانند شاه شطرنج حرکت می‌کند، امّا بسته به هر بازی قدرت متفاوتk(عددی طبیعی بزرگتر یا مساوی ۱)دارد. بازی با صفحهٔ خالی و فرشته در خانهٔ شروع آغاز می‌شود. در هر نوبت فرشته به یک خانه متفاوت به فاصله حد اکثر k، یعنی خانه‌ای که با حد اکثر k حرکت فرشته قابل دسترسی است. (فاصله از مربّع شروع در نرم نامتناهی حد اکثر kاست)شیطان در هر نوبت می‌تواند مانعی در هر خانه به جز خانه حاوی فرشته قرار دهد. فرشته می‌تواند از روی موانع پرش کند، امّا نمی‌تواند در آن خانه‌ها قرار گیرد. در صورتی که فرشته قادر به انجام حرکتی نباشد، شیطان پیرّوز خواهد شد، همچنین اگر فرشته بتواند به تعداد نامتناهی بار نجات پیدا کند فرشته برنده خواهد بود.

حال سؤال این است که آیا فرشته‌ای با قدرت کافی می‌تواند پیروز شود؟

باید استراتژی ای برای پیروزی یکی از دو بازیکن وجود داشته باشد. اگر شیطان برنده شود، این کار را در تعداد متناهی حرکت می‌تواند انجام دهد و اگر شیطان نتواند برنده شود، همواره حرکتی برای فرشته برای رهایی از شکست وجود خواهد داشت و استراتژی پیروزی برای او این خواهد بود که چنین حرکتی را انتخاب کند. به‌طور مطلق، مجموعه پرداخت (مجموعه همه بازیهایی که در آن‌ها فرشته برنده می‌شود) مجموعه‌ای بسته‌است، و این بازی‌ها مشخّص‌اند.

کانوی جایزی برای حل کلّی این مسئله(۱۰۰$ برای ارایهٔ یک استراتژی پیروزی برای فرشتی با قدرت کافی، و ۱۰۰۰$ برای اثبات این که شیطان می‌تواند مستقل از قدرت فرشته پیروز شود). ابتدا پیشرفتهایی در ابعاد بالاتر صورت گرفت و اثبات‌های زیبایی ارائه شد. در سال ۲۰۰۶، مسئله اصلی حل شد و ثابت شد که فرشته می‌تواند پیروز شود.

تاریخچه

مسئله ابتدا در سال ۱۹۸۲ در کتاب استراتژی برد نوشته برلکمپ، کانوی و گای، با نام «فرشته و مربّع خوار» منتشر شد. در فضای دو بعدی. چند نتیجه جزئی شامل:

• اگر فرشته قدرت ۱ داشته باشد، شیطان استراتژی پیروزی دارد(کانوی، ۱۹۸۲)(طبق گفته کانوی این نتیجه‌گیری متعلق به برلکمپ است)
• اگر فرشته هرگز مولفه yخود را افزایش ندهد، شیطان استراتژی پیروزی دارد. (کانوی ۱۹۸۲)
• اگر فرشته همواره فصلهٔ خود را از مبدأ زیاد کند، شیطان استراتژی پیروزی دارد (کانوی. ۱۹۹۶)

در ۳ بد نشان داده شده‌است که:

• اگر فرشته همواره مؤلفهyخود را افزایش دهد، و شیطان فقط بتواند در یک صفحه بازی کند، آنگاه فرشته استراتژی پیروزی دارد.
• اگر فرشته همواره مؤلفه yخود را افزایش دهد، و شیطان فقط بتواند در دو صفحه بازی کند، آنگاه فرشته استراتژی پیروزی دارد.
• اگر فرشته قدرت بزرگتر یا مساوی ۱۳ داشته باشد، استراتژی پیروزی دارد.
• اگر تعدادی متناهی شیطان داشته باشیم که هر کدام در فواصل ...>d_۱<d_۲< ''d_۳''بازی می‌کنند، آنگه فرشته در صورتی که قدرت کافی داشته باشد، همچنان می‌تواند پیروز شود. (منظور از «بازی در فاصله d» این است که شیطان نمی‌تواند در این فواصل از مبدأ بازی کند).

نهایتاً، در سال ۲۰۰۶، در حالی که زمان زیادی از انتشار کتاب Peter Winkler «معماهای ریاضی» که کمک به سزایی در معرفی این مسئله به عموم داشت، چهار اثبات مستقل و تقریباً به‌طور هم‌زمان برای وجود استراتژی پیروزی فرشته در دو بعد مطرح شدند. اثبات Brian Bowditch برای ۴-فرشته درست بود، ولی اثبات‌های Oddvar Kloster و András Máthé برای ۲-فرشته درست بود. اثبات Péter Gács برای ثابت کمی بزرگتر برقرار بود. اثبات‌های Bowditchو Máthé در ترکیب‌شناسی، احتمال و محاسبه (ویراسته توسط Bela Bollobas و Imre Leader)به چاپ رسیده‌است.

سؤال‌های حل نشدهٔ دیگر در سه بعد

اگر فرشته فقط مؤلفه y خود را افزایش دهد، و شیطان فقط به بازی در ۳ صفحه محدود شود، معلوم نیست که آیا شیطان استراتژی پیروزی دارد یا نه.

طرح کلی اثبات این که فرشته با قدرت زیاد در سه بعد استراتژی پیروزی دارد

این اثبات ملزم به استفاده نگهبانان است. برای هر مکعب با هر اندازه، نگهبانی از آن مکعب محافظت می‌کند. نگهبانان در مورد بی‌خطر یا تقریباً بی‌خطر بودن یا خطرناک بودن هر حرکت در آن مکعب تصمیم می‌گیرند. این تصمیم بستگی به تراکم موانع و ابعاد آن مکعب دارد. اگر فرشته دستوری دریافت نکند، آنگاه فقط به سمت بالا می‌رود. اگر برخی از مکعب‌ها که فرشته در آن‌ها قرار دارد امن باشند، آنگاه نگهبان بزرگّترین این مکعب‌ها به فرشته دستور می‌دهد که به یکی از مرژای این مکعب برود. اگر قرار باشد که یک نگهبان، از فرشته تا رسیدن به یک وجه به خصوص آن مکعب محافظت کند، آنگه نگهبان این کار را با مشخص کردن مسیری از زیر مکعب‌ها که همگی امن هستند انجام می‌دهد. نگهبانان نگهبانان این مکعب‌ها نیز از فرشته تا رسیدن به زیر مکعب مربوط محافظت مکنند. ثابت می‌شود که این استراتژی کار می‌کند، زیرا زمانی که لازم است تا شیطان یک مکعب امن در مسیر فرشته را به مکعبی نا امن تبدیل کند، بیشتر از زمانی است که برای رسیدن فرشته به آن مکعب لازم است. تعریف امن یا نا امن بودن برای تضمین این اتفاق لازم است. توجه:مسیر فرشته در یه زیر مکعب تا زمانی که فرشته با آن نرسیده‌است مشخص نیست، حتی بعد از رسیدن نیز فقط طرحی تقریبی از این مسیر وجود دارد. به همین دلیل شیطان نمی‌تواند مکانی را در مسیر که از فرشته فاصله زیادی دارد را نا امن کند. این اثبات متعلق بهImre LeaderوBéla Bollobás است. اثباتی مشابه نیز توسط Martin Kutzمنتشر شده‌است.

طرح کلی اثبات Máthé

Máthéشیطان نجیب را مرفی کرد، که هیچ‌گاه خانه‌ای که فرشته در نوبت زودتر می‌تواند برای اشغال انتخاب کند. نابود نمی‌کند. وقتی فرشته در مقابل شیطان نجیب بازی می‌کند، در صورتی شکست می‌خورد که شیطان او را در یک منطقه بسته محبوس کند (در غیر این صورت فرشته فقط می‌تواند بین دو خانه جست و خیز کند؟!!!>:"ل: و هرگز شکست نمی‌خورد!)، اثبات Máthé به دو قسمت تقسیم می‌شود:(۱)او نشان داد که اگر فرشته بتواند در برابر شیطان نجیب پیروز شود، در مقابل شیطان واقعی نیز پیروز می‌شود؛ (۲)او استراتژی دقیقی را نیز برای پیروزی فرشته مقابل شیطان نجیب ارائه داد. به‌طور کلی دربارهٔ قسمت دوم، اگر فرشته وانمود کند که تمام نیم-صفحه سمت چپ خراب می‌شود (علاوه بر خانه‌هایی که توسط شیطان نجیب خراب شده‌اند)، و با خانه‌های خراب شده مثل دیوارهای یک راه پر پیچ و خم رفتار کند، و آن‌ها رو دور زند، می‌تواند شیطان نجیب را شکست دهد. این کار به وسیله تکنیک «دست روی دیوار»(hand-on-the-wall)انجام می‌شود، به این صورت که فرشته دست چپ خود را به دیوارهای راه تکیه می‌دهد و در طول مسیر دیوار می‌دود. Máthéثابت کرد که با این روش شیطان نجیب نمی‌تواند فرشته را به دام بیندازد. اثبات قسمت (۱) به وسیله برهان خلف است، بنابراین اثبات Máthé به‌طور مستقیم یک استراتژی پیروزی در برابر شیطان واقعی ارائه نمی‌دهد.

طرح کلی اثبات Bowditch

Bowditch بازی متفاوتی از بازی اصلی با قوانین تغییر یافتهٔ زیر نسبت به بازی اصلی ارائه داد:

1. فرشته می‌تواند به هر خانه‌ای که قبلاً در آن بوده برگردد، حتی اگر شیطان متعاقباً سعی در مانع گذاری در آن را داشته باشد. !؟
2. یک k-شیطان قبل از مانع گذاری در یک خانه kبار در آن وارد شده باشد.
3. فرشته فقط می‌تواند یک خانه در جهات مختلف حرکت کند.
4. برای پیروزی فرشته باید مسیر غیر مستقیم (تعریف شده در ذیل) را طی کند.

مسیر غیرمستقیم مسیری است که $\pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})$و$\sigma =\cup _{i=1}^{\infty }\sigma _{i}$یک کمان نیمه نامتناهی است (مسیری غیر خود متقطع که نقطه شروع دارد ولی نقطه پایان ندارد)و γi دورهای دو به دو منفصل از هم هستند که دارای ویژگی‌های زیر اند:

• $\forall i:|\gamma _{i}|\leq i$که | γi | طول iامین دور است.

(توجه داشته باشید که برای خوش تعریف بودن، باید نقطهٔ شروع و پایان γi نقطه پایانی σiباشد و σi باید در نقطهٔ شروع σi + ۱ پایان یابد)

Bowditchبازی متفاوتی با بازی قبل (بازی ۱) با تغییر ۲ و ۳ به ۵-شیطان در نظر گرفت. سپس نشان داد که استراتژی پیروزی در این بازی استراتژی پیروزی در بازی اصلی برای ۴-فرشته را نتیجه می‌دهد. او نشان داد که فرشته‌ای که با یک ۵-شیطان بازی می‌کند، می‌تواند با یک الگوریتم ساده پیروز شود.

Bowditchادعا کرد که یک ۴-فرشته، با در نظر گرفتن یک فرشته خیالی که با یک ۵-شیطان در بازی ۲ بازی می‌کند، می‌تواند پیروز شود.

فرشته، مسیر فرشتهٔ خیالی بدون در نظر گرفتن دور هارادنبال می‌کند. بنا بر این چون مسیرσ یک کمان نیمه متناهی است، فرشته به خانه‌ای که قبلاً در آن بوده بر نمی‌گردد، پس مسیر، یک مسیر پیروزی خواهد بود، حتی در بازی اصلی.

همچنین مشاهده کنید

Homicidal chauffeur problem

منابع

• Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your mathematical plays, volume 2: Games in Particular, Academic Press, 1982.
• Brian H. Bowditch, The angel game in the plane, Combin. Probab. Comput. ۱۶(۳):۳۴۵–۳۶۲، ۲۰۰۷.
• John H. Conway, The angel problem, in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages ۳–۱۲، ۱۹۹۶.
• Martin Kutz, Conway's Angel in three dimensions, Theoret. Comp. Sci. ۳۴۹(۳):۴۴۳–۴۵۱، ۲۰۰۵.
• Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, PhD Thesis FU Berlin, ۲۰۰۴
• András Máthé, The angel of power 2 wins, Combin. Probab. Comput. ۱۶(۳):۳۶۳–۳۷۴، ۲۰۰۷.

پیوند به بیرون

• The Angel problem by John H Conway
• Kloster's Angel Problem site