![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/4/44/Mathematicians_playing_Konane.jpg/640px-Mathematicians_playing_Konane.jpg&w=640&q=50)
نظریه بازیهای ترکیبیاتی
From Wikipedia, the free encyclopedia
نظریه بازیهای ترکیبیاتی (به انگلیسی: Combinatorial game theory) شاخهای از ریاضیات و علوم نظری رایانه است که بهطور معمول به مطالعهٔ بازیهای ترتیبی و دنبالهدار با اطلاعات کامل میپردازد و مطالعهٔ آن بیشتر شامل بازیهای دونفرهای است که در آن بازیکنان به نوبت، حرکاتی در راستای رسیدن به موقعیت برد انجام میدهند. همچنین این بازیها در زمان متناهی پایان مییابند و برنده براساس قوانین بازی مشخص میشود.
این نظریه بهطور سنتی، به بررسی بازیهای شانسی یا بازیهای اطلاعات ناقص نمیپردازد و موضوع عمدهٔ آن بازیهایی است که مجموعهٔ حرکات در هر مرحله از بازی مشخص است و بازیکنها نیز از آن مطلعاند. هدف از بررسی بازیها یافتن برندهٔ بازی از یک حالت اولیه مشخص و همچنین نحوهٔ پیروزی برنده است -یعنی برنده با چه حرکاتی میتواند پیروز شود- که اصطلاحاً به آن استراتژی برد میگویند.
امروزه با استفاده از تکنیکهای پیشرفتهٔ ریاضی، نوع و تعداد بازیهایی که میتوانند به صورت ریاضی تحلیل و بررسی شوند، در حال گسترش است. یه طوریکه در بازیهای ترکیبیاتی تمامی قوانین و حرکات مجاز و حتی تحلیل بازی نوشته میشوند.
شطرنج، چکرز و گو از بازیهای ترکیبیاتی غیر بدیهی بهشمار میروند، اما بازیهایی مانند ایکس او جزء بازیهای بدیهی به حساب میآیند و در هر دو نوع این بازیها، حرکات را میتوان به کمک درخت بازیها نمایش داد.
بازیهای ترکیبیاتی شامل بازیهای یکنفره با جداول ترکیبیاتی مانند سودوکو یا بازیهای بدون بازیکن اتوماتیک مانند بازی زندگی کانوی است.[1]
همچنین نظریه بازیها بهطور کلی شامل بازیهای شانسی، بازیهایی که نیاز به دانش خاص ندارند و بازیهایی است که بازیکنها همزمان میتوانند بازی کنند و هدف آن شبیهسازی تصمیمات واقعی زندگی است.
نظریه بازیهای ترکیبیاتی با نظریه بازیهای سنتی یا اقتصادی، که در ابتدا برای مطالعهٔ بازیهای ترکیبیاتی سادهٔ دارای شانس توسعه پیدا کردند، متفاوت است.
در نظریه بازیهای ترکیبیاتی تأکید کمتری بر پالایش عملی الگوریتمهای جستجو مانند هرس آلفا بتا - که در اکثر کتابهای هوش مصنوعی به آن اشاره شدهاست - وجود دارد و بیشتر بر روی نتایج نظری توصیفی، مانند محاسبهٔ پیچیدگی بازیها یا یافتن راهحلهای بهینه تأکید میشود.
همچنین بخش مهمی از نظریه بازیهای ترکیبیاتی دربارهٔ بازیهای حل شده است. بهطور مثال در بازی ایکس او میتوان ثابت کرد که اگر هر دو بازیکن بهطور بهینه بازی کنند، مساوی میشوند. معمولاً هرچه بازیها ساختار ترکیبیاتی بیشتری پیدا کنند، یافتن نتایج مشابه برای آنها سختتر میشود. بهطور مثال در سال ۲۰۰۷ اعلام شد که بازی چکرز حل شدهٔ ضعیف است. بازیهای دنیای واقعی عموماً پیچیدهتر از آن هستند که بتوانیم به راحتی تحلیلشان کنیم، اگرچه به تازگی تحلیل و آنالیز آخر بازی گو موفقیتآمیز بودهاست. با استفاده از نظریه بازیهای ترکیبیاتی، بازیکنها در هر مرحله میتوانند دنبالهای از تصمیمات بهینه را برای برد پیدا کنند ولی در برخی بازیها این تصمیمات به راحتی یافت نمیشوند.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/Mathematicians_playing_Konane.jpg/640px-Mathematicians_playing_Konane.jpg)