Majominoes (new abstract game)

(view this message with a monospace font)

Last night during a caffeine-induced insomnia, I came up with a new abstract pencil & paper game for two players that I thought was interesting. I call it 'Majominoes', a combination of 'majority' and 'polyominoes'. What follows is a description of the rules, and then some questions.

I've cross-posted this since I think both groups would have an interest in it.

Since draw is impossible and the game is deterministic, either X or O can force a win. Note also that the order that the X's and O's are placed make no difference for the final score. Assume O can force a win. This means that any move X makes is followed by a move by O such that the final result gives a higher score to O. Furthermore, the placement of O's pieces is determined only by the position of the already placed pieces (by X and O). X can now do the following: Place the first piece anywhere on the board, then wait for O to make her move. Now, X ignores his first piece and plays as if O started. He will always respond to O's move by pretending O started and the first X piece isn't there, unless this is the place that perfect play suggests. In this case, he just places randomly and ignores this new piece in the same way he previously ignored the first. Since the assumption was that the second player can win regardless of what the first player does, it doesn't matter that O has fewer choices than if she played first, X can always find a perfect response. In the end, X can make the board look like O started except that O can't place her final stone since it is occupied by X on his last move. Hence, the board will be the reverse of the board where O started except for one piece being swapped in X's favour. Since that can't possibly hurt X's score, he wins. Since we concluded that X wins from the assumption that O wins, the assumption was incorrect and, hence, X is guaranteed to win.

Yes. Assume a 3x3 board where the regions coincide with the rows. No matter where X places, O can place in the same column in the two other rows. If X later places in one of the two rows that already has an O, O does the same, winning this. Hence, O will definitely win two rows and one column (taken in her first move). Since rows are also regions, that gives her 5 regions. The total number of regions is 9, so she has more than half.

I suspect the double move will actually allow O to win on all boards for N>=3, essentially by using it in her first move and hence turning it into a game similar to the one in question 1 with her as first player (and, hence, a winner in a perfect game). I can't quite factor the two initial plays out of the proof, though, so I may be wrong.

If my assumption above is correct, she can always win by using it in her first move, so there would be no advantage in waiting (if all we care about is win/lose and not maximizing scores).

Offhand, I'd say X, but I haven't done an exhaustive search.

I believe Torben is right in stating that this make the game a win for O. A modification of the rules (which may or may not drastically alter the game strategies) could be to allow X a double move after O has made hers. This could be made a general rule - at any time, the player in turn may mark two cells, if she has currently fewer marked cells than her opponent.

Looking forward to trying it in real life.

Note that a deterministic game with no draw possible will always be a certain win for one side, assuming perfect play. At best, variants of Majominoes may be wins for different sides depending on initial setup (board size, shape of regions etc.).

But this need not make it a bad game, as long as perfect play is hard to do, both for humans and computers (unlike tic-tac-toe or Nim).

On a 5x5 board, the search space is small enough that a computer can play perfectly, but I doubt this would be the case on a 9x9 board or bigger. 7x7 will probably be O.K. as well.

That sounded like a good idea to me at first glance. But then I figured that what would probably happen is that each player would always take two moves (except for X's first move, where it's prohibited). This means that X would end up with the extra cell on the board. So not only would X go first but she'd always get the extra cell.

and, Torben Ægidius Mogensen mentioned this:

Yes, that's exactly right. There was a thread here (I think it was here) a few years ago about Trax being the perfect game because (under perfect play) it was not a win for either player, and had no draw. The only remaining possibility I could see was that the game never ended.

My motivation was to find a new pencil-and-paper game that I could play with an 11 year old. The rules had to be simple but I wanted to have some depth of strategy.

It's poosible that this game doesn't have any obvious strategy until close to the end game. Similar, in that regard, to Hexbo (do you know that game), which looks like a really clever but which, to me anyway, the first gazillion moves seem like they may as well be made at random (which may just mean I'm too stupid to understand the game).

It might make a nice little puzzle applet, where a 5x5 board is presented, and you know you have a win, but you have to find it.

With such a rule, O would postpone her double move until her last move, thus ensuring herself the extra cell.

I believe 5-in-a-row (gomuku, renji, ...) on an unbounded board has a similar property - games can go on for very long and it may well be that it will be infinite with perfect play on both sides. Since it is never a disadvantage to have an extra mark, the only possibilities are forced first-player win and infinite play (which can be classified as a kind of draw).

For that, it would probably be fine. The aforementioned 5-in-a-row is fine for that also.

I don't know that game, but I have seen games like that (with no obvious strategy until the endgame).

True. You could let the applet do exhaustive search but start second (without the double-move rule), so the player can always win with perfect play.

An alternative to the double-move rule is a rule whereby the second player can choose to swap sides at some point during the game. This, obviously, shouldn't be near the end of the game when the outcome is obvious. Also, he might be required to declare the switch one turn before it is made, so the first player can make one more move before the switch happens.

This still doesn't change the fact that the game is a preordained certain win for one of the players (assuming perfect play), but it makes it harder to find the perfect strategy.

See http://www1.ics.uci.edu/~eppstein/cgt/gomoku.html for 5-in-a-row on a 15x15 board being a first player win (infinite boards not mentioned) and http://home.hia.no/~jkhaug00/Neutreeko.doc for a simple game where in certain positions the next player has a forced, but very remote win :->

<Snip>

In a Hex variant I posted some time ago, the players alternate making double moves but the two stones cannot be adjacent. I exhaustively examined boards up to 6x6 I believe, and one or the other player had a win (of course) but I could see no pattern. I called the game Scorpio due to the tactical

This, I am afraid, will make the game a win for X. In the games I have played so far, the last moves are in general not important - one times I have given away the last 4 squares on a 5*5.

So tempo is key. I'd like to make the observation that the usual proof of a win for Black (first mover) breaks down if White is given a double-move at the end. This is also true for Hex. (For example, consider a trivial 1x3 'majority wins' game