Algorithms for Connect 4?

Question

Im designing a program to play Connect 6, a variation of connect 4. I have narrowed down my options to the following:

1) Minimax with Alpha-Beta Proning

2) A Neural Net

3) Machine Learning

My program has one second to make a move, so I can only branch out 2 moves ahead with Minimax. Which solution would best perform under 1 second?

I looked around the web, but couldn't find anything relevant.

Also, are there any other additional resources you suggest I have a look at?

Answer 1

Connect Four was solved in 1988. The first solution was given by Allen and, in the same year, Allis coded VICTOR which actually won the computer-game olympiad in the category of connect four.

I would suggest you to go to Victor Allis' PhD who graduated in September 1994. You can get a copy of his PhD here. In Section 6.3.2 Connect-Four (page 163) you can actually read the following:

"In September 1988, James Allen determined the game-theoretic value through a brute-force search (Allen, 1998): a win for the player to move first. A few weeks later, in October 1988, connect-four was solved through a knowledge-based approach, resulting in the tournament program VICTOR (Allis, 1988; Uiterwijk et al., 1989a; Uiterwijk et al., 1989b). Recently John Tromp has calculated the game-theoretic value for all 8-ply connect-four positions (Tromp, 1993)."

You will find all the bibliographical references in the Bibliography chapter of the PhD in case you need further information. Of these, the most relevant to your case is Allis (1998). A Knowledge-Based Approach of Connect-Four. The Game is Solved: White Wins. M.Sc. Thesis, Faculty of Mathematics and Computer Science, Vrije Universiteit, Amsterdam. Go to Chapter 6 and you'll discover that this game can be optimally solved just by considering a number of rules. And this take almost no time!

So, my first suggestion would be for you to consider none of the approaches you mention but a knowledge-based approach instead. From what I remember when I studied these works, most of these rules should be easy to generalize to connect six though it might be the case that you need additional ones. However, if all you want is a computer-game to give a quick reasonable response, this is definitely the way to go.

Additionally, in case you are interested in trying to extend the results by Tromp that Allis mentions in the exceprt I was showing above or even to strongly solve the game (according to Jonathan Schaeffer's taxonomy this implies that you are able to derive the optimal move to any legal configuration of the game), then you should read some of the latest works by Stefan Edelkamp and Damian Sulewski where they use GPUs for optimally traversing huge state spaces and even optimally solving some problems.

Hope this helps,

Answer 2

If your looking for a suitable solution that you can implement quickly, I would go with the Minimax algorithm because this is the typical kind of problem where you would use Minimax.

If you choose Neural nets or some other form of machine learning, the runtime performance would probably be good but the question is would it find good moves?

To train a neural net you give it a data set of whit inputs and for each set of inputs a correct output, so in this case you might try to have inputs a0, a1, ..., aN where the value of aK is a 0 = empty, 1 = your chip, 2 = opponents chip. Indicating whether there is a chip in slot k on the playing board. The output would then be the best move to make in that situation. So how do you decide which is the best possible move? You could perhaps do a minimax to try to find some optimal move or you could manually create a data set where you choose what you think is a good move.

Still it's hard to say how well a neural net would do even with good training data. Also neural nets can be configured in different way, so you would have to do a whole lot of tweaking to get good results (if at all possible).

A lot of what I've said applies to other types of machine learning also.

Answer 3

Monte Carlo Method

Aside from the knowledge-based approach and minimax, I'd recommend looking into a Monte Carlo method.

The idea is simple: in a given position, a player has at most 7 possible moves (fewer, as columns fill up). For each possible candidate move, make a copy of the board and play the move. Then, play the game making completely random moves until a terminal state (win, loss or draw) is reached. Take note of the outcome. Repeat this procedure as long as time remains for the algorithm to run.

Once the clock expires on the algorithm, compare the win/loss count for each candidate move and determine which option yielded the best win percentage. This is likely the strongest move in the position--make it!

Advantages of the MC method:

• Easy to implement. No domain-specific knowledge or heuristics are necessary (you could think of it as the opposite of the knowledge-based approach).
• You can search positions up to your precise time bound in CPU/clock time. There is no problem with cutting the search off at an arbitrary point. The longer time you spend, the stronger the AI.
• It's embarassingly parallel, so you could have a few worker threads running the simulations on their own copies of the board on different cores.

Disadvantages:

• There's no absolute guarantee of finding the best or winning move as is the case in an exhaustive search, although the evaluation of positions in MC converges slowly to minimax.
• In games with high branching factor or when supplying insufficient search time to the algorithm, performance can degrade. Monte Carlo Tree Search uses additional techniques beyond the pure MC method described here to help minimize the search space and is the algorithm behind Google's DeepMind victories in Go.

---

Here's a snippet from a MC function for a simple Connect 4 game (source) to give a sense of how straightforward a basic implementation is:

/**
 * drop pieces on a board randomly until the game reaches a terminal state
 *
 * @param connect4 *c4 a pointer to the game
 */
void c4rand_game(connect4 *c4) {
    while (!c4just_won(c4) && !c4full(c4)) {
        c4move(c4, rand() % c4->cols);
    }
}

/**
 * runs a simulation from current position to determine the best move
 *
 * @param connect4 *c4 a pointer to the game
 * @param simulations the number of simulations to attempt per move
 * @return the column of the best move or -1 if none found
 */
int c4simulate(connect4 *c4, int simulations) {
    int i, j; 
    double ratio;
    double best_ratio = 0;
    int best_move = -1;

    for (i = 0; i < c4->cols; i++) {
        int wins = 0;
        int losses = 0;

        for (j = 0; j < simulations; j++) {
            connect4 cpy = c4cpy(c4);
            c4move(&cpy, i);
            c4rand_game(&cpy);

            if (c4just_won(&cpy)) {
                (c4->ply & 1) == (cpy.ply & 1) ? losses++ : wins++;
            }
        }

        ratio = losses > 0 ? (double)wins / losses : wins;

        if (ratio > best_ratio) {
            best_ratio = ratio;
            best_move = i;
        }
    }

    return best_move;
}

Answer 4

You could use a Neural Net, you'd just need to create a genetic algorithm to train it. No need to collect any data, just have it continuously play against existing bots.

The only problem I can see with this approach is that it's more of an approximation rather than the actual solution. You'd also need to give it enough of a degree of freedom so that it can adapt to any arbitrary strategy played.

If your approach is to have it be a normal bot, though I think this would work fine.