Search code examples
algorithmartificial-intelligencetic-tac-toerate

Tic-tac-toe rate a board algorithm


I've implemented a tic-tac-toe with ai but now im facing one problem, how to rate a board of tic-tac-toe game ?

Maybe at start I will descript how it should work :

  1. We have n boards of tic-tac-toe game (with different variants)
  2. Our ai should rate which board is the best to move on/the worst for opponent
  3. Ai calculate move by minimax algorithm (done)

Problem is in 2. Is there any way to "rate" a board?

I want to say that i dont want anybody to write me a code, just to help me finding algorithm or something :)

Thanks for help guys!

Edit #1

Ok, i have a minimax to play a board, but how to rate many boards and choose which is the best. Maybe im not clearly say what i want so i will show it.

e = empty

 *   x | e | e      e | o | e
 *  ---+---+---    ---+---+---
 *   x | e | e      e | o | e
 *  ---+---+---    ---+---+---
 *   o | e | e      x | x | e

And now, my implementation of minimax algorith is just telling me where i should put my sign (lets say o) but I need to tell on which board, so how to use it to rate whole board to choose on which to play ?

Minimax code :

minimax : function(tempBoard,depth){
    if (CheckForWinner(tempBoard) !== 0)
        return score(tempBoard, depth);
    depth+=1;
    var scores = new Array();
    var moves = new Array();
    var availableMoves = Game.emptyCells(tempBoard);
    var move, possibleGame, maxScore, maxScoreIndex, minScore,minScoreIndex;

    for(var i=0; i < availableMoves.length; i++) {
        move = availableMoves[i];
        possibleGame = Game.getNewBoard(move,tempBoard);
        scores.push(Ai.minimax(possibleGame, depth));
        moves.push(move);
        tempBoard = Game.undoMove(tempBoard, move);
    }
    if (Game.turn === "ai") {
        maxScore = Math.max.apply(Math, scores);
        maxScoreIndex = scores.indexOf(maxScore);
        choice = moves[maxScoreIndex];
        return scores[maxScoreIndex];

    } else {
        minScore = Math.min.apply(Math, scores);
        minScoreIndex = scores.indexOf(minScore);
        choice = moves[minScoreIndex];
        return scores[minScoreIndex];
    }
}

Solution

  • Here is one formula with which you can rate the board:

    value = (10 * x3 + 3 * x2 + x1) - (10 * o3 + 3 * o2 + o1)
    

    where:

    • xN => number of rows/columns/diagonals with N x's on it and no o's
    • oN => number of rows/columns/diagonals with N o's on it and no x's

    This assumes max-player is X. You can change signs if its otherwise.