Project CEMAPRE internal
| Title | Cyclic games |
| Participants | Alda Carvalho (Principal Investigator), João P Neto, Carlos P Santos |
| Summary | Combinatorial Game Theory (CGT) is a branch of mathematics that studies sequential games (alternated decisions) with perfect information (no hidden information, no chance devices, [1, 2, 3, 4]). In CGT, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving; that is, in all situations, the sets of options are exactly the same for both players. Regarding finite games (games without cycles), Sprague-Grundy Theory states that the values of impartial combinatorial games are nimbers (*n={0,*,...,*(n-1)|0,*,...,*(n-1)}) and the Grundy value of an impartial combinatorial game is the unique non negative integer n such that G=*n. Given an impartial game, an important mathematical goal is to present a closed formula or a polynomial time procedure fo find its Grundy value. The Sprague-Grundy theory was extended to general finite games with cycles by Cedric Smith [6] and by Aviezri Fraenkel and coauthors [6, 7]. This extension is mainly a theoretical work, not presenting non-trivial applications. In this project, we will try to analyze some non-trivial rulesets in the light of Smith-Fraenkel Theory. References: [1] J Conway. On Numbers and Games. Academic Press, 1976. [2] E. Berlekamp, J. Conway, R. Guy. Winning Ways. Academic Press, London, 1982. [3] M. Albert, R. Nowakowski, D. Wolfe. Lessons in Play: An Introduction to Combinatorial Game Theory. A. K. Peters, 2007. [4] A. N. Siegel. Combinatorial Game Theory, American Math. Soc., 2013. [5] C. A. Smith. Graphs and composite games. J. Comb. Thy., 1(1):51–81, 1966. [6] A. S. Fraenkel and U. Tassa. Strategy for a class of games with dynamic ties. Comput. Math. Appl., 1(2):237–254, 1975. [7] A. S. Fraenkel, Y. Perl. Constructions in combinatorial games with cycles. In Infinite and Finite Sets (to Paul Erdõs on his 60th birthday), Volume 2, ed. A. Hajnal, R. Rado, and V. Sos, pages 667-699. North-Holland, 1975. |