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

قضیه اسپراگ-گراندی در نظریه‌بازی‌های ترکیبیاتی بیان می‌دارد هر بازی منصفانه‌ای با شرط بازی کردن متعادل، با بازی نیم معادل است. مقیاس گراندی یا مقدار نیم، عدد یکتایی است که معادل بازی نیم متناظر است.
این قضیه توسط رولاند پرسیوال اسپراگ و پاتریک مایکل گراندی به صورت مستقل از هم در دهه ۴۰ قرن ۱۹ کشف شد.
تعریف
در قضیه اسپراگ-گاندی، یک بازی به معنی بازی دونفره متوالی با اطلاعات کامل با پایانی رضایت بخش و شرایط بازی معمولی میباشد.
درهرنکته‌ای در بازی، وضعیت بازیکن اول شامل حرکاتی است که میتواند انجام دهد. مثلا بازی صفر میتواند یک بازی دونفره باشد که هربازیکن میتواند حرکت منطقی انجام دهد وضعیت آن‌ها میشود : ({ , {) = (A,B)
بازی عادلانه بازی‌ای است که در آن هربازیکن اجازه داشته باشد حرکات یکسانی انجام دهند بازی nim مثالی از آن است که در آن یک یا بیشتر هرم و دوبازیکن وجود دارد که درهرنوبت میتوانند یکی از عناصر هرم را حذف کنند. برنده کسی است که آخرین عنصر از آخرین هرم را حذف کند و این بازی شرایط بازی عادلانه را دارد. اما بازی checkers شرایط بازی عادلانه را ندارد.
مثالی ازبازی nim :
اندازه هرم‌ها
A B C
1 2 2بازیکن اول از هرم اول عنصری را برمیدارد
0 2 2بازیکن دوم از هرم دوم عنصری را برمیدارد
0 1 2بازیکن اول از هرم سوم عنصری را برمیدارد
0 1 1بازیکن دوم از هرم دوم عنصری را برمیدارد
0 0 1بازیکن اول از هرم سوم عنصری را برمیدارد
0 0 0 بازیکن اول برنده شد
{n+1) = *n ∪ {*n)*
کد زیر بازی‌ای منصفانه است که در انتها بازیکن اول برنده شده است:
{int calculateMex(unordered_set Set)
int Mex = 0;
while (Set.find(Mex) != Set.end())
Mex++;
return (Mex);
int calculateGrundy(int n, int Grundy)
Grundy0 = 0;
Grundy1 = 1;
Grundy2 = 2;
Grundy3 = 3;
if (Grundyn != -1)
return (Grundyn);
unordered_set Set;
for (int i=1; i<=3; i++)
Set.insert (calculateGrundy (n-i, Grundy));
Grundyn = calculateMex (Set);
return (Grundyn);
void declareWinner(int whoseTurn, int piles,int Grundy, int n)
int xorValue = Grundypiles0;
for (int i=1; i<=n-1; i++)
xorValue = xorValue ^ Grundypilesi;
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(piles0);
int maximum = *max_element(piles, piles + n);
int Grundymaximum + 1;
memset(Grundy, -1, sizeof (Grundy));
for (int i=0; i<=n-1; i++)
calculateGrundy(pilesi, Grundy);
declareWinner(PLAYER1, piles, Grundy, n);
int piles = {3, 8, 2;
int n = sizeof(piles)/sizeof(piles0);
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(pilesi, 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۳(۱۴) = ۱⊕۴⊕۶ = ۳.
نیم (بازی)