7
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ You have not shown that the game terminates. It may be that the player who would lose can keep it going indefinitely. Otherwise, it is a deterministic perfect information game, so the concept of N(ext) and P(revious) positions applies. $\endgroup$ – Ross Millikan Jun 18 '15 at 14:26
  • $\begingroup$ @RossMillikan I drew all the 16 states (with 32 edges) for the 2x2 game and there are no cycles (I can post it if it helps). I hope this is enough to say that the game always terminates. I also have a strong feeling that it always terminates, because 1 always go in down-right direction, they can't go back. And I can't craft a looping example. I'm not sure if I know the concept you mentioned, do you maybe have a link, so I can read up about it? Thank you. $\endgroup$ – Adam Stelmaszczyk Jun 18 '15 at 14:37
  • 1
    $\begingroup$ I had not noticed that the two other squares flipped were not in line. Yes, you can argue that the 1's have to sweep down the board and the game must terminate. The basic theorem here is the Sprague-Grundy theorem, which says that in a finite impartial game with no draws, each position is either won for the Previous player or by the Next player. An N position is one that can move to at least one P position. A P position is one that can only move to N positions. $\endgroup$ – Ross Millikan Jun 18 '15 at 14:46
  • $\begingroup$ @RossMillikan This is the full game graph for 2x2. Yes, that theorem definitely holds here, the states drawn in rectangles in my picture are the winning states. The number above the state is the minimum number of moves to win. Arrows point from 1 in which we are moving to the next state. However I still don't see the optimal strategy. And expanding full tree from 8x8 board is too huge, even for computer (2^64, around 10^19 states). $\endgroup$ – Adam Stelmaszczyk Jun 18 '15 at 14:55
  • 1
    $\begingroup$ I think for each square, the parity of the number of times you can do a move in it only depends on the state of the board to its up/left and not on the moves you do, so the parity of the total number of possible moves doesn't depend on the moves that are played. So in a game with 2 players, neither player has any influence on who wins. $\endgroup$ – mercio Jun 18 '15 at 18:36
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry, I don't understand the first sentence - how should I color the board. Could you please provide a simple example on i.e. 3x3 board or a picture? $\endgroup$ – Adam Stelmaszczyk Jun 18 '15 at 20:15
  • $\begingroup$ I added a picture. $\endgroup$ – mercio Jun 19 '15 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.