بازی موقعیتی قوی (که به آن بازی Maker-Maker نیز گفته میشود) نوعی بازی موقعیتی است. مانند اکثر بازیهای موقعیتی، این بازی با مجموعهای از موقعیتهای موجود () و مجموعهای از مجموعههای برنده (- خانوادهای از زیرمجموعههای ) توصیف میشود. این بازی توسط دو بازیکن به نامهای اول و دوم انجام میشود که به نوبت موقعیتهای قبلاً انتخاب نشده را اشغال میکنند.
در یک بازی موقعیتی قوی، بازیکن اول کسی است که اولین بار تمام عناصر یک مجموعه برنده را در اختیار میگیرد و پیروز میشود. اگر تمام موقعیتها اشغال شوند و هیچ بازیکنی برنده نشود، بازی مساوی میشود. بازی کلاسیک تیک-تاک-تو نمونهای از یک بازی موقعیتی قوی است.
مزیت بازیکن اول
در یک بازی موقعیتی قوی، بازیکن دوم نمیتواند یک استراتژی برنده داشته باشد. این موضوع را میتوان با یک استدلال سرقت استراتژی اثبات کرد: اگر بازیکن دوم استراتژی برنده داشت، بازیکن اول میتوانست آن را بدزدد و او نیز برنده شود، اما این غیرممکن است زیرا تنها یک برنده وجود دارد. بنابراین، برای هر بازی موقعیتی قوی، تنها دو گزینه وجود دارد: یا بازیکن اول دارای استراتژی برنده است، یا بازیکن دوم دارای استراتژی مساویکننده است.
یک نتیجه جالب این است که اگر یک بازی خاص، موقعیتهای مساوی نداشته باشد، بازیکن اول همیشه دارای استراتژی برنده است.
مقایسه با بازی Maker-Breaker
هر بازی موقعیتی قوی، یک نسخه متغیر دارد که یک بازی Maker-Breaker است. در آن نسخه متغیر، تنها بازیکن اول (Maker) میتواند با در اختیار داشتن یک مجموعه برنده، پیروز شود. بازیکن دوم (Breaker) تنها در صورتی میتواند پیروز شود که مانع از تشکیل مجموعه برنده توسط Maker شود.
برای مجموعههای و ثابت، نسخه موقعیتی قوی به طور قابل توجهی برای بازیکن اول دشوارتر است، زیرا در آن، او باید هم "حمله" کند (سعی کند یک مجموعه برنده به دست آورد) و هم "دفاع" کند (مانع از تشکیل مجموعه توسط بازیکن دوم شود)، در حالی که در نسخه Maker-Breaker، بازیکن اول میتواند فقط روی "حمله" تمرکز کند. از این رو، هر استراتژی برنده بازیکن اول در یک بازی موقعیتی قوی، یک استراتژی برنده برای Maker در بازی Maker-Breaker مربوطه نیز محسوب میشود. اما عکس این قضیه صادق نیست. به عنوان مثال، در نسخه Maker-Breaker تیک-تاک-تو، Maker دارای استراتژی برنده است، اما در نسخه موقعیتی قوی (کلاسیک) آن، بازیکن دوم دارای استراتژی مساویکننده است.
به طور مشابه، نسخه موقعیتی قوی به طور قابل توجهی برای بازیکن دوم آسانتر است: هر استراتژی برنده Breaker در یک بازی Maker-Breaker، یک استراتژی مساویکننده برای بازیکن دوم در بازی موقعیتی قوی مربوطه نیز هست، اما عکس آن صادق نیست.
پارادوکس مجموعه اضافی
فرض کنید بازیکن اول دارای استراتژی برنده است. اکنون، یک مجموعه جدید به اضافه میکنیم. برخلاف شهود، ممکن است این مجموعه جدید استراتژی برنده را از بین ببرد و بازی را به سمت تساوی سوق دهد. از نظر شهودی، دلیل این امر این است که بازیکن اول ممکن است مجبور شود برخی از حرکات خود را برای جلوگیری از تصاحب این مجموعه اضافی توسط بازیکن دوم صرف کند.
پارادوکس مجموعه اضافی در بازیهای Maker-Breaker رخ نمیدهد.
مثالها
بازیClique
بازی Clique نمونهای از یک بازی موقعیتی قوی است. این بازی با دو عدد صحیح n و N پارامتری میشود. در آن:
- مجموعه موقعیتها شامل تمام یالهای گراف کامل بر روی {1,...,N} است.
- مجموعه برندهها شامل تمامCliqueهای با اندازه n است.
بر اساس قضیه Ramsey، عددی مانند وجود دارد که برای هر N بزرگتر از ، در هر دو-رنگآمیزی گراف کامل بر روی {1,...,N}، یکی از رنگها باید شامل یک clique با اندازه n باشد.
بنابراین، طبق نتیجهگیری بالا، هنگامی که N > R(n,n)، بازیکن اول همیشه دارای استراتژی برنده است.
تیک-تاک-تو چندبعدی
بازی تیک-تاک-تو را در یک مکعب d-بعدی به طول n در نظر بگیرید. بر اساس قضیه Hales–Jewett، هنگامی که d به اندازه کافی بزرگ باشد (به عنوان تابعی از n)، هر 2-رنگآمیزی سلولهای مکعب شامل یک خط هندسی همرنگ است.
بنابراین، طبق نتیجهگیری بالا، بازیکن اول همیشه دارای استراتژی برنده است.
سوالات باز
علاوه بر این نتایج وجودی، نتایج سازنده کمی در رابطه با بازیهای موقعیتی قوی وجود دارد. به عنوان مثال، در حالی که مشخص است که بازیکن اول در یک بازی Clique به اندازه کافی بزرگ دارای استراتژی برنده است، در حال حاضر هیچ استراتژی برنده مشخصی شناخته نشده است.
منابع
- بازیهای موقعیتی