Project CEMAPRE internal
| Title | On Generalizations of Sprague-Grundy Theory |
| Participants | Alda Carvalho (Principal Investigator) |
| Summary | "Combinatorial impartial games are the subject of the well-known Sprague-Grundy Theory [1,2,3]. To simplify, considering games in finite digraphs with no cycles and no carry-on moves, where pieces do not conflict, the theory is easily applied: one begins by identifying the terminal nodes (G-value=0), and then, using a backward algorithm, applies the Mex Rule until obtaining the G-values of all nodes. If the digraph, although finite and without carry-on moves, has cycles, the Smith-Sprague-Grundy Theory applies [4]. One begins by identifying the terminal nodes (G-value=0), and then, using a backward algorithm, applies the Mex Rule together with reversibility until it is no longer possible to do more. At that point, the unfilled nodes are in a cyclic zone and should be marked with infinity(C), where C is a set of reachable nimbers (C may be empty). If the digraph, although finite and without cycles, admits carry-on moves, the LNS-Sprague-Grundy Theory applies [5]. In a graph with carry-on moves, there are green nodes that should not be associated with any Grundy value. Whenever a piece is moved to one of these nodes by a player, the opponent has to play that piece in the next move. One begins by identifying the terminal nodes (G-value=0), and then, using a backward algorithm, applies the Mex Rule to I union P (immediate nimbers and protected nimbers) until obtaining the G-values of all nodes that are not green. The aim of this project consists of understanding what the most comprehensive generalization of the Sprague-Grundy Theory is. In particular, is it possible to achieve a generalization that simultaneously encompasses all the cases mentioned in the previous paragraphs? [1] Bouton, C. «Nim, a game with a complete mathematical theory», The Annals of Mathematics, 3(2), 35-39, Princeton, 1902. [2] Grundy, P. «Mathematics and games», Eureka, 2, 6-8, Cambridge University, 1939. [3] Sprague, R. «Über mathematische Kampfspiele», Tohoku Mathematical Journal, 41, 438-444, Tohoku University, 1935. [4] Smith, C. «Graphs and composite games», Journal of Combinatorial Theory, Series A, 1, 51-81, 1966. [5] Larsson, U., Nowakowski, R., Santos, C. «Impartial games with entailing moves», Integers: The Electronic Journal of Combinatorial Number Theory, 21B, #A17, 2021. " |