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

قضیه اسپراگ-گراندی (به انگلیسی: Sprague–Grundy theorem) در نظریه‌بازی‌های ترکیبیاتی بیان می‌دارد هر بازی منصفانه‌ای با شرط بازی کردن متعادل، با بازی نیم معادل است. مقیاس گراندی یا مقدار نیم، عدد یکتایی است که معادل بازی نیم متناظر است.
این قضیه توسط رولاند پرسیوال اسپراگ و پاتریک مایکل گراندی به صورت مستقل از هم در دهه ۴۰ قرن ۱۹ کشف شد.

تعریف

در قضیه اسپراگ-گاندی، یک بازی به معنی بازی دونفره متوالی با اطلاعات کامل با پایانی رضایت بخش و شرایط بازی معمولی میباشد.
درهرنکته ای در بازی، وضعیت بازیکن اول شامل حرکاتی است که میتواند انجام دهد. مثلا بازی صفر میتواند یک بازی دونفره باشد که هربازیکن میتواند حرکت منطقی انجام دهد وضعیت آن ها میشود :  ({} , {}) = (A,B)
بازی عادلانه(به انگلیسی: impartial game) بازی ای است که در آن هربازیکن اجازه داشته باشد حرکات یکسانی انجام دهند بازی nim مثالی از آن است که در آن یک یا بیشتر هرم و دوبازیکن وجود دارد که درهرنوبت میتوانند یکی از عناصر هرم را حذف کنند. برنده کسی است که آخرین عنصر از آخرین هرم را حذف کند و این بازی شرایط بازی عادلانه را دارد. اما بازی checkers  شرایط بازی عادلانه را ندارد.
مثالی ازبازی nim :
اندازه هرم ها
A B C
1 2 2بازیکن اول از هرم اول عنصری را برمیدارد
0 2 2بازیکن دوم از هرم دوم عنصری را برمیدارد
0 1 2بازیکن اول از هرم سوم عنصری را برمیدارد
0 1 1بازیکن دوم از هرم دوم عنصری را برمیدارد
0 0 1بازیکن اول از هرم سوم عنصری را برمیدارد
0 0 0 بازیکن اول برنده شد
1.{}
2.{*0}
3.{*1}
4.{*1 , {*1}}
5.{*1 , {*1} , *2}
6.{{*1 , {*1} , *2} , *2}
7.{ {*1,{*1} *2} , {*2,{{*1} , *1 ,*2}} , {{*1} , {{*1}} , {*1, {*1} , *2}} }
{n+1)  = *n ∪ {*n)*
کد زیر بازی ای منصفانه است که در انتها بازیکن اول برنده شده است:

{int calculateMex(unordered_set<int> Set)
   int Mex = 0;
   while (Set.find(Mex) != Set.end())
       Mex++;
   return (Mex);
int calculateGrundy(int n, int Grundy[])
   Grundy[0] = 0;
   Grundy[1] = 1;
   Grundy[2] = 2;
   Grundy[3] = 3;

   if (Grundy[n] != -1)
       return (Grundy[n]);
   unordered_set<int> Set; 

   for (int i=1; i<=3; i++)
           Set.insert (calculateGrundy (n-i, Grundy));

   Grundy[n] = calculateMex (Set);

   return (Grundy[n]);
void declareWinner(int whoseTurn, int piles[],int Grundy[], int n)
   int xorValue = Grundy[piles[0]];

   for (int i=1; i<=n-1; i++)
       xorValue = xorValue ^ Grundy[piles[i]];

   if (xorValue != 0)
       if (whoseTurn == PLAYER1)
           printf("Player 1 will win\n");
       else
           printf("Player 2 will win\n");
   else
       if (whoseTurn == PLAYER1)
           printf("Player 2 will win\n");
       else
           printf("Player 1 will win\n"); 
   return;
   int piles[] = {3, 4, 5};
   int n = sizeof(piles)/sizeof(piles[0]);
   int maximum = *max_element(piles, piles + n);

   int Grundy[maximum + 1];
   memset(Grundy, -1, sizeof (Grundy));

   for (int i=0; i<=n-1; i++)
       calculateGrundy(piles[i], Grundy);
   declareWinner(PLAYER1, piles, Grundy, n);

   int piles[] = {3, 8, 2};
   int n = sizeof(piles)/sizeof(piles[0]);
   int maximum = *max_element (piles, piles + n);

   int Grundy [maximum + 1];
   memset(Grundy, -1, sizeof (Grundy));

   for (int i=0; i<=n-1; i++)
       calculateGrundy(piles[i], Grundy); 
   declareWinner(PLAYER2, piles, Grundy, n);    
   return (0);

بازی ها ترکیبی

دو بازی را میتوان با جمع وضعیت آن دو بازی ترکیب کرد.

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

فرض کنید G1,G2,G3,…Gn بازی های ترکیبیاتی با توابع g1,g2,…,gn و G = G1+G1+..+Gn مجموع بازی هاست، برای هروضعیت (x1,x2,..,xn)  در بازی G داریم:
g(x1,x2,..,xn) = g(x1) ⊕ g(x2) ⊕ … ⊕ g(xn)
برای مثال:
ﻓﺮضﮐﻨﯿﺪدرﯾﮏﺑﺎزی٣ﮐﯿﺴﻪﺑﻪﺗﺮﺗﯿﺐﺷﺎﻣﻞ٠١،٣١و۶١ﻣﻬﺮه دراﺧﺘﯿﺎردارﯾﻢ.ﻗﺎﻧﻮنﺑﺎزیﻋﺒﺎرت اﺳﺖازاﻧﺘﺨﺎبﮐﯿﺴﻪ١وﺑﺮداﺷﺘﻦ١،٢ﯾﺎ٣ﻣﻬﺮه ازآنﯾﺎ اﻧﺘﺨﺎبﮐﯿﺴﻪ ٢و ﺑﺮداﺷﺘﻦ١،٢،٣،۴ﯾﺎ ۵ﻣﻬﺮه از آن ﯾﺎ اﻧﺘﺨﺎبﮐﯿﺴﻪ٣و ﺑﺮداﺷﺘﻦ ١،٢،٣،۴،۵،۶ﯾﺎ ٧ﻣﻬﺮه ازآن اﺳﺖ.اﯾﻦﺑﺎزی راﻣﯽﺗﻮانﺑﻪﺻﻮرتﻣﺠﻤﻮع سه بازی درنظرگرفت. برای وضعیت (14و10و9) :
g(۹,۱۰,۱۴) = g۱(۹)⊕g۲(۱۰)⊕g۳(۱۴) = ۱⊕۴⊕۶ = ۳.