Kombinatoryczna teoria gier

Kombinatoryczna teoria gier jest matematyczną teorią, że bada gry dla dwóch graczy z pojęciem pozycji , a gdzie gracze po kolei odgrywających strzał w sposób określony przez przepisy w celu osiągnięcia pewnego warunku zwycięstwa. Teoria gier kombinatorycznych koncentruje się na grach z pełną informacją, w których przypadek nie ma wpływu, takich jak szachy , warcaby lub gra w go .

Historyczny

Teoria gier kombinatorycznych powstała w związku z bezstronną teorią gier , w której ruchy dostępne z jednej pozycji są takie same dla obu graczy. Szczególnie ważną bezstronną grą jest gra nim , całkowicie rozwiązana w 1901 roku przez CL Boutona. Następnie, w 1907 roku, Willem Wythoff wynalazł i opublikował rozwiązanie do gry Wythoffa , odmianę gry Nima. W latach trzydziestych XX wieku Sprague i Grundy niezależnie udowadniają twierdzenie Sprague-Grundy'ego , które stwierdza, że ​​każda bezstronna gra jest równoważna pewnej stosie gry Nima. To twierdzenie wykazało zatem, że ważne unifikacje są możliwe, gdy gry rozpatruje się na poziomie kombinatorycznym.

Pierwsze gry partyzanckie , w których dostępne ruchy są już nie koniecznie identyczne dla dwóch graczy, wydaje się, że zostały uznane przez John Milnor w 1953 roku, ale to spotkanie Elwyn Berlekamp , John Conway i Richard Guy , który jest punktem początek pełnej teorii w latach sześćdziesiątych XX wieku.

Pierwsza książka traktująca o teorii gier partyzanckich , O liczbach i grach , została opublikowana przez Johna Conwaya w 1976 roku. W szczególności zdefiniował on liczby surrealistyczne i bardziej ogólną koncepcję gier partyzanckich . Następnie, w 1982 roku, wszystkie wyniki Berlekampa, Conwaya i Guya zostały opublikowane w ich książce Winning Ways for your Mathematical Plays , która do dziś pozostaje punktem odniesienia w tej dziedzinie.

Od 1982 roku temat ten był wówczas przedmiotem licznych publikacji. Wybrane artykuły Richarda J. Nowakowskiego zostały opublikowane w seriach książkowych Gry bez szans (1996), Więcej gier bez szans (2002) i Gry bez szans 3 (2009).

Definicja gier

Gry początkowo rozważane przez kombinatoryczną teorię gier mają następujące właściwości:

• Dwóch graczy, zwanych Lewym i Prawym , gra na przemian.
• Gra składa się z kilku, zazwyczaj w ciągu, od pozycji , a zwłaszcza stanowisko nazywa pozycji wyjściowej .
• Zasady jasno określają uderzenia, jakie zawodnik może wykonać z danej pozycji. Pozycje dostępne dla gracza nazywane są jego opcjami .
• Obaj gracze są w pełni świadomi stanu gry, czyli gra jest pełna informacji.
• Nie ma przypadkowej interwencji.
• Gra kończy się, gdy gracz nie może już grać, a zasady zapewniają, że każda gra kończy się skończoną liczbą ruchów (nazywa się to warunkiem zakończenia ).
• W normalnej konwencji gry przegrywa gracz, który nie może już grać.

Jeśli istnieją pozycje z różnymi opcjami dla dwóch graczy, mówi się, że gra jest partyjna , a jeśli dostępne opcje są zawsze takie same dla obu graczy, mówi się, że gra jest uczciwa .

Gry takie jak szachy lub warcaby nie należą do tej kategorii gier, ponieważ wiążą się z pojęciem remisu.

Rekursywna i formalna definicja gier została podana w O numerach i grach w 1976 roku: jeśli L i R są zbiorem gier, to {L | R} jest grą. L reprezentuje zestaw opcji gracza Lewy, a R zestaw opcji dla prawego gracza. Nazwy graczy biorą się z faktu, że opcje dla lewej są zapisane po lewej stronie, a opcje dla prawicy są zapisane po prawej stronie w poprzedniej notacji.

Suma gier

Suma dwóch gier G i H, oznaczona jako G + H, jest zdefiniowana jako gra, w której gracz może grać w trybie G lub H, pozostawiając drugi składnik nietknięty. Formalnie suma G + H jest zdefiniowana przez {G L + H, G + H L | G R + H, G + H R }. Głównym celem kombinatorycznej teorii gier jest zdefiniowanie metody określania, który gracz wygrywa w sumie gier, na podstawie niezależnych informacji o każdym z elementów.

Ocena gier

Niektóre gry mają określoną ocenę.

Te numery surrealistyczne są szczególnym przypadkiem gry, a wszystkie klasyczne numery, szczególnie prawdziwe i porządkowa odpowiada grze:

0={|}{\ Displaystyle {0} = \ lewo \ {| \ prawo \}} 1={0|},2={1|},3={2|}{\ Displaystyle {1} = \ lewo \ {0 | \ prawo \}, {2} = \ lewo \ {1 | \ prawo \}, {3} = \ lewo \ {2 | \ prawo \}} -1={|0},-2={|-1},-3={|-2}{\ Displaystyle {-1} = \ lewo \ {| 0 \ prawo \}, {- 2} = \ lewo \ {| -1 \ prawo \}, {- 3} = \ lewo \ {| -2 \ prawo \}} 12={0|1}{\ Displaystyle {1 \ ponad 2} = \ lewo \ {0 | 1 \ prawo \}} ω={0,1,2,3,⋯|}{\ Displaystyle \ omega = \ lewo \ {0,1,2,3, \ cdots | \ prawo \}} ω+1={ω|}{\ Displaystyle \ omega + 1 = \ lewo \ {\ omega | \ prawo \}}

Liczby surrealistyczne zawierają również nieznane wcześniej liczby, takie jak:

ω-1={0,1,2,3,⋯|ω}{\ Displaystyle \ omega -1 = \ lewo \ {0,1,2,3, \ cdots | \ omega \ prawo \}}

Ale w większości gier nie chodzi o liczby, na przykład:

* = {0 | 0} gwiazdka, która weryfikuje * + * = 0 * n = {* 0, * 1, ... * (n-1) | * 0 * 1 * ... (n-1)} nimber n x * = {x | x} = x + * dla dowolnej liczby x ↑ = {0 | *} w górę ↓ = {* | 0} dół

Jak wygrywają twoje notatki matematyczne , teoria gier kombinatorycznych wyróżnia się wieloma zaskakującymi tożsamościami, takimi jak {↑ | ↓} = * lub {0 | ↑} = ↑ + ↑ + *.

Uwagi i odniesienia

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu Wikipedii w języku angielskim zatytułowanego „  Kombinatoryczna teoria gier  ” ( zobacz listę autorów ) .

1. Richard J. Nowakowski „  Historia teorii gier kombinatorycznych  ” ( Archiwum • Wikiwix • Archive.is • Google • Co robić? ) Jan. 2009
2. Richard J. Nowakowski Gry bez szans Cambridge University Press, Cambridge, 1996.
3. Richard J. Nowakowski Więcej gier bez szans Cambridge University Press, Cambridge, 2002.
4. Richard J. Nowakowski Games of No Chance 3 Cambridge University Press, Cambridge, 2002.
5. E. Berlekamp, ​​JH Conway, R. Guy. Zwycięskie sposoby na swoje gry matematyczne. AK Peters Ltd., 2001, t. 1, 14
6. E. Berlekamp, ​​JH Conway, R. Guy. Zwycięskie sposoby na swoje gry matematyczne. AK Peters Ltd., 2001, t. 1, str.71

Zobacz też

Dodatkowa bibliografia

• (en) Michael H. Albert  (en) , Richard J. Nowakowski i David Wolfe , Lessons in Play: An Introduction to Combinatorial Game Theory , AK Peters  (en) ,2007, 304  s. ( ISBN  978-1-56881-277-9 )
• (en) Jörg Bewersdorff , Luck, Logic, and White Lies: The Mathematics of Games , AK Peters,2004, 486,  str. ( ISBN  978-1-56881-210-6 ) , str.  169-261

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">