Kombinatoryczna teoria gier

Autor: Leandro Alegsa

17-12-2020

Teoria gier kombinowanych, znana również jako CGT, jest gałęzią matematyki stosowanej i informatyki teoretycznej, która bada gry kombinowane i różni się od "tradycyjnej" lub "ekonomicznej" teorii gier. CGT powstało w związku z teorią gier bezstronnych, w szczególności gry dwuosobowe Nima, z naciskiem na "rozwiązywanie" pewnych rodzajów gier kombinowanych.

Gra musi spełniać kilka warunków, aby była to gra kombinowana. To są te warunki:

W grze musi brać udział co najmniej dwóch graczy.
Gra musi być sekwencyjna (tzn. Gracze wykonują obroty na przemian).
Gra musi mieć doskonałe informacje (tzn. żadna informacja nie jest ukryta, jak w pokerze).
Gra musi być deterministyczna (tzn. nie szansa). Szczęście nie jest częścią gry.
Gra musi mieć określoną ilość możliwych ruchów.
Gra musi się w końcu skończyć.
Gra musi się zakończyć, gdy jeden z graczy nie może się już poruszać.

Teoria gier kombinowanych jest w dużej mierze ograniczona do badania podzbioru gier kombinowanych, które są dwuosobowe, skończone i mają zwycięzcę i przegranego (tzn. nie kończą się remisami).

Te kombinatoryczne gry mogą być reprezentowane przez drzewa, z których każdy wierzchołek jest grą wynikającą z konkretnego ruchu z gry bezpośrednio pod nim na drzewie. Do tych gier można przypisać wartości gry. Znalezienie tych wartości gry jest bardzo interesujące dla teoretyków CG, tak samo jak teoretyczna koncepcja dodawania gry. Suma dwóch gier jest grą, w której każdy z graczy na swojej kolejce musi poruszać się tylko w jednej z dwóch gier, pozostawiając drugą taką, jaka była.

Elwyn Berlekamp, John Conway i Richard Guy są założycielami tej teorii. Pracowali razem w latach 60-tych. Ich publikowana praca nazywała się "Zwycięskie sposoby na twoje sztuki matematyczne".

Definicje

W teorii są dwaj gracze zwani lewymi i prawymi. Gra jest czymś, co pozwala lewemu i prawemu wykonywać ruchy do innych gier. Na przykład, w grze w szachy, istnieje zwykłe ustawienie początkowe. Można jednak również myśleć o grze w szachy po pierwszym ruchu jako o innej grze, z innym ustawieniem. Tak więc każda pozycja jest również nazywana grą.

Gry mają notację {L|R}. L, $L$ to gry, do których może przejść lewy gracz. R - styl R $R$ - to gry, do których może przejść prawy gracz. Jeśli znasz notację szachową, to zwykłe ustawienie szachów jest grą.

{ 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 , ... } \a3,a4,Na3,b3,b4,c3,c4,Nc3,\a6,a5,Na6,b6,b5,c6,c5,Nc6,\doty $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Kropki "..." oznaczają, że jest wiele ruchów, więc nie wszystkie są pokazane.

Szachy są bardzo skomplikowane. Lepiej pomyśleć o łatwiejszych grach. Nim, na przykład, jest o wiele prostszy do myślenia. Nim jest rozgrywany w ten sposób:

Jest zero lub więcej stosów liczników.
Po kolei, gracz może wziąć tyle liczników z jednego stosu, ile chce.
Gracz, który nie może wykonać ruchu, przegrywa.

Najprostsza gra Nima zaczyna się bez liczników! W takim przypadku, żaden z graczy nie może się ruszyć. To jest pokazane jako {|} Obie strony są puste, bo żaden z graczy nie może się ruszyć. Pierwszy gracz, który pójdzie, nie może się ruszyć, a więc przegra. W CGT, ludzie często piszą {|} jako symbol 0 (zero).

Następna najprostsza gra ma tylko jedną kupkę, z tylko jedną ladą. Jeśli lewy gracz idzie pierwszy, to musi wziąć licznik, pozostawiając prawy bez ruchów ({|}, lub 0). Jeśli zamiast tego najpierw ruszy prawy, nie będzie więcej ruchów na lewy. Tak więc zarówno lewy jak i prawy może wykonać ruch do 0. Jest to pokazane jako {{|}|{|}, lub {0|0}. Pierwszy gracz, który wykona ruch, wygra. Gry równe {0|0}są bardzo ważne. Są napisane symbolem, * (gwiazda).

Pytania i odpowiedzi

P: Co to jest kombinatoryczna teoria gier?

O: Kombinatoryczna teoria gier (CGT) jest dziedziną matematyki stosowanej i informatyki teoretycznej, która bada gry kombinatoryczne i różni się od "tradycyjnej" lub "ekonomicznej" teorii gier.

P: Jakie warunki musi spełniać gra, aby można ją było uznać za grę kombinatoryczną?

O: Aby gra mogła być uznana za grę kombinatoryczną, musi mieć co najmniej dwóch graczy, musi być sekwencyjna (tzn. gracze zmieniają się na przemian), musi mieć doskonałą informację (tzn. żadna informacja nie jest ukryta), musi być deterministyczna (tzn. nie może być przypadkowa), szczęście nie może być częścią gry, musi być określona ilość możliwych ruchów, gra musi się w końcu skończyć i gra musi się skończyć, gdy jeden z graczy nie może się już poruszać.

P: Na jakich grach skupia się Kombinatoryczna Teoria Gier?

O: Kombinatoryczna teoria gier koncentruje się głównie na dwuosobowych grach skończonych, które mają zwycięzców i przegranych (tzn. nie kończą się remisem).

P: Jak przedstawia się tego typu gry?

O: Tego typu gry można przedstawić w postaci drzew, gdzie każdy wierzchołek reprezentuje grę będącą wynikiem danego ruchu z punktu znajdującego się bezpośrednio pod nim na drzewie.

P: Jakie są niektóre cele dla teoretyków CG?

O: Niektóre cele teoretyków CG to znalezienie wartości dla tego typu gier, a także zrozumienie koncepcji "dodawania gier", która polega na tym, że każdy gracz wykonuje tylko jeden ruch w dwóch różnych grach, pozostawiając drugą grę bez zmian podczas swojej tury.

P: Kto założył CGT?

O: Elwyn Berlekamp, John Conway i Richard Guy są uznawani za założycieli CGT w swojej pracy zatytułowanej Winning Ways for Your Mathematical Plays, opublikowanej w latach 60-tych.