Negamax Ai for TicTacToe

Recommended Posts

cryobuzz75    105

Hi all,

I'm doing a simple TicTacToe so that I can implement a Negamax algorithm which I can later use for other abstract games. However I'm encountering problems whereby the AI doesn't play the best move, and it loses constantly. My suspect is the static evaluation function. Here it is:

	public int getScore()
{
int score = 0;

CellState state = CellState.Empty;

if ((cells[0] == cells[1] || cells[1] == cells[2]) && (cells[1] != CellState.Empty))
state = cells[1];

if ((cells[6] == cells[7] || cells[7] == cells[8]) && (cells[7] != CellState.Empty))
state = cells[7];

if ((cells[0] == cells[3] || cells[3] == cells[6]) && (cells[3] != CellState.Empty))
state = cells[3];

if ((cells[2] == cells[5] || cells[5] == cells[8]) && (cells[5] != CellState.Empty))
state = cells[5];

if (((cells[3] == cells[4] || cells[4] == cells[5]) && (cells[4] != CellState.Empty)) ||
((cells[1] == cells[4] || cells[4] == cells[7]) && (cells[4] != CellState.Empty)) ||
((cells[0] == cells[4] || cells[4] == cells[8]) && (cells[4] != CellState.Empty)) ||
((cells[2] == cells[4] || cells[4] == cells[6]) && (cells[4] != CellState.Empty)))
{
state = cells[4];
}

if (state == currentPlayer)
score = getMaxScoreValue();

else if (state == currentPlayer.getOpponent())
score = -getMaxScoreValue();

return score;
}


Cells is just an array of size 9 that represent the board positions. CellState is just an enum with values {Empty(0), Player(1), Opponent(2)}. getmaxScoreValue just returns the highest score (65536),

Is this static function complete or am I missing other conditions?

Thanks,

C

Edited by cryobuzz75

Share on other sites
alvaro    21246

The evaluation function seems correct (although you only need to check cells[4] != CellState.Empty' once in that long condition). The problem might be that you need to check those conditions in every node of the tree, not just the leaves. Maybe you can show us your search function (I would call it NegaMax', but I don't know what you are calling it).

Share on other sites
DarrylStein    653

All your conditions are only checking if two adjacent cells containt the same state.  I assume you mean to be checking for lines as you are assigning the max score to this.

So they should be

if ((cells[0] == cells[1] && cells[1] == cells[2]) && (cells[1] != CellState.Empty))
state = cells[1];

the logical "and" replaces the logical "or"

Share on other sites
cryobuzz75    105

Here's my Negamax class:

public class Negamax
{
IBoard board;
int maxDepth;
private Move[] dummyMove = new Move[1];

public Move GetBestMove(IBoard board, int depth)
{
maxDepth = depth;
int alpha = -999999, beta = 999999;
Move[] newMove = new Move[1];

alphaBeta(board, depth, alpha, beta, newMove);

return newMove[0];
}

private int alphaBeta(IBoard board, int depth, int alpha, int beta, Move[] bestMove)
{
bestMove[0] = null;

if (depth == 0)
return board.getScore();

if (board.getWon() != 0)
return board.getScore();

List<Move> bestMoves = null;
List<Move> moves = board.getMoves();

if (depth == maxDepth)
{
bestMoves = new ArrayList<Move>();
bestMoves.clear();
}

int minimax = -board.getMaxScoreValue();
int val;

for (Move move : moves)
{
this.board = board.copy();
this.board.makeMove(move, true);

val = -alphaBeta(this.board, depth - 1, -beta, -alpha, dummyMove);
move.setScore(val);

if (val > minimax)
minimax = val;

if (depth == maxDepth)
{
if (val > bestMoves.get(0).getScore())
{
bestMoves.clear();
}
else if (val == bestMoves.get(0).getScore())
}
else
{
if (val > alpha)
alpha = val;
if (alpha >= beta)
return alpha;
}
}

if (depth == maxDepth)
{
int rnd = MathUtils.random(bestMoves.size() - 1);
bestMove[0] = bestMoves.get(rnd);
}

return minimax;
}
}


Share on other sites
alvaro    21246

All your conditions are only checking if two adjacent cells containt the same state.  I assume you mean to be checking for lines as you are assigning the max score to this.

So they should be

if ((cells[0] == cells[1] && cells[1] == cells[2]) && (cells[1] != CellState.Empty))
state = cells[1];

the logical "and" replaces the logical "or"

Ooops! I can't believe I missed that he was using the wrong operator. That's the first thing to fix. Then I wonder what board.getWon()' does, since it must be almost identical.

Share on other sites
cryobuzz75    105

This is getWon():

	public int getWon()
{
//If any winning row has three values that are the same (and not EMPTY),
//then we have a winner
for (byte c = 0; c < WINNING_POS.length; c++)
{
if ((cells[WINNING_POS[c][0]] != CellState.Empty) &&
(cells[WINNING_POS[c][0]] == cells[WINNING_POS[c][1]]) &&
(cells[WINNING_POS[c][1]] == cells[WINNING_POS[c][2]]))
{
return cells[WINNING_POS[c][0]].ordinal();
}
}

//Since nobody has won, check for a draw (no empty squares left)
byte empty = 0;
for (byte c = 0; c < cells.length; c++)
{
if (cells[c] == CellState.Empty)
{
empty++;
break;
}
}
if (empty == 0)
return 3;

//Since nobody has won and it isn't a tie, the game isn't over
return 0;
}
`

getScore checks for 2 in a line. Even if I change maxscore with eg, 100, the AI still plays bad.

Share on other sites
cryobuzz75    105

I changed the operands in getScore() as suggested, and now the AI looks like it's playing good.

So my question is: Why should getScore() check for 3 in a line?

Edited by cryobuzz75

Share on other sites
alvaro    21246

So my question is: Why should getScore() check for 3 in a line?

It doesn't have to! If your search is looking for 3 in a line, you can just return a losing score when it happens: Since the 3-in-a-line condition just appeared, it must be that the opponent of the player to move won.

Tic-tac-toe is such a small game that you don't need an evaluation function at all. You can always just explore the tree to the end.

Edited by Álvaro

Share on other sites
cryobuzz75    105

So I guess I need to do a Connect4 to test negamax with an evaluation function.

Share on other sites
DarrylStein    653

I changed the operands in getScore() as suggested, and now the AI looks like it's playing good.

So my question is: Why should getScore() check for 3 in a line?

You evaluation function should generally return a value for a win/draw/loss at the very least.  For most games this isn't very useful because you aren't searching terminal nodes. However it still needs to be there so that the search function returns a value when it does find a terminal node.

For instance you were returning a score when you detected a getWon.  But this score was meaningless as it would just try to ensure there was at least one adjacent symbol and not find an actual winning position.

So on top of scoring a win/loss/draw you can add other criteria such as in your initial version of the scoring that detected useful features (adjacent symbols).  So that non-terminal nodes that are search will return a useful evaluation.

So you can still test your negamax function on tic tac toe - but you would have to limit its depth so that you can see if the negamax parts are working correctly.  The tree is so small that without limiting the depth you are probably searching all the way to terminal nodes from the beginning.  Try limiting the depth to 3 or 4.

Share on other sites
cryobuzz75    105

Thanks for the insight. So basically I start the scoring by calling getWon() and return maxscore, -maxscore or 0 depending if the game is won, lost or drawn. If this is not the case, the evluation function will check of other combinations.

I will implement this in the connect4 I'm doing to make sure that negamax works fine before adding extensions to it.

Share on other sites
alvaro    21246

Yes, Connect Four is a much better game to learn alphabeta search. Checkers is also good.

Share on other sites

does anyone here knows how to measure the efficiency of negamax? sorry newbie here

Share on other sites
alvaro    21246

does anyone here knows how to measure the efficiency of negamax? sorry newbie here

What do you mean by "efficiency"? And why do you want to measure it?