Комбинаторна теория на игрите — дефиниция, правила и примери

Открийте Комбинаторната теория на игрите: ясна дефиниция, ключови правила и илюстрирани примери за решаване на стратегии и анализ на двубойни игри.

Автор: Leandro Alegsa

21-09-2025 23:48

Комбинаторната теория на игрите, известна също като CGT, е клон на приложната математика и теоретичната информатика, който изучава комбинаторните игри и се различава от "традиционната" или "икономическата" теория на игрите. КГТ възниква във връзка с теорията на безпристрастните игри, по-специално играта на Ним за двама играчи, като основната цел е "решаването" на определени видове комбинаторни игри — намиране на алгоритми и правила, които определят кой играч може да спечели при оптимална игра.

Критерии за комбинаторна игра

Една игра трябва да отговаря на няколко условия, за да бъде комбинаторна игра. Това са:

Играта трябва да има поне двама играчи.
Играта трябва да е последователна (играчите се редуват при правене на ходове).
Играта трябва да е с перфектна информация (да няма скрита информация или неизвестни елементи като в покера).
Играта трябва да е детерминистична (без елемент на шанс или случайни събития). Късметът не е част от играта.
Има ограничен (краен) брой възможни ходове от всяка позиция.
Играта трябва да приключи след краен брой ходове (да няма безкрайни цикли при правилна игра).
Терминален резултат: играта приключва, когато един от играчите не може да направи ход — тогава се определя победител и губещ според договореното правило (например при "normal play" побеждава последният, който е направил ход).

Основни понятия и класификация

В рамките на КГТ най-често разграничават два основни типа игри:

Безпристрастни (impartial) игри — възможните ходове зависят само от текущата позиция, а не от това кой е на ход. За тези игри важен инструмент е теоремата на Sprague–Grundy, която придава на всяка позиция число (grundy-число или nimber). При сумата на безпристрастни игри се използва операцията XOR (битово изключващо ИЛИ) върху тези стойности: позицията е печеливша за следващия играч точно тогава, когато XOR на grundy-числата е различно от нула — това е фундаменталният пример е играта Ним.
Пристрастни (partizan) игри — ходовете, достъпни за левия и десния играч могат да се различават. За тези игри се развива по-обща теория на стойностите (сюрреални числа, "hot" и "cold" игри, инфинитезимали и др.), въведена от Джон Конуей и сътрудници.

Представяне, стойности и суми от игри

Комбинаторните игри често се представят чрез дървета на разгръщане: всеки връх от дървото е позиция, а дъщерните върхове са позиции, получени чрез възможни ходове. На тези позиции могат да се присвоят игрови стойности, които описват кои играчи имат печеливша стратегия.

Сборът (дизюнктивната сума) на две или повече игри е фундаментална операция: в сумата всеки ход на играч се прави в точно една от съставните игри, като останалите се запазват. Изследването на сумите е ключово за разбирането на сложни позиции, тъй като много реални игри се разлагат на независими компоненти.

Стратегии и резултатни класове

За крайни безпристрастни игри има просто разграничение между две основни класови резултати:

P-позииции (Previous player win) — позициите, от които играчът, чийто ход е "предходният" (т.е. опонентът), има печеливша стратегия; следващият играч губи при оптимална игра.
N-позиции (Next player win) — позициите, от които следващият играч има печеливша стратегия.

За безпристрастни игри тези класове се определят ефективно чрез Grundy-числата; за пристрастни игри е необходимо по-фино разглеждане на стойностите и понякога се използват алгебрични конструкции (сюрреални числа и др.).

Примери и приложения

Класически примери, разглеждани в КГТ, включват:

Ним — купчина(и) камъни; ход: премахваш произволен брой камъни от една купчина. Оптималната стратегия се дава от XOR на големините на купчините (Sprague–Grundy теория).
Kayles, Hackenbush, Domineering и други пъзел-игри — дават богати примери както за безпристрастни, така и за пристрастни ситуации с интересни стойности.

Практически приложения на КГТ включват анализ на възможности в игри и пъзели, алгоритми за стратегии в изкуствен интелект, както и теоретични връзки с комбинаторика и теория на числата. От гледна точка на изчислителната сложност, много задачи свързани с обобщени (многоходови или неограничени) варианти на комбинаторни игри са трудни за решаване — често PSPACE-пълни или NP-трудни.

Ограничения и вариации

Комбинаторната теория на игрите обикновено се ограничава до двама играчи и крайни позиции без равенство (т.е. с ясно определен победител и губещ при нормална игра). Съществуват важни вариации: например misère-условие (последният, който направи ход, губи) променя правилата за оценка и прави някои стандартни техники (като Sprague–Grundy) неподходящи или изискващи модификация.

Основатели на теорията са Елуин Берлекамп, Джон Конуей и Ричард Гай. Те работят заедно през 60-те години на миналия век. Публикуваният им труд се нарича Печеливши начини за вашите математически игри — класическо изследване, което систематизира много от идеите и методите в комбинаторната теория на игрите.

Определения

В теорията има двама играчи, наречени ляв и десен. Играта е нещо, което позволява на левия и десния да правят ходове към други игри. Например в играта шахмат има обичайна начална настройка. Може обаче да се мисли и за шахматна партия след първия ход като за друга игра, с друга настройка. Така че всяка позиция също се нарича игра.

Игрите се означават с {L|R}. L {\displaystyle L} $L$ са игрите, в които може да се движи левият играч. R {\displaystyle R} $R$ са игрите, в които може да се движи десният играч. Ако познавате шахматната нотация, обичайната шахматна конфигурация е играта

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Точките "..." означават, че има много ходове, затова не са показани всички.

Шахматът е много сложен. По-добре е да мислите за по-лесни игри. Например Ним е много по-проста за мислене. Ним се играе по следния начин:

Има нула или повече купчини от броячи.
В хода си играчът може да вземе толкова жетони от една купчина, колкото иска.
Играчът, който не може да направи ход, губи.

Най-лесната игра на Nim започва без никакви броячи! В този случай никой от играчите не може да се движи. Това е показано като {|}. И двете страни са празни, защото никой от играчите не може да се движи. Първият играч не може да се движи и затова ще загуби. В CGT хората често изписват {|} като символа 0 (нула).

Следващата най-лесна игра има само една купчина с един брояч. Ако левият играч отиде пръв, той трябва да вземе брояча, а десният няма ход ({|} или 0). Ако вместо това десният ход е първи, левият няма да има повече ходове. Така че и левият, и десният могат да направят ход до 0. Това е показано като {{|}|{|}}, или {0|0}. Първият играч, който направи ход, ще спечели. Игрите, равни на {0|0}, са много важни. Те се изписват със символа * (звезда).

Въпроси и отговори

Въпрос: Какво представлява комбинаторната теория на игрите?

О: Комбинаторната теория на игрите (КТГ) е клон на приложната математика и теоретичната информатика, който изучава комбинаторните игри и се различава от "традиционната" или "икономическата" теория на игрите.

В: На какви условия трябва да отговаря една игра, за да се счита за комбинаторна игра?

О: За да се счита една игра за комбинаторна игра, тя трябва да има поне двама играчи, да е последователна (т.е. играчите да се редуват), да има перфектна информация (т.е. да не се крие никаква информация), да е детерминистична (т.е. да не е случайна), късметът не може да е част от играта, да има определен брой възможни ходове, играта да завършва в крайна сметка и да завършва, когато един от играчите вече не може да се движи.

Въпрос: Върху какъв тип игри се фокусира комбинаторната теория на игрите?

О: Комбинаторната теория на игрите се фокусира основно върху крайни игри за двама играчи, които имат победители и губещи (т.е. не завършват с реми).

В: Как се представят тези видове игри?

О: Тези видове игри могат да бъдат представени чрез дървета, като всеки връх представлява резултата от играта, получен в резултат на определен ход от дървото, разположено непосредствено под него.

В: Какви са някои цели на теоретиците на CG?

О: Някои от целите на теоретиците на CG включват намирането на стойности за тези видове игри, както и разбирането на концепцията за "добавяне на игра", която включва всеки играч да направи само един ход в две различни игри, като остави другата непроменена по време на хода си.

В: Кой е основател на CGT?

О: Елуин Берлекамп, Джон Конуей и Ричард Гай са признати за основатели на CGT в публикувания от тях труд "Печеливши начини за вашите математически игри" през 60-те години на миналия век.

обискирам