我想通过引入深度来限制搜索级别，将无与伦比的tic-tac修改为5乘5块。有什么建议吗？

Question

这是极大极小算法的代码片段。对于一个5乘5的矩阵来说，这似乎要花很多时间。我想引入一个变量来跟踪递归的深度并限制它。以下是完整代码的链接:http://ideone.com/e.js/pyFHRu

int MiniMax(char _board[25], player _player) {
    int best_val = -INFINITY, index = 0;
    std::list<int> move_list;
    char best_moves[25] = {0};
    generate_moves(_board, move_list);
    while(!move_list.empty()) {
        _board[move_list.front()] = _player.symbol;
        cSymbol = _player.symbol;
        int val = MinMove(_board, _player);
        if(val > best_val) {
            best_val = val;
            index = 0;
            best_moves[index] = move_list.front() + 1;
        } else if(val == best_val) {
            best_moves[++index] = move_list.front() + 1;
        }
        _board[move_list.front()] = 0;
        move_list.pop_front();
    }
    if(index > 0) {
        index = rand() % index;
    }
    return best_moves[index];
}

// finds best move for 'min player'
int MinMove(char _board[25], player _player) {
    int pos_value = evaluate_position(_board, _player);
    if(pos_value != -1) {
        return pos_value;
    }
    int best_val = +INFINITY;
    std::list<int> move_list;
    generate_moves(_board, move_list);
    while(!move_list.empty()) {
        _player.symbol == 'X' ? cSymbol = 'O' : cSymbol = 'X';
        _board[move_list.front()] = cSymbol;
        int val = MaxMove(_board, _player);
        if(val < best_val) {
            best_val = val;
        }
        _board[move_list.front()] = 0;
        move_list.pop_front();
    }
    return best_val;
}

// finds best move for 'max player'
int MaxMove(char _board[25], player _player) {
    int pos_value = evaluate_position(_board, _player);
    if(pos_value != -1) {
        return pos_value;
    }
    int best_val = -INFINITY;
    std::list<int> move_list;
    generate_moves(_board, move_list);
    while(!move_list.empty()) {
        _player.symbol == 'X' ? cSymbol = 'X' : cSymbol = 'O';
        _board[move_list.front()] = cSymbol;
        int val = MinMove(_board, _player);
        if(val > best_val) {
            best_val = val;
        }
        _board[move_list.front()] = 0;
        move_list.pop_front();
    }
    return best_val;
}

Answer 1

如果您已经在使用较小的深度，那么您必须计算启发式方法。启发式是介于 -1 和 1 之间的值，显示位置评估。如果你的深度为 10（你计算 10 层），那么当你到达评估的最终位置（深度为 0 或有人赢了）时，你需要计算启发式方法。

因此，我们可以达到具有有限最大深度的MiniMax算法，如果游戏未获胜，您可以使用启发式函数计算结果位置的评估。如果您想使用启发式算法消除评估树中看似无用的分支，以进一步优化评估时间，那么您可以使用Alpha Beta修剪，在这里和这里查看更多信息。