Anonymous user
Talk:Morpion solitaire: Difference between revisions
m
no edit summary
mNo edit summary |
|||
| (13 intermediate revisions by 4 users not shown) | |||
Line 5:
:Ah. Yeah, it's fine to add a point anywhere that creates a line of 5. When it says lines cannot overlap, I think a better way of putting it might be that lines can't share more than one point. (They can cross at one point, but can't overlap pieces of the line itself.) [[User:MagiMaster|MagiMaster]] 21:15, 7 June 2011 (UTC)
::Presumably that means that we cannot have a line of more than five. [[User:Markhobley|Markhobley]] 21:05, 18 July 2011 (UTC)
::: That's not what I presummed (with a '''T''' game). A line of '''xxxxbxxxx''' where '''b''' is a blank --- when the next move is placed at the '''b''', you have a line of nine. -- [[User:Gerard Schildberger|Gerard Schildberger]] 05:56, 16 May 2012 (UTC)
:Can we drop "and drawing a line through them" from the task description (or is that some sort of crossing out or deletion?). In other words do we keep the line of 5 Xs? or do we delete them (by changing them to dots), or do we need change them to Os (representing a crossing out) to prevent them from being reused? [[User:Markhobley|Markhobley]] 21:05, 18 July 2011 (UTC)
:: Well, they can be reused when lines cross. -- [[User:Gerard Schildberger|Gerard Schildberger]] 05:56, 16 May 2012 (UTC)
:Are these legal or not legal?:
Line 46 ⟶ 50:
. = an empty position in the grid we can use to make a new line</pre>
These cases eliminate duplicates (reversed patterns). Everything else is not valid. --[[User:Dgamey|Dgamey]] 14:58, 12 January 2012 (UTC)
==Multiple lines==
Suppose a newly marked grid creates more than one line. How much does this score? How many new marks are permitted? Until specified, I'd say the programmer should freely choose and state which rule the code follows. I choose that only one line scores and the game continues in the simple fashion with only a next turn. In some cases it seems that a new mark would create a contiguous line of 5 on one of the alternate paths. --LambertDW 00:45, 24 June 2014 (UTC)
== Solution Sizes / Sub-pages ==
I looked into this a bit more and think that many of the solutions will be on the longish side and should have their own sub-pages (e.g. [[Morpion_solitaire/C]]) like tasks such as [[Go_Fish]]. --[[User:Dgamey|Dgamey]] 00:51, 23 January 2012 (UTC)
Line 54 ⟶ 62:
::::I say if you think it might be too long, just put it on its own page. I usually move them off if they approach 10 KB or so (maybe a little less than that...7 or 8?). You can see how big an edit is on the recent changes feed. Then just make sure you name the solution page well--something like [[Task name/Language]] or [[Task name/Language/Language subheading]]. --[[User:Mwn3d|Mwn3d]] 14:48, 23 January 2012 (UTC)
::::: I'd put it down to how large the overall page is as the threshold to start doing things. There definitely are some pages that ought to have some attention. OTOH, I don't think this page has got to that point. Well, not yet. I vote for YAGNI on elaborate stuff (well, at least until the point when we ''do'' need it) since simple pages have the benefit of being known to work. I don't know exactly what the threshold should be though; the old 32kB point where MW moans at us is probably a bit low, since next to nobody seriously uses old IE any more due to the hardware it was on finally being junked. (IIRC, IE7 and up aren't nearly as brain-damaged…) –[[User:Dkf|Donal Fellows]] 22:19, 23 January 2012 (UTC)
:::::: Further to this, see [[Arithmetic/Rational#Tcl]] for an example of how to do the inclusion once pages start getting split up. –[[User:Dkf|Donal Fellows]] 15:58, 17 February 2012 (UTC)
==
* [[wp:Morpion Wikipedia]]
* On August 12, 2011 Chris Rosin achieved [http://www.morpionsolitaire.com/English/RecordsGrids5T.htm 178 moves]. Unfortunately this graphic of the game requires the a bit more effort on the part of the reader to work out any ambiguities.
* [http://www.chrisrosin.com/morpion/index.html previous 177 move record] also by Chris Rosin. This graphic includes 'stops' that disambiguate lines when there are multiple choices in one direction, its also sans background grid.
* [http://paths.sheffield.ac.uk/wikiana/wiki/Morpion_solitaire Sheffield Paths Wiki] which has some good references▼
* [http://koozdra.wordpress.com/2011/05/21/morpion-dna-encoding/ Koozdra blog] which discusses some approaches to heuristics▼
I've noted very few references or discussion about human player strategies. --[[User:Dgamey|Dgamey]] 22:00, 4 February 2012 (UTC)▼
* [http://www.chrisrosin.com/rosin-ijcai11.pdf Rosin's paper on NPRA (Nested Rollout Policy Adaption for Monte Carlo search algorithm] this describes some heuristics as well as the search and other good references.
* [http://www.lamsade.dauphine.fr/~cazenave/ Tristan Cazenave's articles] Earlier search algorthims
* [http://www.ipgp.fr/~sibilla/divers/pmorpion_solitaire01.html Jean-Jacques Sibilla's page and best reported random game of 102 moves (french)].
* New Heuristics for Morpion Solitaire, 2007 by Hyyro and Poranen
* Morpion Solitare, 2006 by Demaine, Demaine, Langerman, and Langerman gives bounds of 170 <= 5T <= 704
* Le Morpion Solitare, 2003 by Flammenkamp claims 5T <= 324
▲* [http://paths.sheffield.ac.uk/wikiana/wiki/Morpion_solitaire Sheffield Paths Wiki] which has some good references
▲* [http://koozdra.wordpress.com/2011/05/21/morpion-dna-encoding/ Koozdra blog] which discusses some approaches to heuristics
▲I'
--[[User:Dgamey|Dgamey]] 01:48, 9 February 2012 (UTC)▼
== Game Notation ==
While working on this I realized it might be handy to be able to replay games and a game notation would be needed.
The advantage of using this system of output is that the Pentasol player will validate the game and provide an image of the result.
(28,28)▼
(27,25) - +2▼
The notation looks like this:
(32,32) / 0▼
<pre>
(30,28) - +2▼
#
(28,35) | -2▼
# XXXX
(30,33) / 0▼
# X X
# X X
# XXXR XXXX
# X X
# X X
# XXXX XXXX
# X X
# X X
# XXXX
#
# R = reference point
# List of moves starts with reference point (col,row) i.e. (12,8) below
#
# Annotations:
# Lines are
# (col,row) <direction> <center>
# direction - +
# | up down
# - left right
# \ left right
# / left right
# center is the distance -2, -1, ..., +2 from
# the move coordinate to the center of the line being drawn
#
...</pre>
While I was unable to find a detailed description of the format, what I worked out is in the annotated comments above. Comment lines are preceded by hashes. The first line references the final position of the north-west valley of the starting cross. Each line is a set of coordinates of the move followed by a direction and an offset to the center of the line created by the move. The table in the comment above tells you how to figure out where the start of the line is. All coordinates use (column, row) order. --[[User:Dgamey|Dgamey]] 13:41, 13 February 2012 (UTC)
== Proposed Addition to the task definition ==
* Tasks really need to have some form of comparable output. Drawings of games are often missing information and difficult to validate. I'm going to suggest that each task should output the game in the notation that is used by the Pentasol player. It seems to be accepted as a defacto standard for morpion and the images it produces are better than ascii art. I'd suggest that people could use the output of one of their random games played through pentasol to illustrate their example.
* Alternately, they should produce some kind of output like ASCII art. Keep in mind that an image using a single character for all moves will be an undecipherable blob. Adding numbers for the moves will require handling of two digit numbers making the art larger. And lastly, even if you can see each move in order, there is the problem of deciphering up to 5 possible ambiguous moves at a point. --[[User:Dgamey|Dgamey]] 13:43, 17 February 2012 (UTC)
== Tips and Tricks ==
* The initial two solutions work with expandable boards. While nice it's not needed. You'll never get near the world record grids so a fixed grid of say 30x30 would be more than large enough. If you're worried about changing it later, you could pick an offset so the cross is always constructed from a fixed reference point say 0,0 or 1,1 depending on your language. --[[User:Dgamey|Dgamey]] 12:38, 22 February 2012 (UTC)
* Playing morpion smartly or exploring the problem space isn't a trivial task and will require lots of effort, code and complexity. Playing a random game is fairly straight forward. The core code for the original two solutions comes in at about 200 lines each. --[[User:Dgamey|Dgamey]] 12:38, 22 February 2012 (UTC)
== Thoughts for Long Games ==
* Maximizing the number of possible moves seems like an obvious game solver strategy. How about instead maximizing the area? The initial grid makes me think low density is sufficient to have many possible moves. --LambertDW 19:39, 5 July 2014 (UTC)
| |||