19
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ This belongs on the Puzzles stack exchange... not here. $\endgroup$ Aug 17, 2018 at 21:39
  • 3
    $\begingroup$ This seems to fall under the "combinatorial game theory" tag. $\endgroup$
    – Jens
    Aug 17, 2018 at 21:49
  • 19
    $\begingroup$ @DavidG.Stork I disagree -- combinatorial games like this are absolutely in scope for this site $\endgroup$ Aug 17, 2018 at 22:17
  • $\begingroup$ How does Alice winning consistently $56\%$ of the time differ from Alice winning $56\%$ of the time? $\endgroup$
    – joriki
    Aug 21, 2018 at 4:06
  • 1
    $\begingroup$ @joriki No special meaning. I just ran it a couple of times with a $1000$ games, then ran it with $10,000$ games and the result was every time $56 \%$. $\endgroup$
    – Jens
    Aug 21, 2018 at 15:18

1 Answer 1

-3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .