Null being returned?

[Labdabeta]

I have this code for AlphaBeta implementation and have created versions of the required interfaces that work perfectly (I have debugged them quite thoroughly). Unfortunately my algorithm keeps returning an empty vector and score of 0. Here is the code:

#include <vector>
#include <limits.h>
using namespace std;
typedef vector<unsigned char> GameMove;
struct MoveScore
{
    GameMove move;
    int score;
};
class IGameState
{
    public:
    virtual IGameState &execute(GameMove)=0;//execute the move
    virtual IGameState &undo(GameMove)=0;//undo the move
    virtual unsigned char *data()=0;
    virtual bool gameOver()=0;
};
class IGamePlayer
{
    public:
    virtual int evaluate(IGameState&)=0;//evaluate the move
    virtual vector<GameMove> getMoves(IGameState&)=0;
};
MoveScore AlphaBeta(IGameState &current, IGamePlayer &us, IGamePlayer &them, int ply, int low=-INT_MAX, int high=INT_MAX)
{
    //RND r;
    MoveScore best={GameMove(),0};
    if (ply==0||current.gameOver())
    {
        best.score=us.evaluate(current);
        return best;
    }
    vector<GameMove> moves=us.getMoves(current);
//    for (int i=0; i<moves.size(); i++)
//    {
//        int swap=r.RAND<int>()%moves.size();
//        GameMove tmp=moves[i];
//        moves[i]=moves[swap];
//        moves[swap]=tmp;
//    }
    for (int i=0; i<moves.size(); i++)
    {
        current.execute(moves[i]);
        MoveScore tmp=AlphaBeta(current,them,us,ply-1,-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;
}

Can anybody see where I went wrong?

[daviddoria]

I suggest simplying your entire code to about the same length as you have posted. You don't show us any non-virtual classes, and you don't show how AlphaBeta is constructed.

[Labdabeta]

Here is my TicTacToeTest.cpp:

#include <iostream>
#include "PathFindingAI.h"
class TicTacToeState: public IGameState
{
    private:
    unsigned char board[9];
    public:
    TicTacToeState(){board={' ',' ',' ',' ',' ',' ',' ',' ',' '};}
    virtual TicTacToeState &execute(GameMove m)
    {
        if (m.size()!=2||(m[0]!='X'&&m[0]!='O')||m[1]>8)
            return *this;
        board[m[1]]=m[0];
        return *this;
    }
    virtual TicTacToeState &undo(GameMove m)
    {
        if (board[m[1]]!=m[0])
            return *this;
        board[m[1]]=' ';
        return *this;
    }
    void output()
    {
        cout<<board[0]<<"|"<<board[1]<<"|"<<board[2]<<endl;
        cout<<"|||||"<<endl;
        cout<<board[3]<<"|"<<board[4]<<"|"<<board[5]<<endl;
        cout<<"|||||"<<endl;
        cout<<board[6]<<"|"<<board[7]<<"|"<<board[8]<<endl<<endl;
    }
    virtual unsigned char *data(){return board;}
    virtual bool gameOver()
    {
        unsigned char tiars[8][3]={ {board[0],board[1],board[2]},
                                    {board[3],board[4],board[5]},
                                    {board[6],board[7],board[8]},
                                    {board[0],board[4],board[8]},
                                    {board[2],board[4],board[6]},
                                    {board[0],board[3],board[6]},
                                    {board[1],board[4],board[7]},
                                    {board[2],board[5],board[8]}};
        for (int i=0; i<8; i++)
        {
            if (tiars[i][0]==tiars[i][1]&&tiars[i][1]==tiars[i][2]&&tiars[i][2]!=' ')
                return true;
        }
        for (int i=0; i<8; i++)
        {
            if (board[i]==' ')
                return false;
        }
        return true;
    }
};
class TicTacToePlayer: public IGamePlayer
{
    private:
    bool isX;
    public:
    TicTacToePlayer(bool isX):isX(isX){};
    virtual int evaluate(IGameState &s)
    {
        unsigned char tiars[8][3]={ {s.data()[0],s.data()[1],s.data()[2]},
                                    {s.data()[3],s.data()[4],s.data()[5]},
                                    {s.data()[6],s.data()[7],s.data()[8]},
                                    {s.data()[0],s.data()[4],s.data()[8]},
                                    {s.data()[2],s.data()[4],s.data()[6]},
                                    {s.data()[0],s.data()[3],s.data()[6]},
                                    {s.data()[1],s.data()[4],s.data()[7]},
                                    {s.data()[2],s.data()[5],s.data()[8]}};
        int ret=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)
                    return (tiars[i][0]=='X'?INT_MAX:-INT_MAX);
                else
                    return (tiars[i][0]=='X'?-INT_MAX:INT_MAX);
            }//then return [# of 3-in-a-rows left for me]-[# of 3-in-a-rows left for you]
            else
            {
                if (tiars[i][0]==' '||tiars[i][1]==' '||tiars[i][2]==' ')
                {
                    if (!(tiars[i][0]=='X'||tiars[i][1]=='X'||tiars[i][2]=='X'))//O can get this row!
                        (isX?ret--:ret++);
                    if (!(tiars[i][0]=='O'||tiars[i][1]=='O'||tiars[i][2]=='O'))//X can get this row!
                        (isX?ret++:ret--);
                }
            }
        }
        return ret;
    }
    virtual vector<GameMove> getMoves(IGameState &s)
    {
        vector<GameMove> ret;
        for (int i=0; i<9; i++)
        {
            if (s.data()[i]==' ')
            {
                GameMove m;
                m.push_back(isX?'X':'O');
                m.push_back(i);
                ret.push_back(m);
            }
        }
        return ret;
    }
};
int main()
{
    TicTacToeState board;
    TicTacToePlayer x(true),o(false);
    bool isX=true;
    while (!board.gameOver())
    {
        board.output();
        GameMove gm=AlphaBeta(board,(isX?x:o),(isX?o:x),9).move;
        board.execute(gm);
    }
    return true;
}

[Labdabeta]

This doesnt make sense. I have debugged this program countless times, as far as I can tell the value of best is always legit until the function returns! What is wrong?!

[raptr_dflo]

I've never been thrilled with the idea of complex data types as return values of functions. That may well just be personal preference, but I would either dynamically allocate an instance of the MoveScore structure, return the pointer to it, and free the allocated instance when done; or pass a reference to the structure as one of the arguments, so there's no local version of it at all in AlphaBeta().

Assuming that's not the problem, have you at least tried saving the return value of the function into a local variable, before trying to access one of the structure memebers? E.g.,

...
MoveScore ms = AlphaBeta(board, (isX?x:o), (isX?o:x), 9);
GameMove gm = ms.move;
board.execute(gm);
...

[Labdabeta]

I have tried that and I have tried saving the return value into a local variable before accessing any members. I have even tried converting the code to Java (which has a simpler inheritance structure) but no matter what AlphaBeta returns 'real' values up until the final 'unwind' at which point it returns null. I cannot figure this out!

[raptr_dflo]

Hmmmm. In your call to AlphaBeta() from main(), in the while (!board.gameOver()) {} loop, do you want to pass 9 as the number of plays to test each time? Or do you want to start with 9, and then pass in successively smaller values while (each time) you commit the optimal next play? I don't know whether this solves your problem, i.e., if you're getting a NULL best-move back from the first call.

[Labdabeta]

That shouldn't matter since the escape condition is if (ply==0||current.gameOver()) so it will only ever loop until the end of the game. I think the problem is that -tmp.score is never greater than 0 in my outer (first-non-recursive) call of alphabeta. I just cannot figure out a way to debug that without having to go through all of the recursive function calls.

[raptr_dflo]

Try filling 8 of the 9 spaces on the board, in such a way that neither player has won already, and then call AlphaBeta() with ply=1?

[Labdabeta]

Ok, I made some modifications and a few minor fixes (I have no clue why I was returning true from main?) Now it works but only with very few empty spaces, once the move is not obvious it goes back to returning null...

new TicTacToeTest.cpp:

#include <iostream>
#include "PathFindingAI.h"
class TicTacToeState: public IGameState
{
    private:
    unsigned char board[9];
    public:
    TicTacToeState(){board={' ',' ',' ',' ',' ',' ',' ',' ',' '};}
    TicTacToeState(char b[10])
    {
        for (int i=0; i<9; i++)
            board[i]=b[i];
    }
    virtual TicTacToeState &execute(GameMove m)
    {
        if (m.size()!=2||(m[0]!='X'&&m[0]!='O')||m[1]>8)
            return *this;
        board[m[1]]=m[0];
        return *this;
    }
    virtual TicTacToeState &undo(GameMove m)
    {
        if (board[m[1]]!=m[0])
            return *this;
        board[m[1]]=' ';
        return *this;
    }
    void output()
    {
        cout<<board[0]<<"|"<<board[1]<<"|"<<board[2]<<endl;
        cout<<"|||||"<<endl;
        cout<<board[3]<<"|"<<board[4]<<"|"<<board[5]<<endl;
        cout<<"|||||"<<endl;
        cout<<board[6]<<"|"<<board[7]<<"|"<<board[8]<<endl<<endl;
    }
    virtual unsigned char *data(){return board;}
    virtual bool gameOver()
    {
        unsigned char tiars[8][3]={ {board[0],board[1],board[2]},
                                    {board[3],board[4],board[5]},
                                    {board[6],board[7],board[8]},
                                    {board[0],board[4],board[8]},
                                    {board[2],board[4],board[6]},
                                    {board[0],board[3],board[6]},
                                    {board[1],board[4],board[7]},
                                    {board[2],board[5],board[8]}};
        for (int i=0; i<8; i++)
        {
            if (tiars[i][0]==tiars[i][1]&&tiars[i][1]==tiars[i][2]&&tiars[i][2]!=' ')
                return true;
        }
        for (int i=0; i<9; i++)
        {
            if (board[i]==' ')
                return false;
        }
        return true;
    }
};
class TicTacToePlayer: public IGamePlayer
{
    private:
    bool isX;
    public:
    TicTacToePlayer(bool isX):isX(isX){};
    virtual int evaluate(IGameState &s)
    {
        unsigned char tiars[8][3]={ {s.data()[0],s.data()[1],s.data()[2]},
                                    {s.data()[3],s.data()[4],s.data()[5]},
                                    {s.data()[6],s.data()[7],s.data()[8]},
                                    {s.data()[0],s.data()[4],s.data()[8]},
                                    {s.data()[2],s.data()[4],s.data()[6]},
                                    {s.data()[0],s.data()[3],s.data()[6]},
                                    {s.data()[1],s.data()[4],s.data()[7]},
                                    {s.data()[2],s.data()[5],s.data()[8]}};
        int ret=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)
                    return (tiars[i][0]=='X'?INT_MAX:-INT_MAX);
                else
                    return (tiars[i][0]=='X'?-INT_MAX:INT_MAX);
            }//then return [# of 3-in-a-rows left for me]-[# of 3-in-a-rows left for you]
            else
            {
                if (tiars[i][0]==' '||tiars[i][1]==' '||tiars[i][2]==' ')
                {
                    if (!(tiars[i][0]=='X'||tiars[i][1]=='X'||tiars[i][2]=='X'))//O can get this row!
                        (isX?ret--:ret++);
                    if (!(tiars[i][0]=='O'||tiars[i][1]=='O'||tiars[i][2]=='O'))//X can get this row!
                        (isX?ret++:ret--);
                }
            }
        }
        return ret;
    }
    virtual vector<GameMove> getMoves(IGameState &s)
    {
        vector<GameMove> ret;
        for (int i=0; i<9; i++)
        {
            if (s.data()[i]==' ')
            {
                GameMove m;
                m.push_back(isX?'X':'O');
                m.push_back(i);
                ret.push_back(m);
            }
        }
        return ret;
    }
};
int main()
{
    LABRandom r;
    TicTacToeState board("OXX      ");
    board.output();
    TicTacToePlayer x(true),o(false);
    bool isX=false;
    while (!board.gameOver())
    {
        GameMove gm=AlphaBeta(board,(isX?x:o),(isX?o:x),9,r).move;
        board.execute(gm);
        board.output();
    }
    return 0;
}

new PathFindingAI.h:

#include <vector>
#include <limits.h>
#include <LABRandom.h>
using namespace std;
typedef vector<unsigned char> GameMove;
struct MoveScore
{
    GameMove move;
    int score;
};
class IGameState
{
    public:
    virtual IGameState &execute(GameMove)=0;//execute the move
    virtual IGameState &undo(GameMove)=0;//undo the move
    virtual unsigned char *data()=0;
    virtual bool gameOver()=0;
};
class IGamePlayer
{
    public:
    virtual int evaluate(IGameState&)=0;//evaluate the move
    virtual vector<GameMove> getMoves(IGameState&)=0;
};
MoveScore AlphaBeta(IGameState &current, IGamePlayer &us, IGamePlayer &them, int ply, LABRandom r,int low=-INT_MAX, int high=INT_MAX)
{
    MoveScore best={GameMove(),0};
    if (ply==0||current.gameOver())
    {
        best.score=us.evaluate(current);
        return best;
    }
    vector<GameMove> moves=us.getMoves(current);
    for (int i=0; i<moves.size(); i++)
    {
        int swap=r.random<int>()%moves.size();
        GameMove tmp=moves[i];
        moves[i]=moves[swap];
        moves[swap]=tmp;
    }
    for (int i=0; i<moves.size(); i++)
    {
        current.execute(moves[i]);
        MoveScore tmp=AlphaBeta(current,them,us,ply-1,r,-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;
}

[Labdabeta]

I figured it out! I made the mistake of creating my code from pseudo-code. When I initialize best I should set it's score to -infinity, not to 0.