翻译Deep Learning and the Game of Go（5）本书第二部分（第4章：使用树搜索来玩游戏）

第二部分 机器学习和游戏AI

 在第二部分中，您将学习经典游戏AI和现代游戏AI的组件。您将从各种树搜索算法开始，这些算法是做游戏AI和优化各种问题必不可少的工具。接下来，您将了解深度学习和神经网络，从数学基础开始，并进行许多实际的设计考虑。最后，你会得到一个关于强化学习框架的介绍，这是让你的游戏AI能够通过练习提升的框架。

当然，这些技术不只是用在游戏上，一旦你掌握了这些组件，你将有机会将它们用到任何领域

 

第 4 章 使用树搜索来玩游戏

这一章包括：

• 使用极小极大算法去找到最好的落子点
• 修剪极小极大树搜索以加快速度
• 应用蒙特卡洛树搜索到游戏中

假设你有两个任务：第一个是编写一个能下国际象棋的电脑程序..第二是编写一个可以在仓库中高效地挑选订单的程序。那这些程序有什么共同点吗？乍一看，共同点不多。但如果你退一步，用抽象思维去思考，你可以看到一些相似之处：

• 你有一系列的决定要做。在国际象棋中，你的决定是关于要移动哪个棋子。在仓库里，你的决定是关于下一步要拿起哪一件物品。
• 早期的决定都会影响我们未来的决定。在国际象棋中，提前移动一个棋子可能会让你的皇后在许多回合之后被攻击。在仓库里，如果你先去找17号货架上的一个小部件，你可能需要用各种方式回溯到99号货架之后。
• 在一系列步骤结束后，你可以评估一下有没有实现了目标。在国际象棋中，当你对局结束后，你就会知道谁赢了。在仓库里，你可以收集所有物品所花的时间。
• 可能序列的数量是很巨大的。下棋大概有种方法。在仓库里，如果你有20件东西要捡，就有20亿条可能的序列可供选择。

当然，它们的类似仅此而已。例如，在国际象棋中，你会与一个积极地试图识破你意图的对手周旋，而这在任何仓库里都不会发生。

在计算机科学中，树搜索算法是一种在许多可能决策序列中寻找可以导向最优结果的一个序列的算法。在这一章中，我们涵盖了树搜索算法，许多原则可以扩展到其他优化问题。我们从极小极大搜索算法开始，在该算法中，每个回合中两个互相对立的玩家之间会轮流切换，这种算法可以找到完美的落子序列，但它的速度太慢，因此无法应用到复杂的游戏。接下来，我们将研究两种技术，只搜索树的一小部分去获得有用的结果。其中之一就是剪枝：可以加快对搜索树部分的评估。为了进行有效地修剪，您需要在代码中引入关于问题的真实世界知识，当这个无法做到时，你可以应用蒙特卡洛树搜索（MCTS）。它是一种随机搜索算法，可以在没有任何领域特定代码的情况下找到一个好结果。

当您的工具包中使用了这些技术，您就可以开始构建可以下各种棋和各种纸牌游戏的AI了

4.1 将游戏进行分类

树搜索算法主要与你轮流玩的游戏相关，每个回合都有一组不关联的选项。许多棋盘游戏和纸牌游戏都符合这一描述。另一方面，树搜索不会帮助电脑打篮球，猜字谜，或魔兽世界。我们可以根据两个有用的特性进一步对棋盘和纸牌游戏进行分类：

 

• 确定性与非确定性-在确定性游戏中，游戏的过程只取决于玩家的决定。在非确定性博弈中，会涉及一个随机性元素，如打骰子或洗牌。
• 完全的信息与隐藏的信息——在完美的信息游戏中，两个玩家都可以随时看到完整的游戏状态；整个棋盘都是可见的，或者每个人出的的牌都在桌子上。在隐藏信息游戏中，每个玩家只能看到游戏状态的一部分，隐藏信息在纸牌游戏中很常见，每个玩家都会被处理几张牌，而不能选择其他球员持有的东西。隐藏信息游戏的部分吸引力在于根据其他玩家的游戏决定猜测他们的牌

在本章中，我们主要关注确定性的，有完全信息的游戏。在这种游戏的每一个回合中，理论上必有一个落子是最好的。没有运气和秘密成分；在你选择之前你就应该知道，你的对手可能会选择什么落子作为回应，以及在那之后你要下在哪里等等，直到比赛结束。从理论上讲，你应该把整盘对局在第一步的时候就计划好，而极大极小算法正是这样做的，从而能够有完美的发挥。

在现实中，国际象棋和围棋等经受了时间考验的游戏都有着大量的可能性。对人类来说，每个游戏似乎都有自己的生命，即使是计算机也不能一直计算到最后。

本章中的所有示例都包含了很少的游戏特定逻辑，因此您可以将它们适应于任何确定性的、有完全信息的游戏。要做到这一点，您可以遵循我们的goboard模块的模式在类中实现新的游戏逻辑，如Player、Move和GameState。Game State的基本功能是apply_move、legal_move、is_over和winner。我们已经实现了井字棋。

4.2 使用极大极小搜索法去预测你的对手

你如何去编写一个AI去决定在游戏中的下一步应该下在哪里？首先，你可以考虑人类是如何做出相同的决定。让我们从最简单的具有确定性和完全信息的游戏--井字棋开始。我们将要采用的技术名称是极小极大。这个术语是极小化和极大化的浓缩：你尽力想最大化你的局面评分，同时你的对手正尝试最小化你的局面评分时。你可以用一句话来总结算法：假设你的对手和你一样聪明。

让我们看看极小极大在实践中是如何使用的。看图4.1，想想下一步X应该下在哪里？

                                                 

这里没有任何把戏，X下在右下角就可以赢得对局。你可以把这个变成一个一般的规则：去下任何能够立即赢得对局的落子。这个规则永远不可能出错。你可以参照下面代码去实现这种规则

# 寻找必胜下法
def find_winning_move(game_state, next_player):
    for candidate_move in game_state.is_valid(next_player): 
    next_state = game_state.apply_move(candidate_move) 

    # 如果下到这里棋局结束且赢家就是你，就选择下在这里
    if next_state.is_over() and next_state.winner == next_player: 
       return candidate_move 
    return None

图4.2说明了该功能将评估的假定的棋盘局面。这种结构，在这种结构中，一个棋盘落子点会指向所有可能的后续行动，这就被称为一棵游戏树

 我们往回倒一步，你是怎么得到这个局面的？也许前面一步的局面看起来像图4.3。O天真地希望在底部连成三个棋子，但那只有在X配合你的时候才会成立，这就导出了一个推论：不要选择任何让你的对手可以获胜的落子点。

                             

实现大致如下： 

# 去除会让对方一步获胜的落子点
def eliminate_losing_moves(game_state, next_player): 
     opponent = next_player.other()
     possible_moves = [] #所有不会让对方一步获胜的合法落子点
     for candidate_move in game_state.legal_moves(next_player): 
         # 计算你如果下了这个点后棋盘盘面会怎么样
         next_state = game_state.apply_move(candidate_move) 
         # 看看会不会给你的对手带来胜利，如果不行就就加入到数组中
         opponent_winning_move = find_winning_move(next_state, opponent) 
         if opponent_winning_move is None: 
              possible_moves.append(candidate_move) 
     return possible_moves

现在，你知道你必须阻止你的对手进入一个胜利的局面。因此，你应该假设你的对手也会这样对你。考虑到这一点，你要怎么才能赢呢？看看图4.4中的棋盘。 

                            

如果你在下在中间，你就有两种方法可以连成三子：1和2，对手根本无法阻挡你获胜。于是我们可以这样描述这个一般原则：寻找一个对手无法阻止你取胜的落子点。这听起来很复杂，但是在已经编写的函数之上构建这个逻辑很容易。

# 寻找可以两步获胜的落子点，即对手无法阻止你获胜
def find_two_step_win(game_state, next_player): 
    opponent = next_player.other() 
    for candidate_move in game_state.legal_moves(next_player): 
        # 假定下了这步棋，去看看对手有无好的方法去阻止你获胜
        next_state = game_state.apply_move(candidate_move) 
        good_responses = eliminate_losing_moves(next_state, opponent)  
        if not good_responses: 
            return candidate_move 
    return None

你的对手会预料到你会这样做，并试图阻止这样的下法。现在你可以看到一个总的战略：

1 看看你下一步能不能赢。如果能赢，那就去下。

2 如果不能赢，就去看看你的对手下一步是否能赢。如果能的话，就去阻止它

3.如果也不能的话，看看你能不能在两步后取得胜利。如果能的话，那就去下吧。

4.如果还没有，那就看看你的对手能不能两步取胜。

请注意，所有三个函数都具有类似的结构。每个函数循环遍历所有有效的落子，并评估假定落子后的棋盘局面。此外，每个函数都建立在前一个函数的基础上，以模拟对手的反应。如果你归纳好这些函数，你就会得到一个总能确定最好的落子的算法。

4.3 一个极大极小算法的例子：解决井字棋

在上一节中，你研究了如何预测对手的一到两个动作落子。在这一节中，我们展示了如何去归纳这一策略，从而选择出好的举措。这个核心思想是完全相同的，但您需要灵活性，从而在未来看到任意数量的落子。

首先，让我们定义一个枚举类型，它代表一个游戏的三个可能的结果：输、赢或平局。这些可能性是相对于一个特定的玩家来定义的：一个玩家数，那另一个就是赢了。

import enum


# 游戏的三种状态
class GameResult(enum.Enum):
    loss = 1
    draw = 2
    win = 3

想象一下，你有一个函数best_result，它告诉你可以在该棋盘状态下获得的最佳结果。如果能保证一位棋手以任何顺序取胜，那么就不会太复杂，结果将会返回GameResult.Win。如果最佳结果是平局，该函数将返回GameResult.Draw。否则，它将返回Game Result.loss。如果您假设函数已经存在，那就很容易编写一个函数来选择一个落子：您可以循环所有可能的落子，然后调用best_result函数，并选择能导致您的结果最佳的落子。有可能不同的落子会导向相同的结果，在这种情况下，您可以从它们中随机选择一个落子去下。下面显示了如何实现这一点。

先在之前GameState类里加上获取所有合法点的方法

  # 获取所有合法落子点
  def legal_moves(self):
       moves = []
       for row in range(1, self.board.num_rows + 1):
           for col in range(1, self.board.num_cols + 1):
                move = Move.play(Point(row, col))
                if self.is_valid_move(move):
                    moves.append(move)
       return moves

然后设计一个使用极小极大算法的AI，对每一个合法的落子点，去判断对手在该点落子后的最好结果，根据结果放入到相应的集合里，若有必胜招法，就随机选一种，否则去看有无平局招法，有就随机一种，若都无就是随机的必输招法，其实这时就可以投降了，算法如下： 

# 使用极小极大算法的AI
class MiniMaxAgent(Agent):
    def select_move(self,game_state):
        winning_moves = []  # 赢棋落子点集合
        drawing_moves = []  # 平局落子点
        losing_moves = []  # 输棋落子点
        for possible_move in  game_state.legal_moves():
            next_state = game_state.apply_move(possible_move)
            opponent_best_result = best_result(next_state)  # 查看对手在我落子后的最好结果
            if opponent_best_result == GameResult.loss:  # 对手必输
                winning_moves.append(possible_move)
            elif opponent_best_result == GameResult.draw: # 对手最好是平局
                drawing_moves.append(possible_move)
            else:
                losing_moves.append(possible_move)
        # 有必胜招法，就随机选一种去下
        if winning_moves:
            return random.choice(winning_moves)
        elif drawing_moves:
            return random.choice(drawing_moves)
        else:
            return random.choice(losing_moves)

 现在的主要问题是如何实现best_result这个方法，可以像之前章节一样，先从游戏结束开始判断

# 得到游戏的最佳结果
def best_result(game_state):
    if game_state.is_over():
        if game_state.current_player == game_state.winner():
            return GameResult.win
        elif game_state.winner() is None:
            return GameResult.draw
        else:
            return GameResult.loss

如果你在中盘阶段，你需要往下搜索。到现在，所有模式就比较熟悉了。您首先要循环遍历所有可能的落子和计算下一个游戏状态，然后你必须假设你的对手会尽力反击你。要做到这一点，您可以调用best_result去获得这个新局面下你的对手的最佳结果，从而知道你的结果。在你所考虑的所有落子中，你去选择一个能为你带来最好结果的落子。下图展示了这个过程：

                        

你可以在上面best_result里加上以下代码

    best_result_so_far = GameResult.loss
    for candidate_move in game_state.legal_moves():
        next_state = game_state.apply_move(candidate_move)     # 获得如果落了这个子后的局面
        opponent_best_result = best_result(next_state)         # 对方的最好结果
        our_result = reverse_game_result(opponent_best_result) # 我的最好结果
        if our_result > best_result_so_far:        # 我当前的最好结果比默认好，所以更新最好结果
            best_result_so_far = our_result
    return best_result_so_far

 如果你把这个算法应用到一个简单的游戏中，比如井字棋，那么你会得到一个无法被击败的对手。.理论上，这种算法也适用于国际象棋、围棋或任何其他确定性的、具有完全信息地博弈。但实际上，这种算法对于任何一种游戏来说都太慢了

注：有关使用极大极小算法实现井字棋AI实现的所有代码我都放在这个网盘链接里https://pan.baidu.com/s/1l0C18DAOqXDGg3E_zP7q5Q