Optimal strategy for 2 players Lights Out game variation

Question

Consider a turn-based game for 2 players. They're both playing on the same board. The board is 8x8, 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 8x8 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?

Answer 1

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 :

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.

Answer 2

let's take a simple 1x3 board

101

This is a loss for player 1.

But the loss is faster if the cell on the left is chosen first.

Since there is a move limit, the losing play can squeeze out a draw by stalling as much as possible.

The winning player, when possible needs to make a move that can't be undone.

Let's try a simple board where player 1 wins.

1011

player 1 can take out the right 2, which forces the game to 5 moves. player 1 can take left for

0111

player 2 then can't take left or right, which lets player 1 win on move 3.

instead, player 2 will take the middle, which recreates the same situation as if player 1 had started with the right.

So now we have the strategy.

1. solve the board as quickly as possible. making required moves that can't be undone, working from upper left to lower right. Count the number of moves it took. This is very easy. You simply sweep from upper left to lower right, clicking each 1. This will reveal all the currently required moves, and is an optimal solution always.

2. If ODD, you are winner. Try to find a move that can't be tagged back (there is always at least one) that doesn't overlap any required cells, but does overlap as many unrequired cells that are 1 as possible, to deny them to your opponent on their turn. Say you are starting on a full 3x3 board. upper left is the ideal move because it permanently removes the corner 1, and knocks out two non required moves next to it so they can't be selected by the opponent. Prefer permanent unlights of non required cells, but always pick one that cannot relight. Therefore, you will never directly lengthen the game.

3. if EVEN, you are loser, and must avoid those required moves if you can. instead, pick a NOT required move that unlights 2 required moves if possible, and if not, unlights one 1. If only required cells ae currently available, then try to pick the one that is closest to the bottom right. If you are starting with the 3x3 board with the bottom right cell already taken, then picking one of the two unrequired next to the start is a good move, because it tags two required cells, but is not a required move itself. the upper left move is still required, and it will tag your cell you picked again, making it a new required cell. Hopefully if you keep doing this, you will extend the game past the 100 move mark and salvage a draw. You may get a chance to force extra clicks on required cells too. take these if you find them.

And here we go. :)

if you were playing alone, the order would not matter for the required moves. but since you are competing, the important thing to do is permanently remove as many chances for the opponent to extend the game as you can.