مسئله فرشته
مسئله فرشته از مسائل نظریه بازی‌ها است که توسط هرتن کانوی پیشنهاد شد. این بازی معمولاً با نام فرشته‌ها شیاطین شناخته می‌شود. بازی دو بازیکن به نامهای فرشته و شیطان دارد و روی صفحهٔ شطرنج نا متناهی (یا به‌طور هم ارز نقاط روی صفحه مشبّک دوبعدی) بازی می‌شود. فرشته مانند شاه شطرنج حرکت می‌کند، امّا بسته به هر بازی قدرت متفاوت"k"(عددی طبیعی بزرگتر یا مساوی ۱)دارد. بازی با صفحهٔ خالی و فرشته در خانهٔ شروع آغاز می‌شود. در هر نوبت فرشته به یک خانه متفاوت به فاصله حد اکثر "k"، یعنی خانه‌ای که با حد اکثر "k" حرکت فرشته قابل دسترسی است. (فاصله از مربّع شروع در نرم نامتناهی حد اکثر "k"است)شیطان در هر نوبت می‌تواند مانعی در هر خانه به جز خانه حاوی فرشته قرار دهد. فرشته می‌تواند از روی موانع پرش کند، امّا نمی‌تواند در آن خانه‌ها قرار گیرد. در صورتی که فرشته قادر به انجام حرکتی نباشد، شیطان پیرّوز خواهد شد، همچنین اگر فرشته بتواند به تعداد نامتناهی بار نجات پیدا کند فرشته برنده خواهد بود.
باید استراتژی ای برای پیروزی یکی از دو بازیکن وجود داشته باشد. اگر شیطان برنده شود، این کار را در تعداد متناهی حرکت می‌تواند انجام دهد و اگر شیطان نتواند برنده شود، همواره حرکتی برای فرشته برای رهایی از شکست وجود خواهد داشت و استراتژی پیروزی برای او این خواهد بود که چنین حرکتی را انتخاب کند. به‌طور مطلق، مجموعه پرداخت (مجموعه همه بازیهایی که در آن‌ها فرشته برنده می‌شود) مجموعه‌ای بسته‌است، و این بازی‌ها مشخّص‌اند.
"کانوی" جایزی برای حل کلّی این مسئله(۱۰۰$ برای ارایهٔ یک استراتژی پیروزی برای فرشتی با قدرت کافی، و ۱۰۰۰$ برای اثبات این که شیطان می‌تواند مستقل از قدرت فرشته پیروز شود). ابتدا پیشرفتهایی در ابعاد بالاتر صورت گرفت و اثبات‌های زیبایی ارائه شد. در سال ۲۰۰۶، مسئله اصلی حل شد و ثابت شد که فرشته می‌تواند پیروز شود.
مسئله ابتدا در سال ۱۹۸۲ در کتاب استراتژی برد نوشته "برلکمپ"، "کانوی" و "گای"، با نام «"فرشته و مربّع خوار"» منتشر شد. در فضای دو بعدی. چند نتیجه جزئی شامل: در ۳ بد نشان داده شده‌است که: نهایتاً، در سال ۲۰۰۶، در حالی که زمان زیادی از انتشار کتاب 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é به دو قسمت تقسیم می‌شود:(۱)او نشان داد که اگر فرشته بتواند در برابر شیطان نجیب پیروز شود، در مقابل شیطان واقعی نیز پیروز می‌شود؛ (۲)او استراتژی دقیقی را نیز برای پیروزی فرشته مقابل شیطان نجیب ارائه داد. به‌طور کلی دربارهٔ قسمت دوم، اگر فرشته وانمود کند که تمام نیم-صفحه سمت چپ خراب می‌شود (علاوه بر خانه‌هایی که توسط شیطان نجیب خراب شده‌اند)، و با خانه‌های خراب شده مثل دیوارهای یک راه پر پیچ و خم رفتار کند، و آن‌ها رو دور زند، می‌تواند شیطان نجیب را شکست دهد. این کار به وسیله تکنیک «دست روی دیوار»(hand-on-the-wall)انجام می‌شود، به این صورت که فرشته دست چپ خود را به دیوارهای راه تکیه می‌دهد و در طول مسیر دیوار می‌دود. Máthéثابت کرد که با این روش شیطان نجیب نمی‌تواند فرشته را به دام بیندازد. اثبات قسمت (۱) به وسیله برهان خلف است، بنابراین اثبات Máthé به‌طور مستقیم یک استراتژی پیروزی در برابر شیطان واقعی ارائه نمی‌دهد.
Bowditch بازی متفاوتی از بازی اصلی با قوانین تغییر یافتهٔ زیر نسبت به بازی اصلی ارائه داد:
مسیر غیرمستقیم مسیری است که formula_1وformula_2یک کمان نیمه نامتناهی است (مسیری غیر خود متقطع که نقطه شروع دارد ولی نقطه پایان ندارد)و γi دورهای دو به دو منفصل از هم هستند که دارای ویژگی‌های زیر اند: (توجه داشته باشید که برای خوش تعریف بودن، باید نقطهٔ شروع و پایان γi نقطه پایانی σiباشد و σi باید در نقطهٔ شروع σi + ۱ پایان یابد)
Bowditchبازی متفاوتی با بازی قبل (بازی ۱) با تغییر ۲ و ۳ به ۵-شیطان در نظر گرفت. سپس نشان داد که استراتژی پیروزی در این بازی استراتژی پیروزی در بازی اصلی برای ۴-فرشته را نتیجه می‌دهد. او نشان داد که فرشته‌ای که با یک ۵-شیطان بازی می‌کند، می‌تواند با یک الگوریتم ساده پیروز شود.
Bowditchادعا کرد که یک ۴-فرشته، با در نظر گرفتن یک فرشته خیالی که با یک ۵-شیطان در بازی ۲ بازی می‌کند، می‌تواند پیروز شود.
فرشته، مسیر فرشتهٔ خیالی بدون در نظر گرفتن دور هارادنبال می‌کند. بنا بر این چون مسیرσ یک کمان نیمه متناهی است، فرشته به خانه‌ای که قبلاً در آن بوده بر نمی‌گردد، پس مسیر، یک مسیر پیروزی خواهد بود، حتی در بازی اصلی.