موضوع مقاله: مسئله فرشته | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله فرشته | مقدمه: بازی دو بازیکن به نامهای فرشته و شیطان دارد و روی صفحهٔ شطرنج نا متناهی (یا به‌طور هم ارز نقاط روی صفحه مشبّک دوبعدی) بازی می‌شود. | ## بخش 1: مسئله فرشته | فرشته مانند شاه شطرنج حرکت می‌کند، امّا بسته به هر بازی قدرت متفاوتk(عددی طبیعی بزرگتر یا مساوی ۱)دارد. در هر نوبت فرشته به یک خانه متفاوت به فاصله حد اکثر k، یعنی خانه‌ای که با حد اکثر k حرکت فرشته قابل دسترسی است. (فاصله از مربّع شروع در نرم نامتناهی حد اکثر kاست)شیطان در هر نوبت می‌تواند مانعی در هر خانه به جز خانه حاوی فرشته قرار دهد. در صورتی که فرشته قادر به انجام حرکتی نباشد، شیطان پیرّوز خواهد شد، همچنین اگر فرشته بتواند به تعداد نامتناهی بار نجات پیدا کند فرشته برنده خواهد بود. اگر شیطان برنده شود، این کار را در تعداد متناهی حرکت می‌تواند انجام دهد و اگر شیطان نتواند برنده شود، همواره حرکتی برای فرشته برای رهایی از شکست وجود خواهد داشت و استراتژی پیروزی برای او این خواهد بود که چنین حرکتی را انتخاب کند. به‌طور مطلق، مجموعه پرداخت (مجموعه همه بازیهایی که در آن‌ها فرشته برنده می‌شود) مجموعه‌ای بسته‌است، و این بازی‌ها مشخّص‌اند. کانوی جایزی برای حل کلّی این مسئله(۱۰۰$ برای ارایهٔ یک استراتژی پیروزی برای فرشتی با قدرت کافی، و ۱۰۰۰$ برای اثبات این که شیطان می‌تواند مستقل از قدرت فرشته پیروز شود). تاریخچه مسئله ابتدا در سال ۱۹۸۲ در کتاب استراتژی برد نوشته برلکمپ، کانوی و گای، با نام «فرشته و مربّع خوار» منتشر شد. چند نتیجه جزئی شامل: اگر فرشته قدرت ۱ داشته باشد، شیطان استراتژی پیروزی دارد(کانوی، ۱۹۸۲ طبق گفته کانوی این نتیجه‌گیری متعلق به برلکمپ است) اگر فرشته هرگز مولفه yخود را افزایش ندهد، شیطان استراتژی پیروزی دارد. (کانوی ۱۹۸۲) اگر فرشته همواره فصلهٔ خود را از مبدأ زیاد کند، شیطان استراتژی پیروزی دارد (کانوی. ۱۹۹۶) در ۳ بد نشان داده شده‌است که: اگر فرشته همواره مؤلفهyخود را افزایش دهد، و شیطان فقط بتواند در یک صفحه بازی کند، آنگاه فرشته استراتژی پیروزی دارد. اگر فرشته همواره مؤلفه yخود را افزایش دهد، و شیطان فقط بتواند در دو صفحه بازی کند، آنگاه فرشته استراتژی پیروزی دارد. | ## بخش 2: مسئله فرشته | اگر تعدادی متناهی شیطان داشته باشیم که هر کدام در فواصل ...>d۱<d۲< 'd۳'''''بازی می‌کنند، آنگه فرشته در صورتی که قدرت کافی داشته باشد، همچنان می‌تواند پیروز شود. (منظور از «بازی در فاصله d» این است که شیطان نمی‌تواند در این فواصل از مبدأ بازی کند). نهایتاً، در سال ۲۰۰۶، در حالی که زمان زیادی از انتشار کتاب Peter Winkler «معماهای ریاضی» که کمک به سزایی در معرفی این مسئله به عموم داشت، چهار اثبات مستقل و تقریباً به‌طور هم‌زمان برای وجود استراتژی پیروزی فرشته در دو بعد مطرح شدند. سؤال‌های حل نشدهٔ دیگر در سه بعد اگر فرشته فقط مؤلفه y خود را افزایش دهد، و شیطان فقط به بازی در ۳ صفحه محدود شود، معلوم نیست که آیا شیطان استراتژی پیروزی دارد یا نه. طرح کلی اثبات این که فرشته با قدرت زیاد در سه بعد استراتژی پیروزی دارد این اثبات ملزم به استفاده نگهبانان است. نگهبانان در مورد بی‌خطر یا تقریباً بی‌خطر بودن یا خطرناک بودن هر حرکت در آن مکعب تصمیم می‌گیرند. اگر برخی از مکعب‌ها که فرشته در آن‌ها قرار دارد امن باشند، آنگاه نگهبان بزرگّترین این مکعب‌ها به فرشته دستور می‌دهد که به یکی از مرژای این مکعب برود. اگر قرار باشد که یک نگهبان، از فرشته تا رسیدن به یک وجه به خصوص آن مکعب محافظت کند، آنگه نگهبان این کار را با مشخص کردن مسیری از زیر مکعب‌ها که همگی امن هستند انجام می‌دهد. نگهبانان نگهبانان این مکعب‌ها نیز از فرشته تا رسیدن به زیر مکعب مربوط محافظت مکنند. ثابت می‌شود که این استراتژی کار می‌کند، زیرا زمانی که لازم است تا شیطان یک مکعب امن در مسیر فرشته را به مکعبی نا امن تبدیل کند، بیشتر از زمانی است که برای رسیدن فرشته به آن مکعب لازم است. توجه:مسیر فرشته در یه زیر مکعب تا زمانی که فرشته با آن نرسیده‌است مشخص نیست، حتی بعد از رسیدن نیز فقط طرحی تقریبی از این مسیر وجود دارد. به همین دلیل شیطان نمی‌تواند مکانی را در مسیر که از فرشته فاصله زیادی دارد را نا امن کند. | ## بخش 3: مسئله فرشته | طرح کلی اثبات Máthé Máthéشیطان نجیب را مرفی کرد، که هیچ‌گاه خانه‌ای که فرشته در نوبت زودتر می‌تواند برای اشغال انتخاب کند. وقتی فرشته در مقابل شیطان نجیب بازی می‌کند، در صورتی شکست می‌خورد که شیطان او را در یک منطقه بسته محبوس کند (در غیر این صورت فرشته فقط می‌تواند بین دو خانه جست و خیز کند؟!!!>:"ل: و هرگز شکست نمی‌خورد!)، اثبات Máthé به دو قسمت تقسیم می‌شود:(۱)او نشان داد که اگر فرشته بتواند در برابر شیطان نجیب پیروز شود، در مقابل شیطان واقعی نیز پیروز می‌شود؛ (۲)او استراتژی دقیقی را نیز برای پیروزی فرشته مقابل شیطان نجیب ارائه داد. به‌طور کلی دربارهٔ قسمت دوم، اگر فرشته وانمود کند که تمام نیم-صفحه سمت چپ خراب می‌شود (علاوه بر خانه‌هایی که توسط شیطان نجیب خراب شده‌اند)، و با خانه‌های خراب شده مثل دیوارهای یک راه پر پیچ و خم رفتار کند، و آن‌ها رو دور زند، می‌تواند شیطان نجیب را شکست دهد. اثبات قسمت (۱) به وسیله برهان خلف است، بنابراین اثبات Máthé به‌طور مستقیم یک استراتژی پیروزی در برابر شیطان واقعی ارائه نمی‌دهد. طرح کلی اثبات Bowditch Bowditch بازی متفاوتی از بازی اصلی با قوانین تغییر یافتهٔ زیر نسبت به بازی اصلی ارائه داد: فرشته می‌تواند به هر خانه‌ای که قبلاً در آن بوده برگردد، حتی اگر شیطان متعاقباً سعی در مانع گذاری در آن را داشته باشد. مسیر غیرمستقیم مسیری است که ویک کمان نیمه نامتناهی است (مسیری غیر خود متقطع که نقطه شروع دارد ولی نقطه پایان ندارد)و γi دورهای دو به دو منفصل از هم هستند که دارای ویژگی‌های زیر اند: که | γi | طول iامین دور است. (توجه داشته باشید که برای خوش تعریف بودن، باید نقطهٔ شروع و پایان γi نقطه پایانی σiباشد و σi باید در نقطهٔ شروع σi + ۱ پایان یابد) Bowditchبازی متفاوتی با بازی قبل (بازی ۱) با تغییر ۲ و ۳ به ۵-شیطان در نظر گرفت. سپس نشان داد که استراتژی پیروزی در این بازی استراتژی پیروزی در بازی اصلی برای ۴-فرشته را نتیجه می‌دهد. او نشان داد که فرشته‌ای که با یک ۵-شیطان بازی می‌کند، می‌تواند با یک الگوریتم ساده پیروز شود. Bowditchادعا کرد که یک ۴-فرشته، با در نظر گرفتن یک فرشته خیالی که با یک ۵-شیطان در بازی ۲ بازی می‌کند، می‌تواند پیروز شود. | ## جمع‌بندی | بنا بر این چون مسیرσ یک کمان نیمه متناهی است، فرشته به خانه‌ای که قبلاً در آن بوده بر نمی‌گردد، پس مسیر، یک مسیر پیروزی خواهد بود، حتی در بازی اصلی.