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

（Tic Tac Toe：一款2人游戏（X玩家和O玩家），在15x15棋盘上，由一个5个棋子组成的链子的玩家首先获胜）
More description
所以我实现了一个tic-tac-toe算法，它使用简单的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

这样做很好，但显然代理需要太多时间才能返回移动。。
然后我发现了威胁空间搜索的概念，它的基本目标是放置“威胁”。
在这个tic tac toe中，威胁是攻击序列，比如“.o o o.”、“xooo.”（如果我是玩家o）
问题是，我不知道我应该把这个威胁空间搜索放在我的
α-β函数….
我很确定这个想法是把威胁空间搜索和最初的α-β极小极大结合起来
算法，，，但我不确定应该在哪里以及如何做。。。
有人能给我一个解释或者简单的伪代码吗？
谢谢！

最佳答案

这里的另一个想法是将mini max搜索本地化，也就是说，如果网格被稀疏地占用，那么不需要对整个网格求值minimax搜索，只需要对已占用区域附近的下一个位置求值minimax就像在游戏开始的时候，你可以只考虑5*5网格作为你的状态空间，而不是15*15网格，这个小的优化可以节省你很多时间当网格被填充时，你可以看到有效状态的数量减少了，因此你的算法将保持同样的速度。