Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


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.

  • You cannot reply to this topic
13 replies to this topic

#1 cryobuzz75   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.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13884

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



#3 Druzil   Members   -  Reputation: 627

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"



#4 cryobuzz75   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: 13884

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.



#6 cryobuzz75   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.



#7 cryobuzz75   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: 13884

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.


#9 cryobuzz75   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.



#10 Druzil   Members   -  Reputation: 627

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.



#11 cryobuzz75   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: 13884

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.



#13 midnightvarmint   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: 13884

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