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

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

این قضیه توسط رولاند پرسیوال اسپراگ و پاتریک مایکل گراندی به صورت مستقل از هم در دهه ۴۰ قرن ۱۹ کشف شد.

تعریف

در قضیه اسپراگ-گاندی، یک بازی به معنی بازی دونفره متوالی با اطلاعات کامل با پایانی رضایت بخش و شرایط بازی معمولی میباشد. درهرنکته ای در بازی، وضعیت بازیکن اول شامل حرکاتی است که میتواند انجام دهد. مثلا بازی صفر میتواند یک بازی دونفره باشد که هربازیکن میتواند حرکت منطقی انجام دهد وضعیت آن ها میشود : ({} , {}) = (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۳(۱۴) = ۱⊕۴⊕۶ = ۳.

جستارهای وابسته

منابع
  1. مشارکت کنندگان ویکی‌پدیای انگلیسی. «Sprague–Grundy theorem».
  • ریچارد ک. گای (۱۳۸۰)، بازی منصفانه، ترجمهٔ عبادالله محمودیان، آناهیتا آریاچهر، دانشگاه صنعتی شریف، مؤسسه انتشارات علمی از پارامتر ناشناخته |کشور= صرف‌نظر شد (کمک)

مقاله دکتر مزروعی ، [1]

سایت جیکس فور جیکس ، [2]

  1. http://cacna2015.old.kashanu.ac.ir/Files/Mazrooei.pdf
  2. https://www.geeksforgeeks.org/combinatorial-game-theory-set-4-sprague-grundy-theorem/
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.