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 ¤t, 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?
