Mathematics – Combinatorics
Scientific paper
2009-08-30
Mathematics
Combinatorics
16 pages, 7 figures
Scientific paper
Sprouts is a two-player topological game, invented in 1967 by Michael Paterson and John Conway. The game starts with p spots, lasts at most 3p-1 moves, and the player who makes the last move wins. In the misere version of Sprouts, on the contrary, the player who makes the last move loses. Sprouts is a very intricate game, and the first computer analysis in 1991 reached only p=11. New results were made possible in 2007 up to p=32 by using combinatorial game theory: when a position is a sum of independant games, it is possible to replace some of these games by a natural number, called the nimber, without changing the winning or losing outcome of the complete position. However, this reduction does not apply to the misere version, making the analysis of Sprouts (and more generally of any game) more difficult in the misere version. In 1991, only p=9 was reached in misere Sprouts, and we describe in this paper how we obtained up to p=17. First, we describe a theoretical tool, the reduced canonical tree, which plays a role similar to the nimber in the normal version. Then, we describe the way we have implemented it in our program, and detail the results it allowed us to obtain on misere Sprouts.
Lemoine Julien
Viennot Simon
No associations
LandOfFree
Analysis of misere Sprouts game with reduced canonical trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Analysis of misere Sprouts game with reduced canonical trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of misere Sprouts game with reduced canonical trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-622047