关于《游戏学导论》的研学记录与个人思考 - ( 11 )

• 参考资料：华中科技大学-熊硕《游戏学导论》（系列课程）
• 本系列博客中，未标注“思考”、“便签”的部分，多摘引、校饰自熊硕老师的课件原文。

十一、游戏中的人工智能·决策与搜索

由于人工智能在游戏中的应用广泛涉及到人工智能学科的相关知识，一节课的时间远远无法涵盖相关所有内容，仅概略性的介绍游戏中的人工智能在游戏中的两大最常见应用——决策与搜索。同样，这一课仍然是相对科普性的，也是本系列的最后一节课。之后的博客更新，笔者或将更多地围绕自身的游戏开发日志、优质游戏的拆解、相关文献与知识的学习等领域进行。

此外，需要注意，这一课程发布于2020年，距今已有六年之久，而近年来AI产业发展迅猛，则课程中部分信息或观点有可能已经不完全匹配当下的现状，读者需加以辨析！

人工智能是这个时代的热门话题，而桌面游戏与单机游戏是在所有行业领域中，最早使用人工智能的平台。

关于人工智能的简述

人工智能的基础

支撑学科与发展阶段：

支撑学科（时间线） * 哲学（BC428——Now） * 数学（AD800——Now） * 经济学（1776——Now） * 神经科学（1861——Now） * 心理学（1879——Now） * 计算机工程（1940——Now） * 控制论（1948——Now） * 语言学（1957——Now）

发展阶段（时间线） * 孕育期（1943——1955） * 诞生（1956） * 早期的热情（1952——1969） * 现实的困境（1966——1973） * 算法推进（1969——1979） * 工业化（1980——Now） * 神经网络（1986——Now） * 科学化（1987——Now） * 智能体（1995——Now）

人工智能学科的大致分类

其研究方向包括： * 图像处理 * 逻辑推论 * 数据优化 * 探索 * 自然语言处理 * 机器学习 * Class分类·函数近似分析·回归 * 聚类学习 * 强化学习 * 深度学习

目前游戏AI的背景

• 游戏AI的两种流派方向：
  • 电子游戏的AI（企业应用，以有趣为目的）
  • 桌游的AI（信息科学，以强大为目的）
• 学术论文一般以桌游和强度为研究要素。
• 这几年桌游AI不断增强，然后一一被Solved。
• 金字塔
  • DeepBlue vs Kasparov（1997）
  • Checker is solved（Schaeffer 2007）
  • ボンクラーズ vs 米长邦雄 (2012)
  • AlphaGO vs 柯洁 (2017)

机器学习的三种分类

• 监督式学习
  • 通过给予一个个正确的实例，并依此模式推测新的实例来对后续的正确判断进行学习（比如文字判断）
  • 输入空间X（判断材料），输出空间Y（判断结果）
  • 学习数据 L = {(x_i, y_i)}, x_i ∈ X, y_i ∈ Y
  • 输入对于未知的 x ∈ X，输出合适的 y ∈ Y
• 无监督学习
  • 不给予正确的个案，通过数据间的关系进行学习（比如聚类学习）
• 强化学习
  • 根据环境和行动方案，给予奖励或惩罚的刺激下，让对象逐步形成对刺激的预期，产生能获得最大利益的习惯性行为（机器人）

机器学习的日常应用

• 识别手写的汉字
• 识别表情
• 推断某说话声是由谁发出来的
• 检查欺诈垃圾邮件
• 检测服务器的异常或非法访问
• 预测游戏中的下一步
• 通过体检结果来判断人是否有病
• 其他各种日常中应用面非常广，也非常重要的技术

决策

从一个简单的问题开始

以《Akinator》（又称《网络天才》）为例，其可以对玩家提出一系列问题，并根据玩家的回答猜测到玩家心中所想的人物，可以引出决策树。

决策树（Decision Tree）

• 类似于流程图；
• 通过If-then规则集合决定输出；
• Eager learning（积极学习）的一种，需要事先进行学习，但是一旦学习后使用效率高；
• 决策树模型对人来说更容易理解，因此该模型常常被使用；
  • 也是最基础的一种人工智能模型；
• 主要在离散输出的情况下使用；
• 避免无意义的决策树：
  • 错误的决策
  • 冗余的决策
• 决策树的学习：
  • 考虑如何分割样本，才能使学习效果最佳。
  • 将杂乱不堪的熵（Entropy）进行定量化、最小化。

熵（Entropy）

• 以只有正例和负例的二分场合为例子

• 正例的占比记为 p₊，负例的占比记为 p₋

• 熵的计算公式： Entropy = −p₊log₂p₊ − p₋log₂p₋

• 示例：7例中正例占了4例，负例占3例

  • p₊ = 4/7，p₋ = 3/7
  • 计算： Entropy ≈ −0.571 × (−0.807) − 0.429 × (−1.222) ≈ 0.985

• 关键特性：

  • p 在接近 0 或者 1 的时候，熵就越接近于 0
  • 当 p 越接近 0.5，则熵越接近 1

信息增益

• 以某种条件，将数据集 S → {S_i} 进行分割，具体能减低多少的熵： $$ \text{Gain} = \text{Entropy}(S) - \frac{1}{|S|} \sum |S_i| \text{Entropy}(S_i) $$

• 如果将 S{○ ○ ○ ○ × × ×} → S1{○ ○ ○}, S2{○ × ××} 进行分割。

  • Entropy(S) = 0.985 高度混乱。
  • Entropy(S1) = 0 完全一致。
  • Entropy(S2) = −0.25 × (−2) − 0.75 × (−0.415) = 0.811 此部分依旧有混乱。
  • $\text{Gain} = 0.985 - \frac{3}{7} \times (0) - \frac{4}{7} \times (0.811) = 0.522$。

• 熵明显降低。

搜索

思考：人工智能是怎么去玩Puzzle和Game的？

游戏在处理信息时分为很多种，比如：单人、双人、多人游戏，或者信息完全公开（围棋）、信息不完全（DOTA2），或者零和（象棋）与非零和（战争——日常“游戏”），或者回合制与即时制（还有半即时制）。其中单人的、信息完全公开的、零和的、回合制的游戏最为简单。而之前不断强调“关注桌游”，是因为桌游往往是“多人的、信息完全公开的、零和的、回合制的”（当然有例外，这里只是一般结论）。

但是人工智能在思考这些游戏问题的时候有万变不离其宗的方法：准备一定的后手策略，基于某种算法评价所有的后手策略的价值，搜索所有的后手并找出最优解。这一方式简单粗暴，但非常计算机、非常有效。

状态（State）与行动（Action）

• 基于当前盘面所决定的必要信息被称为状态，对于可能的全部状态被称为状态空间。
• 导致状态发生变化的选择与博弈策略称为行动。
  • 这里的“发生变化”的状态不仅仅是指棋盘本身的状态，某些情况下包括自己的回合顺序、角色状态、持子状态的变化也算。
  • 状态空间越大，行动理论上就越难以抉择。

状态空间图

• 为了更好地进行行动，我们需要分析状态空间，寻找合适的表现方法。
• 使用计算机思维画出状态空间图：
  • 将状态用节点（Node）表示；
  • 将变化的行动操作用树枝（Edge）表示；
• 根据得到的状态空间图。我们开始寻找路径从起点到合适的终点

搜索树（游戏AI核心）

• 将搜索空间用树状结构进行表现的图称之为搜索树。
• 节点代表状态，枝代表行动

基于搜索树的搜索

• 对于给予的问题，我们从多种可能的状态与路径中找出满足特定条件的路径。
• 算法描述：
  • 用后部列表对已知信息进行保存。
  • 从候补列表中调看状态、选择着手。
  • 展开新的节点，更新列表。
  • 重复此流程。

系统的搜索方法

• 保证搜索到整棵树的所有节点，这样就一定能找到最优解。
• 确保不会重复或者漏搜。
  • 那么就有一个衍生问题，按照怎样的搜索方法或顺序可以保证以上的需求？
• 根据“候补列表”所选择的目标决定搜索顺序。
• 主要有两种基础思路：
  • 深度优先（纵型）搜索。
  • 广度优先（横型）搜索。

深度优先（纵型）搜索-Depth-first search (DFS)

• 沿着子节点，不断地向更深的枝干进行遍历
• 如果子节点有复数个，那么先从其中一个子节点开始一直往下搜寻到其末端为止，再对下一个子节点进行遍历
• 例如：当你在一个巨型迷宫里迷路了
  • “遇到分叉路口了，怎么办呢……总之先走左边的吧”
  • “又遇到分叉路了，选择左边的路继续前进”
  • “啊，死路不通，那么就退回最后的分岔路口，选择另外一条路”

Depth-first search (DFS) 算法路径

对于给定搜索树：

· 起始节点（Start）：S
· 目标节点（Goal）：G
· 节点层级关系：
· 根节点：S
 · S的子节点：A、B
 · A的子节点：C、D
 · B的子节点：E、F
 · E的子节点：G、H

• DFS搜索顺序为 S → A → C → D → B → E → G

• open列表变化过程 open : (S) → (AB) → (CDB) → (DB) → (B) → (EF) → (GHF)

• closed列表变化过程 closed : () → (S) → (AS) → (CAS) → (DCAS) → (BDCAS) → (EBDCAS)

• Open list

  • 保存计算中的节点

• Closed list

  • 保存计算完成的节点

DFS的特征

• 不断地深入进行搜索
  • 优点：适用于搜索并迅速发现埋得很深的目标节点
  • 缺点：对于一些埋得很浅的目标节点搜索效率不高
  • 实际上，计算机机能的限制也导致DFS不能无限制地深度搜索，会设置深度限制
  • 有回溯操作（数据结构上，反复入栈、出栈），运行速度慢
• 内存使用量小
  • 防止胡乱地进行无限制无目的搜索
  • 最重要的优点——相对广度优先搜索
• 不保证得到的解是最优解
  • 当深度设置不合理的时候甚至找不到解
  • 这是DFS最大的缺点

广度优先（横型）搜索-Breadth-first search (BFS)

• 核心遍历规则：首先搜索全部深度为1的子节点，接着搜索全部深度为2的孙节点，再接着搜索全部深度为3的曾孙节点。如此反复，直到每一层被遍历完毕后，进入下一层。

• 博弈论应用示例（如何给自己带来最大利益）

  • 先思考遍历自己全部可能的第一步行动
  • 再思考根据自己的行动，对手可能会做出的下一步全部反应

• 迷宫示例

  • “你的面前有个分叉路口”
  • 先检索这几个分叉路口
  • 接着再看分叉路口的各自岔路
  • 仅适用于开了上帝视角的纸迷宫

Breadth-first search (BFS)算法路径

对于前文DFS部分提到的示例搜索树：

• 横型搜索的遍历顺序为 S → A → B → C → D → E → F → G

• open列表变化过程 open : (S) → (AB) → (BCD) → (CDEF) → (DEF) → (EF) → (FGH) → (GH)

• close列表变化过程 close : () → (S) → (AS) → (BAS) → (CBAS) → (DCBAS) → (EDCBAS) → (FEDCBAS)

• 最终得到的解路径 S → B → E → G

BFS的特征

• 不断地从浅处节点进行搜索。
  • 优点：适用于简单问题，能迅速发现埋得很浅的目标节点。
  • 最重要的优点：能用最短方法解决问题。
  • 特性：保留全部结点，占用空间大；无回溯操作，运行速度快。
• 需要占用大量内存

  • 最致命的缺点：一旦内存不足，搜索就中断。

  • 特性：一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中必须考虑溢出和节省内存空间的问题。

    所以吃CPU还是吃内存？这是个问题。所谓鱼和熊掌不可兼得，要根据具体硬件情况，以及问题需求来做选择，对简单问题寻求最优解，那就使用横型搜索，对于复杂问题，特别是内存有限制的情况下，使用纵型搜索。

零和游戏

• 游戏有很多不同的博弈分类：静态/动态，完全信息/不完全信息，1人/2人/多人，随机/非随机，合作/对抗，零和/非零和。
• 本次我们考虑最常见的两人·完全信息·零和·动态博弈（回合制游戏）。
• 典型适用场景：四大棋类。
  • 国际象棋，中国象棋，将棋和围棋。
  • 也适用于黑白棋，斗兽棋，五子棋等等游戏。
• 核心本质：零和，以妨碍对手为最优先操作（其本质就是鼓励“损人利己”）。
  • 经典参考：冯诺依曼的分饼。

评价函数

• 展开一定深度的决策树，对于决策树中每个节点的局面进行状态表示的数学方法，称为状态评价函数（state evaluation function）。
• 黑白棋场景的核心评价维度：己方棋子数、可合法落子的格子数等。
• 象棋场景的核心评价维度：消灭对方棋子的程度、自身王的安全性。
• 各类场景的局面判定，可通过阴阳例进行判定。
• 评价函数本身的性能优劣，与人工智能的强度直接相关；评价函数的研究也是AI研究的重要组成部分。为了方便起见，本节课直接给出所有状态经过评价函数计算后的参考值。

MINMAX Tree

• 自己的回合，永远选择最大值的一手。
• 对方的回合，永远选择最小值的一手（对方视角对自己而言）。
• 核心逻辑：预估最大（MAX）手、最小（MIN）手不断交替后得到的未来局面。
• 适用场景：MINMAX法完美契合两人完全信息的零和游戏（象棋、将棋、黑白棋），是典型的损人利己博弈策略。
• 节点定义：
  • 自己回合的节点称为MAX node。
  • 对手回合的节点称为MIN node。
• 通常使用纵型搜索模型。

便签-11.1

MINMAX的精髓在于刻画了与理性对手进行两人完全信息零和动态博弈的决策逻辑——它最终给出的，一定是最坏情况下的最好结果——也就是在理性对手每一步都追求自身收益最大化（也就是零和场景下我方收益最小化）的前提下，我方当前能选到的最优决策。

它和贪心算法有本质区别：贪心算法只关注当前一步的即时收益，选当前决策节点中收益最大的选项；而MINMAX不关注单步的即时奖励，它会向前遍历完整的决策分支，预判双方后续的所有理性应对，最终通过回溯末端节点的收益 / 估值，逐层取极值来确定当前的最优选择。

这里要补充一个严谨定义：博弈论中，只有博弈终局才能计算唯一确定的“收益”，中间节点的即时得失只能称为 “即时奖励”；为了表述方便，我们统一用 “收益” 代指奖励。

需要注意，所谓 “收益（终局的确定结果，或过程中的即时奖励数值）” 与 “评价函数” 是两个完全不同的概念。收益是可被计算的确定精确值；而评价函数，是针对无法穷举完整决策树的复杂博弈场景（可被穷举并计算收益的搜索树不需要评价函数），在有限深度搜索的边界上，对未到终局的节点局面，通过特定规则估算其对应终局的期望收益，以此给 AI 的搜索和决策提供引导的启发式工具。

MINMAX法特征

• 如果通过评价函数给末端节点一个评价值，现实中，就能在搜索限制范围内尽可能找到最优解；数学理论上一定会找到最优解。
  • 对应概念：Solved Game
• 隐含假设：想象你的对手足够聪明，对手不会永远“最大可能地唯利是图”。
• 复杂度问题：如果Branching Factor记为b，搜索深度depth记为d，那么游戏复杂度则为b^d，随着搜索深度的增加，搜索量会指数级爆炸。
  • 示例：4×4的黑白棋，节点搜索量为12!（大约接近5亿）。

显然，现阶段计算机性能上，我们不可能接受这种强度的搜索量。

所以游戏人工智能的一个重要研究共组偶，就是尽可能高效地寻找最优解，优化搜索算法，包括使用人文社科专业相关理论去优化，也是文工联合的一种研究手段。

αβ法

• 计算叶子节点的评价值（通过使用状态评价函数）。
• 利用αβ法（αβ剪枝，αβ pruning）剪掉没必要搜索的点。

1. 基于纵型搜索中的MINMAX搜索。
2. 保持MAXnode临时的最大值α，以及MINnode临时的最小值β。
3. 对于MINnode，β（某个子节点的评价值）小于亲节点的α，那么剩下的子节点就不用搜索了。
4. 对于MAXnode，α（某个子节点的评价值）大于亲节点的β，那么剩下的子节点也不用搜索了。

思考一个相亲的简单问题就能理解这个复杂的描述。

αβ法（αβ pruning）的效率化

• 为了提高效率
  • 越早读出关键手，cut的效率就越高，也越容易操作。
  • 如果读出关键手也是研究的重点之一。
  • 探索模型和顺序就很重要！
  • 行动评价函数。

[Remi2007]Computing Elo Ratings of Move Patterns in the Game of Go 围棋AI研究的必读论文

因此，我们说，

MINMAX搜索树配合各种优化过的搜索算法，理论上可以结局一切固定信息的零和对抗游戏，但是有很多博弈其信息是无法预估的，更不会是固定的——譬如围棋，这时候就需要我们使用另外的手段。

蒙特卡洛方法

有些情况下很难描述状态评价函数

• 在象棋里面，你可以很容易的根据棋子数目，棋子摆放的局势判断双方的利益得失，以将棋为例： f(s) = 兵 × 10 + 马 × 40 + ... + 炮 × 50 + ... + 士象双全 × 80 + ...

• 围棋没法用这个方法实现：

  • 本质是部落圈地。
  • 跟棋子本身强度无关。
  • 棋子的强弱和棋子间关系有关。
  • 也和棋子的“势”有关……
  • 所谓“形”“势”，即形势。
  • 300多步，探索树深的可怕，现有计算机绝对做不到这种计算量。
  • 对这种暧昧的局面，需要有相当的直觉。

蒙特卡洛法 (Monte Carlo method, MC)

• 通过随机数进行模拟和数值计算的手法。
• 约翰·冯诺依曼为了探究原子弹里面的中子物质运动方式，以摩纳哥的赌城Monte Carlo来命名这种方法。
• 摩纳哥公国是世界第二小的国家，被法国包围，整个国家以赌博业为主体，分为四个区，其中一个区的名字就叫蒙特卡洛，可谓是欧洲的澳门/拉斯维加斯。
• 蒙特卡洛方法因为和随机数扯上关系，冯诺依曼的这个命名方式也堪称完美。
• 但事实上很早就有蒙特卡洛法，只是不叫这个名字而已。

蒙特卡洛法应用实例：计算圆周率π

• 在如下的正方形内随机打一个点→通过落在圆内的个数求圆周率π
• 如果打点的行为进行无限次 圆内点个数 : 全个数 = 圆的面积 : 正方形的面积 = π/4 : 1

内部的点——π的值： * 82个——3.28 * 802个——3.208 * 7886个——3.1464

不难发现这一值趋于精确——当然，工学方法自然无法与莱布尼茨公式等理学分析来得精确，但好在其具有实践意义。

蒙特卡洛探索树的意义

• 蒙特卡洛树搜索的意义在于部分解决了MINMAX的两个问题：
• 对于没法设计评估函数的游戏，它可以给出一个局面评估，虽然不准，但比没有强。所谓聊胜于无。
• 根据它的设计原理，搜索树会较好地自动集中到“更值得搜索的变化”（当然也不一定准）从而去掉不必要的冗余。如果发现一个不错的着法，蒙特卡洛树搜索会较快地把它看到很深，可以说它结合了广度优先搜索和深度优先搜索。
• 最后，随着搜索树的自动生长，如果给定足够的计算时间和足够的存储空间，蒙特卡洛树搜索可以保证在足够长的时间后收敛到完美解（类似于求圆周率π）。
  • 为什么跟李世石比赛后，再和柯洁比赛的AlphaGo更强了，不仅是因为AlphaGo会“思考”，而是蒙特卡洛方法的属性。

蒙特卡洛法和游戏

• 具体算法：

1. 对于存在的某初始行动a，之后的行动全部从合法的决策中任意的做出选择，从而向最终结局迈进（称之为模拟）。
2. 终局时，计数胜负的次数。经过N_a次的反复操作，得到胜利次数W_a。
3. 通过步骤1和2对全部的最初行动进行操作，选择胜率 w_a/N_a 最高的决策。

蒙特卡洛法的特征

蒙特卡洛法的优点：

• 不需要评价函数→因此该方法大活跃于几乎没法设计评价函数的围棋中。
  • 比起评价函数+MINMAX系程序方法在围棋中有着压倒性的优势。
  • 仅仅5年时间，就从业余初段晋升到职业六段的水平，进而发展出AlphaGo这样击败人类职业九段的怪物。
  • 比起MINMAX那种和人类完全不一样的暴力型思考逻辑，蒙特卡洛方法处理的黑白棋与围棋人工智能，不仅仅强大，而且下棋的方式看上去更加自然符合人类行为模式。

蒙特卡洛法的缺点：

• 需要进行足够次数的模拟。
  • 对于分支过多的游戏而言，处理很困难。
  • 对于象棋这样的游戏，随机模拟不容易收敛游戏过程（即可能导致游戏无法终结），模拟效果低下，还不如MINMAX简单粗暴给出最优的唯一解。
• 不管怎么模拟，基本上是基于一个概率值做出的选择，概率这东西有时候是错的，万分之一的胜机事实上和理论上都存在，因此蒙特卡洛法在准确性上要比MINMAX要低（如果MINMAX可以很好地处理问题的话）即便是模拟无穷大次，也不能像MINMAX那样简单粗暴拍着胸脯给出最优解。
  • 所以围棋还不敢说Solved game。

** END

**