I have an alpha beta interface and have implemented a tic tac toe class from it. For some reason my AI tends to occasionally make stupid moves (such as making a fork rather than blocking a 2 in a row) I was wondering if anybody can see where I went wrong:

StaticTicTacToe class:

class StaticTicTacToe:public IAlphaBetaPlayer
{
    private:
    bool isX;
    LABRandom r;
    public:
    StaticTicTacToe(bool isX):isX(isX),r(){}
    virtual double evaluate(IGameState &gs)
    {
        if (gs.ID()!=TICTACTOEID)
            return 0.0;
        char *s=(char*)gs.data;
        char tiars[8][3]={ {s[0],s[1],s[2]},{s[3],s[4],s[5]},{s[6],s[7],s[8]},
                           {s[0],s[4],s[8]},{s[2],s[4],s[6]},{s[0],s[3],s[6]},
                                {s[1],s[4],s[7]},{s[2],s[5],s[8]}};
        double ret=50.0;
        for (int i=0; i<8; i++)
        {
            //1st check for win
            if (tiars[i][0]==tiars[i][1]&&tiars[i][1]==tiars[i][2])
            {
                if (isX)
                {
                    if (tiars[i][0]=='X')
                        return 100.0;
                    else if (tiars[i][0]=='O')
                        return 0.0;
                }
                else
                {
                    if (tiars[i][0]=='O')
                        return 100.0;
                    else if (tiars[i][0]=='0')
                        return 0.0;
                }
            }
            else
            {
                int numx=0;
                int numo=0;
                if (tiars[i][0]=='X')
                    numx++;
                if (tiars[i][0]=='O')
                    numo++;
                if (tiars[i][1]=='X')
                    numx++;
                if (tiars[i][1]=='O')
                    numo++;
                if (tiars[i][2]=='X')
                    numx++;
                if (tiars[i][2]=='O')
                    numo++;
                if (isX)
                {
                    if ((s[0]=='O'||s[2]=='O'||s[6]=='O'||s[8]=='O')&&s[4]!='X')
                        return 0.01;//we will lose if they are smart...
                    if (numx==0&&numo==2)
                    {
                        return 0.01;
                    }
                    else if (numx==0&&numo==1)
                    {
                        ret-=(tiars[i][1]=='O'?1.0:3.0);
                    }
                    else if (numo==0)
                    {
                        if (numx==2)
                        {
                            if (tiars[i][1]==' ')
                                ret+=5.0;
                            else
                                ret+=2.0;
                        }
                        if (numx==1)
                        {
                            if (tiars[i][1]==' ')
                                ret+=2.0;
                            else
                                ret+=1.0;
                        }
                    }
                }
                else
                {
                    if ((s[0]=='X'||s[2]=='X'||s[6]=='X'||s[8]=='X')&&s[4]!='O')
                        return 0.01;//we will lose if they are smart...
                    if (numo==0&&numx==2)
                    {
                        return 0.01;
                    }
                    else if (numo==0&&numx==1)
                    {
                        ret-=(tiars[i][1]=='X'?1.0:3.0);
                    }
                    else if (numx==0)
                    {
                        if (numo==2)
                        {
                            if (tiars[i][1]==' ')
                                ret+=5.0;
                            else
                                ret+=2.0;
                        }
                        if (numo==1)
                        {
                            if (tiars[i][1]==' ')
                                ret+=2.0;
                            else
                                ret+=1.0;
                        }
                    }
                }
            }
        }
    }
    virtual double negEvaluate(IGameState &gs)
    {
        isX=!isX;
        double ret=evaluate(gs);
        isX=!isX;
        return ret;
    }
    virtual GameMove *getMoves(IGameState &s, int &len)
    {
        if (s.ID()!=TICTACTOEID)
            return NULL;
        GameMove *ret;
        len=0;
        const char *sd=(const char*)s.data;
        int ind[9]={0,1,2,3,4,5,6,7,8};/* THIS IS COMMENTED OUT BECAUSE IT CAUSES A SIGSEG... WHY IS THAT?
        for (int i=0; i<9; i++)
        {
            int index=r.random<int>()%9;
            int tmp=ind[i];
            ind[i]=ind[index];
            ind[index]=tmp;
        }*/
        for (int i=0; i<9; i++)
        {
            if (sd[ind[i]]==' ')
            {
                GameMove *tmp=new GameMove[len+1];
                for (int i=0; i<len; i++)
                    tmp[i]=ret[i];
                tmp[len]=MOVE((isX?'X':'O'),i);
                if (len>0)
                    delete[]ret;
                ret=tmp;
                len++;
            }
        }
        return ret;
    }
    virtual GameMove *getTheirMoves(IGameState &s, int &len)
    {
        isX=!isX;
        GameMove *ret=getMoves(s,len);
        isX=!isX;
        return ret;
    }
    virtual int ply(){return 9;}
};

TicTacToeState class:

class TicTacToeState:public IGameState
{
    public:
    TicTacToeState()
    {
        char *board=new char[9];
        for (int i=0; i<9; i++)
            board[i]=' ';
        data=board;
    }
    virtual bool gameOver()
    {
        char *s=(char*)data;
        char tiars[8][3]={ {s[0],s[1],s[2]},{s[3],s[4],s[5]},{s[6],s[7],s[8]},
                           {s[0],s[4],s[8]},{s[2],s[4],s[6]},{s[0],s[3],s[6]},
                                {s[1],s[4],s[7]},{s[2],s[5],s[8]}};
        for (int i=0; i<8; i++)
        {
            if (tiars[i][0]==tiars[i][1]&&tiars[i][1]==tiars[i][2]&&tiars[i][0]!=' ')
                return true;
        }
        for (int i=0; i<9; i++)
        {
            if (s[i]==' ')
                return false;
        }
        return true;
    }
    virtual bool equals(IGameState &other)
    {
        if (other.ID()!=TICTACTOEID)
            return false;
        //I have not yet gotten around to optimizing this function (IE implementing rotation and reflection)
        char *o=(char*)other.data;
        char *us=(char*)data;
        for (int i=0; i<9; i++)
        {
            if (o[i]!=us[i])
                return false;
        }
        return true;
    }
    virtual int ID(){return TICTACTOEID;}
    virtual IGameState &execute(GameMove m)
    {
        //here's hoping its a TicTacToeMove!
        char player=*(char*)m;
        char pos=((char*)(m))[1];
        char *us=(char*)data;
        if (us[pos]==' ')
            us[pos]=player;
        return *this;
    }
    virtual IGameState &undo(GameMove m)
    {
        //here's hoping its a TicTacToeMove!
        char *move=(char*)m;
        char player=*move;
        char pos=move[1];
        char *us=(char*)data;
        if (us[pos]==player)
            us[pos]=' ';
        return *this;
    }
    virtual IGameState *clone()
    {
        TicTacToeState *ret=new TicTacToeState;
        char *retdata=new char[9];
        for (int i=0; i<9; i++)
            retdata[i]=((char*)data)[i];
        ret->data=retdata;
        return ret;
    }
    virtual void output()
    {
        char *s=(char*)data;
        cout<<s[0]<<'|'<<s[1]<<'|'<<s[2]<<endl<<"|||||"<<endl<<s[3]<<'|'<<s[4]<<'|'<<s[5]<<endl<<"|||||"<<endl<<s[6]<<'|'<<s[7]<<'|'<<s[8]<<endl;
    }
};

IGameState interface:

typedef void *GameMove;
class IGameState
{
    public:
    void *data;
    virtual bool gameOver()=0;
    virtual bool equals(IGameState &)=0;
    virtual int ID()=0;
    virtual IGameState &execute(GameMove)=0;
    virtual IGameState &undo(GameMove)=0;
    virtual IGameState *clone()=0;
    virtual void output()=0;
};

IGamePlayer interface:

class IGamePlayer
{
    public:
    virtual GameMove getMove(IGameState&)=0;
};

IAlphaBetaPlayer abstract class:

class IAlphaBetaPlayer:public IGamePlayer
{
    private:
    MoveScore AlphaBeta(IGameState &current, int ply, bool us, double alpha, double beta)
    {
        MoveScore best={NULL,-101.0};
        if (ply<=0||current.gameOver())
        {
            best.score=(us?evaluate(current):negEvaluate(current));
            return best;
        }
        int numMoves;
        GameMove *moves=(us?getMoves(current,numMoves):getTheirMoves(current,numMoves));
        for (int i=0; i<numMoves; i++)
        {
            current.execute(moves[i]);
            MoveScore tmp=AlphaBeta(current,ply-1,!us,-beta,-alpha);
            current.undo(moves[i]);
            if ((-tmp.score)>best.score)
            {
                alpha=(-tmp.score);
                best.move=moves[i];
                best.score=alpha;
            }
            if (alpha>=beta)
            {
                return best;
            }
        }
        return best;
    }
    public:
    GameMove getMove(IGameState &g){
        return AlphaBeta(g,ply(),true,-101.0,101.0).move;
    }
    virtual double evaluate(IGameState &)=0;
    virtual double negEvaluate(IGameState &)=0;
    virtual GameMove *getMoves(IGameState &,int &)=0;
    virtual GameMove *getTheirMoves(IGameState &, int &)=0;
    virtual int ply()=0;
};

I really cannot see why it is that my TicTacToe AI that usually makes the best possible move should occasionally make a stupid move. Any ideas?

Recommended Answers

All 12 Replies

I have an alpha beta interface and have implemented a tic tac toe class from it. For some reason my AI tends to occasionally make stupid moves (such as making a fork rather than blocking a 2 in a row) I was wondering if anybody can see where I went wrong:

...

I really cannot see why it is that my TicTacToe AI that usually makes the best possible move should occasionally make a stupid move. Any ideas?

Well, with nothing to go on but the term 'stupid move' (not a clue what a fork is) and 300 lines of uncommented code with no indication of where to look, it's fairly time consuming to try to understand all the code you wrote just to answer this question.

Try pinpointing where the problem might be and make our life easier...

Sorry about my ambiguity. I think (but I am not sure) that the problem is in the evaluation function or in the implementation of my alpha beta algorithm. Here is an example of a game I played against it (I am 'O'):
X--
---
--- Perfect 1st move for Tic Tac Toe!

X--
-O-
--- A fair counter-attack that can ensure a tie

X--
-O-
--X Excellent play by the program, trying to set up a 'fork'

X--
OO-
--X I have to go in an edge to block the 'fork'


XX-
OO-
--X Why is X suddenly making such a stupid move? HERE IS THE PROBLEM!


XX-
OOO
--X I won... why wouldn't the program block me?

X--
---
--- Perfect 1st move for Tic Tac Toe!

To begin with, I wouldn't call it perfect.

Now, if you are sure that the alpha-beta works correctly (I didn't bother to check), then the problem must be in a statical evaluation. And it is there indeed. Hint: pay attention to the compiler warnings.

Ok, I improved it a bit (noticed a few other problems too, along with your suggestion) here is the resulting class:

class StaticTicTacToe:public IAlphaBetaPlayer
{
    private:
    bool isX;
    LABRandom r;
    public:
    StaticTicTacToe(bool isX):isX(isX),r(){}
    virtual double evaluate(IGameState &gs)
    {
        if (gs.ID()!=TICTACTOEID)
            return 0.0;
        char *s=(char*)gs.data;
        //get all possible three in a rows
        char tiars[8][3]={ {s[0],s[1],s[2]},{s[3],s[4],s[5]},{s[6],s[7],s[8]},
                           {s[0],s[4],s[8]},{s[2],s[4],s[6]},{s[0],s[3],s[6]},
                                {s[1],s[4],s[7]},{s[2],s[5],s[8]}};
        double ret=50.0;
        if ((s[0]=='O'||s[2]=='O'||s[6]=='O'||s[8]=='O')&&s[4]!='X'&&isX)
            return 0.01;//we will lose if they are smart...
        if ((s[0]=='X'||s[2]=='X'||s[6]=='X'||s[8]=='X')&&s[4]!='O'&&!isX)
            return 0.01;//we will lose if they are smart...
        for (int i=0; i<8; i++)//loop through the three in a rows
        {
            //1st check for win
            if (tiars[i][0]==tiars[i][1]&&tiars[i][1]==tiars[i][2]&&tiars[i][0]!=' ')
            {
                if (tiars[i][0]=='X')
                    return (isX?100.0:0.0);
                else
                    return (isX?0.0:100.0);
            }
            else//now find out how many of each player's marks are in each three in a row
            {
                int numx=0;
                int numo=0;
                for (int ii=0; ii<3; ii++)
                {
                    if (tiars[i][ii]=='X')
                        numx++;
                    if (tiars[i][ii]=='O')
                        numo++;
                }
                if (isX)
                {
                    if (numx==0&&numo==2)
                        ret-=0.50;//they will likely win!
                    else if (numx==0&&numo==1)
                        ret-=(tiars[i][1]=='O'?5.0:15.0);//they still have a claim on this three in a row!
                    else if (numo==0)
                    {
                        if (numx==2)//we have two in a row!
                        {
                            if (tiars[i][1]==' ')
                                ret+=15.0;
                            else
                                ret+=10.0;
                        }
                        if (numx==1)//we have a claim still
                        {
                            if (tiars[i][1]==' ')
                                ret+=2.0;
                            else
                                ret+=1.0;
                        }
                    }
                }
                else//see above!
                {
                    if (numo==0&&numx==2)
                        ret-=0.50;
                    else if (numo==0&&numx==1)
                        ret-=(tiars[i][1]=='X'?5.0:15.0);
                    else if (numx==0)
                    {
                        if (numo==2)
                        {
                            if (tiars[i][1]==' ')
                                ret+=15.0;
                            else
                                ret+=10.0;
                        }
                        if (numo==1)
                        {
                            if (tiars[i][1]==' ')
                                ret+=2.0;
                            else
                                ret+=1.0;
                        }
                    }
                }
            }
        }
        return ret;
    }
    virtual double negEvaluate(IGameState &gs)
    {
        isX=!isX;
        double ret=evaluate(gs);
        isX=!isX;
        return ret;
    }
    virtual GameMove *getMoves(IGameState &s, int &len)
    {
        if (s.ID()!=TICTACTOEID)
            return NULL;
        GameMove *ret;
        len=0;
        const char *sd=(const char*)s.data;
        int ind[9]={0,1,2,3,4,5,6,7,8};/*I STILL CANNOT GET THIS TO WORK!!!
        for (int i=0; i<9; i++)
        {
            int index=r.random<int>()%9;
            int temp=ind[i];
            ind[i]=ind[index];
            ind[index]=temp;
        }*/
        for (int i=0; i<9; i++)
        {
            if (sd[ind[i]]==' ')
            {
                GameMove *tmp=new GameMove[len+1];
                for (int ii=0; ii<len; ii++)
                    tmp[ii]=ret[ii];
                tmp[len]=MOVE((isX?'X':'O'),i);
                if (len>0)
                    delete[]ret;
                ret=tmp;
                len++;
            }
        }
        return ret;
    }
    virtual GameMove *getTheirMoves(IGameState &s, int &len)
    {
        isX=!isX;
        GameMove *ret=getMoves(s,len);
        isX=!isX;
        return ret;
    }
    virtual int ply(){return 9;}
};

Here is the resulting game (its even worse in my opinion):
X--
---
--- Same as before, strong opening, but mainly because I CANNOT get the shuffling to work!

X--
-O-
--- Again... nothing new

XX-
-O-
--- WHY?!

XXO
-O-
--- I block.

XXO
-O-
-X- What is my program thinking?

XXO
-O-
OX- Again... I win.

What is my program thinking?

I have no idea. You need to debug. For that, I'd recommend to provide an ability to call evaluate() directly with any given position. Call it with

XXO
-O-
-X-

and

XXO
-O-
X--

See which one gets better score. If the first one scores better, the error is in evaluate(). Trace its execution line by line. Otherwise, the error is in alpha-beta. Again, trace why the better scoring position gets rejected.

I tried your suggestion and it does seem like some of the bad moves are getting better scores. I just can't think of a better evaluator, do you have any ideas? Also why is the code that is commented out not working (its causing a sigseg)?

Also I have tried analysing the score part of the AlphaBeta function in my debugger and it always seems to return either 0, -0, or 100, but no values in between (this is in the getMove() function) I have not fully stepped through AlphaBeta itself because the iterative recursion makes it take for ever!

I just can't think of a better evaluator, do you have any ideas?

Use a magic square:

[b]
6 1 8 
7 5 3
2 9 4
[/b]

All directions add up to 15
If you see 2 consecutive chosen values and 1 not chosen that equal 15, the unchosen value will win.
By the way, the center position is the best opener. It has more ways to win than any other position.

I have implemented another evaluator, but I am having the trouble that AlphaBeta is returning a score of zero consistently until the final move. I cannot figure out why?!

I really cannot see what is wrong... the evaluator seems functional but I tried looking at the alphabeta algorithm and it seems to be working incorrectly. I really need this program to work.

I am sorry to keep reposting like this, but I have added some comments to my code:

class IAlphaBetaPlayer:public IGamePlayer
{
    protected:
    MoveScore AlphaBeta(IGameState &current, int ply, bool us, double alpha, double beta)
    {
        MoveScore best={NULL,-DBL_MAX};//default value: no move, -infinity
        if (ply<=0||current.gameOver())//this is the exit condition for rthe recursion
        {
            best.score=(us?evaluate(current):negEvaluate(current));//get the score of this state.
            return best;
        }
        int numMoves;
        GameMove *moves=(us?getMoves(current,numMoves):getTheirMoves(current,numMoves));//get a list of available moves
        for (int i=0; i<numMoves; ++i)//for each move
        {
            current.execute(moves[i]);
            MoveScore tmp=AlphaBeta(current,ply-1,!us,-beta,-alpha);//recurse using the state after the move, one less ply and swapped ab
            current.undo(moves[i]);//reset the game state
            if ((-tmp.score)>best.score)//this is the new best move as it makes their score less
            {
                alpha=(-tmp.score);//set the new alpha value
                best.move=moves[i];//save the move
                best.score=alpha;//and the score
            }
            if (alpha>=beta)//no matter what we will not be able to find a value greater than alpha and less than beta
            {
                return best;
            }
        }
        return best;
    }
    public:
    virtual GameMove getMove(IGameState &g){
        return AlphaBeta(*(g.clone()),ply(),true,-DBL_MAX,DBL_MAX).move;
    }
    virtual double evaluate(IGameState &)=0;
    virtual double negEvaluate(IGameState &)=0;
    virtual GameMove *getMoves(IGameState &,int &)=0;
    virtual GameMove *getTheirMoves(IGameState &, int &)=0;
    virtual int ply()=0;
};

Perhaps that will help you sort out the problem? I am still looking for it, but it is a stealthy one!

I decided to try converting the code to java because it has simpler inheritance, and it worked. My problem was a little bit too much shallow copying! Thanks for the help!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.