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$
6
  • 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
4
$\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$
2
  • $\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
0
$\begingroup$

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.

$\endgroup$

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.