Talk:Morpion solitaire

From Rosetta Code

Rules, References, How it works

The wikipedia page doesn't exist - where else can the exact rules be seen? The task says "A move is made by adding one point to the end of a line of 4 and drawing a straight line through the 5 points." But the in the given example RosinA the move number 2 is the middle point of a diagonal line (not the end). So obviously diagonal lines are allowed, but what means then "drawing a straight line through the 5 points"? Also, the description says that "lines cannot overlap existing lines" which contradicts this --Abu 13:48, 7 June 2011 (UTC)

The WP page does exist, the link was just spelled wrong. The rules are pretty clear there. Looks like it takes practice to get it. --Mwn3d 13:52, 7 June 2011 (UTC)
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.) MagiMaster 21:15, 7 June 2011 (UTC)
Presumably that means that we cannot have a line of more than five. 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. -- 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? Markhobley 21:05, 18 July 2011 (UTC)
Well, they can be reused when lines cross. -- Gerard Schildberger 05:56, 16 May 2012 (UTC)
Are these legal or not legal?:
X   X      X   X     XXXXX       X
X   X      XXXXX      XXXXX      XX
XXXXX      X   X                XXXXX
X   X      XXXXX                 XX
X   X      X   X                 XX
                                  X

(Presumably they are impossible to form and none are legal. Is that right?)

Markhobley 07:44, 19 July 2011 (UTC)

"Drawing a straight line" simply marks the line just completed so it's easier to see what happened. Each node is allowed to be shared by multiple lines, if the lines are all oriented at different directions. If two lines are aligned, apparently there are two different rules: the "T" (touching) rule says two colinear lines are allowed to share one end point only; the "D" (disjoint) rule says colinear lines can't share nodes at all. The following:

AAAACBBBB

is allowed by the T rule, where AAAAC and CBBBB are two legal lines; by D rule, only one of them is legal (whichever came first). On the other hand, 

XXXXXOOOOO

are considered two legal lines by both rules. I'm unsure what happens if you put a piece at the blank in 

XXX_XXX

--whether the whole thing is considered as one oversized line, or only 5 or them would be considered used... Then again, the whole thing is pretty bogus in that it's NP-hard so no "proper" solution exists, it's not much fun to play, and it's not much fun to watch, so there. --Ledrug 08:40, 19 July 2011 (UTC)

I found some rules: http://www.morpionsolitaire.com/English/Rules.htm :) Markhobley 11:02, 19 July 2011 (UTC)
Sorry for not posting this sooner, but the idea was to get the computer to play it, probably randomly, or by some simple heuristic. Dealing with all the intricacies of the rules is not an insignificant programming challenge. Trying to find the best solution is beyond this task. MagiMaster 14:11, 20 July 2011 (UTC)
It is not stated in the rules that I found, but I reckon that you must score at least one line of five for each turn of play. (In other words you cannot place marks just anywhere on the grid, you have make a line of five.) If you cannot make a move that creates a line of five, then the game is over. Additionally, marks can be crossed out from the direction that they make the line of 5 in, but can be used from other directions. So 5 in a row vertically, are crossed out vertically, but the marks can still be used to form horizontal or diagonal lines, which then also become crossed out. (I have been playing a version of this on paper for couple of days.) Markhobley 16:56, 20 July 2011 (UTC)

I was looking at this. It looks to me that the following are valid: 

YES (touching, 5T):
+++.-
++.+-
+.++-
-+++.

YES (non-touching, 5T&D):
++++.
+++.+
++.++

Where:
+ = any X not part of a line running in the same direction being contemplated
- = an X used in a line running in the same direction
. = an empty position in the grid we can use to make a new line

These cases eliminate duplicates (reversed patterns). Everything else is not valid. --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. --Dgamey 00:51, 23 January 2012 (UTC)

It would be possible to move the tasks into a subpage and use mediawiki trickery (i.e. template magic) to make the contents appear in the page anyway. I'm not planning to do anything about rearranging yet; while there's only one solution, there's no need to act… –Donal Fellows 09:33, 23 January 2012 (UTC)
Hi Donal, I know there are some plans/considerations underway to restructure RC with SML but not sure where they are. I think there may have been something about putting all solutions in their own pages, auto sorting within the task, etc. Not sure where that is. It would be very cool if the page could expand the solutions you select. In the meantime if solutions for this start showing up then something probably should be done. Any idea if there is a policy/guideline on what size of solution should be sub-paged off? I recall the current C solution is 225 lines. --Dgamey 12:06, 23 January 2012 (UTC)
We tried this, and it's something I'd very much love to see become the norm. Ran into a SMW bug involving transclusions that's still not fixed upstream. Had to do with templates. People are absolutely welcome to experiment in getting this kind of thing working again. You won't kill the server. :) --Michael Mol 14:20, 23 January 2012 (UTC)
Also, no explicit policy/guidelines regarding solution sizes. (that I remember) It comes down to what's reasonable for a page, which is different for every page. --Michael Mol 14:20, 23 January 2012 (UTC)
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. --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…) –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. –Donal Fellows 15:58, 17 February 2012 (UTC)

Consolidated References

I'm still looking for references or discussion about human player strategies.

consolidated references --Dgamey 13:48, 13 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. There is a defacto standard which is used for downloadable games found on the Morpionsolitare.com records page]. These games can be replayed on the Pentasol player.

The advantage of using this system of output is that the Pentasol player will validate the game and provide an image of the result.

The notation looks like this: 

#
#     XXXX
#     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
#
(12,8)
(11,14) - +2
(12,4) | +2
(9,12) | -2
(18,7) | +2
(14,11) - +2
...

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. --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. --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. --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. --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)
Retrieved from "https://rosettacode.org/wiki/Talk:Morpion_solitaire?oldid=187674"