I have been teaching myself algorithms and I am stuck with the AlphaBeta AI algorithm. I want to test my knowledge of it with a TicTacToe simulation. The thing is I want it to be easy to modify for any two player game and I cannot figure out how to get it to return the best next move. Can anybody give me any pointers, or maybe an idea of how to make the abstract classes that will be used by my function? I am really stuck.

(1) Are you asking for advice concerning the AlphaBeta algorithm or (2)have you written code and you need help to progress further?

If (2), post the code you have written so far(using code tags, of course)..
If (1), get a good C++ book.

I have some code, but I am missing the meat and potatoes of the code (I think). Here is what I have in a header file called AlphaBeta.h:

#include <vector.h>
using namespace std;
class GameMove
{
    //what do i put here?
};
struct MoveScore
{
    GameMove move;
    int score;
};
class GameState
{
    public:
    virtual GameState &execute(GameMove)=0;//execute the move
    virtual GameState &undo(GameMove)=0;//undo the move
    virtual vector<GameMove> getMoves()=0;//get all possible moves
};
class GamePlayer
{
    public:
    virtual int evaluate(GameMove)=0;//evaluate the move
};
#define INT_MINVAL
#define INT_MAXVAL
template <unsigned int ply>
MoveScore AlphaBeta(GameState current, GamePlayer us, GamePlayer them, GameMove nullMove, int low=INT_MINVAL, int high=INT_MAXVAL)
{
    MoveScore best={nullMove,0};
    if (ply==0||current.getMoves().size()==0)
    {
        best.score=us.evaluate(current);
        return best;
    }
    vector<GameMove> moves=current.getMoves();
    for (int i=0; i<moves.size(); i++)
    {
        current.execute(moves[i]);
        MoveScore tmp=AlphaBeta<ply-1>(current,them,us,nullMove,-high,-low);
        current.undo(moves[i]);
        if (-tmp.score>best.score)
        {
            low=-tmp.score;
            best.move=moves[i];
            best.score=low;
        }
        if (low>=high)
            return best;
    }
    return best;
}

I also have a file called tictactoe.cpp and I know that I need to define the different interfaces but I do not know exactly how. I am also not sure that my alphabeta algorithm is correct.

This article has been dead for over six months. Start a new discussion instead.