Morpion Solitaire
January 8, 2012 11:19 AM Subscribe
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.
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, 2012
posted by Jonathan Livengood at 12:28 PM on January 8, 2012
Touching, not disjoint.
posted by fleacircus at 12:37 PM on January 8, 2012
posted by fleacircus at 12:37 PM on January 8, 2012
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, 2012 [1 favorite]
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, 2012 [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, 2012 [2 favorites]
posted by elgilito at 12:50 PM on January 8, 2012 [2 favorites]
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, 2012
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, 2012
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, 2012 [2 favorites]
posted by KMB at 2:27 PM on January 8, 2012 [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, 2012 [1 favorite]
posted by JHarris at 3:17 PM on January 8, 2012 [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, 2012
posted by LSK at 3:31 PM on January 8, 2012
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, 2012
posted by Wolfdog at 3:41 PM on January 8, 2012
The record-setting games remind me strangely (poignantly?) of maps of Paris.
posted by threeants at 3:53 PM on January 8, 2012
posted by threeants at 3:53 PM on January 8, 2012
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, 2012
posted by exphysicist345 at 5:51 PM on January 8, 2012
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, 2012
posted by webhund at 6:22 PM on January 8, 2012
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, 2012
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, 2012
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, 2012
posted by RustyBrooks at 7:43 PM on January 8, 2012
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, 2012
posted by From Bklyn at 4:01 AM on January 9, 2012
RustyBrooks: From digging around on the site I found the following:
posted by DRMacIver at 4:49 AM on January 9, 2012
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.(DU, this is also what they mean by inapproximable)
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.
posted by DRMacIver at 4:49 AM on January 9, 2012
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, 2012
posted by robstercraw at 1:44 PM on January 9, 2012
« Older Gone Silent. | It's Been Done Before, A Seven Nation Army... Newer »
This thread has been archived and is closed to new comments
posted by spiderskull at 11:47 AM on January 8, 2012