Connect-four human-computer game

Task

Write an "AI" computer player for the Connect-four game.

Details

First, you'll need to copy the Connect-four code that I wrote. Do it like this (in Putty; don't forget the final "dot"):

cp /home/8/eckroth/connect-four/funcs.{o,h} .

You will need to make a new C++ file that has at least one function:

#include <iostream>
#include "funcs.h"
using namespace std;

int computerMove(char g[6][7])
{
    int column;

    // decide which column...

    return column; // return the choice
}

That's it. You can have just that one function or many more, depending on how complex your AI player is.

Note that in the grid g, your computer player is called 'C' and the human player is called 'H'.

Also note that the grid g is a 2D array where the first dimension is the row, second dimension is the column (g[i][j] is row i, column j), and g[0][0] is the top-left.

Compile the program like this (in Putty):

g++ main.cpp funcs.o

Hints

If you want to improve on the methods below, first think about how to combine them. So put the "random" example as a last resort, and try to find perhaps a "vertical run" or "win or block" move first.

Examples

Random

Completely random column choices:

#include <iostream>
#include <cstdlib>
#include "funcs.h"
using namespace std;

int computerMove(char g[6][7])
{
    int column;
    do {
        column = rand() % 7;
    } while(columnFull(g, column));

    return column;
}

Notice it's necessary to continue trying random column choices so long as the choice is a full column.

Left-right

Fill up the left first, then move right.

#include <iostream>
#include <cstdlib>
#include "funcs.h"
using namespace std;

int computerMove(char g[6][7])
{
    int column;
    for(column = 0; column < 7 && columnFull(g, column); column++);

    return column;
}

Win or block

Find a winning computer move first, or if that fails, find a move that blocks the human; if that fails, too, then just choose a random move.

#include <iostream>
#include <cstdlib>
#include "funcs.h"
using namespace std;

void copyGrid(char gridA[6][7], char gridB[6][7])
{
    for(int i = 0; i < 6; i++)
    {
        for(int j = 0; j < 7; j++)
        {
            gridB[i][j] = gridA[i][j];
        }
    }
}

// this function returns a column if the computer
// can win or can block a human win, otherwise
// returns -1

int checkMove(char g[6][7])
{
    char tmp[6][7];

    // can computer win with one move?
    for(int j = 0; j < 7; j++)
    {
        if(columnFull(g, j)) continue;

        copyGrid(g, tmp);
        // make move
        addToColumn(tmp, j, 'C');
        if(won(tmp, 'C'))
            return j;
    }

    // can human win with one move? block it
    for(int j = 0; j < 7; j++)
    {
        if(columnFull(g, j)) continue;

        copyGrid(g, tmp);
        // make move
        addToColumn(tmp, j, 'H');
        if(won(tmp, 'H'))
            return j;
    }

    return -1;
}

int computerMove(char g[6][7])
{
    int col;

    col = checkMove(g);
    if(col != -1) return col;

    // no good move; return a random one
    do {
        col = rand() % 7;
    } while(columnFull(g, col));

    return col;
}

Vertical runs

Look for vertical runs of 3 or 2 length; stop them if they are the human player's vertical runs, or continue them if they are the AI player's vertical runs.

#include <iostream>
#include <cstdlib>
#include "funcs.h"
using namespace std;

bool verticalRun(char g[6][7], int col, int length, char player)
{
    int count = 0;
    for(int i = 0; i < 6; i++)
    {
        if(g[i][col] == player) count++;
        else if(g[i][col] != ' ') break;

        if(count == length) break;
    }
    return (count == length);
}

int computerMove(char g[6][7])
{
    for(int length = 3; length > 1; length--)
    {
        // check defensive moves
        for(int j = 0; j < 7; j++)
        {
            if(!columnFull(g, j) && verticalRun(g, j, length, 'H'))
            {
                return j;
            }
        }

        // then check offensive moves
        for(int j = 0; j < 7; j++)
        {
            if(!columnFull(g, j) && verticalRun(g, j, length, 'C'))
            {
                return j;
            }
        }
    }

    int column;
    do {
        column = rand() % 7;
    } while(columnFull(g, column));
    return column;
}

Look two moves ahead

This example uses the "win or block" check first; if that doesn't give a good move, then the grid is copied 49 times so that every possible computer move followed by possible every human move is made in a copy of the grid, and then these copies are checked for "win or block". If "win or block" gives a good result in these hypothetical situations (two moves ahead), then the pretend computer move that preceded the pretend human move that preceded a good "win or block" move is chosen as the move.

#include <iostream>
#include <cstdlib>
#include "funcs.h"
using namespace std;

void copyGrid(char gridA[6][7], char gridB[6][7])
{
    for(int i = 0; i < 6; i++)
    {
        for(int j = 0; j < 7; j++)
        {
            gridB[i][j] = gridA[i][j];
        }
    }
}


// this function returns a column if the computer
// can win or can block a human win, otherwise
// returns -1

int checkMove(char g[6][7])
{
    char tmp[6][7];

    // can computer win with one move?
    for(int j = 0; j < 7; j++)
    {
        if(columnFull(g, j)) continue;

        copyGrid(g, tmp);
        // make move
        addToColumn(tmp, j, 'C');
        if(won(tmp, 'C'))
            return j;
    }

    // can human win with one move? block it
    for(int j = 0; j < 7; j++)
    {
        if(columnFull(g, j)) continue;

        copyGrid(g, tmp);
        // make move
        addToColumn(tmp, j, 'H');
        if(won(tmp, 'H'))
            return j;
    }

    return -1;
}

int computerMove(char g[6][7])
{
    int col;

    char tmp[6][7];
    char tmp2[6][7];

    // check first move
    col = checkMove(g);
    if(col != -1) return col;

    // make all possible computer moves followed by all possible human moves;
    // at this point, if the above code did not find a good move,
    // then we know that neither one move for the computer
    // nor one move for the human can result in a win
    for(int c = 0; c < 7; c++)
    {
        // if computer can make this move...
        if(!columnFull(g, c))
        {
            // make a copy of the grid, and make the move
            copyGrid(g, tmp);
            addToColumn(tmp, c, 'C');

            // consider all possible next human moves
            for(int h = 0; h < 7; h++)
            {
                // if human can make this move
                if(!columnFull(tmp, h))
                {
                    // make a copy of the grid, and make the move
                    copyGrid(tmp, tmp2);
                    addToColumn(tmp2, h, 'H');

                    // determine if there is a good move after these
                    // two pretend moves were made; if so, use
                    // the computer's pretend move as the current
                    // move
                    col = checkMove(tmp2);
                    if(col != -1) return c; // not col!
                }
            }
        }
    }


    // no good move; return a random one
    do {
        col = rand() % 7;
    } while(columnFull(g, col));

    return col;
}

Nasty tree search

This program looks a few moves ahead, trying every move (for both computer and human). So this program takes a few moments to decide, and looking just one more move ahead would basically make it unplayable (because it would take too long to look that far).

#include <iostream>
#include <cstdlib>
#include "funcs.h"
using namespace std;

int recursive_calls;

void copyGrid(char gridA[6][7], char gridB[6][7])
{
    for(int i = 0; i < 6; i++)
    {
        for(int j = 0; j < 7; j++)
        {
            gridB[i][j] = gridA[i][j];
        }
    }
}

void scoreMoves(char g[6][7], double scores[7], bool full[7], int depth)
{
    char hgrids[7][7][6][7]; // hypothetical grids
    bool recurse[7]; // which moves are recursable
    bool full_human[7][7];
    for(int i = 0; i < 7; i++)
    {
        recurse[i] = true;
        full[i] = false; // start with no full columns
        for(int j = 0; j < 7; j++)
        {
            full_human[i][j] = false;
        }
    }

    for(int ai = 0; ai < 7; ai++)
    {
        for(int human = 0; human < 7; human++)
        {
            copyGrid(g, hgrids[ai][human]);
        }
    }

    for(int ai = 0; ai < 7; ai++)
    {
        // if ai can't move in this column, skip it;
        // since all hgrids[ai][*] are equivalent, we just check the 0'th one
        if(columnFull(hgrids[ai][0], ai))
        {
            full[ai] = true;
            continue;
        }

        // otherwise, ai can move in this column,
        // so make the move in all hypothetical human-move grids
        for(int human = 0; human < 7; human++)
        {
            addToColumn(hgrids[ai][human], ai, 'C');
        }

        // if we won with this move, record this fact
        if(won(hgrids[ai][0], 'C'))
        {
            scores[ai] -= 1.0;
            recurse[ai] = false;
        }
        else if(tie(hgrids[ai][0]))
        {
            recurse[ai] = false;
            scores[ai] += 0.5;
        }
        else // else did not win with this move, so consider human moves
        {
            // slightly penalize the score ('cause we didn't win already)
            scores[ai] += 0.1;

            // make human moves
            for(int human = 0; human < 7; human++)
            {
                if(columnFull(hgrids[ai][human], human))
                {
                    full_human[ai][human] = true;
                }
                else
                {
                    addToColumn(hgrids[ai][human], human, 'H');

                    // ouch, human won; horrible score
                    if(won(hgrids[ai][human], 'H'))
                    {
                        scores[ai] += 1.0;
                    }
                    else if(tie(hgrids[ai][human]))
                    {
                        scores[ai] += 0.5;
                    }
                }
            }
        }
    }

    if(depth < 1)
    {
        // make recursive calls for non-winning, non-terrible scores
        // also ignore full columns
        for(int ai = 0; ai < 7; ai++)
        {
            if(full[ai] || !recurse[ai]) continue;

            for(int human = 0; human < 7; human++)
            {
                if(full_human[ai][human]) continue;

                // set recursive scores equal to this column's score
                double r_scores[7];
                for(int i = 0; i < 7; i++)
                {
                    r_scores[i] = scores[ai];
                }

                bool r_full[7];
                recursive_calls++;
                scoreMoves(hgrids[ai][human], r_scores, r_full, depth+1);

                // find best score of recursive call, and add it
                double min = 1000;
                for(int i = 0; i < 7; i++)
                {
                    if(r_scores[i] < min)
                    {
                        min = r_scores[i];
                    }
                }
                min /= 100.0;
                scores[ai] += min;
            }
        }
    }
}

int computerMove(char g[6][7])
{
    recursive_calls = 1;
    double scores[7] = {0.0};
    bool full[7];
    scoreMoves(g, scores, full, 0);

    cout << "recursive calls: " << recursive_calls << endl;

    for(int i = 0; i < 7; i++)
    {
        if(!full[i])
            cout << "scores[" << i << "] = " << scores[i] << endl;
    }

    // find minimum non-horrendous
    double min = 10000;
    int min_index = -1;
    for(int i = 0; i < 7; i++)
    {
        if(!full[i] && scores[i] < min)
        {
            min = scores[i];
            min_index = i;
        }
    }

    // if no good move, choose a random one
    int r;
    while(min_index == -1)
    {
        r = rand() % 7;
        if(!columnFull(g, r))
        {
            min_index = r;
        }
    }
    return min_index;
}