Комбинаторна теория на игрите

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

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

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

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

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

Основатели на теорията са Елуин Берлекамп, Джон Конуей и Ричард Гай. Те работят заедно през 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-те години на миналия век.