algorithm - 如何将威胁空间搜索添加到我的井字游戏算法中？

Question

(Tic-Tac-Toe:2 人游戏(玩家 x 和玩家 o)在 15x15 的棋盘上，首先形成一串 5 颗棋子的玩家获胜)

More description

所以我实现了一个井字游戏算法，它使用简单的 alpha beta 修剪..

这是我目前所拥有的:

def ab_minimax(state):
    max_position, max_value, alpha, beta = None, None, float('-inf'), float('inf')
    positions = getAvailablePositions()

    for position in positions:
        temp = next_state(state, position)
        value = self.ab_min_move(temp, 3, alpha, beta)

        if max_value < value:
            max_position = position
            max_value = value

    return max_position

def ab_max_move(state, depth, alpha, beta):
    if game_ended(state) or depth == 0:
        return get_score(state)

    value = float('-inf')

    positions = getAvailablePositions()

    for position in positions:
        temp = next_state(state, position)
        value = max(value, self.ab_min_move(temp, depth-1, alpha, beta))

        if value >= beta:
            return value

        alpha = max(alpha, value)

        if alpha >= beta:
            break

    return value

def ab_min_move(state, depth, alpha, beta):
    if game_ended(state) or depth == 0:
        return get_score(state)

    value = float('inf')

    positions = getAvailablePositions()

    for position in positions:
        temp = next_state(state, position)
        value = min(value, ab_max_move(temp, depth-1, alpha, beta))

        if value <= alpha:
            return value

        beta = min(beta, value)

        if alpha >= beta:
            break           

    return value

这工作正常，但显然代理返回移动需要太多时间..

然后我想到了威胁空间搜索的想法，它基本上旨在放置“威胁”。

在这个井字游戏中，威胁是攻击像“.ooo”这样的序列。 “呜呜呜。” (如果我是玩家 o)

问题是，我不知道我应该把这个威胁空间搜索放在我的哪里

alpha beta 函数....

我很确定这个想法是将威胁空间搜索与原始 alpha beta minimax 相结合

算法，，，但我不确定应该在哪里以及如何完成...

谁能给我一些解释或非常简短的伪代码..？

谢谢!

Answer 1

这里的另一个想法是定位你的 minimax 搜索，也就是说，如果你的网格被稀疏地占用，那么不需要在整个网格上评估 mini-max 搜索，只在已经占用的下一个位置评估 mini-max地区。就像在游戏开始时你可以只考虑 5*5 的网格作为你的状态空间而不是 15*15 的网格，这个小的优化可以为你节省很多时间。随着网格被填满，您可以看到有效状态本身的数量减少了，因此您的算法将保持一样快。