Úvod do teorie kombinatorických her

Literatura a online zdroje na webu

Na této stránce je stále doplňován seznam zdrojů k dalšímu studiu. Seznam zdrojů se dotýká především J. H. Conwayovy Teorie kombinatorických her. Naši pozornost soustřeďujeme na deterministické NP-úplné hry dvou hráčů, s úplnou informací (oba hráči mají všechny informace o stavu hry), bez náhod. Znamená to, že žádný hráč nemá informaci, dotýkající se hry, kterou by druhý hráč neznal. Příklady takových her se berou z reality, studují se hry Mlýn, Go, Šachy, Halma, Dáma a další (viz také lokální seznam her, příklady deskových her). Hry typu Poker, Ruleta,... se tedy zde nestudují. Hráči se střídají ve svých tazích a uplatňují svůj postup, který vede ke konci hry. Zvláštní pozornost je věnováno v tradiční teorii místo hře Go, Hex, Mosty, Tic-Tac-Toe. To jsou totiž v anglosasských zemích tak populární hry, jako naše školní hry Lodě a moře, nebo Piškvorky.

Axiomatická výstavba teorie takových her nevede jen k analýze postavení, strategie hry, ale vede jako vedlejší produkt ke konstrukci čísel, velkých i nekonečně malých. Čísla jsou speciálními hrami. Některé hry sice čísly nejsou, ale chovají se (mají podobné vlastnosti) jako čísla: např. nimbers, sumbers. Všechny studované hry je možné si představit v teorii grafů jako orientované lesy, kde stromy mají i nekonečně mnoho listů. Stromečkem je označován orientovaný strom, kde kořen je dole, vlevo nahoru se kreslí možnosti (tahy) levého hráče, a pod. pro pravého; orientace grafu se tím pádem vynechává.

[ONAG] J. H. Conway: On Numbers and Games, Academic Press, 1976, ISBN 0-12-186350-6, (Über Zahlen und Spiele, Vieweg, Braunschweig, 1983, ISBN 3528084340), 2ed. 2001, ISBN 1-56881-127-6 (několik stránek v němčině online, obsah německy)

[WW01-04] E. R. Berlekamp, J. H. Conway, R. K. Guy: Winning Ways for your Mathematical Plays; Gewinnen, Vieweg, 1985, ISBN 3528085312, ISBN 3528085320, ISBN 3528085339, ISBN 3528085347); (Winning Ways, Academic Press, 1982, ISBN 0-12-091101-9, ISBN 0-12-091102-7); 2ed. vol. 1-4 , A. K. Peters Ltd., 2001-2004, ISBN 1-56881-130-6, ISBN 1-56881-142-X, ISBN 1-56881-143-8, ISBN 1-56881-144-6, (book review , několik stránek online)

[OGAN] J. Cihlář, V. Vopravil: Hry a čísla (On Games and Numbers), Ústí nad Labem, 125 str., 1983, 1995, ISBN 8070441046

[Book96] John H. Conway, Richard K. Guy: The Book of Numbers, Springer-Verlag New York, 330 p., 1996, ISBN 0-387-97993-X

[Knu78] Donald E. Knuth: Surreal Numbers; How two ex-students turned on to pure mathematics and found total happiness (Reading, Massachusetts: Addison-Wesley, 1974), vi+119 pp. ISBN 0-201-03812-9, Illustrated by Jill C. Knuth; (hints) (errata) Czech translation by Helena Nešetřilová, Nadreálná čísla, in Pokroky Matematiky, Fyziky a Astronomie 23 (1978), 66--76, 130--139, 187--196, 246--261.

[Kvant79] A. Kirilov, I. Klumova, A. Sosinskij: Syurrealnye chisla, in Kvant 11 (1979) (v ruštině online)

[AMS] Combinatorial Games (online)

[Ber] Elwyn Berlekamp: Combinatorial Game Theory, several papers, (online)

[Beck08] József Beck: Tic-Tac-Toe Theory, Cambridge University Press, Cambridge, 2008

[Bew03] Jörg Bewersdorff: Glück, Logik und Bluff: Mathematik im Spiel: Methoden, Ergebnisse und Grenzen, 3. Auflage, Wiesbaden 2003 (Vieweg-Verlag), 363+xiv Seiten, ISBN 3-528-26997-9 (Preface, contents and index of the English edition ) (Luck, Logic and White Lies - The Mathematics of Games, AK Peters, 2004, ISBN 1568812108, 486 pages)

[Bib07] Aviezri S. Fraenkel: Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction, The Electronics Journals of Combinatorics 14, 70 p., 2007 (online , online , update local 2009 )

[Bibl] Aviezri S. Fraenkel: Bibliography of Combinatorial Games: Updated, 475-535 (online )

[Brit00] Brit C. A. Milvang-Jensen: Combinatorial Games, Theory and Applications, 98 p., 2000 (online )

[Mat08] Jiří Matoušek, Jaroslav Nešetřil: An Invitation To Discrete Mathematics, 2nd Edition, 461 p., Oxford University Press, 2008, ISBN 978-0-19-857043-1

[CGsite] R. J. Nowakowski: CG Site, (online)

[CGSuite] A. Siegel: A Java based toolkit for evaluating games

[CGT08] Dierk Schleicher, Michael Stoll: An Introduction to Conway's Games and Numbers, 2008 (online )

[Gale74] Gale, D.: A Curious Nim-Type Game. American Mathematical Monthly 81, No. 8, 1974, pp. 876 - 879. (online local )

[Ton1.5] Claus Tondering: Surreal Numbers (online)

[Daw34] Thomas Dawson, Fairy Chess Supplement, The Problemist: British Chess Problem Society 2 (1934), no. 9, p. 94, Problem No. 1603.

[Cuts01] Richard Dedekind: Essays on the Theory of Numbers, transl. W. W. Beman, 1901 (online local )

[Dede01] Stanley Burris: What are numbers, and what is their meaning?: Dedekind, notes, 2001 (online local )

[Epp] David Eppstein: Combinatorial Game Theory (seznam odkazů online)

[Grun39] Patrick Michael Grundy: Mathematics and games, Eureka 2 (1939) 6-8, reprinted in Eureka 27 (1964) 9-11. (online)

[GT.net] Resources for Learning and Teaching Strategy for Business and Life (online)

[Guy96] Richard K. Guy: Unsolved Problems in Combinatorial Games, Games of No Chance, MSRI Publications. Volume 29, 1996. (online )

[Guy08] Richard K. Guy, Richard J. Nowakowski: Unsolved Problems in Combinatorial Games, 2008. (online )

[Hann59] Olof Hanner: Mean play of sums of positional games Pacific Journal of Mathematics, 9 (1959), S. 81-99 (online)

[IEGS] Integers: Electronic Journal of Combinatorial Number Theory (online oddíl 'Games Articles')

[JeffE] Jeff Erickson: Mathematical Games, Toys, and Puzzles (online)

[Kenn03] Kenneth Rosen ed., Discrete Mathematics and Its Applications, 5th Edition, McGraw Hill Publishing Co., 2003

[LiP07] Michael Albert, Richard Nowakowski, David Wolfe: Lessons in Play: An Introduction to Combinatorial Game Theory, A. K. Peters Ltd., 304 p., 2007, ISBN 978-1-56881-277-9

[Mil53] J. Milnor: Sums of positional games, in Annals of Math. Study, Kuhn and Tucker, eds., Princenton, 1953, pp. 291-301.

[NIM02] Charles L. Bouton: Nim, A Game with a Complete Mathematical Theory, The Annals of Mathematics, 2nd Ser., Vol. 3, No. 1/4. (1901 - 1902), pp. 35-39. (online local )

[NIM10] E. H. Moore, A generalization ofthe game called nim, Annals of Mathematics 11 (1910), 93–4

[Now96] Richard J. Nowakowski (ed.): Games of No Chance, Cambridge University Press, 1996 (online) (online local)

[Now03] R. J. Nowakowski (ed.): More Games of No Chance, Cambridge University Press, 2003 (online toc)

[Now09] Michael Albert, Richard Nowakowski (ed.): Games of No Chance 3, Cambridge University Press, 2009 (toc , toc online, online)

[Sch] Mathematical Games (sbírka matematických her online)

[Spr36] Roland Percival Sprague: Über mathematische Kampfspiele, Tôhoku Math. J., 41 (1935-1936), pp. 438-444 (R. Sprague: On mathematical war-games, anglický překlad online )

[Sten07] B. von Stengel: Game theory, LSE University of London, 2007 (toc )

[Vop12] V. Vopravil: Donald Knuth: Nadreálná čísla čtená podruhé, notes, 2012 (online local )

[Vop92] V. Vopravil, J. Porkert: Hry a strategie, Rozhledy matematicko-fyzikální, ročník 70/1992

[Wyt07] W. A. Wythoff: A modifcation of the game of Nim, Nieuw Arch. Wisk. 7 (1907), 199–202 (online local )

[Zar05] Calgero G. Zarba: Naive Set Theory, Theoretical Foundations of Computer Science, 2005 (online local )

[Zarf] List of Interactive Games on the Web

nahoru