[Math] Optimal strategy for 2 players Lights Out game variation

combinatorial-game-theorygame theorylinear algebrapuzzle

Consider a turn-based game for 2 players. They're both playing on the same board. The board is 8×8, randomly generated and each cell has 0 or 1 (with equal probabilities), for example:

01101100
01010101
10111100
00001111
10101010
00000001
11100011
00101000

In turn 1 player 1 moves, in turn 2 player 2 moves, in turn 3 player 1 moves and so on.

Move consists of choosing coordinates (x, y) where 1 is. It flips elements on positions (x, y), (x+1, y) and (x, y+1), if they are in bounds of the board. By flips I mean turns 1 to 0 or 0 to 1.

(0, 0) is top left corner. So, after playing in (1, 1) board looks like this:

01101100
00110101
11111100
00001111
10101010
00000001
11100011
00101000

And after playing in (7, 1) like this:

01101100
00110100
11111101
00001111
10101010
00000001
11100011
00101000

You win when after your move there are only 0 on board.

My question is: what is the optimal strategy for this game?

Research so far:

Lights Out description on MathWorld is worth reading.

Presented game is a variation of Lights Out, but instead of flipping 4 neighbor cells, we flip only 2 and we can move only in cells with 1. It's also similar to Nim.

In the same way like MathWorld describes we can find $S$ – a minimum set of moves to win. For 8×8 board there will be always exactly one solution.

Since matrix addition is commutative, the order in which the moves are performed is irrelevant.

If $|S|$ (minimal number of moves to win) is odd – it's a winning position. For example if it's 1 – we make only one move and we win.

If it's 3 – we make a move from $S$ and opponent gets a board with 2 moves in $S$. Now, if he makes the move from $S$, he will lose, because we will have the final move. So, if he has an option, he will not make a move from $S$.

By trying some examples I find out that opponent move not from $S$ increases our $S$ by 1 move – exactly the move he made. So, we get back the board with 3 (different) moves in $S$. But, he can't stop us like this forever – finally all his possible moves will be in $S$.

So, my hypothesis is: When you don't make a move from $S$, $|S|$ will increase exactly by 1 and his "destroying" move will be added to the set (so later we can "undo" his "destroying" move).

Which would mean that the opponent can only do -1 (by playing a move from $S$) or +1 (by not playing a move from $S$), so he can't change the parity of our $|S|$!

So, if all of above is true, it means that players have no influence on the result of the game. We could even play by random and if the initial $|S|$ was odd – we will win, if it was even – we will lose.

It's hard for me to believe in that. What will be the sense of making AI challenge on HackerRank with such a game? Players in the leader-board have different scores and these scores are consistent each time after recalculation (same people in the top 10), suggesting that players actually have an influence on the game result.

Maybe you can see some mistake I'm making?

Best Answer

Recursively color the board in white and black such that for any legal move, there is an odd number of black squares that are flipped.

In your case the coloring will look like an inverted serpinski pattern shifted diagonally : colored board

Then consider the parity of the number of $1$s on black squares. At every move you invert an odd number of black squares, so the parity changes no matter what the players do. The number of $1$s on black squares either increases by $1$ or decreases by $1$ or $3$.

In your example, there are $17$ $1$s on black squares, so player $1$ will always see an odd number of $1$s on black squares. $0$ is not odd so there will always be at least one $1$ on a black square. He can't possibly receive an empty board so he can't lose : he's forced to win.

I don't know what your website is doing. If some algorithms win more than others then either the rules are different (he never says what happens on the edges of the board) or he has an unfair way of generating random boards. Also I don't know what he does when he recalculates the scores. Maybe this is just an experiment in feeding random results to an elo scoreboard.

Related Question