人工智能导论：蒙特卡洛搜索

第 8章 蒙特卡罗博弈方法 计算机博弈理论的研究希望计算机能够像人一样、思维、判断和推理，并能够 做出理性的决策。棋类博弈由于规则明确、竞技性高，且人类选手往往胜于计算机 等原因，在计算机博弈理论的研究过程中一直受到重要关注和深入的探讨，并促进 了计算机博弈理论的发展。传统的基于博弈树搜索和静态评估的博弈方法在国际象 棋、中国象棋等棋类项目中获得了明显的成功，该类项目的盘面估计与博弈树搜索 过程相对独立，棋子在盘面中的作用相对明确，且棋局中的专家规则相对较为容易 概括和总结。 然而传统的博弈理论在计算机围棋博弈中遇到了明显的困难：围棋具有巨大的 搜索空间；盘面评估与博弈树搜索紧密相关，只能通过对将来落子的可能性进行分 析才能准确地确定棋子之间的关系；与此同时，高层次的围棋知识也很难归纳，归 纳之后常有例外，并且在手工构建围棋知识和规则的过程中常会出现矛盾而导致不 一致性。这些独特的因素为围棋及拥有类似性质的计算机博弈问题研究带来了新的 挑战。 从 2006 年开始，计算机围棋博弈的相关研究有了跨越式的发展，基于蒙特卡罗 模拟的博弈树搜索算法获得了重要的成功，并开始逐步引领计算机博弈理论研究的 方向。在本章，我们将介绍蒙特卡罗博弈理论及其在围棋等棋类博弈中的应用。 8.1 基本概念 8.1.1 马尔科夫决策过程 马尔科夫决策过程是序贯决策过程的主要研究领域之一，一个序贯决策过程包 括以下几点： 1.所有的决策时刻点集； 2.系统的所有可能的状态集合； 3.可以采用的全体行动集合； 4.与状态和行动相关联的既得回报或费用集合； 5.与状态和行动相关联的转移概率的集合。 一般来讲，我们总认为决策者在开始做决策的时候这些量是已知的，在此基础 上，马尔科夫决策过程是一类特殊的序贯决策问题，其特点是可采用的行动集、既 得回报和转移概率只是依赖于当前的状态和选取的行动，而与过去的历史无关。一 个马尔科夫决策过程的主要组成包括：决策周期、状态、行动、转移概率和报酬。 作为决策者，所面对的问题根据系统的转移概率抓住特定的机会，适时的做出一系 列的行动或选择，以期达到决策者心中的某种最优化目标。由于受控制的系统在持 续发展，过去的决策可以通过状态的转移影响到当前的决策，一般来讲，当前一步 的最优选择不一定是全局最优的决策，必须要考虑系统在将来状态上的预期机会和 费用。 决策时刻与决策周期决策时刻与决策周期 选取行动的时间点被称为决策时刻，并用𝑇记录所有决策时刻的点集。𝑇是非负 实直线上的子集，它可以是有限点集、可列无限点集或者是连续集合。在𝑇为离散的 情况下，决策都是在决策时刻做出的；而在𝑇为连续集的情况下，系统可以连续的做 决策，也可以在某些随机点或某些事件发生时做决策，甚至由决策者选择时机做出 决策等。 对于离散时间问题，两个相邻的决策时刻被称为决策周期或者阶段，我们把有 限阶段的决策时刻集记为𝑇 = {0,1,2,…,𝑁}，而把无限阶段的决策时刻记为𝑇 = {0,1,2,…}。 状态与行动集状态与行动集 在每一个决策时刻上对系统的唯一描述符就是“状态” ，记博弈系统的所有可能 状态集合为𝑆，𝑆也被称为“状态空间” 。如果在任一个决策时刻，决策者所观察到的 状态为𝑖 ∈ 𝑆，则他可以在状态𝑖的可用行动集𝐴(𝑖)中选取行动𝑎 ∈ 𝐴(𝑖)，其中𝐴(𝑖)也称 为当前状态的“行动空间” 。令： 𝐴 = ⋃𝑖∈𝑆𝐴(𝑖) 并且假设𝑆和𝐴(𝑖)都不依赖于时刻𝑡，状态集合𝑆和行动集合𝐴(𝑖)可以是任意的有 限集合、可数的无限集合、有限维欧氏空间的紧致子集或者是完备可分度量空间上 的博雷尔（Borel）子集，除非特别声明，我们总考虑𝑆和𝐴(𝑖)均为离散集的情况。 行动的选取可以是确定性的选取一个，也可以在多个允许的行动中随机性地选 取。我们记 𝒫(𝐴(𝑖)) 为𝐴(𝑖)的博雷尔子集上的所有概率分布，记𝒫(𝐴)为𝐴的博雷尔子 集上的所有概率分布，随机选取行动就是选取一个概率分布𝑃(·) ∈ 𝒫(𝐴(𝑖))，其中， 选取行动𝑎 ∈ 𝐴(𝑖)的概率是 𝑃(𝑎)，如果这个分布是退化的，则为确定性地选择行动。 转移概率和报酬转移概率和报酬 对于任意一个决策时刻，在状态 𝑖采取行动𝑎 ∈ 𝐴(𝑖)之后将产生两个结果，一是 决策者获得报酬𝑟(𝑖, 𝑎)；二是下一个决策时刻系统所处的状态将由概率分布 𝑃(· |𝑖,𝑎) 决定。 报酬𝑟(𝑖, 𝑎)是定义在𝑖 ∈ 𝑆和𝑎 ∈ 𝐴(𝑖)上的实值函数，当𝑟(𝑖, 𝑎)为正值时，表示决 策者所获得的收入，当其为负值时，表示决策者所付出的费用。从模型的角度来看， 报酬𝑟(𝑖, 𝑎)是即时的，但是在这个决策周期内它是何时或如何获得的并不重要，在选 取行动后，模型只需知道它的值或期望值。实际上，报酬可以包括到下一个决策时 刻的一次性收入、持续到下一阶段的累积收入，或转移到下一个状态的随机收入等。 一般来讲报酬还依赖下一个决策时刻的状态𝑗，即𝑟(𝑖, 𝑎,𝑗)。此时，采取行动𝑎的期望 报酬值为： 𝑟(𝑖,𝑎) = ∑ 𝑗∈𝑆 𝑟(𝑖,𝑎,𝑗)𝑃(𝑗|𝑖, 𝑎) 上式中非负函数 𝑃(𝑗|𝑖, 𝑎)是下一个决策时刻系统转移到状态 𝑗的概率，函数 𝑃(· |𝑖,𝑎)被称为转移概率函数。需要注意的是，在一般的实际问题中，状态转移是可以 发生在两个决策时刻的中间的，但是在不影响决策的情况下，我们的模型依然适用。 通常我们假设： ∑ 𝑗∈𝑆 𝑃(𝑗|𝑖, 𝑎) = 1 我们把五重组{𝑇,𝑆,𝐴(𝑖),𝑃(· |𝑖,𝑎),𝑟(𝑖, 𝑎)}称为一个“马尔科夫决策过程”，其转 移概率和报酬仅仅依赖于当前的状态和决策者选取的行动，而不依赖于过去的历史。 这里我们把包括了最优准则的马尔科夫决策过程称为“马尔科夫决策问题” 。 8.1.2 围棋落子模型 由于围棋是一种策略性二人棋类游戏，棋手在相互对弈的过程中所下的每一步 棋，都是经过深思熟虑、精密决策的结果。在对弈时，棋手不仅要考虑当前所下棋 子取得的效果，也要照顾到长远的利益。同时，棋手在下棋的过程中只针对当前盘 面进行决策，对于同样的盘面，棋手不用去考虑其中经历的不同步骤。可以说，棋 手在下定一手棋后所能获得的收益，只与当前棋盘的状态和即将选取的行动有关， 而与以往的历史没有关系。所以围棋落子的过程应被看成马尔科夫决策过程。 我们知道， 马尔科夫决策过程可以用五重族 {𝑇,𝑆,𝐴(𝑖),𝑃(· |𝑖,𝑎),𝑟(𝑖, 𝑎)}表示， 围棋落子过程也不例外： 决策时刻𝑇：显然地，围棋是一个有限阶段的决策问题，在有限步对弈后，就能 看到决策的结果。设一盘棋的总行棋步数为𝑁 ，则在[1,𝑁]的时间内，黑白双方交替 进行决策。由于黑方先行，所以在奇数时刻黑方进行决策，而在偶数时刻白方进行 决策。 状态空间𝑆：记𝑠 = (𝐵(𝑚),𝑊(𝑛))为状态，其中向量𝐵(𝑚) = (𝑝𝑏1,𝑝𝑏2,…,𝑝𝑏