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
(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?