8
Morpion solitaire
This is a game that I remember having learnt from my grandparents in my childhood. Initially I didn't know the name. G B has found it to be Join Five (or less ambiguously - Morpion solitaire) with a slightly different starting position.
NOTE: it seems that it's kinda known and this problem formulation has quite good solutions already (http://www.morpionsolitaire.com/English/RecordsGrids5T.htm). I don't know what to do with this thread now honestly.
Description
The game is played by a single player on a 2-dimensional infinite grid. The grid at the start contains some dots in a cross shape:
A player can create either a horizontal, vertical, or a diagonal (or anti-diagonal) line with the following rules:
- The line must be straight and aligned on the grid.
- The line must span exactly 5 grid points (2 on the ends, 3 in the middle).
- All 5 grid points that the line intersects must have dots on them.
- The new line cannot overlap with an already existing line. But they can intersect and the ends can touch. (ie. intersection of any two lines must not be a line)
- A single dot may be put by the player at any grid point before the line is placed. If the player does so then the line must pass through that point.
A move can be described by a grid point position (cartesian coordinates) and a direction (a number between 0 and 7. 0 - north, 1 - north east, 2 - east, and so on). So 3 numbers. The origin choice is arbitrary, but I suggest using this coordinate system: (An example of sample input at the end)
At the start there is 28 possible moves (12 horizontal, 12 vertical, 2 diagonal, 2 antidiagonal).
An example move:
An example state after 16 moves:
I don't know whether there exists an infinite sequence of valid moves from the start position, but I assume not based on a lot of playing and simulations. Any proofs regarding upper bounds are appreciated.
Challenge
The challenge is to find the longest possible sequence of valid moves (for a verifier look at the end). The score is the number of moves in that sequence. Higher score is better.
Tips, help, and resources
A 24x24 board was enough for my random simulations, 32x32 board may be enough for anything possible.
I faintly remember getting scores close to 100 by hand years ago. After billions of random playouts (move uniformly chosen) the best result was 100 consecutive moves:
1 -1 2
1 2 2
1 6 0
-3 5 2
-2 5 0
-5 1 3
-2 -4 2
1 3 1
-5 -1 2
-5 0 1
-5 2 0
0 5 1
-2 0 0
1 -2 3
3 2 0
1 -1 0
-5 2 2
-5 -2 3
-3 3 0
4 3 0
-3 2 3
0 -4 3
-2 0 1
-3 -1 1
-3 -2 2
-1 -3 3
2 2 0
-3 0 1
1 2 1
1 -2 2
1 -5 3
-2 -3 2
1 -4 3
-1 0 0
-3 -2 3
5 2 0
-3 2 1
2 1 2
0 -1 0
0 -1 3
0 0 2
0 1 1
-4 0 2
-6 -2 3
-2 2 1
-2 1 2
0 2 1
-1 5 0
-4 6 1
-3 -3 3
-4 -2 3
-4 2 0
-6 1 2
0 3 0
-7 -2 2
-6 0 1
0 3 2
-7 -2 3
-4 3 2
-6 2 0
-6 1 3
-3 4 2
-3 6 1
1 5 1
-2 2 3
-3 7 0
2 6 0
-1 2 3
-7 3 1
2 5 1
3 6 0
-4 5 1
-3 7 1
-4 6 0
-6 2 3
-6 4 1
-7 3 3
-6 6 1
0 2 3
-6 6 2
-5 6 0
-7 4 2
1 6 2
-7 4 1
-8 3 2
-6 3 3
-6 6 0
-9 2 3
-7 5 2
-7 6 1
-7 6 0
1 2 3
-9 2 2
-9 4 1
1 5 2
1 1 3
4 7 0
1 4 2
5 6 0
1 7 1
Num moves: 100
Board:
o o
|/|\
o-o-o-o-o
/|/|/|X|X \
o o-o-o-o-o o o
/ X|/|X|/|\ \ X
o-o-o-o-o-o-o-o-o-o-o-o-o
\|\|X|X X|X|/|X|X|X|X X|
o o-o-o-o-o o o-o-o-o-o
|X|X|X|X|X|X|X X|X|X|X|
o o o-o-o-o-o-o-o-o-o o
|/|X|X|X X X|X X|X|X| |
o-o-o-o-o-o-o-o-o-o-o-o-o
/|X|X|X|X|X|X|X X|X|/|X|/
o-o-o-o-o-o-o-o-o o o-o-o-o-o
\ /|/|X|X|X|X|X|X|X|X|X|X|/|
o-o-o-o-o-o-o-o-o-o-o-o-o o
/ \|X|X|X|X|X|X|X X|X|X|X|/|
o o-o-o-o-o-o-o-o-o-o-o-o-o
|\|X|X|X|X|X|X X|X|X|X|\|
o-o-o-o-o-o-o-o-o-o-o-o-o
|/|X|\|X|X / \|\|X|\|\|
o o-o-o-o-o o-o-o-o-o
\|X / |
o o o o
Can you beat that?
C++17 helpful codes (hosted, because they don't fit in an answer, each on godbolt and coliru, you can use them however you like).:
clean, reference code, handles board, move generation, random playouts:
http://coliru.stacked-crooked.com/a/1de13a65522db030 https://godbolt.org/z/zrpfyU
optimized and parallelized version of the above (also prints move sequences), also with a verifier that takes moves from stdin:
http://coliru.stacked-crooked.com/a/b991b7c14aaf385e https://godbolt.org/z/vFwHUe
edit. an even more optimized version, about twice as fast:
place where you can put input to be verified:
example input:
10 # number of moves
-6 2 2 # x, y, direction (0-7)
1 6 0
0 2 2
1 -1 0
1 -1 2
-5 1 3
4 2 0
-5 2 0
-3 -1 1
-2 5 2
Sopel
Posted 2019-12-05T21:06:59.150
Reputation: 291
4
Any proofs regarding upper bounds are appreciated.There exists no sequence of valid moves that can grow the outer boundary of the grid (that is, no infinite moves). You need 4 moves all into empty space in order to create a new 5th valid move, which must be strictly non-parallel to all of the previous 4. This new 5th move cannot generate any moves parallel to the first four, due to both being strictly non-parallel and the no-overlap rule. – Draco18s no longer trusts SE – 2019-12-05T21:35:07.997@Draco18s I'm not sure I believe your last sentence "This new 5th move cannot generate any moves parallel to the first four, due to both being strictly non-parallel and the no-overlap rule." If I am not misunderstanding either the question or your comment, but isn't this a counter example to your claim?
– Post Rock Garf Hunter – 2019-12-06T05:43:54.6433A simpler proof of the finiteness in my opinion is the following: Each point can have up to four lines passing through it, (horizontal, vertical and two diagonal), we can call this line slots. Drawing a line consumes one slot on 4 dots for a total of 4 slots and produces a dot which already has one of it's slots occupied. Therefore every line reduces the total number of slots left by at least 1. When there are less than 3 slots left no further lines can be drawn. This gives an upper bound of 141 moves. – Post Rock Garf Hunter – 2019-12-06T05:49:29.780
@WheatWizard The lines must be of length 4. The length of a line is defined by the grid, not by how many dots it spans. – Sopel – 2019-12-06T09:47:37.897
3@WheatWizard A point can be part of up to eight lines, if it is an endpoint for all of them. So assign 8 slots to each point, of which an inner line point uses two. A line with a new point which is an endpoint uses 7 slots and creates 7 new slots. A line with a new point that is an inner point uses 6 slots and creates 6 new ones. That's really tight! – Christian Sievers – 2019-12-06T13:45:06.393
1@Sopel So how long is a diagonal line that passes through 5 total points (two end points and 3 intermediaries)? If it is "four" then the line is defined by how many dots its spanned. If it is "5.657" then it isn't length four and your own example image is wrong (and drawing a line of exactly length 4 would be impossible). – Draco18s no longer trusts SE – 2019-12-06T14:19:10.110
@Draco18s I found the rules unclear and wanted to add some condition ("if ... is allowed"), but then I saw that the 100 moves example from OP has such lines. – Christian Sievers – 2019-12-06T14:19:54.660
@ChristianSievers Re-reading the rule again, you are correct. It is, however, confusing. – Draco18s no longer trusts SE – 2019-12-06T14:23:08.050
@WheatWizard Draw a 4x4 grid of filled dots. Add four lines per Sopel's rules that create four new, colinear points outside the original 4x4 space. These four new points are create a new valid move. This new valid move can never be parallel to the first four lines. It does not matter how you arrange the initial dots and draw your first four lines such that their new points create a 5th move that uses no original dots, that 5th line cannot be parallel to all of the first four lines (you could get it to be parallel with 2, but such an arrangement does not extend the volume; it is interior). – Draco18s no longer trusts SE – 2019-12-06T14:26:30.153
4You might want to rewrite "The line is always of length 4 (2 end points and 3 in the middle)." in a much clearer way, I took this to mean, "The line is always of length 4, which means ...", when it seems to be "The line is always of length 4, and ...". Length 4 is also a confusing concept because under normal assumptions of length our diagonal lines are length $4\sqrt{2}$ (maybe this issue is why I looked to the parentheses for clarification). It also might be worth specifically mentioning that parallel lines can intersect at their endpoints. – Post Rock Garf Hunter – 2019-12-06T14:41:47.083
I clarified it, thanks. Ad. the second part. There is already "But they can intersect and have a common point.", but I'll clarify it more. – Sopel – 2019-12-06T17:07:48.447
Ad. closing vote. I don't see how it is different from, say, https://codegolf.stackexchange.com/questions/53310/shortest-universal-maze-exit-string.
– Sopel – 2019-12-06T18:12:04.7931
The game is Join Five also known as the Morpion Solitaire. It's been studied a lot, the current best is 178 moves.
– G B – 2019-12-10T10:45:54.810@GB yes that looks like it! The start position is different but the rules match. I have to ask my grandparents when they first encountered it because 1970 is not very old. – Sopel – 2019-12-10T11:16:40.417
Actually, I could probably make it into a different kind of challenge, with varying initial boards if this doesn't gain traction, seeing that the version with the filled cross apparently has upper bounds proven. – Sopel – 2019-12-10T11:25:56.793
1
According to http://martindemaine.org/papers/Morpion_TheoryComputSys/paper.pdf the upper bound is 141 moves for the version without allowing touching lines. That matches exactly the simple explanation by @WheatWizard ! But the version with allowing touching lines (the one here) has a much higher upper bound proven there - 704.
– Sopel – 2019-12-10T11:30:54.487Best known is 170, or maybe even higher. So this thread may not be very interesting... – Sopel – 2019-12-10T11:40:02.327
Best known for 5T is 178, for 5D (the variant in this question) is 82 – G B – 2019-12-10T11:42:39.300
the variant in this question explicitly allows touching lines – Sopel – 2019-12-10T11:43:25.230
You are right, sorry. I looked at the picture and I got it wrong. – G B – 2019-12-10T16:22:05.020