•      Sign In
• Create Account

# Negamax Ai for TicTacToe

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

13 replies to this topic

### #1cryobuzz75  Members   -  Reputation: 105

Like
0Likes
Like

Posted 04 March 2013 - 08:35 AM

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, 04 March 2013 - 08:36 AM.

### #2Álvaro  Crossbones+   -  Reputation: 19952

Like
0Likes
Like

Posted 04 March 2013 - 09:48 AM

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).

### #3Druzil  Members   -  Reputation: 653

Like
1Likes
Like

Posted 04 March 2013 - 08:28 PM

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"

### #4cryobuzz75  Members   -  Reputation: 105

Like
0Likes
Like

Posted 05 March 2013 - 01:40 AM

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();
bestMoves.add(moves.get(0));
}

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();
bestMoves.add(move);
}
else if (val == bestMoves.get(0).getScore())
bestMoves.add(move);
}
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;
}
}


### #5Álvaro  Crossbones+   -  Reputation: 19952

Like
0Likes
Like

Posted 05 March 2013 - 08:22 AM

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.

### #6cryobuzz75  Members   -  Reputation: 105

Like
0Likes
Like

Posted 05 March 2013 - 08:33 AM

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.

### #7cryobuzz75  Members   -  Reputation: 105

Like
0Likes
Like

Posted 05 March 2013 - 08:41 AM

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, 05 March 2013 - 08:41 AM.

### #8Álvaro  Crossbones+   -  Reputation: 19952

Like
0Likes
Like

Posted 05 March 2013 - 08:55 AM

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, 05 March 2013 - 08:55 AM.

### #9cryobuzz75  Members   -  Reputation: 105

Like
0Likes
Like

Posted 05 March 2013 - 02:01 PM

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

### #10Druzil  Members   -  Reputation: 653

Like
0Likes
Like

Posted 05 March 2013 - 09:40 PM

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.

### #11cryobuzz75  Members   -  Reputation: 105

Like
0Likes
Like

Posted 06 March 2013 - 01:41 AM

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.

### #12Álvaro  Crossbones+   -  Reputation: 19952

Like
0Likes
Like

Posted 06 March 2013 - 08:59 AM

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

### #13midnightvarmint  Members   -  Reputation: 103

Like
0Likes
Like

Posted 08 July 2013 - 10:35 AM

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

### #14Álvaro  Crossbones+   -  Reputation: 19952

Like
0Likes
Like

Posted 08 July 2013 - 11:58 AM

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?

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS