- Morpion solitaire
-
Morpion solitaire is a one-player paper-and-pencil game. References to the game first appeared in French publications in the 1970s.[1] In addition to being played recreationally, the game has been the subject of theoretical studies[2] and computer searches for solutions.[3]
Contents
Rules
Starting configuration with 36 points marked
The game is played on a square grid, assumed to be of unlimited size. The starting configuration has a set of 36 points marked on the grid in the form of a Greek cross. Each turn, the player makes a legal move by marking one additional point to create a new line of 5 marked points in a row. The line cannot overlap any previous line. The goal is to create as many new lines as possible before reaching a final configuration in which no further legal moves are available.
Variations
The rules may be varied by requiring lines of 4 marked points in a row rather than 5, with a reduced starting configuration. Also, the "disjoint" variation of the game does not allow two parallel lines to share an endpoint, whereas the standard "touching" version does allow this.[4]
Records and computer searches
For the "touching" version of the game with lines consisting of 5 marked points, the present record of 172 lines was established on 2010 August 16, using a Monte-Carlo search by algorithmist Christopher Rosin.[5][6] This is six moves more than the previous 1976 record of 170 lines.[3][5][7] The 1976 record was done by hand, and computer searches have not been able to approach this record[7] despite substantial progress,[8] until August 2010 when Christopher Rosin used a Monte-Carlo search to obtain a result of 172 moves, exceeding the 1976 record.[6]
For the "disjoint" version of the game with lines consisting of 5 marked points, the record of 80 lines[9] has been obtained by computer search.[10]
Theory
Generalized Morpion solitaire, in which the starting configuration may be any finite set of marked points, is a member of the NP-hard class of problems for which no efficient computational method for finding an optimal solution is known. Even the problem of finding an approximately optimal solution for generalized Morpion solitaire is NP-hard.[2]
For the standard versions of Morpion solitaire, there do not exist infinitely large solutions; upper bounds have been proven.[2] on the maximum number of lines that can be obtained.[11]
References
- ^ Christian Boyer, "Morpion Solitaire – Origin (and references therein)", accessed August 8, 2010.
- ^ a b c E. D. Demaine et al. (2006). "Morpion Solitaire", Theory of Computing Systems 39:3 pp. 439–453.
- ^ a b T. Cazenave, "Reflexive Monte-Carlo Search", Computer Games Workshop 2007.
- ^ Christian Boyer, "Morpion Solitaire – Rules of the Game", accessed August 8, 2010.
- ^ a b Christian Boyer, "Morpion Solitaire – Records Grids (5T game)", accessed January 28, 2011.
- ^ a b Chris Rosin, "A new Morpion Solitaire record via Monte-Carlo search", accessed January 28, 2011.
- ^ a b Christian Boyer, "Morpion Solitaire – List of the site's news added February 15th 2010", accessed August 8, 2010.
- ^ H. Hyyrö and T. Poranen (2007). "New Heuristics for Morpion Solitaire".
- ^ Christian Boyer, "Morpion Solitaire – Records Grids (5D game)", accessed August 8, 2010.
- ^ T. Cazenave, "Nested Monte-Carlo Search", IJCAI 2009, pp. 456–461.
- ^ Christian Boyer, "Morpion Solitaire – Score Limits", accessed August 8, 2010.
External links
Categories:- Paper-and-pencil games
Wikimedia Foundation. 2010.
