| Presentation | 2013-06-24 Morpion Solitaire 5D : a new upper bound 121 of the maximum score Akitoshi KAWAMURA, Takuma OKAMOTO, Yuichi TATSU, Yushi UNO, Masahide YAMATO, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Morpion Solitaire is a pencil-and-paper game for a single player, popular in several countries including France. A move in this game consists of putting a cross at a lattice point and then drawing a line segment that passes through exactly five consecutive crosses. The objective is to make as many moves as possible, starting from a standard initial configuration of crosses. For one of the variants of this game, called 5D, we prove the upper bound 121 on the number of moves. This is done by introducing line-based analysis, and improves on the known upper bound 138 obtained by potential-based analysis. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | pencil-and-paper game / lattice points / line-based analysis |
| Paper # | COMP2013-19 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2013/6/17(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Morpion Solitaire 5D : a new upper bound 121 of the maximum score |
| Sub Title (in English) | |
| Keyword(1) | pencil-and-paper game |
| Keyword(2) | lattice points |
| Keyword(3) | line-based analysis |
| 1st Author's Name | Akitoshi KAWAMURA |
| 1st Author's Affiliation | Department of Computer Science, University of Tokyo() |
| 2nd Author's Name | Takuma OKAMOTO |
| 2nd Author's Affiliation | Graduate School of Science, Osaka Prefecture University |
| 3rd Author's Name | Yuichi TATSU |
| 3rd Author's Affiliation | Graduate School of Science, Osaka Prefecture University |
| 4th Author's Name | Yushi UNO |
| 4th Author's Affiliation | Graduate School of Science, Osaka Prefecture University |
| 5th Author's Name | Masahide YAMATO |
| 5th Author's Affiliation | Graduate School of Science, Osaka Prefecture University |
| Date | 2013-06-24 |
| Paper # | COMP2013-19 |
| Volume (vol) | vol.113 |
| Number (no) | 108 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |