1

请帮助我理解为什么这不起作用。我不知道我的代码中是否存在错误，或者我的算法是否存在根本的逻辑缺陷。

我的算法基于 minimax，但我放弃了启发式评估函数以获得更简单的技术。由于简单的 3x3 tic tac toe 简单，我只想计算每个潜在动作的所有可能游戏结果，并选择具有最高“分数”的一个。我创建了一个有效移动的“顶级”向量以及它们相应的“分数”的匹配大小的向量 - 即针对该移动之后的每个可能结果：++ 获胜和 - 失败。

然而，我的移动分数向量变得奇怪的非对称值。尽管即使代码有效，但从逻辑上讲，是否有可能计算出导致最多赢和最少输的移动，对诸如分叉之类的简单策略视而不见？我的直觉说是的，但我还没有详细计算出数学。 

char board [9] = { '.','.','.','.','.','.','.','.','.' };

int com_turn(int turn) 
    {
    char player=COM; // keeps track of current player  

    cout<<"Computer turn. \n";  

    vector<int> moves = get_valid_moves(board); // top level move list
    vector<int> m_scores (moves.size(), 0);  // top level move scores

    for (int m=0; m < moves.size(); m++) // eval each top level move
    {
        board[moves[m]] = player; // do move

        evaluate(board, turn, &m_scores[m], player); 
        cout<< m_scores[m] <<' '; // for debugging

        board[moves[m]]='.'; // undo move
    }

    int bestmove;
    for (int i=0; i < moves.size(); i++) // find best score
    {
        bestmove = max(bestmove, m_scores[i]);
    }
    for (int i=0; i < moves.size(); i++) // match to best move
    {
        if (bestmove == m_scores[i])
        {
            bestmove = moves[i];
            break;
        }
    }

    board[bestmove]=COM; // finally make com move
    print_board();
}

vector<int> get_valid_moves(char *board) 
{
    vector<int> vmoves;
    for (int i=0; i < 9; i++)
    {
        if (board[i]=='.') vmoves.push_back(i);
    }
    return vmoves;
}


void evaluate(char *board, int turn, int *mscore, char player) 
{
    if (check_win(board)) 
    {
        (player==HUMAN)? *mscore -= 1: *mscore += 1;  
        return;  
    }
    if (turn > 9) return;

    vector<int> child_moves = get_valid_moves(board);
    if (child_moves.size() < 1) return;

    (player==COM)? player=HUMAN: player=COM; // switch player

    for (int m=0; m < child_moves.size(); m++) 
    {
        board[child_moves[m]] = player; // do move

        evaluate(board, ++turn, mscore, player);

        board[child_moves[m]]='.'; // undo move
    }
}
4

1 回答 1

2

如果您让评估返回分数而不是使用按引用返回，我认为您会看到问题出在哪里。

评估应该是极小化，但现在我认为由于加法和减法的副作用，它正在对叶节点进行一些奇怪的求和。

为什么总结分数不正确

假设我有董事会：

. . O
. . .
. X X

那么O只有一个动作，（块），因为如果O不成功，X的下一步将获胜。但是，有很多游戏路径从 O 开始进行其他移动，并且 O 获胜，例如：

O2 O1 O
.  .  X1
.  X  X

数字表示哪个动作先出现。

所以你看，仅仅得到总和不会给你正确的答案。

我建议将值向上传递树的原因是，这会迫使您写出节点处的分数是子节点的函数。现在在您的代码中，函数是总和，在 minimax 中，它是最小值或最大值，具体取决于玩家的回合。

于 2011-06-05T04:43:05.180 回答