为什么我的 minimax 不工作

Question

我已经尝试修改我的算法以使其更好地工作，但我没有取得任何结果。我的问题是，在第一步之后，如果我有，例如：

  XX.
  OO.
  ...

计算机没有选择 0 2，而是选择了 1 2，有时会尝试去它不能去的位置。

我的代码：

#include "game.hpp"

pair<int,int> winner;
int m = INT_MAX;

pair<int,int> game::minimax(State ini) {
    int v = maxValue(ini);

    cout << v << endl;
    return winner;
}


int game::maxValue(State u){
    int check = u.getUtility();

    if( check % 700 == 0 ) {

        if( u.moves < m ) {
            winner = u.move;
            m = u.moves;
        }
        return check;
    }

    int v = INT_MIN;
    u.makeDescendents();

    while( !u.ls.empty() ) {
        v = max(v,minValue(u.ls.front()));
        u.ls.pop_front();
    }
    return v;
}

int game::minValue(State u) {
    int check = u.getUtility();

    if( check % 700 == 0 )
        return check;

    int v = INT_MAX;
    u.makeDescendents();

    while( !u.ls.empty() ) {
        v = min(v,maxValue(u.ls.front()));
        u.ls.pop_front();
    }
    return v;
}

为了更好地帮助我，我将一些变量的含义弄清楚：

winner: 就是电脑要移动的位置
u.moves：是搜索树上的深度，对于根是0
m: 应该保存较少深度状态的解，因为那样过滤解和计算机必须更接近解的移动。
检查：此时保存效用值以判断是否为终止状态
获胜效用为 700，平局为 0，失败效用为 -700
u.ls：子状态列表

还有一点，我认为使用 m 和 winner global 以及 return minimax 上的 global 是一个糟糕的解决方案，您能找到改进方法吗？

非常感谢。

Answer 1

首先，如果状态不是终端，u.getUtility() return 是什么？如果它 returns 0，那么 0 % 700 == 0 为真，所以它只是找到它扩展的第一步并选择它。由于我看不到 u.makeDescendents() 算法，我不能排除这种可能性。

如果不是这种情况，那么几乎可以肯定您的 u.getUtility() 函数假设它只会被同一个最大玩家调用。也就是说，如果 X 赢了，它是 returning 700，如果 X 输了，它是 -700。如果你运行双方都通过同一个 minimax，那么当你将 O 评估为 max 时，它仍在尝试找到 X 的胜利，因为这是唯一一次它将评估视为胜利。

如果是这种情况，修复很简单，根据状态确定轮到哪个玩家，return win/loss 评估就好像是那个玩家（通常总是在 TicTacToe 中输是因为你不能下棋而输掉比赛，你只能通过下棋来获胜，而前一个玩家下了最后一步）。

如果这些建议都不能解决问题，调试 minimax 问题的典型方法是一次深入一层地遍历博弈树，探索 return 已知无效评估的路径，直到您发现生成不正确值的点。然后你必须检查它以找出原因。这对于像井字游戏这样的小游戏来说是微不足道的，因为它只有 9 级深并且你可以获得完美的极小最大值，但对于任何非微不足道的游戏，你通常必须查看你的评估函数以确定差异发生在哪里.

为什么我的 minimax 不工作

Why my minimax is not working

c++

algorithm

artificial-intelligence

minimax