9
$\begingroup$

I've been thinking about the following two player game played on a 3x3 grid:

  • Red goes first and players alternate in taking turns.
  • Red moves tokens horizontally right.
  • Blue moves tokens vertically down.
  • Each turn, a player selects a token of their colour and moves it by one cell in the corresponding direction. If an opponent's token is in the target cell then it gets captured and returned to its starting position (top row for blue and left column for red). After a capture the current player can choose to move again, but this is optional.
  • If a token exits the grid then that token cannot be used again.
  • The first player to remove all their tokens from the grid wins the game.

Who will win if both players play optimally? Bonus: who wins in the equivalent 4x4 game?

enter image description here

Improve this question
$\endgroup$
10
  • $\begingroup$ Uhh... when does the game end? Right now the answer seems to be, trivially, "both players score 2 points in every game". $\endgroup$
    – Deusovi ♦
    Commented Mar 7, 2023 at 13:54
  • $\begingroup$ fixed it now. First to remove all their tokens wins. $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 7, 2023 at 13:57
  • $\begingroup$ "If an opponent's token is in the target cell then it gets returned to the starting position" - is 'it' the token in the target cell, or the token being moved? $\endgroup$
    – Deusovi ♦
    Commented Mar 7, 2023 at 13:57
  • $\begingroup$ the opponent's token in the target cell gets returned $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 7, 2023 at 13:58
  • $\begingroup$ Does the player who takes a token have to move again? From the phrasing it looks like they can choose not to, which may be an advantage. $\endgroup$
    – hexomino
    Commented Mar 7, 2023 at 14:10

2 Answers 2

Reset to default
7
+50
$\begingroup$

Using optimal strategy,

the game never ends.

Let's start by assuming red has a winning strategy and ignore any moves we can prove aren't winning. For example,

any position where blue can obtain the mirrored position can not be winning for red.

I'll refer to the tokens closest to the opposing home row as the inner tokens and the other two as the outer tokens. To begin with, if red starts by moving the inner token,

blue can capture it and have the same position.
|v|v| | |v|
|>| | >|v| |
>| | | >| | |

Then in the case where red moves the outer token first, if blue moves the inner token

they lose.
| |v| | |v|
>|v| | >|v| |
|>| | | |>|
If blue the moves the outer token they lose immediately.
| | | |v|v|
>|v|v| | | |
| |>| | |>|
But if they move the inner token they still lose.
| |v| | |v|
>| | | |>| |
|v|>| |v|>|

| |v| | |v|
|>| | |>| |
| |>| | | |

That leaves the case where both players move the outer token first. If red then moves the inner token

blue can once again capture it and have the same position, so this is also not winning.
|v| |
|>|v|
|>| |

| | |
>|v|v|
|>| |

If instead red moves the outer token again

blue is forced to capture or they lose immediately like before.
|v| |
>| |v|
| |>|

| | | |v|v|
>|v|v| | | |
| |>| | |>|

Then the question is, should they move again after they capture?

The answer is yes. If they don't then this happens:
|v| | |v| |
>| | | >| | |
>| |v| |>|v|
and now blue is in zugzwang. They are forced to move their inner token before red does.
| | | |v| |
>|v| | | |>|
|>|v| |>|v|
After this they can no longer force a capture and are more moves away from winning than red, so this is a loss.

If they do move again, which token should they move?

They can't move their outer token off the board. Despite being closer to a victory they are now at a disadvantage because they can only move one token.
|v| | |v| |
>| | | |>| |
>| | | >| | |
Moving again and staying put both lead to defeat.
| | | |v| |
>|v| | | |>|
>| | | >| | |

| | | | | |
|v|>| |v| |
>| | | >| | |

| | | |v| |
| | | | | |
>|v| | | |>|
If they move again:
| | | |v| |
>| | | >| | |
>|v| | | |>|

| | | |v| |
>|v| | | |>|
| |>| | |>|

So what about the other option?

| | |
>|v| |
>| |v|
Red can't move the outer token here or it will just serve as a springboard for blue's inner token.
| | | | | |
>|v| | >| | |
|>|v| >| |v|
It's the same if red captures first.
|v| | | | |
|>| | >| | |
|>|v| >| |v|
Moving the same token again after capturing leads to this position:
|v| |
| |>|
>| |v|
This is actually a mirrored version of a losing position we've seen earlier, so capturing and not moving again is the only move left.
|v| |
|>| |
>| |v|
If blue doesn't capture they lose.
|v| | |v| |
|>| | | |>|
>| | | >| | |

| | | | | |
|v|>| |v| |
>| | | >| | |

| | | |v| |
| | | | | |
>|v| | | |>|
Moving a token off the board after capturing also doesn't work out.
| | | |v| |
>|v| | | |>|
>| | | >| | |
If they move the inner token instead we get another winning position for red we've seen before.
| | | |v| |
>| | | >| | |
>|v|v| |>|v|
That leaves us with capturing and not moving again.
| | |
>|v| |
>| |v|
But this is the same position we started with, so these positions will alternate forever.

So in the end

Red has no way to force a win but they can avoid losing by making the game continue forever. Some of the positions where the other player can get the mirrored position might still be losing, but this doesn't matter so long as red has at least one way to force the game to go on forever.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @JaapScherphuis It doesn't matter because moving again is optional and that means the other player can get the mirrored position if they want to. That alone is enough to prove it can't be a winning position because the other player could then steal this winning position, leading to a contradiction. $\endgroup$
    – CubicBerserker
    Commented Mar 12, 2023 at 19:39
  • $\begingroup$ @CubicBerserker Oh, so the person that got captured couldn't have been using a winning strategy cause the other player is able steal it by not doing the extra move. Got it now. I forgot about the move being optional. $\endgroup$
    – Jaap Scherphuis
    Commented Mar 12, 2023 at 19:43
  • 1
    $\begingroup$ I have carefully checked all your logic. I think you have covered all the cases and found the right answer. Well done you get the bounty! I suspect the larger case is too hard to analyse manually. $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 14, 2023 at 12:23
3
$\begingroup$

The answer is that

playing optimally, the game never ends. Red can prevent Blue from winning by immediately capturing the token in the upper left corner whenever given the opportunity; Blue can prevent Red from winning by doing the same.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Yes good point. I think these rules make the game boring. Can I please change them? $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 7, 2023 at 14:01
  • $\begingroup$ Yes, this looks right and that it generalises to $n \times n$. May want to add what happens if red plays anything else. $\endgroup$
    – hexomino
    Commented Mar 7, 2023 at 14:03
  • $\begingroup$ Your answer was correct, but I think the rules were too trivial. So I decided to change them slightly, sorry. You get to move again when you capture. $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 7, 2023 at 14:05

Not the answer you're looking for? Browse other questions tagged or ask your own question.