# How do I write a “Connect Four” AI?

I've made a Connect Four game. The first move is made by the player and the second by the computer. Currently, the computer moves randomly; its moves are generated by C++'s random number generator `rand()`. I'd like to build a basic AI that tries to win or prevent the player from winning.

How can I go about doing this?

-
How would -you- play connect four? You could try writing an algorithm that is close to your way of playing, and use that as a starting point to make it better and better. – Panda Pajama Mar 11 '14 at 9:31
Is that the only way. – Connect four Mar 11 '14 at 9:33
Connect 4 is a solved game, and the solution is based on following a set of 9 rules. You may be able to implement these rules or variants to guide the AI: informatik.uni-trier.de/~fernau/DSL0607/… – DMGregory Mar 11 '14 at 9:47
That is -a- way. As DMGregory says, that is a solved game, so you can certainly implement it in a way the computer plays perfectly, and your players always lose. Alternatively, you can have it play with your personality, which can make a much more fun game, and you will learn more about AI programming in the meantime. How you do it is up to the goals you have for your game. – Panda Pajama Mar 11 '14 at 9:59
research the minimax algorithm. But you also need a way to measure how good a move is. – concept3d Mar 11 '14 at 13:27

First, you need a rating function. A rating-function analyzes the playing field, rates which player currently appears to have a better chance of winning, and outputs it as a positive (computer has an advantage) or negative (player has an advantage) number.

You could calculate the rating by checking each already placed chip and see how many possible lines of four are still possible to complete with that chip and how complete they already are. When the chip belongs to the AI, add points for every possible line. When the chip belongs to the player, subtract the same amount of points. An already complete four-line would be a rating of +∞ or -∞, depending on which player has it (there is no better move than one which fulfills the win condition).

Then you use this function to calculate the rating of every currently possible AI move followed by every possible player response to that move (when your playing field has 8 columns and no columns are full, you would have to rate 64 possible outcomes). Then pick the AI move where the enemy response with the worst rating (from the PoV of the AI) is still rated higher than the worst-rated response of every other AI move.

A cheap way to make the AI stronger is to not just explore one round in the future but even more rounds. But keep in mind that the computation time will increase exponential. A much more efficient and elegant way, however, is usually to improve your rating function so the AI can make better strategic decisions.

This method is called the minmax algorithm, and it can be applied to any turn-based game without information hiding and a small number of possible moves each turn. The only thing you have to adapt to each game is the rating function. When the game has a large number of possible moves each turn, the performance can be enhanced through alpha-beta pruning (not following obviously bad tree branches).

-
Philipp please take your time and add as many things as you want, even if it fills the whole page i will read it if it will help me finish my game.Thankyou for the answer in advance. – Connect four Mar 11 '14 at 10:41

I suggest you represent your game as a tree. This obviously mandates that you know basic graph theory. Google: BFS, DFS, graph theory - until you get the basic concepts such as node, leaf, children, parents, siblings, etc.

The initial game setting is the root node, its branches are the moves you can make, the other inner nodes are distinct game states that you get to by taking those moves, and leaf nodes are end states that can be `win`, `loss`, or `draw`.

Visualization of the game state tree:

Where #1 is the empty board, and #2 #7 #8 are the game states you get to from possible moves for the first player. Of course, the tree for Connect Four would look different.

Making a move simply means visiting a node, i.e. going by one of the branches. Please note that a single node presents the entire game state - i.e. it is a collection of all the game pieces and the entire board (obviously this can get memory-heavy, but there are optimizations).

You also have to use some stochastic and heuristic methods because the number of nodes will grow exponentially in size - you simply wont be able to traverse all of them and know which one to choose - statistics is your only weapon.

The Monte Carlo method seems to be suitable here.

When deciding which branch to take, you obviously have to pick the one with the highest probability of winning. So you have to calculate that probability for each of the possible branches (moves).

You do this by moving to them, and then picking random paths to go down. You continue down the paths until you reach a final state. Say you sample 10 000 final states. Then the probability of winning for that branch is `winning states / (losing states + draw states)`.

The paths have to be random. You do this by picking a random sample of children of a node and only visiting them. At one point down the tree you will have to take only a single random child of a node because picking even a small percentage is still exponential.

There are also options of dividing the result by the depth of the search since deeper searches are less relevant.

Please note that you have to take into account what the other player would do: some of his moves are more likely to be taken than others, see MiniMax.

-

As has been said, treat the moves as a tree.

However, since you say C++ you're running off local storage and thus I'm going to propose a different answer than trying to write a rating function.

Instead, as has been said, the game has been solved. There are only 4.5 trillion possible boards and the fact that the AI doesn't want to make stupid moves takes out a bunch of them. Given some precalculation combined with modern processors this makes me think it should be possible to make the theoretically perfect move in all situations.

To do this you'll need to start out processing EVERY board on your machine. This will of course be quite slow. Save the first 11 moves of this tree in a form of your response to each of his possible moves. (Note: This can be packed into 20 bits per move, the resulting file is in the tens of megabytes.)

I think this puts you far enough into the game that you can now brute force it faster than a human would play. Code optimization will matter!

-
Note that for a realistic AI you might not always want to make the "correct" response - some randomness might be expected. – jcora Mar 15 '14 at 16:36