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

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