带Minimax和α-β剪枝的3D Tic Tac脚趾选择次优移动

Question

我正试图实现Minimax与阿尔法-β剪枝的一个游戏的3D Tic Tac脚趾。然而，该算法似乎选择了次优路径。

例如，你可以直接穿过立方体的中间，或者穿过一个单板就能赢得胜利。人工智能似乎选择的细胞将是最优的下一轮，而不是当前的回合。

我试着重新创建和玩我返回的启发式算法，但是我没有取得多大的进展。不管铺层情况如何，它似乎都有同样的问题。

代码是这里。

相关的部分是computers_move和think_ahead (以及'2‘变体，这些只是我在尝试一种稍微替代的方法)。

我希望这可能是我忽略的一些简单的事情，但据我所知，我不确定问题是什么。如果有人能说明这个问题，我会非常感激的。

def computers_move2(self):
    best_score = -1000
    best_move = None
    h = None
    win = False

    for move in self.allowed_moves:
        self.move(move, self.ai)
        if self.complete:
            win = True
            break
        else:
            h = self.think_ahead2(self.human, -1000, 1000)
        self.depth_count = 0
        if h >= best_score:
            best_score = h
            best_move = move
            self.undo_move(move)
        else:
            self.undo_move(move)

    if not win:
        self.move(best_move, self.ai)
    self.human_turn = True

def think_ahead2(self, player, a, b):
    if self.depth_count <= self.difficulty:
        self.depth_count += 1
        if player == self.ai:
            h = None
            for move in self.allowed_moves:
                self.move(move, player)
                if self.complete:
                    self.undo_move(move)
                    return 1000
                else:
                    h = self.think_ahead2(self.human, a, b)
                    if h > a:
                        a = h
                        self.undo_move(move)
                    else:
                        self.undo_move(move)
                if a >= b:
                    break
            return a
        else:
            h = None
            for move in self.allowed_moves:
                self.move(move, player)
                if self.complete:
                    self.undo_move(move)
                    return -1000
                else:
                    h = self.think_ahead2(self.ai, a, b)
                    if h < b:
                        b = h
                        self.undo_move(move)
                    else:
                        self.undo_move(move)
                if a >= b:
                    break
            return b
    else:
        diff = self.check_available(self.ai) - self.check_available(self.human)
        return diff

Answer 1

结果我的算法看起来很好。这个问题是由我的助手函数move和undo_move引起的。此外，根本的问题是我允许的一组移动。

我注意到，在探索树时，computer_plays中最外层循环中的移动次数大大减少。即使是第一次扫描，电脑和人类玩家允许的移动次数也会从27次下降到20次，然后是10次，最终会减少到5次。

原来暂时测试过的动作并没有被替换。因此，我将集合替换为一个标准列表，并在每次移动/撤消之后对列表进行排序，并且完全解决了我的问题。