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 you make the last move. In other words, you win when after your move there are only 0 on the board.
This game is a variation of Lights Out Puzzle, but instead of flipping 4 neighbor cells, we flip only 2. It's also a bit similar to Nim.
My question is: what is the optimal strategy for this game?
What I've been thinking of so far:
It's important to notice that since matrix addition is commutative, it follows that the order in which the moves are performed is irrelevant.
In the same way like for the original game described on MathWorld, we can find a minimum set of moves to clear the board.
If that number is odd - great. For example if it's 1 - we make that one move and we win.
If it's 3 - we make a move from minimum set and opponent gets a board with 2 moves till the end. Now, if he makes the move from minimal set, he will lose, because we will have the final move. So, if he has an option, he will not make a move from the minimal set.
By trying simple examples I find out that such a move increases the set of minimal moves by 1 move - exactly the move he made. So, we get back the board with 3 moves in the minimal set.
So, my hypothesis is: When you don't make a move from a minimal set of moves, the size of this set 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 following the minimum set) or +1 (by not following), so he can't change the parity of our number!
And this strikes me. Because if that hypothesis is true that means that the player have zero influence on the result of the game. He could even play by random and if the initial number of minimum moves was odd - he will win, if it was even - he will lose. No matter what players do. That will be silly game, I can't believe that. But I can't find a counterexample for that so far.
I really hope that hypothesis is untrue. Maybe you can spot some mistake I'm making or have an counterexample?