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

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

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"

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;
    }
}

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.

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.

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?

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.

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

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.