نظریه بازی‌های ترکیبیاتی

بازی‌های ترکیبیاتی به دو دستهٔ بازی‌های منصفانه و بازی‌های پارتیزانی تقسیم می‌شوند. بازی‌های منصفانه به بازی‌هایی گفته می‌شود که حرکت‌های قابل قبول در آن وضعیت، تنها به وضعیت کنونی بستگی داشته باشد و نه براساس نوبت بازیکنان. در بازی‌های منصفانه، مستقل از نوبت بازیکنان و تنها براساس وضعیت موجود می‌توان استراتژی برد را تعیین کرد. به بیانی دیگر، اگر وضعیت بازی را ثابت نگه داریم و نوبت بازیکنان را عوض کنیم، تحلیل بازی تغییری نمی‌کند. به‌طور مثال در بازی نیم، هر مجموعه‌ای از شی‌ها که توسط یک بازیکن خارج شوند، توسط بازیکن دیگر نیز می‌توانند خارج شوند. اما به‌طور مثال بازی سلطه‌گر منصفانه نیست زیرا یکی از بازیکن‌ها، دومینوها را به صورت افقی و بازیکن دیگر آن‌ها را عمودی قرار می‌دهد و در نتیجه شرایط برای دو بازیکن یکسان نیست. به همین ترتیب بازی چکرز نیز منصفانه نیست زیرا بازیکن‌ها رنگ‌های مختلف خود را دارند.
بازی نیم

نیم یک بازی دونفرهٔ راهبردی (استراتژیک) ریاضی است که با کپه‌هایی از سنگ‌ریزه انجام می‌شود. در هر نوبت هر بازیکن از یک کپه حداقل یک سنگ‌ریزه برمی‌دارد (بازیکن حتی می‌تواند تمام کپه را نیز بردارد). نیم اغلب به این صورت بازی می‌شود که در هر نوبت بازیکن حداقل یک شیء را برمی‌دارد و ممکن است هر تعدادی را به شرط اینکه از یک پشته باشد بردارد. در نهایت بازیکنی که نتواند چیزی را بردارد بازنده است. نیم به صورت ریاضی برای تعداد متناهی از کپه‌ها و سنگ‌ریزه‌ها حل شده‌است و می‌توان مشخص نمود که کدام بازیکن برنده خواهد شد. با جمع دودویی (باینری) اندازه کپه‌ها می‌توان این مسئله را حل نمود. به این ترتیب که معادل دودویی اندازه کپه‌ها را بدون درنظرگرفتن رقم نقلی با هم جمع کرد. این عمل همان یای انحصاری (XOR) در مدارهای منطقی است که در تئوری بازی‌های ترکیبی آن را جمع نیمی می‌نامند. جمع نیمی را می‌توان به صورت ذهنی که انگشتان دست را به ترتیب توان‌های ۲ در نظر می‌گیرند و اگر عددی دارای آن توان ۲ بود آن را بالا می‌برند و اگر دارای آن توان نبود آن را پایین می‌آورند و در جمع با سایر اعداد اگر آن عدد دارای توانی از ۲ بود وضعیت مربوط به آن انگشت را برعکس می‌کنند؛ یعنی اگر بالا بود آن را پایین می‌آورند و اگر پایین بود آن را بالا می‌برند. در بازی معمولی استراتژی برد، صفر کردن جمع نیمی اندازه کپه‌هاست که این امر تا زمانی‌که جمع نیمی آن‌ها صفر نشده‌است ممکن است. اگر جمع نیمی صفر شود بازیکنی که نوبت آن است خواهد باخت. (در صورتی که بازیکن دیگر اشتباه نکند). همان‌طور که مشخص است این بازی منصفانه می‌باشد زیرا استراتژی برد تنها وابسته به وضعیت کنونی است و به نوبت بازیکنان بستگی ندارد.
بازی ایکس او

ایکس او یک بازی دو نفره‌است. نام این بازی به دلیل علامت‌های X و O است که در طول بازی استفاده می‌شود. برای آغاز این بازی در یک صفحه، جدولی با ۳ ردیف و ۳ ستون رسم می‌شود و هر یک از طرفین یکی از علامت‌های X یا O را انتخاب می‌کنند و تا انتهای بازی برای پر کردن خانه‌های جدول از آن استفاده می‌کنند. برای شروع بازی یکی از طرفین به قید قرعه علامت X یا O را که قبلاً انتخاب کرده در یکی از خانه‌های جدول ۹ خانه‌ای قرار می‌دهد. سپس نفر دوم علامت مربوط به خود را در خانه‌های دیگر که هنوز پر نشده‌اند قرار می‌دهد و این روند به صورت متوالی و گردشی تکرار می‌شود. بازی زمانی به پایان می‌رسد که یکی از بازیکنان بتواند علامتی را که در ابتدای بازی انتخاب کرده در یکی از ردیف‌های افقی، عمودی یا قطری قرار دهد و در این صورت آن بازیکن برنده است. در طول بازی هر یک از طرفین با قرار دادن علامت خود در مقابل علامت‌های حریف نباید اجازه دهند که حریف یک خط عمودی، افقی یا قطری را با علامت خود پر کند. در این بازی نفر اول می‌تواند به گونه‌ای بازی کند که هیچ وقت نبازد. به این صورت که ابتدا خانهٔ وسط را علامت می‌گذارد. حال دو حالت ممکن است پیش آید:

• نفر دوم مهرهٔ خود را گوشه‌ها نگذارد: در این صورت نفر اول مهرهٔ خود را در گوشهٔ دیگری قرار می‌دهد به‌طوری‌که قرینهٔ مهرهٔ حریف نسبت به خانهٔ وسط نباشد.
• نفر دوم مهرهٔ خود را در گوشه‌ها نگذارد: در این صورت نفر اول مهرهٔ خود را درگوشه‌ای قرار می‌دهد که مجاور با این مهرهٔ حریف باشد.

سپس هر فرد به گونه‌ای بازی می‌کند که در اولویت اول اگر امکان برد در همان مرحله داشت، ببردو در اولویت دوم اگر حریف امکان برد داشت، از آن جلوگیری کند و اگر هیچ‌یک از این شرایط نبود، همان روش بالا را تکرار کند.
می‌توان نشان داد با این استراتژی، نفر اول هیچ‌گاه نمی‌بازد. پس این بازی یک بازی پارتیزانی است که در آن نوبت و ترتیب بازی بازیکنان در شکست یا برد آن‌ها نقش دارد.

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

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

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

برای هر عدد ترتیبی می‌توان یک بازی منصفانه تعریف کرد که تعمیمی از بازی نیم است و در آن در هر حرکت هر دو بازیکن می‌توانند یک عدد را با یک عدد ترتیبی کوچک‌تر جایگزین کنند. بازی‌هایی که به این شکل تعریف می‌شوند، با عنوان نیمبرها شناخته می‌شوند. قضیه اسپراگ-گراندی نشان می‌دهد که هر بازی منصفانه معادل است با یک نیمبر. همچنین کوچک‌ترین نیمبرها همان ساده‌ترین و کوچک‌ترین اعداد روی ترتیب معمول اعداد ترتیبی یعنی ۰ و * هستند.

هرس آلفا بتا
بازی ویتوف
سامانه چندعامله
پیچیدگی بازی
شکل گسترده بازی
درخت بازی

• List of combinatorial game theory links at the homepage of David Eppstein
• An Introduction to Conway's games and numbers by Dierk Schleicher and Michael Stoll
• Combinational Game Theory terms summary by Bill Spight
• Combinatorial Game Theory Workshop, Banff International Research Station, June 2005