1

我正在用 javascript 编写井字游戏。我完成了 GUI 等,但我仍然对 AI 有问题。我使用 Alpha-beta-Prune 来找到获胜的动作。但是,我的代码从来没有给出可以赢得比赛的动作。我做了很多研究,但仍然不知道我的代码有什么问题。你们能在这里看看我的主要人工智能部分吗?我的想法是创建一个存储移动的二维数组:1 是人类,-1 是 AI,0 是空的。初始化调用: var test = getBestMove(-1); `

获得最佳移动功能:

function getBestMove(player)  {

    var alpha    = -maxValue;
    var beta     =  maxValue;

    var bestScore = -maxValue;
    var bestMove  = -1;

    for (var r = 0; r < boardSize; ++r)
    {
        for (var c = 0; c < boardSize; ++c)
        {
            if (gameArray[r][c] === 0)
            {
                gameArray[r][c] = player;
                var score = alphaBeta(gameArray, alpha,beta, r * boardSize + c, player);
                gameArray[r][c] = 0;

                if (score > bestScore)
                {
                    bestScore = score;
                    bestMove = r * boardSize + c;
                }
            }
        }
    }
    console.log(bestScore);
    return bestMove;
}

阿尔法-贝塔搜索:

// 1: human
// -1: AI
// 0: empty
function alphaBeta(board, alpha, beta,lastMove, player) {    
    var bestValue;
    //check if the last move make a win
    //checkwin return the winner / 0 if no winner
    var win = checkwin(board, 
                   Math.floor(lastMove / boardSize), 
                   lastMove % boardSize);

    if (win === - 1){
        return 1000;
    }
    else if (win === 1){
        return -1000;
    }
    else if (checktie(board) === true){
        //console.log(win);
        return 0;
    }
    else{
        //return evaluation(board);
    }
    if (player === -1) 
    {
        bestValue = alpha;
        // Recurse for all children of node.
        for (var r = 0; r < boardSize; r++)
        {
            for (var c = 0; c < boardSize; c++)
            {
                if (board[r][c] === 0)
                {            
                    board[r][c] = player;
                    var childValue = alphaBeta(board, bestValue, beta,r*boardSize+c, -player);
                    board[r][c] = 0;
                    bestValue = Math.max(bestValue, childValue);
                    if (beta <= bestValue) 
                    {
                        return bestValue;
                    }
                }
            }
        }
    }
    else {
        bestValue = beta;       
        // Recurse for all children of node.
        for (var r = 0; r < boardSize; r++)
        {
            for (var c = 0; c < boardSize; c++)
            {
                if (board[r][c] === 0)
                {
                    board[r][c] = player;
                    var childValue = alphaBeta(board, alpha, bestValue,r*boardSize+c, -player);
                    board[r][c] = 0;
                    bestValue = Math.min(bestValue, childValue);
                    if (bestValue <= alpha)
                    {
                        return bestValue;
                    }
                }
            }
        }        
    }
    return bestValue;
}

我没有使用评估功能,因为我认为 alpha-beta 应该能够在没有它的情况下找到胜利。

4

1 回答 1

1

我发现了问题,这与算法无关,而是与我的实现有关:由于人工智能总是在人类之后行动,所以 if (player === -1) bestValue = beta; 如果 (player === 1) bestValue = alpha;

第二个错误,子移动是其他玩家的,所以:board[r][c] = -player; 在任何地方

这是游戏的完整版本:www.neokites.com/gomoku/ 我希望这可以帮助某人。

于 2015-03-19T19:05:05.987 回答