18
$\begingroup$

I found this interesting game with no name:

You have a 1x11 grid, like this.

1x11 grid

The way you play is similar to Tic-Tac-Toe (aka Noughts and Crosses). Players take turns to place Xs and Os on the grid, but you can't put one letter directly adjacent to another letter. When one player doesn't have any squares that are valid for he or she to place a letter on, then their opponent wins.

So, my question is:

Is there a strategy that guarantees you to win? If so, what is it?

$\endgroup$
  • $\begingroup$ There is likely a strategy that allows the first player to win, since it looks this game is equivalent to some nim game, if it's still unanswered I'll look for it $\endgroup$ – SilverCookies Apr 26 '18 at 9:00
  • 4
    $\begingroup$ @SilverCookies Well, every impartial game under the normal play convention is equivalent to a nim game, so you're right :) This particular case is usually called Dawson's Chess. $\endgroup$ – ffao Apr 26 '18 at 9:40
  • 1
    $\begingroup$ I think this is equivalent to Dawson's Kayles, which is the game mentioned in the Octal game wikipedia page with the octal code $0.07$. Just play Dawson's Kayles on a size 12 board - every move fills two adjacent cells. The left-hand cell of each pair played corresponds to a move on the size 11 board of the game in this question. Apparently that is equivalent also to Dawson's Chess. $\endgroup$ – Jaap Scherphuis Apr 26 '18 at 9:44
  • $\begingroup$ Assuming that if a player loses if all the squares are filled, then clearly the game can't end in a draw, so one player must have a winning strategy. $\endgroup$ – Acccumulation Apr 26 '18 at 18:08
16
$\begingroup$

I think the answer is that the

First player can always guarantee a win.

Strategy

The first player can play the middle square first giving the configuration

_ _ _ _ _ X _ _ _ _ _

This effectively divides the board into two sets of four playable squares (on the left, and on the right of the initial X) as shown

_ _ _ _ | _ X _ | _ _ _ _

Then, whichever square O plays next will be in one of these sets and there will guaranteed to be at least one playable square for X in that set since a single move can eliminate at most three playable squares. Furthermore, any move of X in the same set of four is guaranteed to eliminate all remaining playable squares in that set.

X just needs to play as such twice.

$\endgroup$
  • $\begingroup$ Yep, I think this is right! $\endgroup$ – mestackoverflow Apr 26 '18 at 9:13
  • $\begingroup$ This method allows the first player to not lose, but it won't allow you to always win. $\endgroup$ – The random guy Apr 26 '18 at 9:13
  • 2
    $\begingroup$ @Therandomguy there are no draws in this game, and this always guarantees a win! In addition this opening also allows First to force a win: _ _ _ X _ _ _ _ _ _ _ $\endgroup$ – SilverCookies Apr 26 '18 at 9:16
  • $\begingroup$ you can't put one letter directly adjacent to another letter ... Missed that one. I should always look at the rules twice. $\endgroup$ – The random guy Apr 26 '18 at 9:19
22
$\begingroup$

Another strategy for

The first player to win

that works for any odd number of squares:

Play in the middle, as hexomino suggested:

_ _ _ _ _ X _ _ _ _ _

Now, whenever O plays in the left or right section of the board, play the square reflected on the opposite section, which is guaranteed to be available by symmetry. Since you won't run out of moves, your opponent is guaranteed to be the one to run out first.

$\endgroup$
  • 1
    $\begingroup$ Nicely, this argument seems to generalize easily for $1\times (2k+1)$ grids. $\endgroup$ – Surb Apr 26 '18 at 12:56
  • $\begingroup$ Yes, I like this argument. $\endgroup$ – hexomino Apr 26 '18 at 13:31
  • $\begingroup$ What if O plays next to the center? $\endgroup$ – Acccumulation Apr 26 '18 at 18:06
  • $\begingroup$ @Acccumulation: That's impossible: "you can't put one letter directly adjacent to another letter" $\endgroup$ – Words Like Jared Apr 26 '18 at 19:40
  • $\begingroup$ @WordsLikeJared Oh, somehow I read it as being you can't put a letter next to your own. $\endgroup$ – Acccumulation Apr 26 '18 at 19:52
8
$\begingroup$

I solved the entire game:

These are the winning pattern for the First move: O X X X O X O X X X O

where X means a First can force a win and O means Second can force a win.

Explanation:

So, I wanted to give a mathematical proof since I thought the game was equivalent to nim S(2,3), but then I realized the edge conditions make this statement untrue, it's still a nim variant but I don't know how to approach it. So instead here's an empirical proof:

user ffao already proved that any game with an odd number of positions(< 1) is a win for First (Proof A), so:
_ _ _ _ _ X _ _ _ _ _ = First wins

X _ _ _ _ _ _ _ _ _ = Second wins since the move leaves Second to play A

_ _ _ X _ _ _ _ _ _= Second wins with _ _ _ _ X _ O _ _ _ _ this leaves First with 2 A type games: they will win the first (where they start), and lose the second (where Second start, who will take the match)

What happens with even numbers of positions? 4 squares is an easy win for Second, and 6 is win for First = _ _ X _ _ _ ,

_ _ _ X _ _ _ _ _ _ _ = First wins since the move splits the game in a 2,6 games. If Second takes 2, First starts 6 and wins, if Second starts 6, they will take it, then First will win 2.

_ _ X _ _ _ _ _ _ _ _ = First wins as it leaves a 1,7 games, just like before if Second takes 1, First will start 7 and win; if Second start 7 they will take it and First will take 1 and win.

_ X _ _ _ _ _ _ _ _ _ = First wins This leaves Second to start an 8 game which can be shown to be a win for the second player (First). Second can reduce the match to a 5 game (which First will win due to A), a 6 game (which we have shown First will win), and a 2,3 game (which First will win with: _ _ _ O _ X _ _).

All the other games are mirrors.

$\endgroup$
1
$\begingroup$

If Player 1 can't force a win when the board is $n$ squares long, he can do it for $n+2$ or $n+3$ by filling any of the first or second squares from outside to inside respectively, turning it into an $n$-square-long game.

If 1 can force a win for $n$, then when it's $n+4$ squares long, he can fill the 3rd square to the right or left, leaving 2 "games" with $n$ and 1 square-long games. Then, Player 2 can't complete the latter for fear of leaving the former game to the other and allowing him to win. If he makes a "winning" first move in the larger game (one he can force a win with), 1 plays along to act the "loser". If 2 starts with a losing move in the larger game, 1 does the same.

If $n<4$, 1 wins.

If $n=4$, 2 wins.

If $n=5$, 1 wins.

If $n=6$, 1 can win by occupying the first or last square.

If $n=7$, 1 can win by occupying the second or second-to-last. Then 2 uses one of the four available squares, but loses.

11 mod 4 is 3, so it's a number allowing 1 to win (shortened due to symmetry - third to last square):

--------X--

-----O--X--

X----O--X--

(1 eventually wins)

or

--------X--

------O-X-- (O may want to play the loser)

-X----O-X--

(1 eventually wins)

or

--------X--

----O---X--

-X--O---X--

(1 eventually wins)

or

--------X--

---O----X--

---O-X--X--

(1 eventually wins)

$\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.