# What's the optimal score in the MU-game?

Mary and Ursula play a game by alternately writing letters into a $9\times9$ grid. In every move, the player picks an empty square and then writes her initial letter (M or U) into it.

• Mary has the first move.
• The game ends once all squares have been filled.
• When the game has ended, $N(M)$ is the number of rows and columns that contain more Ms than Us, while $N(U)$ is the number of rows and columns that contain more Us than Ms.
• When the game has ended, Mary receives $N(M)-N(U)$ Euros from Ursula.

Question: How much money will Mary receive from (respectively, lose to) Ursula?
(As usual, we assume that Mary and Ursula both use optimal strategies.)

• I've written an interactive version of this game, available here. Comes pre-built with AIs implementing Frodo's strategy for Mary, my strategy for Ursula, and a "pick at random" strategy for either player. I would have done Rob's too, but it's rather trickier to implement. Feb 27 '15 at 18:55

I don't know if this is optimal play for Mary (though I suspect it is), but she can guarantee winning 2 Euros if she initially plays at (5,5) and copies Ursula's moves by translation through (5,5). Rows 1-4,6-9 and columns 1-4,6-9 will be evenly split by the pair, row 5 and column 5 will belong to Mary because of the centre square.

• I haven't thought it all the way through, but I think Ursula can use a similar strategy to minimize her losses. She initially chooses a spot at random and on subsequent turns copies Mary's moves by translation through it. If the translation would go out of bounds, she treats the board as though it wraps around like a Pac Man stage. If the translation would lead to an occupied space, she picks a spot at random, although her "pivot" coordinate remains the same. Feb 26 '15 at 21:22
• @Kevin Won't work if Mary starts as described in the answer and then continues to mirror Ursula (as also described in this answer)? Feb 27 '15 at 0:46
• @Nit, if by "won't work", you mean "Ursula will lose money", that's true, but her losses are minimized to no more than two Euros (against Frodo's or any other strategy that I've tried). If by "won't work" you mean "you will sometimes be unable to choose a new spot to take, even though some are still available", I don't think so - the "pick a spot at random" fallback ought to cover that. Feb 27 '15 at 18:58
• @Kevin What I meant is that if Mary plays as described here, Ursula will have to pick a random slot on every turn. Feb 28 '15 at 9:47
• Maybe we're using different definitions of "translate". Suppose Mary chooses (5,5) and Ursula randomly chooses (4,5). Then Mary chooses (6,5), and Ursula non-randomly chooses (2,5). Feb 28 '15 at 13:53

Mary will win 2 Euros if both of them play optimally. Frodoskywalker has given a strategy that Mary can use to accomplish this.

Here's why this will happen:

Mary will write down 41 M's, and Ursula will write down 40 U's. By Frodoskywalker's strategy, we know Mary can win at least 2 Euros from Ursula, so Ursula will try to limit it to 2 Euros. Taking out Mary's extra letter (in the center), let's consider the rows and columns of the board in terms of $N(M)-N(U)$. For a checkerboard pattern, we get this:

   1 -1  1 -1  0 -1  1 -1  1
1 M  U  M  U  M  U  M  U  M
-1 U  M  U  M  U  M  U  M  U
1 M  U  M  U  M  U  M  U  M
-1 U  M  U  M  U  M  U  M  U
0 M  U  M  U  _  U  M  U  M
-1 U  M  U  M  U  M  U  M  U
1 M  U  M  U  M  U  M  U  M
-1 U  M  U  M  U  M  U  M  U
1 M  U  M  U  M  U  M  U  M


As you can see, the column numbers and the row numbers each balance out. With some slight changes:

   1 -3  1  1  0 -1  1 -1  1
1 U  U  M  M  M  U  M  U  M
-1 M  U  U  M  U  M  U  M  U
1 M  U  M  U  M  U  M  U  M
-1 U  M  U  M  U  M  U  M  U
0 M  U  M  U  _  U  M  U  M
-1 U  M  U  M  U  M  U  M  U
1 M  U  M  U  M  U  M  U  M
-1 U  M  U  M  U  M  U  M  U
1 M  U  M  U  M  U  M  U  M


Here Mary would win an extra 2 Euros, but you can see that the columns numbers and row numbers still sum to zero. The key to this is noticing that in the second column is extra unbalanced in Ursula's favor, leaving her fewer letters to counter Mary. With this information we can come up with a strategy for Ursula that allows her to limit Mary to 2 Euros.

When it is Ursula's turn, there will be an even number of empty squares left and she will have a choice between at least two squares. The column and row differences will each sum to 1. If possible, she will write her letter in square for which she and Mary are tied in the row and column. If that's not possible, her next option will be to write it in a square for which she and Mary are tied for the row or column and she is behind by 1 in the other. Failing that, she should choose a square for which she is behind by 1 for both the row and column. In each of these cases, after her move she will either gain a row and/or a column or tie it up in a row and/or a column.

Towards the end of the game Ursula will eventually be restricted in her options, but by then Mary will be equally restricted. For example, if the last two squares are in the same row, then even if Ursula is ahead by 1 in that row she can choose the square according to which column is better knowing that Mary will be forced to bring the score back to 1 for that row.

Proof that this strategy works will come in a little bit...

• "Proof that this strategy works will come in a little bit..." Do consider posting the proof, if possible. Jul 7 at 19:05