پرش به محتویات

قضیه اسپراگ-گراندی. نیم

مقدمه

این قضیه بازی‌های دو نفره‌ی بی‌طرفانه را توصیف می‌کند، یعنی بازی‌هایی که در آن‌ها حرکات موجود و برد/باخت تنها به وضعیت بازی بستگی دارد. به عبارت دیگر، تنها تفاوت بین دو بازیکن این است که یکی از آن‌ها اول حرکت می‌کند.

علاوه بر این، فرض می‌کنیم که بازی دارای اطلاعات کامل است، یعنی هیچ اطلاعاتی از بازیکنان پنهان نیست (آن‌ها قوانین و حرکات ممکن را می‌دانند).

فرض بر این است که بازی متناهی است، یعنی پس از تعداد معینی حرکت، یکی از بازیکنان در موقعیت بازنده قرار می‌گیرد — موقعیتی که از آن نمی‌تواند به موقعیت دیگری حرکت کند. در مقابل، بازیکنی که این موقعیت را برای حریف ایجاد کرده، برنده می‌شود. طبیعتاً، در این بازی تساوی وجود ندارد.

این‌گونه بازی‌ها را می‌توان به طور کامل با یک گراف جهت‌دار غیرمدور توصیف کرد: رأس‌ها وضعیت‌های بازی و یال‌ها انتقال‌ها (حرکات) هستند. رأسی که یال خروجی ندارد، یک رأس بازنده است (بازیکنی که باید از این رأس حرکت کند، می‌بازد).

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

وظیفه ما طبقه‌بندی وضعیت‌های یک بازی معین است.

نظریه این‌گونه بازی‌ها به طور مستقل توسط Roland Sprague در سال ۱۹۳۵ و Patrick Michael Grundy در سال ۱۹۳۹ توسعه یافت.

نیم (Nim)

این بازی از محدودیت‌های توصیف‌شده در بالا پیروی می‌کند. علاوه بر این، هر بازی دو نفره بی‌طرفانه با اطلاعات کامل را می‌توان به بازی نیم کاهش داد. مطالعه این بازی به ما امکان می‌دهد تا تمام بازی‌های مشابه دیگر را حل کنیم، اما بعداً بیشتر به این موضوع خواهیم پرداخت.

از نظر تاریخی، این بازی در دوران باستان محبوب بوده است. منشأ آن احتمالاً چین است — یا حداقل بازی Jianshizi بسیار شبیه به آن است. در اروپا اولین اشارات به آن به قرن شانزدهم بازمی‌گردد. این نام توسط Charles Bouton انتخاب شد، که در سال ۱۹۰۱ تحلیل کاملی از این بازی را منتشر کرد.

شرح بازی

چندین کپه وجود دارد که هر کدام دارای تعدادی سنگ است. در هر حرکت، یک بازیکن می‌تواند هر تعداد سنگ مثبت را از یکی از کپه‌ها برداشته و دور بریزد. بازیکنی که نتواند حرکتی انجام دهد، می‌بازد، که این اتفاق زمانی رخ می‌دهد که همه کپه‌ها خالی باشند.

وضعیت بازی به طور یکتا با یک چندمجموعه از اعداد صحیح مثبت توصیف می‌شود. یک حرکت شامل کاهش اکید یک عدد صحیح انتخاب شده است (اگر صفر شود، از مجموعه حذف می‌شود).

راه‌حل

راه‌حل Charles L. Bouton به این صورت است:

قضیه. بازیکن فعلی یک استراتژی برد دارد اگر و تنها اگر حاصل جمع xor اندازه‌های کپه‌ها غیرصفر باشد. حاصل جمع xor یک دنباله $a$ برابر است با $a_1 \oplus a_2 \oplus \ldots \oplus a_n$، که در آن $\oplus$ عملگر or انحصاری بیتی است.

اثبات. نکته کلیدی در اثبات، وجود یک استراتژی متقارن برای حریف است. نشان می‌دهیم که اگر بازیکنی در موقعیتی با xor-sum برابر با صفر قرار گیرد، نمی‌تواند در بلندمدت آن را غیرصفر نگه دارد — اگر او به موقعیتی با xor-sum غیرصفر منتقل شود، حریف همیشه حرکتی خواهد داشت که xor-sum را به صفر بازگرداند.

این قضیه را با استقرای ریاضی اثبات خواهیم کرد.

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

حال فرض کنید در یک وضعیت غیرخالی هستیم. با استفاده از فرض استقرا (و غیرمدور بودن بازی) فرض می‌کنیم که قضیه برای تمام وضعیت‌های قابل دسترس از وضعیت فعلی اثبات شده است.

سپس اثبات به دو بخش تقسیم می‌شود: اگر برای موقعیت فعلی، xor-sum $s = 0$ باشد، باید ثابت کنیم که این وضعیت، بازنده است، یعنی تمام وضعیت‌های قابل دسترس دارای xor-sum $t \neq 0$ هستند. اگر $s \neq 0$ باشد، باید ثابت کنیم که حرکتی وجود دارد که به وضعیتی با $t = 0$ منجر می‌شود.

  • فرض کنید $s = 0$ و هر حرکتی را در نظر بگیریم. این حرکت اندازه کپه $x$ را به اندازه $y$ کاهش می‌دهد. با استفاده از ویژگی‌های ابتدایی $\oplus$، داریم:

    $$ t = s \oplus x \oplus y = 0 \oplus x \oplus y = x \oplus y $$

    از آنجایی که $y < x$ است، $y \oplus x$ نمی‌تواند صفر باشد، بنابراین $t \neq 0$ است. این بدان معناست که هر وضعیت قابل دسترس، یک وضعیت برنده است (طبق فرض استقرا)، بنابراین ما در یک موقعیت بازنده هستیم.

  • فرض کنید $s \neq 0$ باشد. نمایش دودویی عدد $s$ را در نظر بگیرید. فرض کنید $d$ اندیس پرارزش‌ترین بیت غیرصفر آن باشد. حرکت ما بر روی کپه‌ای خواهد بود که بیت شماره $d$ اندازه‌اش یک باشد (چنین کپه‌ای باید وجود داشته باشد، در غیر این صورت این بیت در $s$ یک نمی‌شد). ما اندازه آن $x$ را به $y = x \oplus s$ کاهش خواهیم داد. تمام بیت‌ها در موقعیت‌های بزرگتر از $d$ در $x$ و $y$ یکسان هستند و بیت $d$ در $x$ یک است اما در $y$ یک نیست. بنابراین، $y < x$ است، که این تمام چیزی است که برای قانونی بودن یک حرکت نیاز داریم. اکنون داریم:

    $$ t = s \oplus x \oplus y = s \oplus x \oplus (s \oplus x) = 0 $$

    این بدان معناست که ما یک وضعیت بازنده قابل دسترس پیدا کرده‌ایم (طبق فرض استقرا) و وضعیت فعلی برنده است.

نتیجه. هر وضعیت از بازی نیم را می‌توان با یک وضعیت معادل جایگزین کرد، تا زمانی که xor-sum تغییر نکند. علاوه بر این، هنگام تحلیل یک بازی نیم با چندین کپه، می‌توانیم آن را با یک کپه به اندازه $s$ جایگزین کنیم.

بازی میزِر (Misère Game)

در یک بازی میزِر (misère game)، هدف بازی برعکس است، بنابراین بازیکنی که آخرین سنگ را برمی‌دارد، بازنده است. معلوم شده است که بازی نیم میزِر را می‌توان به طور بهینه تقریباً مانند بازی نیم استاندارد بازی کرد. ایده این است که ابتدا بازی میزِر را مانند بازی استاندارد بازی کنیم، اما در انتهای بازی استراتژی را تغییر دهیم. استراتژی جدید در وضعیتی به کار گرفته می‌شود که پس از حرکت بعدی، هر کپه حداکثر یک سنگ داشته باشد. در بازی استاندارد، باید حرکتی را انتخاب کنیم که پس از آن تعداد زوجی از کپه‌های تک‌سنگی وجود داشته باشد. اما در بازی میزِر، حرکتی را انتخاب می‌کنیم که تعداد فردی از کپه‌های تک‌سنگی وجود داشته باشد. این استراتژی کار می‌کند زیرا وضعیتی که در آن استراتژی تغییر می‌کند، همیشه در بازی پیش می‌آید و این وضعیت، یک وضعیت برنده است، زیرا دقیقاً شامل یک کپه با بیش از یک سنگ است، بنابراین حاصل جمع نیم (nim sum) صفر نیست.

معادل بودن بازی‌های بی‌طرفانه و نیم (قضیه اسپراگ-گراندی)

اکنون یاد خواهیم گرفت که چگونه برای هر وضعیت از هر بازی بی‌طرفانه‌ای، یک وضعیت متناظر از بازی نیم پیدا کنیم.

لم در مورد بازی نیم با امکان افزایش

تغییر زیر را در بازی نیم در نظر می‌گیریم: ما اجازه اضافه کردن سنگ به یک کپه انتخاب شده را نیز می‌دهیم. قوانین دقیق در مورد چگونگی و زمان مجاز بودن افزایش، برای ما اهمیتی ندارد، اما این قوانین باید بازی ما را غیرمدور نگه دارند. در بخش‌های بعدی، بازی‌های نمونه‌ای در نظر گرفته می‌شوند.

لم. اضافه کردن امکان افزایش به بازی نیم، نحوه تعیین وضعیت‌های برنده و بازنده را تغییر نمی‌دهد. به عبارت دیگر، افزایش‌ها بی‌فایده هستند و ما مجبور نیستیم از آن‌ها در یک استراتژی برد استفاده کنیم.

اثبات. فرض کنید یک بازیکن به یک کپه سنگ اضافه کرده است. در این صورت حریف او می‌تواند به سادگی حرکت او را خنثی کند — تعداد سنگ‌ها را به مقدار قبلی کاهش دهد. از آنجایی که بازی غیرمدور است، دیر یا زود بازیکن فعلی قادر به استفاده از حرکت افزایش نخواهد بود و مجبور به انجام حرکت معمول نیم خواهد شد.

قضیه اسپراگ-گراندی

یک وضعیت $v$ از یک بازی دو نفره بی‌طرفانه را در نظر بگیرید و فرض کنید $v_i$ وضعیت‌های قابل دسترس از آن باشند (که در آن $i \in \{ 1, 2, \dots, k \} , k \ge 0$). به این وضعیت، می‌توانیم یک بازی نیم کاملاً معادل با یک کپه به اندازه $x$ نسبت دهیم. عدد $x$ را مقدار گراندی (Grundy value) یا مقدار نیم (nim-value) وضعیت $v$ می‌نامند.

علاوه بر این، این عدد را می‌توان به روش بازگشتی زیر پیدا کرد:

$$ x = \text{mex}\ \{ x_1, \ldots, x_k \}, $$

که در آن $x_i$ مقدار گراندی برای وضعیت $v_i$ است و تابع $\text{mex}$ (minimum excludant) کوچکترین عدد صحیح نامنفی است که در مجموعه داده شده یافت نمی‌شود.

با در نظر گرفتن بازی به عنوان یک گراف، می‌توانیم مقادیر گراندی را به تدریج با شروع از رأس‌های بدون یال خروجی محاسبه کنیم. مقدار گراندی برابر با صفر به معنای بازنده بودن یک وضعیت است.

اثبات. از اثبات با استقرا استفاده خواهیم کرد.

برای رأس‌های بدون حرکت، مقدار $x$ برابر با $\text{mex}$ یک مجموعه تهی است که برابر با صفر است. این درست است، زیرا یک بازی نیم خالی، بازنده است.

اکنون هر رأس دیگری مانند $v$ را در نظر بگیرید. طبق فرض استقرا، فرض می‌کنیم مقادیر $x_i$ مربوط به رأس‌های قابل دسترس از آن، قبلاً محاسبه شده‌اند.

فرض کنید $p = \text{mex}\ \{ x_1, \ldots, x_k \}$ باشد. آنگاه می‌دانیم که برای هر عدد صحیح $i \in [0, p)$، یک رأس قابل دسترس با مقدار گراندی $i$ وجود دارد. این بدان معناست که $v$ معادل با یک وضعیت از بازی نیم با امکان افزایش و با یک کپه به اندازه $p$ است. در چنین بازی‌ای، ما انتقال‌هایی به کپه‌هایی با هر اندازه کوچکتر از $p$ و احتمالاً انتقال‌هایی به کپه‌هایی با اندازه‌های بزرگتر از $p$ داریم. بنابراین، $p$ در واقع همان مقدار گراندی مورد نظر برای وضعیت فعلی است.

کاربرد قضیه

در نهایت، الگوریتمی برای تعیین نتیجه برد/باخت یک بازی را توصیف می‌کنیم که برای هر بازی دو نفره بی‌طرفانه قابل اجرا است.

برای محاسبه مقدار گراندی یک وضعیت معین، باید:

  • تمام انتقال‌های ممکن از این وضعیت را بدست آورید.

  • هر انتقال می‌تواند به مجموعی از بازی‌های مستقل منجر شود (در حالت خاص، یک بازی). مقدار گراندی را برای هر بازی مستقل محاسبه کرده و حاصل جمع xor آنها را بدست آورید. البته اگر فقط یک بازی وجود داشته باشد، عمل xor تأثیری ندارد.

  • پس از محاسبه مقادیر گراندی برای هر انتقال، مقدار وضعیت را به عنوان $\text{mex}$ این اعداد پیدا می‌کنیم.

  • اگر مقدار صفر باشد، وضعیت فعلی بازنده است، در غیر این صورت برنده است.

در مقایسه با بخش قبل، این واقعیت را در نظر می‌گیریم که ممکن است انتقال‌هایی به بازی‌های ترکیبی وجود داشته باشد. ما آن‌ها را به عنوان یک بازی نیم در نظر می‌گیریم که اندازه کپه‌های آن برابر با مقادیر گراندی بازی‌های مستقل است. طبق قضیه بوتون، می‌توانیم آنها را مانند بازی نیم معمولی با هم xor کنیم.

الگوها در مقادیر گراندی

اغلب هنگام حل مسائل خاص با استفاده از مقادیر گراندی، مطالعه جدول مقادیر برای یافتن الگوها می‌تواند مفید باشد.

در بسیاری از بازی‌ها که تحلیل نظری آن‌ها ممکن است دشوار به نظر برسد، مقادیر گراندی به صورت دوره‌ای یا شکلی به سادگی قابل درک ظاهر می‌شوند. در اکثریت قریب به اتفاق موارد، الگوی مشاهده شده صحیح است و در صورت تمایل می‌توان آن را با استقرا اثبات کرد.

با این حال، مقادیر گراندی همیشه حاوی چنین نظم‌هایی نیستند و حتی برای برخی بازی‌های بسیار ساده، مسئله وجود این نظم‌ها هنوز یک مسئله باز است (مثلاً "بازی گراندی").

بازی‌های نمونه

صلیب-صلیب

قوانین. یک نوار شطرنجی به اندازه $1 \times n$ را در نظر بگیرید. در یک حرکت، بازیکن باید یک صلیب قرار دهد، اما قرار دادن دو صلیب در کنار هم (در خانه‌های مجاور) ممنوع است. طبق معمول، بازیکنی که حرکت معتبری نداشته باشد، می‌بازد.

راه حل. وقتی یک بازیکن در هر خانه‌ای یک صلیب قرار می‌دهد، می‌توانیم اینطور در نظر بگیریم که نوار به دو بخش مستقل تقسیم می‌شود: بخش سمت چپ صلیب و بخش سمت راست آن. در این حالت، خانه دارای صلیب و همچنین همسایه‌های چپ و راست آن از بین می‌روند — دیگر نمی‌توان چیزی در آن‌ها قرار داد. بنابراین، اگر خانه‌ها را از $1$ تا $n$ شماره‌گذاری کنیم، قرار دادن صلیب در موقعیت $1 < i < n$ نوار را به دو نوار به طول $i-2$ و $n-i-1$ می‌شکند، یعنی به مجموع بازی‌های $i-2$ و $n-i-1$ منتقل می‌شویم. برای حالت‌های کناری که صلیب در موقعیت $1$ یا $n$ قرار می‌گیرد، به بازی $n-2$ منتقل می‌شویم.

بنابراین، مقدار گراندی $g(n)$ به این شکل است:

$$g(n) = \text{mex} \Bigl( \{ g(n-2) \} \cup \{g(i-2) \oplus g(n-i-1) \mid 2 \leq i \leq n-1\} \Bigr) .$$

بنابراین ما یک راه‌حل با پیچیدگی $O(n^2)$ داریم.

در واقع، $g(n)$ از $n=52$ به بعد دارای یک دوره تناوب به طول ۳۴ است.

مسائل تمرینی