0.Search - 让电脑玩井字棋 ¶

就不介绍井字棋的规则了（

要让电脑与玩家完成井字棋游戏，我们需要让电脑能够做出最优的决策。这就需要我们用到 Minimax 算法。

我们将最后的结果用 value 表示，当 X 连成一条线，定义此时 value 为 1，而当 O 连成一条线，定义 value 为 -1，平局为 0。因此，X 玩家应该让 value 尽量大，O 玩家应该让 value 尽量小。这就是 Minimax 算法的核心思想。

Minimax 算法 ¶

芝士什么？¶

Minimax 算法是一种递归算法，它会遍历所有可能的走法，然后选择最优的走法。

注意，Minimax 算法使用的前提是，双方玩家都是 足够聪明 的，即双方玩家都会选择最优的走法。

例如，当电脑是 X 玩家时，电脑会遍历接下来所有的可能下法，随后选择所有情况中 value 最小值的最大值 ，即所有选择下 最坏情况最好的 （因为对手足够聪明，所以对手的选择对你而言一定是“最坏”的）

伪代码 ¶

def minimax(board):
    if game over in current board:
        return winner of current board

    for each possible move:
        score = minimax(new board)
        if score is better than best score:
            best score = score
    return best score

上述代码中，better 的定义取决于当前玩家是 X 还是 O。如果当前玩家是 X，那么 better 就是 max，如果当前玩家是 O，那么 better 就是 min。

优化 - Alpha-Beta Pruning ¶

为啥优化？¶

Minimax 算法的一个缺点是它会遍历所有可能的走法，这会导致算法的效率很低。因此，我们需要对其进行优化，这就是剪枝优化。剪枝优化的思想是，如果我们已经找到了一个更好的走法，那么就没有必要再去找更差的走法了。因此，我们可以在递归的过程中，记录当前最优的走法，然后在遍历的过程中，如果发现当前走法已经比最优走法差了，那么就可以停止遍历了。

代码 ¶

def minimax(board):
    """
    Returns the optimal action for the next player on the board.
    """
    if terminal(board):
        return None

    next_player = player(board)
    best_value = -2 if next_player == "X" else 2

    # Looping through all possible actions and
    # finding the most valuable (optimal) action
    for action in actions(board):
        new_value = find_value(result(board, action), best_value)

        if next_player == X:
            new_value = max(best_value, new_value)
        if next_player == O:
            new_value = min(best_value, new_value)

        if new_value != best_value:
            best_value = new_value
            optimal_action = action

    return optimal_action

def find_value(board, best_value):
    """
    Finds the best value for each recursive iteration. Optimized to use Alpha-Beta Pruning.
    """
    if terminal(board):
        return utility(board)

    next_player = player(board)
    value = -2 if next_player == "X" else 2

    # Loops through all possible actions and finds their corresponding value
    for action in actions(board):
        new_value = find_value(result(board, action), value)

        if next_player == X:
            if new_value > best_value:
                return new_value

            value = max(value, new_value)

        if next_player == O:
            if new_value < best_value:
                return new_value

            value = min(value, new_value)

    return value

以上代码中部分函数被省略。完整代码可以参考 tictactoe.py ，以及 runner.py 。