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

قضیه اسپراگ-گراندی (به انگلیسی: Sprague–Grundy theorem) در نظریه بازی های ترکیبیاتی بیان می دارد هر بازی منصفانه ای با شرط بازی کردن متعادل، با بازی نیم معادل است. مقیاس گراندی یا مقدار نیم، عدد یکتایی است که معادل بازی نیم متناظر است.
نیم (بازی)
این قضیه توسط رولاند پرسیوال اسپراگ و پاتریک مایکل گراندی به صورت مستقل از هم در دهه ۴۰ قرن ۱۹ کشف شد.
در قضیه اسپراگ-گاندی، یک بازی به معنی بازی دونفره متوالی با اطلاعات کامل با پایانی رضایت بخش و شرایط بازی معمولی میباشد.درهرنکته ای در بازی، وضعیت بازیکن اول شامل حرکاتی است که میتواند انجام دهد. مثلا بازی صفر میتواند یک بازی دونفره باشد که هربازیکن میتواند حرکت منطقی انجام دهد وضعیت آن ها میشود : ({} , {}) = (A,B)
بازی عادلانه(به انگلیسی: impartial game) بازی ای است که در آن هربازیکن اجازه داشته باشد حرکات یکسانی انجام دهند بازی nim مثالی از آن است که در آن یک یا بیشتر هرم و دوبازیکن وجود دارد که درهرنوبت میتوانند یکی از عناصر هرم را حذف کنند. برنده کسی است که آخرین عنصر از آخرین هرم را حذف کند و این بازی شرایط بازی عادلانه را دارد. اما بازی checkers شرایط بازی عادلانه را ندارد.