13
$\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
  • 17
    $\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

Your Answer

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

Browse other questions tagged or ask your own question.