Morpion Solitaire

January 8, 2012 11:19 AM

Morpion Solitaire is a very simple pencil-and-paper, line-drawing game for which the best possible score is not known! New records are still being set.
posted by Wolfdog (21 comments total)

Oooooh.. this is great.
posted by odinsdream at 11:26 AM on January 8

This is neat! I'm very tempted to try and solve this using SAT...
posted by spiderskull at 11:47 AM on January 8

Rules clarification. If I put two lines head-to-head such that they share exactly one point (but both lie on the same straight line), are they overlapping or only touching?
posted by Jonathan Livengood at 12:28 PM on January 8

Touching, not disjoint.
posted by fleacircus at 12:37 PM on January 8

I will play this as soon as I am done saying "Morpion" over and over again.

I wish I had something to name right now, because I would totally call it Morpion.
posted by louche mustachio at 12:38 PM on January 8 [1 favorite]

English-speaking readers should know that morpion is the usual French name of Pediculosis pubis (the origin page is a little bit shy about this).
posted by elgilito at 12:50 PM on January 8 [1 favorite]

The most thrilling satisfaction for all mankind
Better than everything you ever imagined in your wildest dreams
The secret of... Morpion Solitaire.
posted by fleacircus at 12:56 PM on January 8

BRB...
posted by Splunge at 1:09 PM on January 8

Neat!
posted by cortex at 1:36 PM on January 8

In order to safe some trees and octopuses there is a software-section hidden in the links (see bottom of left frame) with software off- and online-versions (mostly misstated as Java instead of JavaScript), like this. And of course, there are apps for that...
posted by KMB at 2:27 PM on January 8 [2 favorites]

The existence of things like this that I hadn't previous heard of makes me miss Martin Gardner and his Mathematical Games column tremendously.
posted by JHarris at 3:17 PM on January 8 [1 favorite]

After five attempts, my best was 66. I look forward to using this to occupy myself in next semester's classes.
posted by LSK at 3:31 PM on January 8

I find it interesting that the record-setting solutions like the one in the second link are so... ugly. It's not an elegant symmetrical web of beauty, it's just a jumble that happens to be the best thing anyone knows.
posted by Wolfdog at 3:41 PM on January 8

The record-setting games remind me strangely (poignantly?) of maps of Paris.
posted by threeants at 3:53 PM on January 8

Well, yes, the browser version is very nice, but now do you play the game with it? Clicking doesn't seem to do anything. How do you draw an X? How do you draw a line? Pant, pant, ready to play...
posted by exphysicist345 at 5:51 PM on January 8

On the browser version above, I can just touch the grid to make a new + on my iPad. It records your moves and lets you undo. Cool.
posted by webhund at 6:22 PM on January 8

it is proved that this game is NP-hard and the highest score is inapproximable

I can't easily find a clear definition of that last word, but it seems to be that not only is the optimum solution NP-hard, but so are "arbitrarily close" nearly-optimal ones. Or, in other words, if you come up with some polynomial time algorithm for getting a high-score, UR DOIN IT RONG.
posted by DU at 6:23 PM on January 8

What's the "N" in algorithm? Number of x's that could be played off? Like in the travelling salesman problem, N is the number of cities, and so forth.
posted by RustyBrooks at 7:43 PM on January 8

I'm really surprised there isn't more symmetry to these. There's gotta be some math behind this. Meanwhile, back on the plane I operate on, this is very cool, thanks!
posted by From Bklyn at 4:01 AM on January 9

RustyBrooks: From digging around on the site I found the following:

Theorem 2. For any k ≥ 3, it is NP-hard to find the longest play from a pattern of n dots, or even to find a play of length within n^(1-ε) of the longest play, for any constant ε > 0. This result holds for both variants of the game.

In their paper, k is the number of segments in a line (joining k+1 dots). And n is the number of dots in the initial pattern. Both variants are Touching and Disjoint.

(DU, this is also what they mean by inapproximable)
posted by DRMacIver at 4:49 AM on January 9

66 on the first go. I'm excited to try again if my lecture tonight gets boring.
posted by robstercraw at 1:44 PM on January 9