نظریه بازی‌های ترکیبیاتی: تفاوت میان نسخه‌ها

محتوای حذف‌شده محتوای افزوده‌شده

درخط

نسخهٔ ‏۳۰ آوریل ۲۰۱۷، ساعت ۱۷:۵۲

نظریه بازی‌های ترکیبیاتی شاخه‌ای از ریاضیات و علوم نظری رایانه است که به طور معمول به مطالعۀ بازی‌های ترتیبی و دنباله‌وار با اطلاعات کامل می‌پردازد و مطالعۀ آن بیشتر شامل بازی‌ های دونفره‌ایست که در آن بازیکنان به نوبت، حرکاتی در راستای رسیدن به موقعیت برد انجام می‌دهند. همچنین این بازی‌ها در زمان متناهی پایان می‌یابند و برنده براساس قوانین بازی مشخص می‌شود.
بازی‌های ترکیبیاتی به دو دستۀ بازی‌های منصفانه و بازی‌های پارتیزانی تقسیم می‌شوند.
این نظریه به طور سنتی، به بررسی بازی‌های شانسی و یا بازی‌های اطلاعات ناقص نمی‌پردازد و موضوع عمدۀ آن بازی‌هایی است که مجموعۀ حرکات در هر مرحله از بازی مشخص است و بازیکن‌ها نیز از آن مطلع اند. هدف از بررسی بازی‌ها یافتن برنده‌ی بازی از یک حالت اولیه مشخص و همچنین نحوه‌ی پیروزی برنده است -یعنی برنده با چه حرکاتی می‌تواند پیروز شود- که اصطلاحاً به آن استراتژی برد می‌گویند.
امروزه با استفاده از تکنیک‌های پیشرفتۀ ریاضی، نوع و تعداد بازی‌هایی که می‌توانند به صورت ریاضی تحلیل و بررسی شوند، در حال گسترش است. یه طوری که در بازی‌های ترکیبیاتی تمامی قوانین و حرکات مجاز و حتی تحلیل بازی نوشته می‌شوند.
شطرنج، چکرز و گو از بازی‌های ترکیبیاتی غیر بدیهی به‌شمار می‌روند، اما بازی‌هایی مانند ایکس او جزء بازی‌های بدیهی به حساب می‌آیند و در هر دو نوع این بازی‌ها، حرکات را می‌توان به کمک درخت بازی‌ها نمایش داد. بازی‌های ترکیبیاتی شامل بازی‌های یک نفره با جداول ترکیبیاتی مانند سودوکو و یا بازی‌های بدون بازیکن اتوماتیک مانند بازی زندگی کانوی است. همچنین نظریه بازی‌ها به طور کلی شامل بازی‌های شانسی، بازی‌هایی که نیاز به دانش خاص ندارند و بازی‌هایی است که بازیکن‌ها همزمان می‌توانند بازی کنند و هدف آن شبیه‌سازی تصمیمات واقعی زندگی است.
نظریه بازی‌های ترکیبیاتی با نظریه بازی‌های سنتی و یا اقتصادی، که در ابتدا برای مطالعۀ بازی‌های ترکیبیاتی سادۀ دارای شانس توسعه پیدا کردند، متفاوت است.
در نظریه بازی‌های ترکیبیاتی تأکید کمتری بر پالایش عملی الگوریتم‌های جستجو مانند هرس آلفا بتا - که در اکثر کتاب های هوش مصنوعی به آن اشاره شده است - وجود دارد و بیشتر بر روی نتایج نظری توصیفی، مانند محاسبۀ پیچیدگی بازی‌ها و یا یافتن راه‌حل‌های بهینه تأکید می‌شود.
همچنین بخش مهمی از نظریه بازی‌های ترکیبیاتی دربارۀ بازی‌های حل شده است. به طور مثال در بازی ایکس او می‌توان ثابت کرد که اگر هر دو بازیکن به طور بهینه بازی کنند، مساوی می‌‌شوند. معمولاً هرچه بازی‌ها ساختار ترکیبیاتی بیشتری پیدا کنند، یافتن نتایج مشابه برای آن‌ها سخت تر می‌شود. به‌طور مثال در سال ۲۰۰۷ اعلام شد که بازی چکرز حل شدۀ ضعیف است. بازی‌های دنیای واقعی عموماً پیچیده‌تر از آن هستند که بتوانیم به راحتی تحلیلشان کنیم، اگرچه به تازگی تحلیل و آنالیز آخر بازی گو موفقیت‌آمیز بوده‌است. با استفاده از نظریه بازی‌های ترکیبیاتی، بازیکن‌ها در هر مرحله می‌توانند دنباله‌ای از تصمیمات بهینه را برای برد پیدا کنند ولی در برخی بازی‌ها این تصمیمات به راحتی یافت نمی‌شوند. ^[۱]

تاریخچه

نظریه بازی‌های ترکیبیاتی در رابطه با تئوری بازی‌های منصفانه که در آن‌ها هر دو بازیکن قادر به انجام اعمال یکسان هستند، به وجود آمد. یکی از این بازی‌های مهم، بازی نیم است که به صورت کامل حل شده است. تاکنون تحلیل‌های زیادی از بازی‌های گوناگون به چاپ رسیده‌اند که نقطۀ آغاز آن‌ها تحلیل بازی نیم توسط چارلز ال بوتون در سال ۱۹۰۲ بوده است. نیم یک بازی دونفرۀ منصفانه است و هر کس که در انتها قادر به انجام حرکتی نباشد، بازنده است.
در سال ۱۹۳۰، قضیه اسپراگ-گراندی نشان داد که تمامی بازی‌های منصفانه با کپه‌ها در بازی نیم معادلند. پس از آن جان کانوی نظریه بازی‌های پارتیزانی را که پیشرفت شگرفتی بود، ارائه و توسعه داد.

بررسی اجمالی

یک بازی در ساده‌ترین حالت خود لیستی از حرکت‌های ممکن است که دو بازیکن که آن‌ها را چپ و راست می‌نامند، می‌توانند انجام دهند. موقعیت بازی از تمام حرکاتی که حتی از یک بازی دیگر می‌توان انجام داد، نتیجه می‌شود. این ایده که بازی‌ها از جهت حرکت‌های ممکن آن‌ها منجر به بازی دیگری می‌شوند، تعریف بازگشتی ریاضی بازی است که در نظریه بازی‌های ترکیبیاتی، استاندارد است. در این تعریف هر بازی نمادی به شکل {L|R} دارد که در آن $L$ و $R$ مجموعه‌ای از موقعیت‌های بازی هستند که به ترتیب توسط بازیکن چپ و راست می‌توانند ایجاد شوند و نمادهای یکسانی دارند.

کاربرد‌ها

نظریه بازی‌های ترکیبیاتی روش‌های جدیدی برای آنالیز‌کردن درخت بازی‌ها ارائه کرده است. مانند استفاده از اعداد سوررئال که زیر کلاسی از همه‌ی بازی‌های دو نفره با اطلاعات کامل است. بازی‌هایی که در نظریه بازی‌های ترکیبیاتی مورد بررسی قرار می‌گیرند، در هوش مصنوعی و به خصوص در برنامه‌ریزی‌های خودکار و زمانبندی شده نیز کاربرد دارند. همچنین این شاخه ارتباط‌هایی با دیگر شاخه‌های ریاضیات مانند نظریه کدگذاری،نظریه گراف، نظریه اعداد، منطق ریاضی، نظریه ماتروید‌ها و نظریه شبکه دارد.^[۲]

نیمبر‌ها

بازی‌های منصفانه به بازی‌هایی گفته می‌شود که حرکت‌های قابل قبول در آن وضعیت، تنها به وضعیت کنونی بستگی داشته باشد و نه براساس نوبت بازیکنان. در بازی‌های منصفانه، مستقل از نوبت بازیکنان و تنها براساس وضعیت موجود می‌توان استراتژی برد را تعیین کرد. به بیانی دیگر، اگر وضعیت بازی را ثابت نگه داریم و نوبت بازیکنان را عوض کنیم، تحلیل بازی تغییری نمی‌کند. به طور مثال در بازی نیم، هر مجموعه‌ای از شی‌ها که توسط یک بازیکن خارج شوند، توسط بازیکن دیگر نیز می‌توانند خارج شوند.^[۳] اما به طور مثال بازی سلطه‌گر منصفانه نیست زیرا یکی از بازیکن‌ها، دومینو‌ها را به صورت افقی و بازیکن دیگر آن‌ها را عمودی قرار می‌دهد و در نتیجه شرایط برای دو بازیکن یکسان نیست. به همین ترتیب بازی چکرز نیز منصفانه نیست زیرا بازیکن‌ها رنگ‌های مختلف خود را دارند.^[۴] برای هر عدد ترتیبی می‌توان یک بازی منصفانه تعریف کرد که تعمیمی از بازی نیم است و در آن در هر حرکت هر دو بازیکن می‌توانند یک عدد را با یک عدد ترتیبی کوچک‌تر جایگزین کنند. بازی‌هایی که به این شکل تعریف می‌شوند، با عنوان نیمبرها شناخته می‌شوند. قضیه اسپراگ-گراندی نشان می‌دهد که هر بازی منصفانه معادل است با یک نیمبر. همچنین کوچک‌ترین نیمبر‌ها همان ساده‌ترین و کوچک‌ترین اعداد روی ترتیب معمول اعداد ترتیبی یعنی ۰ و * هستند.

منابع

↑ https://en.wikipedia.org/wiki/Combinatorial_game_theory
↑ ریچارد ک. گای (۱۳۸۰)، بازی منصفانه، ترجمهٔ عبادالله محمودیان، آناهیتا آریاچهر، دانشگاه صنعتی شریف، موسسه انتشارات علمی از پارامتر ناشناخته |کشور= صرف‌نظر شد (کمک)
↑ http://opedia.ir/آموزش/ترکیبیات/بازی‌های_منصفانه_و_غیرمنصفانه
↑ Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003). Winning Ways for Your Mathematical Plays. A K Peters, Ltd. ISBN 0-12-091150-7.

[1] ttps://en.wikipedia.org/wiki/Combinatorial_game_theory

[2] ریچارد ک. گای (۱۳۸۰)، بازی منصفانه، ترجمهٔ عبادالله محمودیان، آناهیتا آریاچهر، دانشگاه صنعتی شریف، موسسه انتشارات علمی از پارامتر ناشناخته |کشور= صرف‌نظر شد (کمک)

[3] ttp://opedia.ir/آموزش/ترکیبیات/بازی‌های_منصفانه_و_غیرمنصفانه

[4] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (2003). Winning Ways for Your Mathematical Plays. A K Peters, Ltd. ISBN 0-12-091150-7.

[۱]

[۲]

[۳]

[۴]

@@ خط ۱: / خط ۱: @@
 [[Image:Mathematicians playing Konane.jpg|thumb|جمعی از ریاضیدان‌ها در حال بازی کردن [[Konane]] در کارگاه نظریه بازی‌های ترکیبیاتی]]
-'''نظریه بازی‌های ترکیبیاتی''' شاخه‌ای از [[ریاضیات]] و [[علوم نظری رایانه]] است که به طور معمول به مطالعۀ [[بازی‌های ترتیبی]] و دنباله‌وار با اطلاعات کامل می‌پردازد و مطالعۀ آن بیشتر شامل [[بازی‌]] های دونفره‌ایست که در آن بازیکنان به نوبت، حرکاتی در راستای رسیدن به موقعیت برد انجام می‌دهند. همچنین این بازی‌ها در زمان متناهی پایان می‌یابند و برنده براساس قوانین بازی مشخص خواهد شد.
+'''نظریه بازی‌های ترکیبیاتی''' شاخه‌ای از [[ریاضیات]] و [[علوم نظری رایانه]] است که به طور معمول به مطالعۀ [[بازی‌های ترتیبی]] و دنباله‌وار با اطلاعات کامل می‌پردازد و مطالعۀ آن بیشتر شامل [[بازی‌]] های دونفره‌ایست که در آن بازیکنان به نوبت، حرکاتی در راستای رسیدن به موقعیت برد انجام می‌دهند. همچنین این بازی‌ها در زمان متناهی پایان می‌یابند و برنده براساس قوانین بازی مشخص می‌شود.
 {{سخ}}
 بازی‌های ترکیبیاتی به دو دستۀ [[بازی‌های منصفانه]] و [[بازی‌های پارتیزانی]] تقسیم می‌شوند.
 {{سخ}}
-این نظریه به طور سنتی، به بررسی [[بازی‌های شانسی]] و یا اطلاعات ناقص نمی‌پردازد و موضوع عمدۀآن بازی‌هایی است که مجموعۀ حرکات در هر مرحله از بازی مشخص است و بازیکن‌ها نیز از آن مطلع اند. هدف از بررسی بازی‌ها یافتن برنده‌ی بازی از یک حالت اولیه مشخص و همچنین نحوه‌ی پیروزی برنده است (یعنی برنده با چه حرکاتی می‌تواند پیروز شود) که اصطلاحاً به آن استراتژی برد می‌گویند.
+این نظریه به طور سنتی، به بررسی [[بازی‌های شانسی]] و یا بازی‌های اطلاعات ناقص نمی‌پردازد و موضوع عمدۀ آن بازی‌هایی است که مجموعۀ حرکات در هر مرحله از بازی مشخص است و بازیکن‌ها نیز از آن مطلع اند. هدف از بررسی بازی‌ها یافتن برنده‌ی بازی از یک حالت اولیه مشخص و همچنین نحوه‌ی پیروزی برنده است -یعنی برنده با چه حرکاتی می‌تواند پیروز شود- که اصطلاحاً به آن استراتژی برد می‌گویند.
 {{سخ}}
-امروزه با استفاده از تکنیک های پیشرفتۀ ریاضی، نوع و تعداد بازی‌هایی که می‌توانند به صورت ریاضی تحلیل و بررسی شوند، در حال گسترش است. یه طوری که در بازی‌های ترکیبیاتی تمامی قوانین و حرکات مجاز و حتی تحلیل بازی نوشته می‌شوند.
+امروزه با استفاده از تکنیک‌های پیشرفتۀ ریاضی، نوع و تعداد بازی‌هایی که می‌توانند به صورت ریاضی تحلیل و بررسی شوند، در حال گسترش است. یه طوری که در بازی‌های ترکیبیاتی تمامی قوانین و حرکات مجاز و حتی تحلیل بازی نوشته می‌شوند.
 {{سخ}}
-[[شطرنج]]، [[چکرز]] و [[گو (بازی)|گو]] از بازی‌های ترکیبیاتی غیر بدیهی به شمار می‌روند، اما بازی‌هایی مانند [[ایکس او]] جزء بازی‌های بدیهی به حساب می‌آیند و در هر دو نوع این بازی‌ها، حرکات را می‌توان به کمک [[درخت بازی|درخت بازی‌ها]] نمایش داد.
+[[شطرنج]]، [[چکرز]] و [[گو (بازی)|گو]] از بازی‌های ترکیبیاتی غیر بدیهی به‌شمار می‌روند، اما بازی‌هایی مانند [[ایکس او]] جزء بازی‌های بدیهی به حساب می‌آیند و در هر دو نوع این بازی‌ها، حرکات را می‌توان به کمک [[درخت بازی|درخت بازی‌ها]] نمایش داد.
 بازی‌های ترکیبیاتی شامل بازی‌های یک نفره با جداول ترکیبیاتی مانند [[سودوکو]] و یا بازی‌های بدون بازیکن اتوماتیک مانند [[بازی زندگی کانوی]]  است.
-{{سخ}}
 همچنین [[نظریه بازی‌ها]] به طور کلی شامل بازی‌های شانسی، بازی‌هایی که نیاز به دانش خاص ندارند و بازی‌هایی است که بازیکن‌ها همزمان می‌توانند بازی کنند و هدف آن شبیه‌سازی تصمیمات واقعی زندگی است.
+{{سخ}}
 نظریه بازی‌های ترکیبیاتی با نظریه بازی‌های سنتی و یا اقتصادی، که در ابتدا برای مطالعۀ بازی‌های ترکیبیاتی سادۀ دارای شانس توسعه پیدا کردند، متفاوت است.
 {{سخ}}
-در نظریه بازی‌های ترکیبیاتی تأکید کمتری بر پالایش عملی [[الگوریتم جستجو|الگوریتم‌های جستجو]] مانند [[هرس آلفا بتا]] - که در اکثر کتاب های هوش مصنوعی به آن اشاره شده است - وجود دارد و بیشتر بر روی نتایج نظری توصیفی، مانند محاسبۀ [[پیچیدگی بازی‌ها]] و یا یافتن راه‌حل های بهینه تأکید می‌شود.
+در نظریه بازی‌های ترکیبیاتی تأکید کمتری بر پالایش عملی [[الگوریتم جستجو|الگوریتم‌های جستجو]] مانند [[هرس آلفا بتا]] - که در اکثر کتاب های هوش مصنوعی به آن اشاره شده است - وجود دارد و بیشتر بر روی نتایج نظری توصیفی، مانند محاسبۀ [[پیچیدگی بازی‌ها]] و یا یافتن راه‌حل‌های بهینه تأکید می‌شود.
 {{سخ}}
-همچنین بخش مهمی از نظریه بازی‌های ترکیبیاتی دربارۀ [[بازی‌های حل شده]] است. به طور مثال در بازی ایکس او می‌توان ثابت کرد که اگر هر دو بازیکن به طور بهینه بازی کنند، مساوی می‌‌شوند. هرچه بازی‌ها ساختار ترکیبیاتی بیشتری پیدا کنند، یافتن نتایج مشابه برای آن‌ها سخت تر می‌شود. به‌طور مثال در سال ۲۰۰۷ اعلام شد که بازی چکرز حل شدۀ ضعیف است. بازی‌های دنیای واقعی عموماً پیچیده تر از آن هستند که بتوانیم به راحتی تحلیلشان کنیم، اگرچه به تازگی تحلیل و آنالیز آخر بازی گو موفقیت‌آمیز بوده‌است. بااستفاده از نظریه بازی‌های ترکیبیاتی، بازیکن‌ها در هر مرحله می‌توانند دنباله‌ای از تصمیمات بهینه را برای برد پیدا کنند ولی در برخی بازی‌ها این تصمیمات به راحتی یافت نمی‌شوند.
+همچنین بخش مهمی از نظریه بازی‌های ترکیبیاتی دربارۀ [[بازی‌های حل شده]] است. به طور مثال در بازی ایکس او می‌توان ثابت کرد که اگر هر دو بازیکن به طور بهینه بازی کنند، مساوی می‌‌شوند. معمولاً هرچه بازی‌ها ساختار ترکیبیاتی بیشتری پیدا کنند، یافتن نتایج مشابه برای آن‌ها سخت تر می‌شود. به‌طور مثال در سال ۲۰۰۷ اعلام شد که بازی چکرز حل شدۀ ضعیف است. بازی‌های دنیای واقعی عموماً پیچیده‌تر از آن هستند که بتوانیم به راحتی تحلیلشان کنیم، اگرچه به تازگی تحلیل و آنالیز آخر بازی گو موفقیت‌آمیز بوده‌است. با استفاده از نظریه بازی‌های ترکیبیاتی، بازیکن‌ها در هر مرحله می‌توانند دنباله‌ای از تصمیمات بهینه را برای برد پیدا کنند ولی در برخی بازی‌ها این تصمیمات به راحتی یافت نمی‌شوند.
 <ref>https://en.wikipedia.org/wiki/Combinatorial_game_theory</ref>
 {{سخ}}
 == تاریخچه ==
-نظریه بازی‌های ترکیبیاتی در رابطه با تئوری بازی‌های منصفانه که در آن‌ها هر دو بازیکن قادر به انجام اعمال یکسان هستند، به‌وجود آمد. یکی از این بازی‌های مهم، بازی [[نیم (بازی)|نیم]] است که به صورت کامل حل شده است. تاکنون تحلیل های زیادی از بازی‌های گوناگون  به چاپ رسیده‌اند که نقطۀ آغاز آن‌ها تحلیل بازی نیم توسط [[چارلز ال بوتون]] در سال ۱۹۰۲ بوده‌است. نیم یک بازی دونفرۀ منصفانه است و هرکس که در انتها قادر به انجام حرکتی نباشد، بازنده است.
+نظریه بازی‌های ترکیبیاتی در رابطه با تئوری بازی‌های منصفانه که در آن‌ها هر دو بازیکن قادر به انجام اعمال یکسان هستند، به وجود آمد. یکی از این بازی‌های مهم، بازی [[نیم (بازی)|نیم]] است که به صورت کامل حل شده است. تاکنون تحلیل‌های زیادی از بازی‌های گوناگون  به چاپ رسیده‌اند که نقطۀ آغاز آن‌ها تحلیل بازی نیم توسط [[چارلز ال بوتون]] در سال ۱۹۰۲ بوده است. نیم یک بازی دونفرۀ منصفانه است و هر کس که در انتها قادر به انجام حرکتی نباشد، بازنده است.
 {{سخ}}
 در سال ۱۹۳۰، [[قضیه اسپراگ-گراندی]] نشان داد که تمامی بازی‌های منصفانه با کپه‌ها در بازی نیم معادلند. پس از آن [[جان هورتون کانوی|جان کانوی]] نظریه بازی‌های پارتیزانی را که پیشرفت شگرفتی بود، ارائه و توسعه داد.
 {{سخ}}
 == بررسی اجمالی ==
-یک بازی در ساده‌ترین حالت خود لیستی از حرکت‌های ممکن است که دو بازیکن آن را چپ و راست می‌نامند.
+یک بازی در ساده‌ترین حالت خود لیستی از حرکت‌های ممکن است که دو بازیکن که آن‌ها را چپ و راست می‌نامند، می‌توانند انجام دهند.
-موقعیت بازی از تمام حرکاتی که حتی از یک بازی دیگر می‌توان انجام داد، نتیجه می‌شود.این ایده که بازی‌ها از جهت حرکت‌های ممکن آن‌ها  منجر به بازی دیگری می‌شود، تعریف [[توابع بازگشتی|بازگشتی]] ریاضی بازی است که در نظریه بازی‌های ترکیبیاتی، استاندارد است. در این تعریف هر بازی نمادی به شکل '''{L|R}''' دارد که در آن  <math>L</math>و<math>R</math> [[مجموعه (ریاضی)|مجموعه]] ای از موقعیت‌های بازی هستند که به ترتیب توسط بازیکن چپ و راست می‌توانند ایجاد شوند و نمادهای یکسانی دارند.
+موقعیت بازی از تمام حرکاتی که حتی از یک بازی دیگر می‌توان انجام داد، نتیجه می‌شود. این ایده که بازی‌ها از جهت حرکت‌های ممکن آن‌ها  منجر به بازی دیگری می‌شوند، تعریف [[توابع بازگشتی|بازگشتی]] ریاضی بازی است که در نظریه بازی‌های ترکیبیاتی، استاندارد است. در این تعریف هر بازی نمادی به شکل '''{L|R}''' دارد که در آن  <math>L</math> و <math>R</math> [[مجموعه (ریاضی)|مجموعه]]‌ای از موقعیت‌های بازی هستند که به ترتیب توسط بازیکن چپ و راست می‌توانند ایجاد شوند و نمادهای یکسانی دارند.
 {{سخ}}
 == کاربرد‌ها ==
-نظریه بازی‌های ترکیبیاتی روش‌های جدیدی برای آنالیز‌کردن درخت بازی‌ها ارائه کرده‌است. مانند استفاده از[[اعداد سوررئال]] که زیر کلاسی از همه‌ی بازی‌های دو نفره با اطلاعات کامل است. بازی‌هایی که در نظریه بازی‌های ترکیبیاتی مورد بررسی قرار می‌گیرند، در [[هوش مصنوعی]] و به خصوص در [[برنامه‌ریزی‌های خودکار و زمانبندی شده]] نیز کاربرد دارند. همچنین این شاخه ارتباط‌هایی با دیگر شاخه‌های ریاضیات مانند [[نظریه کدگذاری]]،[[نظریه گراف]]، [[نظریه اعداد]]، [[منطق ریاضی]]، [[ماتروید|نظریه ماتروید‌ها]] و [[نظریه شبکه]] دارد.<ref>{{یادکرد|کتاب=بازی منصفانه|نویسنده=[[ریچارد ک. گای]]|ترجمه=عبادالله محمودیان، آناهیتا آریاچهر|کشور=تهران|ناشر=[[دانشگاه صنعتی شریف]]، موسسه انتشارات علمی|سال=۱۳۸۰|شابک= }}</ref>
+نظریه بازی‌های ترکیبیاتی روش‌های جدیدی برای آنالیز‌کردن درخت بازی‌ها ارائه کرده است. مانند استفاده از [[اعداد سوررئال]] که زیر کلاسی از همه‌ی بازی‌های دو نفره با اطلاعات کامل است. بازی‌هایی که در نظریه بازی‌های ترکیبیاتی مورد بررسی قرار می‌گیرند، در [[هوش مصنوعی]] و به خصوص در [[برنامه‌ریزی‌های خودکار و زمانبندی شده]] نیز کاربرد دارند. همچنین این شاخه ارتباط‌هایی با دیگر شاخه‌های ریاضیات مانند [[نظریه کدگذاری]]،[[نظریه گراف]]، [[نظریه اعداد]]، [[منطق ریاضی]]، [[ماتروید|نظریه ماتروید‌ها]] و [[نظریه شبکه]] دارد.<ref>{{یادکرد|کتاب=بازی منصفانه|نویسنده=[[ریچارد ک. گای]]|ترجمه=عبادالله محمودیان، آناهیتا آریاچهر|کشور=تهران|ناشر=[[دانشگاه صنعتی شریف]]، موسسه انتشارات علمی|سال=۱۳۸۰|شابک= }}</ref>
 {{سخ}}
 ==نیمبر‌ها==
-بازی‌های منصفانه به بازی‌هایی گفته می‌شود که حرکت‌های قابل قبول در آن وضعیت، تنها وابسته به وضعیت کنونی بستگی داشته باشد و نه براساس نوبت بازیکنان. در بازی‌های منصفانه مستقل از نوبت بازیکنان و تنها براساس وضعیت موجود می‌توان استراتژی برد را تعیین کرد. به بیانی دیگر، اگر وضعیت بازی را ثابت نگه‌داریم و نوبت بازیکنان را عوض کنیم، تحلیل بازی تغییری نمی‌کند. به طور مثال در بازی [[نیم (بازی)|نیم]]، هر مجموعه‌ای از شی‌ها که توسط یک بازیکن خارج شوند، توسط بازیکن دیگر نیز می‌توانند خارج شوند.<ref>http://opedia.ir/آموزش/ترکیبیات/بازی‌های_منصفانه_و_غیرمنصفانه</ref> اما به طور مثال بازی [[سلطه‌گر]] منصفانه نیست زیرا یکی از بازیکن‌ها، دومینو‌ها را به صورت افقی و بازیکن دیگر آن‌ها را عمودی قرار می‌دهد و در نتیجه شرایط برای دو بازیکن یکسان نیست. به همین ترتیب بازی [[چکرز]] نیز منصفانه نیست زیرا بازیکن‌ها رنگ‌های مختلف خود را دارند.<ref>{{cite book | first=Elwyn R.   | last=Berlekamp | authorlink=Elwyn Berlekamp
+بازی‌های منصفانه به بازی‌هایی گفته می‌شود که حرکت‌های قابل قبول در آن وضعیت، تنها به وضعیت کنونی بستگی داشته باشد و نه براساس نوبت بازیکنان. در بازی‌های منصفانه، مستقل از نوبت بازیکنان و تنها براساس وضعیت موجود می‌توان استراتژی برد را تعیین کرد. به بیانی دیگر، اگر وضعیت بازی را ثابت نگه داریم و نوبت بازیکنان را عوض کنیم، تحلیل بازی تغییری نمی‌کند. به طور مثال در بازی [[نیم (بازی)|نیم]]، هر مجموعه‌ای از شی‌ها که توسط یک بازیکن خارج شوند، توسط بازیکن دیگر نیز می‌توانند خارج شوند.<ref>http://opedia.ir/آموزش/ترکیبیات/بازی‌های_منصفانه_و_غیرمنصفانه</ref> اما به طور مثال بازی [[سلطه‌گر]] منصفانه نیست زیرا یکی از بازیکن‌ها، دومینو‌ها را به صورت افقی و بازیکن دیگر آن‌ها را عمودی قرار می‌دهد و در نتیجه شرایط برای دو بازیکن یکسان نیست. به همین ترتیب بازی [[چکرز]] نیز منصفانه نیست زیرا بازیکن‌ها رنگ‌های مختلف خود را دارند.<ref>{{cite book | first=Elwyn R.   | last=Berlekamp | authorlink=Elwyn Berlekamp
              | first2=John H.    | last2=Conway   | author2-link=John Horton Conway
              | first3=Richard K. | last3=Guy      | author3-link=Richard K. Guy
@@ خط ۳۹: / خط ۳۹: @@
   }}</ref>
 برای هر [[عدد ترتیبی]] می‌توان یک بازی منصفانه تعریف کرد که تعمیمی از بازی نیم است و در آن در هر حرکت هر دو بازیکن می‌توانند یک عدد را با یک عدد ترتیبی کوچک‌تر جایگزین کنند. بازی‌هایی که به این شکل تعریف می‌شوند، با عنوان [[نیمبر|نیمبرها]] شناخته می‌شوند. [[قضیه اسپراگ-گراندی]] نشان می‌دهد که هر بازی منصفانه معادل است با یک نیمبر.
-همچنین کوچک ترین نیمبر‌ها همان ساده‌ترین و کوچک ترین اعداد روی ترتیب معمول اعداد ترتیبی یعنی ۰  و * هستند.
+همچنین کوچک‌ترین نیمبر‌ها همان ساده‌ترین و کوچک‌ترین اعداد روی ترتیب معمول اعداد ترتیبی یعنی ۰  و * هستند.
 {{سخ}}
 ==منابع==