15
$\begingroup$

To help people think this out, I've made a web game with increasingly difficult cpu players to allow brainstorming and testing strategies:

cpu player, easiest (version 1 - at least 5-in-a-row is possible against this strategy)
cpu player, easy (version 2 - at least 4-in-a-row is possible against this strategy)
cpu player, hard (version 3 - I have yet to get 4-in-a-row against this strategy)


This puzzle is about strategy in a variant of Tic-Tac-Toe. The game differs from the usual version in the following ways:

  • The board is 16x16

  • The two players have different goals

  • Your only goal is to get as long a line of pieces in-a-row as possible (horizontal, vertical, or diagonal)

  • Your opponent's only goal is to limit the line of pieces you can get in-a-row (it does not matter how many pieces in a row the opponent gets)

  • One final twist: for every move you make, your opponent gets to move twice

With perfect play can you get four in-a-row? Or can you prove that it is not possible?


NOTE: I am not a web developer, so I apologize if the interactive version doesn't work for you. The goal is to figure out how to guarantee four in-a-row or prove it is impossible for the game described above please let me know if the interactive game seems to deviate from that.

The version 3.0 cpu player does not try to think any moves ahead. It just calculates a heuristic score for one of 24 spots around the player's last move, and moves in the best available spots allowed. I set it up this way, to make it easier to reason about. If it turns out that this strategy is sufficient to prevent 4-in-a-row, then that solves it and I find it is easier to reason against a simple concrete opponent. Alternatively if one can find how to get 4-in-a-row against this computer player, it may allow for a strategy to guarantee 4-in-a-row. If you'd like to know more about the cpu ver3 strategy, I've tried to comment the code to explain, so just read the cpu player's javascript.

Again, the goal of the puzzle isn't to beat the cpu, but playing against the cpu may help you think out ideas and try strategies. That being said, if you manage to beat the hardest cpu player, please post your move log so we can learn from your amazing strategy skills. Good luck!

$\endgroup$
18
  • 1
    $\begingroup$ Essentially the inverse puzzle of the game listed in Tic-tac-toe 1000 in a row but on a finite board. Also a specific case of this puzzle in 2D but on a finite board. $\endgroup$
    – MWilliams
    Commented Nov 20, 2014 at 9:00
  • $\begingroup$ Also, if someone that likes programming wants to make a more sophisticated AI, feel free to copy the code and post something better. $\endgroup$
    – MWilliams
    Commented Nov 20, 2014 at 9:28
  • $\begingroup$ Might not actually be possible but I beat your bot. Move Sequence: DhFiIgLiOgJgLhMiMhOhOiOj $\endgroup$
    – warspyking
    Commented Nov 20, 2014 at 9:51
  • $\begingroup$ @warpsyking Yeah, after playing the computer a bit, you can exploit its weaknesses and get four-in-a-row (best I've done so far is getting a chain of four after I make 9 moves), although I haven't been able to get a chain of 5 yet. Maybe I need to make the bot better for it to be helpful. $\endgroup$
    – MWilliams
    Commented Nov 20, 2014 at 9:56
  • 1
    $\begingroup$ BbBeBfCeCfDdDeDfEf $\endgroup$
    – jwize
    Commented Nov 21, 2014 at 8:45

2 Answers 2

5
$\begingroup$

Note: the contents of this answer are not actually correct; however, I've been asked to undelete this because it contains content that might be useful.

I'm still trying to work through what I missed, but in essence, I think it comes down to the assumption that Red plays pieces that are adjacent to existing pieces, or do not otherwise interfere with them. I'm not totally sure, though, and I'd definitely be interested in an explanation.


With perfect playing, it is not possible to get four-in-a-row. It is at most possible to get three-in-a-row.

Let's let Player 1 be the player who's trying to achieve a high length using red squares, and Player 2 be the player who's trying to restrict the max length using blue squares. This follows your web example, but I just wanted to establish clear terminology.

It actually makes absolutely no difference what player 1 does in this situation, since it's not possible for player 1 to achieve anything more than a length of 2. Here's what you have to do, as player 2:

Whenever Player 1 makes a move look at all the adjacent squares.

  • First, check to see if Red could form a chain of four anywhere on their next move. If such spots exist, fill them in. (There will never be more than two of these at at time - see below.)
  • Then, check to see if Red could form a chain of three anywhere on their next move. If any such spots exist, fill them in.
  • If neither of the above are true, place Blue squares anywhere next to the square that red just placed.

It's that simple.

How does this work in practice? I'll walk through a few steps.

Step 1: Red makes the first move.

enter image description here (becomes) enter image description here

Blue sees that there's a red square, and there are no places where Red could go to create a chain of three. So, per instructions, Blue fills in two squares on opposite sides of the red square.

Step 2: Red tries to break away!

enter image description here (becomes) enter image description here

Blue sees that Red has tried to break away diagonally. Since there are two spots opposite each other where Red could break away, Blue fills those in.

Step 3: Red creates more escape routes!

enter image description here (becomes) enter image description here

Blue here sees four spaces which could generate chains of three. Since two of them are opposite squares, Blue picks a random pair and fills them in. The result is the same.

Step 4: Red creates a chain of three!

enter image description here (becomes) enter image description here

Blue here sees two spots where a four-in-a-row could happen. Blue obviously fills them in.


Why does this work?

Here's an easy explanation that's very intuitive: any time Red could make a 4-chain, they're cut off at both ends. This is actually not simple to demonstrate, though.

What we need to show is that Red can generate at most two openings for a fourth piece to go into at a given time. If there are only two open slots, Blue will fill them on the next turn and the chain will die at length 3.

We know that Red can produce 2-chains, and that Red can produce 3-chains from them. Let's take a closer look at why Red can even do this, and classify it a little. In order to create a 3-chain, Red needs to unify two 2-chains at a common point. (I'll call these linked 2-chains.) Each individual 2-chain only has two openings to expand into 3-chain. However, if we conjoin two of them at a common point, then the resulting group is given not two, but four openings.

In other words, the fundamental property is: a single chain of length two or greater can only have two degrees of movement. (A chain of length 1 can have up to eight, by comparison.) Because the chain must go in a certain direction, at most two possibilities exist: continuing off either end. When we stick them together into linked chains, however, we can at most add those degrees of movement together, and adding two 2-chains' movements together gets us a 2-chain with movement 4.

enter image description here

Here, Red only has two openings to create a new chain. Both of these will be cut off when Blue moves next. However, Red can force Blue into a helpful chain:

enter image description here

How did Red do this? They went first in Cb. Blue blocked some random squares off, then Red went in Cc. Blue necessarily blocked off this chain of two from becoming a chain of three. However, at this point, Red goes in Bc. Bc gives red two unrestricted pairs, (Cb-Bc) and (Cc-Bc). Blue can only stop one of these, so the other will be able to expand into a chain of three.

Why is this important? In order to create a 4-chain, we need to create a linked 3-chain. Each 3-chain only has two degrees of movement, but if we can add them together at once, we can create a linked 3-chain that has at most four degrees of movement. This means that blue can't kill all degrees of movement in the next turn, and Red can play to win.

Easy, right? Turns out it's not possible.

The reason is actually pretty simple: you need to create two 2-chains that are adjacent to each other. You'll get to a position comparable to this:

enter image description here (becomes) enter image description here

Blue sees Red place a tile somewhere totally irrelevant. Following the steps in logical order, Blue spots a space where Red could, in theory, create a 4-chain on the next turn. Blue fills that in. Blue then spots a space where red could, in theory, create a 3-chain on the next turn, so Blue fills that in, too.

In other words, you've created a 2-chain. That's fine and good, but now you need to make another one, and doing so consumes six degrees of movement. It takes three moves. Your process creates four degrees of movement, so there's a net loss of two degrees of movement. Where do those two degrees come from? The chain you're trying to link to, on the first turn you try to link to it!

It's theoretically possible, if you already had two existing 2-chains and could link them at a unifying spot. But it's not possible to get to that position; if you tried to create the second 2-chain you need, the first one will be cut off and die.

Thus, it's not possible to get four in a row if Blue plays perfectly. QED.


tl;dr? The maximum-length chain that Red can create is three. There's no possible way to generate a longer-length chain.

$\endgroup$
9
  • $\begingroup$ How the heck did you post this so quickly? Anyway, look at the image you have after the "Dd" move. There are three places red could move next to get a chain of 3, but blue can only move in two spots. $\endgroup$
    – MWilliams
    Commented Nov 20, 2014 at 9:33
  • $\begingroup$ @MWilliams I only see one. Are you including diagonals? And I have screenshot tools :] $\endgroup$
    – user20
    Commented Nov 20, 2014 at 9:35
  • $\begingroup$ Yes diagonals are allowed in Tic-Tac-Toe. $\endgroup$
    – MWilliams
    Commented Nov 20, 2014 at 9:35
  • $\begingroup$ @MWilliams I figured out the rigorous proof. $\endgroup$
    – user20
    Commented Nov 20, 2014 at 10:51
  • $\begingroup$ When you say "check to see if Red could form a chain of three anywhere", do you mean, just in Red's next move? $\endgroup$
    – xnor
    Commented Nov 20, 2014 at 10:53
2
$\begingroup$

Here is one possible move sequence with nine moves:

BbFfGiJfHhGgFhGhIh

The program seems to prioritize threats and then surround if none are available. By shooting one of your red blocks in the leg and leaving him in the corner, it lets you set up without hindrance. The strategy is to create a series of forced moves in spaces that needn't be occupied culminating in a cross.

It's actually a lot like playing chess.

$\endgroup$
2
  • $\begingroup$ Please note the puzzle isn't to beat the simplistic computer player. The puzzle is whether you can find a strategy (or disprove one exists) to get a line of 4 regardless of what your opponent does. So the question is therefore: Is a score of 4 guaranteed with perfect play? Or is 3 the best one can guarantee? $\endgroup$
    – MWilliams
    Commented Nov 22, 2014 at 6:07
  • $\begingroup$ I've made a better computer player (it is still quite simple though), if you want to try playing against that to test some strategies out. $\endgroup$
    – MWilliams
    Commented Nov 22, 2014 at 6:10

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