Kombinatorická teorie her

Kombinatorické teorie her je matematická teorie, která studuje dva hráče her s konceptem polohy , a kde hráči se střídají hrát na snímek způsobem, definovaným pravidlům, aby bylo dosaženo určité podmínky vítězství. Teorie kombinatorických her se zaměřuje na úplné informační hry, kde nezasahuje náhoda, jako jsou šachy , dáma nebo hra go .

Historický

Kombinatorická teorie her vznikla v souvislosti s nestrannou teorií her , kde jsou tahy dostupné z jedné pozice pro oba hráče stejné. Obzvláště důležitou nestrannou hrou je hra nim , kterou v roce 1901 zcela vyřešil CL Bouton. Poté, v roce 1907, Willem Wythoff vynalezl a publikoval řešení Wythoffovy hry , variaci Nimovy hry. Ve třicátých letech 20. století pak Sprague a Grundy nezávisle prokázali teorém Sprague-Grundy , který uvádí, že jakákoli nestranná hra je ekvivalentní určité hromadě Nimovy hry. Tato věta tak ukázala, že jsou možná důležitá unifikace, když jsou hry zvažovány na kombinatorické úrovni.

První partyzánské hry , ve kterých jsou k dispozici pohybuje již nejsou nutně identické pro dva hráče, zdá se, že byly považovány za Johnem Milnor v roce 1953, ale to je setkání Elwyn Berlekamp , John Conway a Richard Guy , který je bod začátek úplné teorie v 60. letech.

První kniha zabývající se teorií partyzánských her , O číslech a hrách , byla vydána Johnem Conwayem v roce 1976. Významně definoval surrealistická čísla a obecnější koncept partyzánských her . Poté, v roce 1982, byly všechny výsledky Berlekampa, Conwaye a Guye publikovány ve své knize Winning Ways for your Mathematical Plays , která dodnes zůstává v této oblasti odkazem.

Od roku 1982 byl předmět poté předmětem mnoha publikací. Výběr článků Richarda J. Nowakowského byl publikován v edicích knih Hry bez šance (1996), Více her bez šance (2002) a Hry bez šance 3 (2009).

Definice her

Hry původně zvažované kombinační teorií her mají následující vlastnosti:

Hrají střídavě dva hráči, kteří se nazývají Levý a Pravý .
Hra se skládá z počtu pozic , obvykle přes , a konkrétní pozice se nazývá počáteční pozice .
Pravidla jasně určují tahy, které může hráč z dané pozice provést. Pozice přístupné hráči se nazývají jeho možnosti .
Oba hráči si plně uvědomují stav hry, to znamená, že ve hře jsou úplné informace.
Neexistuje žádný náhodný zásah.
Hra končí, když hráč již nemůže hrát, a pravidla zajišťují, že každá hra končí konečným počtem tahů (tomu se říká podmínka ukončení ).
V běžné herní konvenci je hráč, který již nemůže hrát, poražený.

Pokud existují pozice s různými možnostmi pro dva hráče, hra je považována za partyzánskou , a pokud jsou dostupné možnosti vždy stejné pro oba hráče, hra je považována za spravedlivou .

Hry jako šachy nebo dáma do této kategorie her nepatří, protože zahrnují pojem remízy.

Rekurzivní a formální definice her byla uvedena v On Numbers and Games v roce 1976: pokud L a R jsou každá sada her, pak {L | R} je hra. L představuje sadu možností hráče Left a R sadu možností pro Správného hráče. Jména hráčů vycházejí ze skutečnosti, že možnosti Left jsou psány vlevo a možnosti Right jsou psány vpravo v předchozí notaci.

Součet her

Součet dvou her G a H, označených jako G + H, je definován jako hra, kde může hráč hrát buď v G, nebo v H, přičemž ostatní komponenty zůstanou nedotčené. Formálně je součet G + H definován {G L + H, G + H L | G R + H, G + H R }. Hlavním cílem kombinatorické teorie her je definovat metodu pro určení, který hráč vyhraje součet her, z nezávislých informací o každé ze složek.

Hodnocení her

Některé hry mají zvláštní hodnocení.

Tyto surrealistické čísla jsou zvláštním případem hry a všechny klasické čísla, zejména skutečný a pořadové odpovídají ke hře:

{0} = \ vlevo \ {| \ vpravo \}

{1} = \ left \ {0 | \ right \}, {2} = \ left \ {1 | \ right \}, {3} = \ left \ {2 | \ right \}

{-1} = \ left \ {| 0 \ right \}, {- 2} = \ left \ {| -1 \ right \}, {- 3} = \ left \ {| -2 \ right \}

{1 \ nad 2} = \ vlevo \ {0 | 1 \ vpravo \}

\ omega = \ vlevo \ {0,1,2,3, \ cdots | \ vpravo \}

\ omega + 1 = \ left \ {\ omega | \ right \}

Surrealistická čísla také obsahují dříve neznámá čísla, například:

\ omega -1 = \ vlevo \ {0,1,2,3, \ cdots | \ omega \ vpravo \}

Ale většina her není o číslech, jako například:

* = {0 | 0} hvězdička, která ověří * + * = 0 * n = {* 0, * 1, ... * (n-1) | * 0, * 1, ... * (n-1)} hnízdo n x * = {x | x} = x + * pro libovolné číslo x ↑ = {0 | *} nahoru ↓ = {* | 0} dolů

Jak poznamenává Winning Ways pro vaše Mathematical Plays , kombinatorická teorie her je pozoruhodná mnoha překvapivými identitami, například {↑ | ↓} = * nebo {0 | ↑} = ↑ + ↑ + *.

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z anglického článku Wikipedie s názvem „ Kombinatorická teorie her “ ( viz seznam autorů ) .

Richard J. Nowakowski „ Historie teorie kombinatorických her “ ( archiv • Wikiwix • Archive.is • Google • co dělat? ) Jan. 2009
Richard J. Nowakowski Hry bez šance Cambridge University Press, Cambridge, 1996.
Richard J. Nowakowski Další hry bez šance Cambridge University Press, Cambridge, 2002.
Richard J. Nowakowski Hry bez šance 3 Cambridge University Press, Cambridge, 2002.
E. Berlekamp, JH Conway, R. Guy. Vítězné způsoby pro vaše matematické hry. AK Peters Ltd., 2001, roč. 1, s. 14
E. Berlekamp, JH Conway, R. Guy. Vítězné způsoby pro vaše matematické hry. AK Peters Ltd., 2001, roč. 1, s. 71

Podívejte se také

Další bibliografie

(en) Michael H. Albert (en) , Richard J. Nowakowski a 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 s. ( ISBN 978-1-56881-210-6 ) , str. 169-261