使用Alpha-Beta剪枝算法寻找井字棋的最佳移动

Question

尝试找到最佳走法和得分。我已经让我的程序可以正确返回游戏的得分，但我希望它也能够返回走法。我该如何修改我的代码来实现这一点？类似于这个和这个。请参见我失败的代码此处，如果游戏结束，应该返回走法而不是None。

def alphabeta(game_state, alpha, beta, our_turn=True):
    if game_state.is_gameover():
         return game_state.score()
    if our_turn:
        score = -9999
        for move in game_state.get_possible_moves():
            child = game_state.get_next_state(move, True)
            temp_max = alphabeta(child, alpha, beta, False) 
            if temp_max > score:
                score = temp_max
            alpha = max(alpha, score)
            if beta <= alpha:
                break
        return score
    else:
        score = 9999
        for move in game_state.get_possible_moves():
            child = game_state.get_next_state(move, False)
            temp_min = alphabeta(child, alpha, beta, True)
            if temp_min < score:
                score = temp_min
            beta = min(beta, score)
            if beta <= alpha:
                break
        return score

- PAS

---

天啊，你就是15年前的我。开发一款无敌的井字棋游戏是我进入编程世界的入门药物。我记得有一个难以理解的if...then语句树，我从未完全搞懂它。这是我第一次了解到可读代码的重要性。编辑：哦等等，alpha-beta剪枝？算了吧，你已经比我当时进步得多了。 - CivFan

哈哈！两年前开始接触，明年就要上高中了！ :) - PAS

Answer 1

你可以跟踪到目前为止最佳的移动方案，类似于以下内容：

    if game_state.is_gameover():
         return game_state.score(), None
    if our_turn:
        score = -9999
        for move in game_state.get_possible_moves():
            child = game_state.get_next_state(move, True)
            temp_max, _ = alphabeta(child, alpha, beta, False) # _ to disregard the returned move
            if temp_max > score:
                score = temp_max
                best_move = move
            alpha = max(alpha, score)
            if beta <= alpha:
                break
        return score, best_move

并且其他情况类似

- Julien

---

是的，但是当我想要在game_state.is_gameover()时返回得分和最佳移动对时，它还没有被定义。 - PAS

被定义为 None。 - Julien