C++ Minmax Failing

Question

I've been working on this for such a long time that it isn't funny anymore. I'm trying to implement Minmax on Tic Tac Toe and while I have gotten several versions of AI that make reasonable initial moves, I can never make one that never loses.

One of the issues which I cannot sort out is the heuristic value. It is currently returning as -10 on the first Minmax call, whereas it should be returning 0 (It should be able to draw no matter what happens).

Another issue is that it runs through 400,000 iterations, whereas 322,000 is the max and given early win situations, should even stop around 250,000.

Any help would be infinitely appreciated.

int MiniMax(TGameBoard _GameBoard)
{
    //Always goes for max of course, just expanded in case you wanted two AIs

    int iBestMove;      
    int iHeuristicReturned = 0;

    if (_GameBoard.ePlayer == COMPUTER)
    {
        iHeuristicReturned = MaxMove(_GameBoard, iBestMove);
    }
    else
    {
        iHeuristicReturned = MinMove(_GameBoard, iBestMove);
    }
    //cout<<"\nHeuristic is "<<iHeuristicReturned<<endl;

    g_iHeuristic = iHeuristicReturned;
    return iBestMove;
}

int MaxMove(TGameBoard _GameBoard, int& _iMove)
{
    //Logic
    //If its an end node, calculate the score
    //Otherwise, do minmax until the end node, and pass back the value
    //If returned value is greater than v, then pass the move back upwards
    ++g_iIterations;
    if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
    {
        int x;
        x = EvaluateStaticPosition(_GameBoard, MAX);
        return EvaluateStaticPosition(_GameBoard, MAX);
    }
    vector<int> moveList;
    GenerateMoveList(_GameBoard, moveList);
    int iNumMoves = moveList.size();
    int v = -10000;

    for(int i = 0; i < iNumMoves; ++i)
    {
        int iMove = moveList[i];

        _GameBoard.Set(iMove, CROSS);
        int opponentsBestMove;
        ++g_iDepth;
        int curRating = MinMove(_GameBoard, opponentsBestMove);
        --g_iDepth;
        if (curRating > v)
        {
            v = curRating;
            _iMove = iMove;
        }
        RetractMove(&_GameBoard, iMove);
    }
    return v;
}

int MinMove(TGameBoard _GameBoard, int& _iMove)
{
    ++g_iIterations;
    if (g_iIterations > 320000)
    {
        int x = 0;
    }

    if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
    {
        return EvaluateStaticPosition(_GameBoard, MIN);
    }

    vector<int> moveList;
    GenerateMoveList(_GameBoard, moveList);
    int iNumMoves = moveList.size();
    int v = 10000;

    for(int i = 0; i < iNumMoves; ++i)
    {
        int iMove = moveList[i];
        _GameBoard.Set(iMove, NAUGHT);
        int opponentsBestMove;
        ++g_iDepth;
        int curRating = MaxMove(_GameBoard, opponentsBestMove);
        --g_iDepth;
        if (curRating < v)
        {
            v = curRating;
            _iMove = iMove;
        }
        RetractMove(&_GameBoard, iMove);
    }
    return v;
}

int EvaluateStaticPosition(TGameBoard _GameBoard, EGoal _eGoal)
{
    if(_GameBoard.CheckWinner(_GameBoard, COMPUTER))
    {
        return 10;
    } 
    if(_GameBoard.CheckWinner(_GameBoard, PLAYER))
    {
        return -10;
    } 
    return 0;
}

The other related functions can be checked here, but I'm pretty sure they're okay. http://pastebin.com/eyaNfBsq

Yes I'm aware there's a few unnecessary parameters - After failing my own version I tried follow a tutorial off the internet. Unfortunately they're giving the same results.

I've been on this for 12 hours and it seems such a simple task, can't find out what's wrong

Answer 1

Following code may help you:

(Bonus: alphabeta with less than 8000 boards examined.)

#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>

enum class Square
{
    Empty,
    O,
    X
};

Square other(Square c) {
    switch (c) {
        case Square::O: return Square::X;
        case Square::X: return Square::O;
        default: assert(0); return Square::Empty;
    };
}

template <typename STREAM>
STREAM& operator << (STREAM& stream, Square c)
{
    switch (c)
    {
        case Square::Empty: stream << "."; break;
        case Square::X: stream << "X"; break;
        case Square::O: stream << "O"; break;
    }
    return stream;
}

class Board
{
public:
    Board() : board({{Square::Empty, Square::Empty, Square::Empty,
                    Square::Empty, Square::Empty, Square::Empty,
                    Square::Empty, Square::Empty, Square::Empty}})
    {}

    void display() const {
        for (int y = 0; y != 3; ++y) {
            for (int x = 0; x != 3; ++x) {
                std::cout << board[3 * y + x] << " ";
            }
            std::cout << std::endl;
        }
    }

    void play(unsigned int x, unsigned int y, Square c)
    {
        assert(x < 3);
        assert(y < 3);

        board[3 * y + x] = c;
    }
    void play(unsigned int offset, Square c)
    {
        assert(offset < 9);

        board[offset] = c;
    }

    bool isFull() const {
        return std::find(board.cbegin(), board.cend(), Square::Empty) == board.cend();
    }

    int computeScore(Square c) const
    {
        for (int i = 0; i < 3; ++i) {
            if (board[3 * i] != Square::Empty && board[3 * i] == board[3 * i + 1] && board[3 * i] == board[3 * i + 2]) {
                return board[3 * i] == c ? 1 : -1;
            }
            if (board[i] != Square::Empty && board[i] == board[i + 3] && board[i] == board[i + 6]) {
                return board[i] == c ? 1 : -1;
            }
        }
        if (board[4] == Square::Empty) {
            return 0;
        }
        if ((board[4] == board[0] && board[4] == board[8])
            || (board[4] == board[2] && board[4] == board[6])) {
            return board[4] == c ? 1 : -1;
        }
        return 0;
    }

    int minmax(Square c, unsigned int* counter, unsigned int* pos = NULL)
    {
        const int currentScore = computeScore(c);
        if (currentScore != 0 || isFull()) {
            if (counter) {++*counter; }
            return currentScore;
        }
        int bestScore = -10;

        for (unsigned int i = 0; i != 9; ++i) {
            if (board[i] != Square::Empty) { continue; }

            play(i, c);
            int score = -minmax(other(c), counter);
            if (bestScore < score) {
                bestScore = score;
                if (pos) { *pos = i; }
            }
            play(i, Square::Empty);
        }
        return bestScore;
    }

    int alphabeta(Square c, int alpha, int beta, unsigned int* counter, unsigned int* pos = NULL)
    {
        const int currentScore = computeScore(c);
        if (currentScore != 0 || isFull()) {
            if (counter) {++*counter; }
            return currentScore;
        }

        for (unsigned int i = 0; i != 9; ++i) {
            if (board[i] != Square::Empty) { continue; }

            play(i, c);
            int score = -alphabeta(other(c), -beta, -alpha, counter);
            if (beta <= score) {
                if (pos) { *pos = i; }
                play(i, Square::Empty);
                return score;
            }
            if (alpha < score) {
                alpha = score;
                if (pos) { *pos = i; }
            }
            play(i, Square::Empty);
        }
        return alpha;
    }

private:
    std::array<Square, 9> board;
};

int main()
{
    Board b;
    Square c = Square::X;

    while (b.computeScore(Square::X) == 0 && b.isFull() == false) {
        std::cout << c << " to play" << std::endl;
        b.display();
        unsigned int counter = 0;
        unsigned int pos;
        const int s = b.minmax(c, &counter, &pos);
        //const int s = b.alphabeta(c, -10, 10, &counter, &pos);
        b.play(pos, c);
        std::cout << "score for "<< c <<" = " << s << std::endl;
        std::cout << "#final boards examined = " << counter << std::endl;
        std::cout << "----------------" << std::endl;
        c = other(c);
    }
    std::cout << "Final score for X = " << b.computeScore(Square::X) << std::endl;
    b.display();

    return 0;
}

The count of "iterations" is the number of final board examined.