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

回答1:

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.

回答2:

The rating of moves of Tic-tac-toe can be done using the Minimax algorithm. This algorithm aims at executing the move to evaluate, switch to the perspective of the opponent (which in turn tries to do the respective best move as well) and recursively evaluate moves until one of the players has won (which means that a leaf of the game tree has been reached).

Although implementation of the basic version of this algorithm is not incredibly difficult, understanding the approach is crucial; note that the 'artificial intelligence' basically consists out of hypothetically playing the entire game with all possible moves - it is not a heuristic but an exact algorithm. It can be refined using Alpha-Beta-Pruning to spare subtrees of the game tree which are not necessary for evaluation.