Talk:Morpion solitaire

From Rosetta Code
Revision as of 01:54, 13 February 2012 by rosettacode>Dgamey (Addition to task)

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)
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)
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)

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)

Musings

The thing with a task like this is it has the potential to get distracting. Just producing a random game doesn't give much insight into what's going on. The task is already moderately involved and going beyond what's asked would be more so. I was looking for references to human strategies for the game but all I seem to come up with is computer strategies. That suggests to me there aren't a lot of people playing it by hand. --Dgamey 12:06, 23 January 2012 (UTC)

Other References

  • On August 12, 2011 Chris Rosin achieved 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.
  • 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.
  • Sheffield Paths Wiki which has some good references
  • Koozdra blog which discusses some approaches to heuristics

I've noted very few references or discussion about human player strategies. --Dgamey 22:00, 4 February 2012 (UTC)

More references

--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. I created one herebefore I found notations used with the Pentasol player. Downloadable text versions of record games can be found on the Morpionsolitare.com records page]. The notation looks like this: 

# Morpion Solitaire game
(28,28)
(27,25) - +2
(32,32) / 0
(30,28) - +2
(28,35) | -2
(30,33) / 0
...

The above is taken from [Rosin's 1st 177 move game]. The first line references the final position of the north-west valley. Each line is a set of coordinates followed by a direction and a distance. I haven't found an explanation of the final integer; however, they appear to be 0,1,2 indicating where the center of the line is relative to the move (center=0, top/left end=+2, etc.). Also the order of coordinates here is (column, row) the reverse of what I used. --Dgamey 12:18, 9 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.

Retrieved from "https://rosettacode.org/wiki/Talk:Morpion_solitaire?oldid=187662"