15
$\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$
  • $\begingroup$ This belongs on the Puzzles stack exchange... not here. $\endgroup$ – David G. Stork Aug 17 '18 at 21:39
  • 3
    $\begingroup$ This seems to fall under the "combinatorial game theory" tag. $\endgroup$ – Jens Aug 17 '18 at 21:49
  • 18
    $\begingroup$ @DavidG.Stork I disagree -- combinatorial games like this are absolutely in scope for this site $\endgroup$ – Gregory J. Puleo Aug 17 '18 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 '18 at 4:06
  • $\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 '18 at 15:18
-2
$\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.

| cite | improve this answer | |
$\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.