Victor Allis Connect 4 Dissertation

The basic strategy when playing Connect Four is to avoid losing in the early stages of the game while setting yourself up for a win in the endgame. With experienced players, the game will usually be decided once the majority of the columns are completely filled. For example, in the graphic below, it is Player A’s (White) turn to move.

Neither player has any choice. Player A plays in the last remaining column, Player B (Black) plays on top of him, and the board looks like this:

Our unfortunate Player A now makes the next move:

Player B claims the victory:

The main thing to understand, then, is what early factors determine who will be in position to win in the end game’s forced moves.

Introducing the Zugzwang

Connect Four is a much deeper game than may be readily apparent. Unlike some children’s games where winning or losing comes primarily by luck, the outcome of a Connect Four game is determined by who plays the best. It is possible to codify the strategic guidelines of the game and construct computer players which range from difficult to impossible to defeat.

Victor Allis and James D. Allen both independently proved that Connect Four is a first player win. If the first player never makes an incorrect move, he, she, or it, as the case may be, will win. Facing an ideal player who starts first, no matter how well you play as the second player, you will always lose. But the game is complex enough that there is no simple list of dos and don’ts that the first-player can follow to play perfectly. In fact, the ideal strategy, while it exists, is complex enough that even the very best human players cannot achieve ideal play in every game.

Allis, in his Master’s thesis, developed a computer system, dubbed VICTOR, that plays Connect Four ideally. If the computer is given first move, it will always win. With the second move, against a human or computer opponent that does not make exactly the right move on every turn, VICTOR will either win or draw.

VICTOR achieves perfect play using a set of strategic rules to always retain control of the Zugzwang. Zugzwang comes from the German “compulsion to move”. Most often used in reference to chess, it refers to the sitatuion where one player must make a move when he would prefer to not move at all. Allis applies the term to describe maintaining control of the board, such that when the end game is reached, the player who has control of the Zugzwang is in position to benefit.

You may have encountered Zugzwang in your own games of Connect Four. As in the example above, one player is forced to move, and that gives his opponent the opportunity to claim victory. It is common to feel that who wins in a situation like this comes down to chance. However, Allis showed that this is not true. His VICTOR engine exploits this fact to guarantee victory.

His thesis is very readable, though I recommend having a copy of the game (physical or virtual) handy to work through the various scenarios and strategic situations he discusses.

Threatening Threats (and Threats That Aren’t)

I will adopt the terminology of Allis’s thesis. The first player, Player A, has white pieces. The second player, Player B, has black pieces. On the board there are 7 columns and 6 rows. The columns are assigned the letters A through G, from left to right, and the rows are numbered 1 through 6, from top to bottom.

A threat is defined as a space, which, if taken by a player, results in a win. In other words, a threat is the last space a player needs to connect four.

Threats are further classified as odd or even. An odd threat is a threat on an odd-numbered row and an even threat is on an even-numbered row. It is possible to make generalizations about which player will get to exploit odd or even threats, given certain conditions on the rest of the board.

The example above is typical of the endgame of Connect Four. Both players have played carefully, and neither is able to connect four in the early game. We see Player A and Player B both have even threats in Column C, Row 4. Whenever some columns are filled and the rest empty, an even number of pieces have been played (there are an even number of spaces in each filled column). As we saw in the example, the next move belongs to Player A. In fact, Player A will play in rows 1, 3, and 5. Player B will get rows 2, 4, and 6. Since Player B has an even threat in row 4, he wins the game.

In this type of end-game scenario, Player A desires odd threats and Player B desires even threats. If Player A had an odd threat in row 3, Player A would have won. However, as Allis demonstrates in great detail in his thesis, there are numerous factors that can disrupt this basic pattern.

In this example, Player A has an odd threat in Column F and Player B has an odd threat in Column C:

It is easy to draw the erroneous conclusion that Player A is going to win, since in the earlier scenario Player B couldn’t use odd threats. But the odd threat in Row C forces Player A to play in Row F, giving up his own threat as Player B follows up by also playing in Row F.

Player A continues to fill Row F, with Player B playing follow up until the row is filled.

With one piece already in Column C, an odd number of pieces have been played. It is Player B’s turn. He is forced to give up his own odd threat.

The game results in a draw. Even though Player A had an odd threat, it was neutralized by Player B’s odd threat.

This is one instance among many where the odd/even threats guideline is not enough to predict the outcome of the game. For a further discussion, see Allis’s thesis or one of the other resources listed below.

Who’s (Probably) Going to Win?

Our simpler approach to creating a computer player was to implement the Minimax alogorithm with Alpha-Beta pruning. We coupled this with a heuristic function that used several strategic rules to estimate the relative strengths of board positions. The computer player looks several moves ahead and chooses the move that the heuristic indicates will lead to the best outcome.

Our heuristic function began by examining all 69 potential winning lines. A winning line is an opportunity for a player to connect four. If both players had at least one piece on a potential winning line, it was ignored as useless to either player. The evaluation function gave a very small amount of importance to the number of winning lines an individual piece contributed to. In the absence of other information, the heuristic valued positions near the center of the board more highly than positions on the periphery.

But if one player occupied three of the four spaces, with the last space empty, it was recorded as a threat for that player. Threats formed the most important part of the heuristic function’s estimate.

The heuristic attached extreme importance to the following three scenarios:

  • If Player A had an odd threat with no even threats from Player B below it in the same column, and Player B had no odd threats in other columns, this was scored as a probable win for Player A.
  • If instead Player A had a greater number of odd threats (with no even threats from Player B below them) than Player B had odd threats anywhere on the board, and Player B had no even threats, this was also scored as a probable win for Player A.
  • And if neither of the above held and Player B had any even threats, it was scored as a probable win for Player B.

Based on the strategic rules of Connect Four, the above heuristic attempts to guide the computer player to victory by controlling the Zugzwang.

It was evident when our program played against Velena (which plays perfectly) that there were many situations where our own program would quickly seize an apparently advantageous situation, such as initially denying Velena even threats while obtaining a good odd threat, that led our heuristic to suggest that our player was going to win. Unfortunately for our computer player, Velena, using Allis’s additional body of strategic rules, was able to subtly control the game such that, towards the end, a threat for Velena would materialize that neutralized our player’s threat and secured a win for Velena.

However, losing to a perfect-play engine is no surprise. Using our heuristic outlined above, and limited to half a second to decide each move, our computer player was able to beat me and my teammates easily in head-to-head games. Moreover, our computer player was able  to beat the majority of computerized opponents using a simpler heuristic, even when those opponents were given additional computation time.

Who “We” Are

The heuristic function described above was implemented by Eric Gribkoff, Pei Guo, and Saerorm Park.

Further Reading

Like this:

LikeLoading...

Related

A JavaScript Connect Four AI

23 Dec 2014

Might I interest you in a rousing game of Connect Four? You and the computer take turns dropping discs into one of the seven colums below. The goal is to get four pieces of your color in a row (vertically, diagonally, or horizontally).

That’s an AngularJS powered Connect Four AI that was originally written in C and then compiled to JavaScript using Emscripten. It runs the actual AI in a web worker to prevent your browser from locking up.

It was implemented using techniques from Stuart Russell and Peter Norvig’s excellent book, Artificial Intelligence: A Modern Approach (3rd Edition). These techniques might not create the best Connect Four AI possible (in fact, Victor Allis’ thesis shows how to create a provably-unbeatable AI), but it can still do pretty well! The code (in C, Python, and JavaScript) is available on GitHub.

The main idea behind the AI is adversarial search. Think of all the possible games of Connect Four represented as a tree. The root of the tree is the empty board. The second tier of the tree represents all the possible moves that can be made by the first player. The third tier of the tree represents all the possible moves that can be made by the second player.

A small subset of the tree (for a small game board) might look like this:

Imagine expanding the tree all the way down to the bottom, where the leaf nodes are “terminal” states – states where one player has won the game, or there is a draw. In order to make moves, the AI applies a minimax strategy. In other words, the AI assumes that its opponent will always play optimally, and thus tries to minimize the maximum gain of its opponent.

This tree is really big. The branching factor is approximately seven, and the depth of the tree could be as high as 42. So, while the the perfect tree formula would tell us that there are boards, some smart mathematicians have figured out that there are “only” around 4 trillion different boards. That’s still way too many to examine.

Thankfully, we can use a technique called alpha-beta pruning. The idea is pretty simple: do not bother searching branches that would either:

  • require our opponent to make a detrimental move (to get an outcome less than the outcome they could get if they played optimally)
  • or, require us to make a move that was less advantageous than another move we could make

Now, this is a hand wavey oversimplification of how the process actually works. I suggest you read the chapters in Russell and Norvig, or fuss through the Wikipedia page, to get a better understanding.

In the average case, alpha-beta pruning reduces the number of nodes we need to evaluate from to . This brings us from 4 trillion boards to around 2.7 billion boards. A pretty good drop – but still not enough for us to enumerate.

Next, we employ a heuristic function. Since we can’t reach the bottom of the tree, we’ll go down a certain depth and then make some kind of guess as to whether or not the board we are evaluating is a winning or losing board. I used a very simple heuristic: the number of possible four-in-a-rows. The computer would calculate how many ways it could win using alignments present in the current board, and then subtract the number of ways the computer’s opponent could win.

Now, the computer will exhaustively evaluate the tree to a certain depth (the number of moves to “think ahead”) and then use a heuristic to evaluate that board. Eventually, as the end of the game draws near, the computer finds winning or losing states within the prescribed depth, and plays perfectly. The hope is that the heuristic function can guide the AI to a winnable position. It seems to work pretty well – if you can beat it, try increasing the number of moves to think ahead. It’ll make it slow down, but it’ll get exponentially more difficult.

Oh – there’s one more complication. A lot of the boards that you encounter when going down the tree are duplicates (there is more than one way to get to a state). To avoid recomputing the desirability of these boards, we store them in a hash table.

It also looks like writing this type of AI is homework for AI classes at Cornell, Northeastern, and Purdue. I could only find one other Javascript Connect Four AI, which moves substantially faster than mine, but is easily defeated (which is exactly the behavior one would expect).

Winner: none yet...Player {{winner}}

Draw: noyes

One thought on “Victor Allis Connect 4 Dissertation

Leave a Reply

Your email address will not be published. Required fields are marked *