Strategy for board game 2

567 Views Asked by At

In this question the following was asked:

Alice and Bob are playing the following game: They have a $4 \times 4$ empty grid and take turns coloring one square each, starting with Alice, both using the same color. Whoever completes any $2 \times 2$ area on the grid (after having made their move) is the loser. Is there any winning strategy for any of the two players?

The answer was that Bob had a winning strategy (see link). It was also determined that for an $n \times n$ grid, where $n$ is odd, Alice has a winning strategy. However, it was not determined who has a winning strategy when $n$ is even with $n \gt 4$.

Can someone spot such a strategy?

Edit

To avoid repeats of answers previously given, here are two strategies for Bob which don't work:

  1. Bob's winning strategy for $n=4$

    If Alice colors $(i,j)$, Bob colors $(1+(i+m-1) \mod n, \ j)$, where $n=2m$. Won't work for $n \gt 4$ as Alice can color e.g. $(1,1)$, $(1,2)$, $(n,1)$, $(n,2)$.

  2. Bob mirror's Alice's move

    If Alice colors $(i,j)$, Bob colors $(n+1-i, n+1-j)$. Won't work as Alice can color two adjacent central squares.

In fact, I think Alice might have a winning strategy. I simulated $10,000$ games on a $6 \times 6$ grid where each player made random "legal" moves, i.e. moves which don't immediately result in a loss, and Alice consistently wins $56 \text {%}$ of the time.

1

There are 1 best solutions below

0
On

Simulating random games tells nothing about whether or not a winning strategy exists. However, as the maximum number of moves before the game ends results in Bob losing (a maximum of 27 out of the 36 squares can be colored without coloring in any 2x2 square). As a result, as long as Alice can force the game to go the maximum number of moves, she wins.