方块 AI 算法历史 (1996–2013)

来自俄罗斯方块中文维基

{{#html:MathJax}}

这个条目的正文所介绍的内容选译自 Simón Algorta 和 Özgür Şimşek 2019 年的论文 The Game of Tetris in Machine Learning 的第三章和附录表格。
这些内容仅对应一篇论文做出的概述。方块 AI 的分类页面有这 18 年间的更多方块 AI 算法的内容。

方块 AI 算法最常见的做法是展开一个线性评价函数，把每一种可能的摆法都评价出来，以选择具有最高评价值的摆法。

早期尝试

Tsitsiklis 和 Van Roy (1996) 将俄罗斯方块用作基于特征[注 1]的大尺度动态规划[注 2]的试验床。
他们使用两个简单的状态特征（洞数、最高一列的高度），在 10 × 16 的场地实现了 30 左右的消行数。

Bertsekas 和 Tsitsiklis (1996) 添加了两套特征（各列的高度、落差[注 3]），用 λ-策略迭代[注 4][注 5]实现了 2,800 左右的消行数。
但要指出的是，二人的实现用了更有效率的终局方法[注 6]，场地缩至 10 × 19。

Lagoudakis 等 (2002) 添加了更多特征（平均列高、总落差），用最小二乘[注 7]策略迭代实现了 1,000–3,000 的平均消行数。

Kakade (2002) 用策略梯度算法[注 8]平均消出 6,800 行，所用特征和 Bertsekas 和 Tsitsiklis 用过的相同。

Ramon 和 Driessens (2004) 用具有高斯核[注 9]的关系型强化学习[注 10][1]实现了 50 左右的消行数。

Farias 和 Van Roy (2006) 研究了一种算法，用贝尔曼方程的形式为线性规划求解器[注 11]采集约束条件样本。
他们寻得了一种消行 4,500 左右的策略，所用特征和 Bertsekas 和 Tsitsiklis 用过的相同。

Romdhane 和 Lamontagne (2008) 结合强化学习和案例推理[注 12]，利用了小部分场地的图案，实现了 50 左右的消行数。

手工制作的智能体

在 2008 年以前的相关报告中，最好的人造方块 AI 是手工制作[注 13]的。Fahey (2003) 的报告指出，一位自称是平均水平的俄罗斯方块玩家 Pierre Dellacherie 认明了六个简单的特征，而且用试错法调了权重。这六个特征分别是洞数、方块着陆高度[注 14]、行转变数（检查每一行“砖空相邻”的总次数[注 15]）、列转变数、累计井数[注 16]和侵蚀格数（当前方块的消行数乘以填入被消行的方格数）。评价函数如下： $$评价 = -4 * 洞数 - 累计井数 - 行转变数 - 列转变数 - 方块着陆高度 + 侵蚀格数$$ 这个线性评价函数在标准场地平均消出 660,000 行。如果方块（在最顶上一行的中间）没有空间入场，游戏就会结束，实现报分。在前面讨论过的做法所用的简化版报分实现中，游戏仍会继续，直到所有的摆法都满出场地。因此，和其他算法相比，这份报告低估了这个简单的线性规则。

遗传算法

Böhm 等 (2005) 用进化算法来开发俄罗斯方块的控制器[注 17]。在他们的实现中，智能体不但知道正在下落的方块，还知道下一块，这就使他们的结果不能和那些只知道当前块的实现所取得的结果相类比。他们把线性策略和指数策略都进化了出来，并做了报告：用线性函数消出了 480,000,000 行，用指数函数消出了 34,000,000 行，都是在标准场地[注 18]上。他们引入了一些新的特征（相连洞数、被占格数、由格高加权的被占格数），这些特征在随后的相关研究中未被重提。

Szita 和 Lörincz (2006) 用交叉熵算法[注 19]实现了 350,000 左右的消行数。这种算法探测随机的参数向量，寻找使分数最大化的线性策略。每一个参数向量都对应若干局游戏，用最佳参数向量的平均值和标准差生成新一代的策略。噪声[注 20]要不断地降低，这样探索参数空间就会有效率。后来，二人 (2007) 还将交叉熵算法的一个版本运用到了另一个困难的领域——“吃豆人小姐”[2]。

Thiery 和 Scherrer (2009) 跟随了 Szita 和 Lörincz 的研究工作。他们添加了一对特征（洞深、有洞的行），用交叉熵算法开发出了著名的“俄罗斯方块系堆建控制器”（BCTS）[注 21]，实现了 35,000,000 的平均消行数。BCTS 添加了“图案多样性”[注 22]这一条特征，在 2008 年的强化学习大赛上赢得了冠军。

Boumaza (2009) 向俄罗斯方块引入了另一种进化算法——协方差矩阵自适应演化策略（CMA-ES）[注 23]，观测到的结果权重和 Dellacherie 非常接近，平均消行也是 35,000,000。

Salimans 等 (2017) 指出，鉴于进化策略作为强化学习算法的有力竞争者再次出现，遗传算法的成功值得关注。需要注意的是，遗传算法比强化学习算法更容易并行化。强化学习算法可在策略评价的步骤中使用进化策略（见下一章）。

近似修正策略迭代

Gabillon 等 (2013) 受到了 Lagoudakis 和 Parr (2003) 的启发，用基于分类的策略迭代算法找到了一个实现 51,000,000 消行数的权重向量，这是第一个性能比得上遗传算法的强化学习算法。Lagoudakis 和 Parr 的想法是在强化学习算法的循环中利用精密分类器来认明良好的动作[注 24]。Gabillon 等人先用锁块[注 25]估计各对“状态-动作”的值，再用 Hansen 和 Ostermeier (2001) 的 CMA-ES 算法做最小化处理，得出这些锁块的一个复杂函数。Salimans 等 (2017) 指出，这种算法是最广为人知的进化算法。其中，CMA-ES 是在执行一个代价敏感的分类任务[注 26]，这种算法因而得名“基于分类的修正策略迭代”（CBMPI）。

CBMPI 先从 BCTS 的落块轨迹中提取所要使用的状态样本，再进行子采样，使场内的列高分布更加均匀。为实现良好的发挥水平，CBMPI 要花费掉和 BCTS 一样长的实行时间；Scherrer 等 (2015) 指出，实现良好发挥的最佳子分类方法仍未被充分理解。

小结

算法 场地 消行数 特征集
TSITSIKLIS & VAN ROY (1996) 近似值迭代  10 × 16  30 洞数、列高峰值
BERTSEKAS & TSITSIKLIS (1996) λ-策略迭代 10 × 19 2,800 BERTSEKAS
LAGOUDAKIS ET AL. (2002) 最小二乘策略迭代 10 × 20 ≈2,000 LAGOUDAKIS
KAKADE (2002) 自然策略梯度 ≈5,000 BERTSEKAS
DELLACHERIE [FAHEY (2003)] 手调 660,000 DELLACHERIE
RAMON & DRIESSENS (2004) 关系型强化学习 ≈50
BÖHM ET AL. (2005) 遗传算法  480,000,000（两块）  BÖHM
FARIAS & VAN ROY (2006) 线性规划 4,274 BERTSEKAS
SZITA & LÖRINCZ (2006) 交叉熵算法 348,895 DELLACHERIE
 ROMDHANE & LAMONTAGNE (2008)   案例推理 + 强化学习  ≈50
BOUMAZA (2009) CMA-ES 35,000,000 BCTS
THIERY & SCHERRER (2009) 交叉熵算法 35,000,000 DT[注 27]
GABILLON ET AL. (2013) 分类策略迭代 51,000,000  策略 DT + 值 RBF[注 28] 

注释和参考

  1. ↑ 机器学习领域的“特征”（feature）是围绕数据而做的表达。
    从数据中提取特征、判断表现，就能对事物进行分类和识别。
  2. ↑ 动态规划（Dynamic Programming，DP）是一种用来求解最优化问题的策略，它和一般性的“编程”（programming）是不一样的。在这个语境下，把 Optimizing 当作 Programming 的近义词来帮助理解，很多概念就会变得清晰。
    DP 这个概念由美国应用数学家理查德·贝尔曼（Richard E. Bellman）于二十世纪五十年代提出，后面提到的“贝尔曼方程”正是 DP 方程。“动态规划”是个具有迷惑性的通称，因为 DP 的核心思想是“找出一组元素当中最大的那一个，新加的元素只要和这一个去比，就能知道哪一个又是最大的”，也就是极值比较，它和动态、规划都没有太大的关系。
  3. ↑ 连续排着的两列的高度差
  4. ↑ 基于美国数学家阿隆佐·邱奇（Alonzo Church）的 λ-演算（Lambda Calculus）的策略迭代
  5. ↑ 策略迭代算法中的“策略”是个缩写，全称为“动态规划策略”（Policy of DP），它和全局性的战略（strategy）是不一样的。这种算法的核心思想是通过交替使用求值计算和策略改进来向最优策略收敛。
  6. ↑ 也就是更简单的死亡判定
  7. ↑ 最小二乘法（Least-squares）是回归分析的一种重要方法，常被用于曲线拟合，它通过最小化误差平方和来寻找数据的最佳函数匹配，进而提取出高质量的特征。
  8. ↑ 策略梯度算法（Policy-gradient Algorithm）是用参数化思想控制策略的算法。
    这种算法的核心思想是直接根据状态输出动作或者动作的概率。在方块 AI 领域使用策略梯度算法，结果就是：摆法的评价值越高，它之后出现的概率也会越高。
  9. ↑ 高斯核（Gaussian Kernel）在多数场合下指高斯核函数。但是，在俄罗斯方块这种图形游戏的 RRL 领域，这个概念指的是“具有图形内核的高斯过程”（Gaussian Processes with Graph Kernels），它是 RRL 的一种泛化算法，常可改进回归树。
  10. ↑ 关系型强化学习（Relational Reinforcement Learning，RRL）的核心思想是把关系学习或归纳逻辑规划（Inductive Logic Programming）结合至强化学习。具体的做法，就是用一阶形式语言（First Order Language）来泛化表示状态、动作和策略，从而更好地利用较早学习阶段的成果。
    （这一条注释的内容选译自 DeepMind 团队 2018 年的一篇论文的第二章，见本条目参考一）
  11. ↑ 线性规划求解器（Linear Programming Solver）是在线性约束条件下求解目标函数极值的工具。
  12. ↑ 在方块 AI 领域，基于案例推理（Case-based Reasoning，中文简称“案例推理”）就是把能够解决问题的历史摆法运用到新的场况。
  13. ↑ 在机器学习领域，手工制作（Hand-crafted）和端对端（End-to-end）是算法开发主题中的一对重要的概念。前者的算法由人设计，可一步步地说清理由，它设计的是特征本身；后者只有输入和输出端，它不是设计具体的算法，而是设计特征的提取框架。前者的替代词包括“手动”、“人设”、“专家指导”，后者的替代词包括“无监督”、“纯学习”、“非专家指导”。
  14. ↑ 列高 + (块高 / 2)
  15. ↑ 场地边界与方块堆的实格等效
  16. ↑ 左右两侧都是砖格或墙壁，就是“井格”
  17. ↑ 这里的“控制器”（controller）指的就是方块 AI，不是输入设备。后面提到的 BCTS 里的 C 就代表控制器。
  18. ↑ 10 × 20
  19. ↑ 交叉熵算法（Cross-entropy Algorithm）是一种基于概率论的进化策略算法。这种算法以重要性采样为基础、以方差最小化为推理线索，在无监督环境下实现参数优化。
  20. ↑ 交叉熵算法本身就是一个（故意从高噪声开始）降噪的过程，Szita 和 Lörincz 甚至没有在原论文的标题中简略掉 Noisy 一词。
  21. ↑ BCTS（全称 Building Controllers for Tetris Systems）是 Thiery 和 Scherrer 为 2008 年强化学习大赛开发的方块 AI 算法。二人在 2009 年的论文的第四章写明了这个算法的特征权重。
  22. ↑ 图案多样性（Pattern Diversity）是落差形成的图案数。例如，如果一列 10 格高，下一列 9 格高，图案就是 1。图案多样性就是在这个量度上低于 3 的不同图案的数量。
    （这一条注释的内容译自本条目主论文附录算法特征集部分的“DT”小节。附加说明：“图案多样性”量度之所以被设为低于 3，是因为有智能的方块 AI 不会大量堆建出必须竖 I 才能解决问题的地形，可顺应这条规律合理减少算法的计算量。）
  23. ↑ CMA-ES（全称 Covariance Matrix Adaptation Evolution Strategy）是 Nikolaus Hansen 和 Andreas Ostermeier 于 2001 年提出的一种无约束（随机的、不需要计算梯度的）数值优化算法（具体内容见这个 pdf 文件）。这种算法的流程分三步：产生新个体、计算适应度并排序、更新参数。
  24. ↑ 在方块 AI 领域，这种想法就是对摆法进行精密分类。
  25. ↑ 此处的“锁块”是英文“rollout”在俄罗斯方块语境下的中文表述。这个词在强化学习领域没有固定的中文译名，其含义重点在于“做出决定性的行动”，要根据实际情景决定表述（例如，AlphaGo 围棋的论文翻译成中文时，Fast rollout 对应“快速走子”）。
  26. ↑ 代价敏感分类算法（Cost-sensitive Classification Algorithm）是一种能够解决分类任务中的数据不平衡问题的算法。分类错误越严重，在代价矩阵中对应出来的惩罚值就会越大。
  27. ↑ DELLACHERIE + THIERY
  28. ↑ 径向基函数（Radial Basis Function，RBF）是样本到数据中心的欧氏距离的单调函数，能够逼近任意的非线性函数，泛化力强、计算稳定、学习收敛迅速。此处的 RBF 指列高均值的 RBF。
  1. ↑ Relational Deep Reinforcement Learning . 2018-06-28. [2022-07-25].
  2. ↑ [1]
检索自“http://tetriswiki.cn/index.php?title=方块_AI_算法历史_(1996–2013)&oldid=1780”