此笔记位置已失效,请从目录继续阅读。
全书导读
本书用谜题和游戏解释一条渐进路线。先把问题写成可以计算的状态与操作,再用规则、估计和采样决定有限预算下先看什么,最后学习原先靠人编写的决策线索。能赢、能证明、能解释局面和能像人一样操作,是几种不同的检验任务。
- 第 1 章用游戏史和战略盗用区分竞赛表现、胜负理论与可执行策略。
- 第 2 章比较按深度、步数和代价估计扩展状态,突出代价与启发式的约定。
- 第 3 章把冲突变成约束、剪枝条件和可追溯的假设,展示怎样减少无用分支。
- 第 4 章让对手也能选择,引出极大极小、上下界剪枝、随机模拟与实时预算。
- 第 5 章从专家棋谱、游戏回报、进化适应度与预测误差学习策略和评估。
- 第 6 章将规则泛化和行为类人性变成不同的目标,并讨论观察方式会怎样改变评价结果。
译者序
译者用围棋说明学习与搜索的分工。策略模型从棋盘估计值得尝试的落子,树搜索再比较这些落子可能带来的后果。序言也把这一取舍与 A* 搜索联系起来,并引出全书最后讨论的类人表现。
前言
前言将游戏和谜题作为观察搜索、学习和优化的场景。正文会结合规则明确的游戏实例解释技术,涉及深度学习、强化学习和进化计算。作者把讲清通用方法作为写作目标,并说明实例部分来自系统工程课程及实验室研究。
第1章 谜题与游戏AI的过去和现在
题页用羽生善治设想改变将棋规则的说法,引出规则固定的游戏被计算机掌握后,人类还能如何继续探索。
1.1 关于AI的预言成真了吗
本节从西蒙和纽厄尔对棋类、定理证明、音乐和心理理论的早期预测切入,比较这些方向的发展速度,并说明正文把游戏与谜题作为讲解 AI 方法的主要场景。
1.2 游戏AI的历史和背景
本节把早期棋类程序、跳棋经验学习和人机对弈放在同一条历史线上。早期设备限制棋盘和搜索深度。后来的系统用更好的盘面表示、评估和学习来提升棋力。图 1.1 是 Travel Mate II 商用电子棋机的实物照片,作为早期可供家庭使用的对弈设备案例。深蓝比赛的叙述还表明,人的压力与对机器能力的先入判断会影响比赛表现。
对弈系统赢下某场比赛,只给出了该次比赛的结果。求解一个游戏至少要确定从指定初始局面出发,双方采用最优策略时会发生什么。书目 [73] 列出 2007 年的跳棋论文,本节正文却写作 2017 年。魔方叙述也突然切换到扑克,因此这里分别保留全搜索与均衡策略的例子,日期与残缺过渡留作版本问题。竞猜式博弈的均衡允许随机选择,猜拳中均匀分配三种动作便是一个例子。
1.3 游戏AI是否会剥夺人类的乐趣
本节讨论棋谱数据库和固定开局如何影响创造性。Chess960 用受约束的随机初始局面减少背谱优势。深蓝案例引出另一问题,即棋力测评与对人类思考的解释各自需要什么证据。 棋力与认知是两项指标。
相关讲解见随机开局减少背谱优势。
1.4 游戏AI的意义
高级国际象棋允许棋手在对弈时查阅软件分析,并保存搜索树以供复盘。随后以数学计算实验说明,计算机还能帮助形成猜想,证明仍需另行给出。 协作流程影响组合棋力。
相关讲解见计算实验帮助形成猜想。
1.5 游戏的深奥程度与“先下手为强”定理
Chomp 的玩家选定一块还在棋盘上的巧克力,同时移除该块以及相对它坐标都不小于它的剩余格。图 1.2 用 4×6 棋盘示范两次操作。以左下格为 (1,1),先取 (5,4),清除顶部最右两格,再取 (4,2),清除仍存在且列号至少为 4、行号至少为 2 的格子。左下毒格仍保留。正文由特殊尺寸的开局过渡到一般尺寸的战略盗用证明,再把约数游戏的质因数指数配对成二维棋盘。两种游戏都按同一条规则删除后续合法选项。约数游戏对应巧克力棋盘说明如何从整除关系得到这条规则。在有限的双人完全信息确定性对局中,若终局按先手胜、后手胜、和棋排序,可以从终局倒推:先手节点选对先手最好的一项,后手节点选对先手最差的一项。初始节点因此得到确定的理论结果。若规则允许无限重复,就需要先按实际规则处理和棋或循环,才能直接使用有限树的倒推说明。 这一分类说明理论结果存在,求出初始节点的值和可执行策略仍可能需要大量计算。 战略盗用证明先手必胜。
第2章 解谜的AI
章题页用一个缺少具体棋局的问题引出本章。要让计算机回答怎样走,先给出局面、合法动作和目标条件。
2.1 搜索树
把谜题转换成状态空间,有两个步骤。先判断初始状态和目标是否在同一可达范围,再规定怎样生成下一状态。15 谜题的具体初局交换了 14 和 15,空格仍在同一位置。由于每次空格和相邻滑块交换,从同一格出发并回到同一格需要偶数步,所以这一个奇置换无法由合法移动完成。渡河题用两岸人数和船的位置表示状态。每一步先枚举船上组合,再剔除人数守恒或安全条件不满足的情况。同一状态可以由不同路线到达,甚至返回原点,图搜索需要识别这些重复状态。
图 2.1 展示 14–15 谜题的历史插画。图 2.2 给出初始人数和船的位置。图 2.3 的两条末端路线共用同一个目标局面,图 2.4 则展示每个非根节点只有一个父节点的树。 相关讲解见空格回原位限制滑块奇偶性、用约束生成渡河状态、搜索路径会汇入同一状态。
2.1.2 深度优先搜索
深度优先搜索先扩展刚生成的后继。无新状态时,回到此前留下的候选。图 2.5 用编号区分生成顺序与扩展顺序;结合公式 (2.22)–(2.24),应当是 k₂ 已扩展、k₃ 待展开,新加入的是 k₆。图 2.6 说明深度上限使另一条通往终点的分支有机会被探索。图 2.7 的 8 谜题在编号 41 处抵达目标,编号表示生成次序。
相关讲解见栈决定深度优先扩展、前沿和已扩展集消除重复、逐步加深避开无限分支。
2.1.3 宽度优先搜索
把待扩展状态放入先进先出队列,即可先扩展距离起点近的状态。每步代价相同时,第一次抵达目标就是最少步数。图 2.8 对照逐层搜索和沿分支纵深搜索。图 2.9 的渡河例先把四个一步可达状态扩展完,才扩展从第二个分支产生的两步状态。图 2.10 的八数码例在第 29 个生成状态找到目标。宽度增加会推高队列及去重存储的开销,不能从一个小例子得出它总比深度优先快。
相关讲解见先进先出保证先扩展浅层。
原书依据 · 1 处
2.1.4 A*搜索
A* 按 f=g+h 选择待扩展节点,g 为已付代价,h 为剩余代价估计。单位步代价下,h 恒为零时按步数逐层扩展。图 2.11 里两个根后继的估分是 8 与 6,编号 3 的低分分支优先,图在编号 10 找到目标。图 2.12 两个设置分别生成到编号 20 与 18。表 2.1 的四组滑块实验中 A* 的表列计数都最小,两个较大例的广度或深度优先至少达到三百万,体现启发式的实例收益。
原文最优性论证依赖候选解从最低 f 节点中取出。该节伪代码却写为一生成目标便终止,而且无条件排除旧状态。实现时应在目标出队时验收,并保存每个状态的最佳 g,发现更低 g 时更新队列,对不一致启发式允许重开。标准计数的八数码曼哈顿距离只加编号滑块,每一步最多减少一,因此确实是下界。原文示例将空格算进错位数、又称距离和可能超过界限,不能用于证明标准版本的最优性。
相关讲解见按已付代价与余程排序、下界如何保证最优解、更紧的启发式压缩搜索。
2.2 推箱子
搜索动作以推箱一格计费,玩家的走动用可达区域表示。从玩家所在格开始,穿过空格做四邻域填充,便知道能从哪一侧推箱。启发式忽略箱体占位与终点分配冲突,把每个箱到最近目标的墙内距离相加。不可达后方会使一些箱子永久卡死。书中进一步把暂时可推的箱子移除,再检查冻结箱和封闭目标;这是检测部分死局的办法。图 2.13 的实例三种算法都以 6 次推动完成。正文写 A* 生成 16 个节点,表 2.2 首个例列 12;比较时分别引述。表内 44 步案例中,广度和迭代加深均受内存限制。
相关讲解见放宽规则得到代价下界、先识别无解状态再扩展。
2.3 数字连线
状态保存已画的部分路径及各自由端。每次只延长一格,并检查格子是否已经占用、是否误穿过别的数字、是否产生交叉或分叉。书中的启发式从对应数字或线头之间的曼哈顿距离估计未连长度,按两端的延伸情况修正记账边界。实际最少代价随计步定义变化,也会因绕开别的线而增大。表 2.3 最后一例广度优先列 2,805,115,A* 列 94;最简单例三者同为 7。
相关讲解见用线头估计剩余连接长度。
原书依据 · 1 处
2.4 日式华容道
大方块要让开其它滑块,最后到达底部出口。书中尝试用下方阻碍块面积的平方和评分,也比较将其他滑块缩成单位块、将主块到出口的距离放大 20 倍两种启发式。这些修改都需要另证下界。一个长滑块整体移动一步,可能比拆成多个单位块逐个移动更省代价。图 2.15 的同一关若按一格一步最少 116 步,连续移动允许合计一步时是 81 步。表 2.4 的 A* 生成节点少于宽度优先,但耗时更高。表 2.5 中三种初局的相对排名变化,不能从单个布局选出统一赢家。
相关讲解见改变计步会改变最短解。
原书依据 · 1 处
2.5 孔明棋
一跳要跨过正交相邻的一枚棋子并落到后方空格,被跳过的子移除。每走一步棋子数减一,同一初终子数的可行解都有相同步数。布局仍影响可达性和搜解难度。书中按剩余棋子所在区域计 1、2 或 3 分,偏好靠近目标形状的局面。表 2.6 给出中心单子、十字、方形。表 2.7 中标准实例只列出所用 A* 的计数 6,095,其他两种列 NA。
相关讲解见位置权重引导孔明棋搜索。
原书依据 · 1 处
2.6 尝试用数学知识解决数独问题
数独把未填格看作变量,候选为不违反行、列和宫约束的数字。候选只剩一个便传播这个必然选择,有零个则当前分支矛盾。需要猜测时,优先试候选最少的格子。书中还用所有剩余候选总数对状态排序。表 2.8 和百题实验显示排序策略可减少扩展,后者的宽度优先有半数因内存不足未完成。
变体把行列唯一与各粗线区域和相等合用。若一次主动选择最多连带确定四格,空格数除以五是按主动选择计费的下界。扣除眼下可确定格数能给更激进的排序,表 2.9 五个例都减少了节点,但该量没有下界保证。
另一条路线把格子的取值、每组的和与积、给定数一起编码为多项式。4×4 例的编号图按行从 x0 起,图 2.23 的两枚 4 在 x3 与 x4;可按此确定其它给定格。图 2.24 演示用 Sage 求一个解,后图所示 Gröbner 基只截取了开头。
相关讲解见先填候选最少的格子、把数独改写为多项式系统。
第3章 依赖约束的谜题和非单调推理
章题页引《Searching for Bobby Fischer》质疑把国际象棋直接等同于智慧。以下各节转向能写成规则、检查矛盾和验证解的棋盘难题。
3.1 纵向搜索与回溯
回溯在给变量逐个赋值时检测约束,失败就撤销最近的试探并试别的值。它可以用递归维护当前路径;大量分支仍可能令运行时间过高。下一节把这一方法落实为皇后搜索。
3.2 数学家弄错的国际象棋谜题
第 i 行的皇后所在列记作 Qᵢ,每行放一个。两行不得占同一列,列差的绝对值也不能等于行距。递归时保留所有已确定行;例如 4 皇后先试第一行第 1 列、第二行第 3 列时,第三行没有合法列,撤销第二行后再试第 4 列。若这个子树也失败,就换第一行的选择。找到一个解后仍可继续搜索以枚举其它解。图 3.1 示题与八皇后解,图 3.2、3.3 分别示撤销分支和 4 皇后的逐步搜索。
相关讲解见冲突时撤回最近的试探。
原书依据 · 1 处
3.3 线条图的解释与错觉画
线描可通过给每条边指定标签来解释,标签表示凸棱、凹棱或带方向的遮挡边界。只讨论无阴影裂纹、每顶点三面相交、视点稍变仍保持交点类型的多面体时,交点只有 L、箭头、叉和 T 四类。对单点理论上有 208 种标签组合,几何条件只允许 18 种。给一条边定标签后,两端的可选交点类型一起缩减。图 3.12 中 z 的两端施加冲突要求。图 3.11 则有贴墙与悬浮两种解释。即使能局部贴标,仍未必存在一致的全局三维物体,强制透视可让实拍物体看起来像不可能的形状。
相关讲解见用局部标签解释立体线描。
原书依据 · 1 处
3.4 ATMS与四色问题
新事实可以使以默认假设为基础的旧结论失效,例如知道一只鸟是企鹅之后撤回会飞的判断。基于假设的真值维护系统(ATMS)记录每个结论由哪些最小假设集支撑。若 x+y=1 可由 A 或 C 与 D 支持,而 x=1 依赖 D,则 y=0 的两套最小支持是 {A,D} 与 {C,D}。环境格图把含 {A,B} 或 {B,C} 的矛盾超集一并删除。
皇后搜索把同一攻击线上的位置对设为矛盾。SEND+MORE=MONEY 用首位非零、进位、字母互异及总和建立局部与整体约束。另一算式用星号表示任意数字。地图着色把每个地区与颜色的配对作为假设,同色相邻为矛盾;还需为每个地区选择且只选择一种颜色。书中的四地区例彼此相邻,需要四种颜色。该求解过程针对给定地图,四色定理讨论的是所有满足条件的平面地图。
相关讲解见新事实会撤销默认结论、记录结论的最小假设集、最小冲突淘汰全部超集。
3.5 解开国际象棋谜题
过渡节把皇后回溯扩展到两个目标类型:放尽可能多的棋子,或让既定数量的棋子攻击指定格。两种目标都能先利用棋盘结构压缩分支。
3.5.1 尽可能放置多个棋子
求最大放置数时,以当前子数加仍可放置格子数得到上界。上界低于已知最好解即可停止这一支,保留等号才能枚举同样好的答案。图 3.25 汇集互不攻击或不共线的例子。骑士总落在另一颜色的格子,故单色可放满 32 个;图 3.26 将盘面分成 2×4 块,每块可用四对互攻格覆盖,补出至多 32 个的论证。国王在每个 2×2 块至多出现一个,全盘至多 16 个,按两方向隔一格摆放可达到 16。
相关讲解见分支上界低于现解就剪枝、用分块证明摆放上限。
3.5.2 尽可能攻击多个区域
找全覆盖时,先挑一个未被攻击的空格,尝试将皇后放在能攻击它的位置,用必需满足的条件缩小分支。图 3.29、3.30 给出不同棋盘与棋子组合。可记录已尝试的放置,并将互为镜像和旋转的解归并。最后一题正文先写减少未攻击格,随后写最大为 11,方向自相矛盾;按可验证的覆盖分支取材,11 不作为最小未覆盖格数。
相关讲解见由未覆盖目标决定搜索分支。
原书依据 · 1 处
3.6 Knuth的谜题与位棋盘
题目从不含轴平行或倾斜正方形的落子集合出发,寻找再加一子便会产生正方形的高子数布局。图 3.32 提醒要检查倾斜边。位棋盘让占用格对应一个位,旋转映射和镜像映射可对整个盘面运算,并把等价局面统一为一个代表。图 3.33 的 6×6 结果为 14 子、4 种;正文还给 7×7 的 18 子、12 种。
相关讲解见用位棋盘归并对称局面。
原书依据 · 1 处
第4章 会玩游戏的AI
章题页用 Fischer 对弈的两个视角引入主动决策:回看棋谱能评价一招,而实际选择必须在有限时间内预测后续局面。
4.1 井字棋与树
双方交替在 3×3 棋盘落子,先在行、列或对角线上连成三子的一方胜。搜索树的孩子是落一子后的局面。旋转、镜像使九种开局归为角、边、中心三类,后续仍可利用当前局面保留的对称性。
4.2 游戏的树搜索
两方交替且规则、局面公开时,可以从固定一方的视角给终局评分。自己的回合取子值最大,对方回合取最小。在深度预算耗尽前尚未终局,就用估分代替。例如井字棋统计尚未被对手封堵的一子线与二子线,终局胜负使用绝对值更大的分数。对同一个零和计算,改用当前行棋方视角并对子值变号,可以用同一条最大值递推。
α–β 维护双方已知可保证的界。比如 MAX 已有 −9 的选择,新的 MIN 分支发现一个 −31 的应手后,该分支至多 −31,剩余应手无须查。先评估可靠棋步更容易触发截断。书中用不同系数、非线性计分和反规则井字棋比较节点数,说明评价与规则都影响搜索。三连即输时,终局效用改写,先手占中后可点对称应对以保和。Fischer 的弃后故事用来说明局部物质价值与深层后果的区别。
4.3 黑白棋与Fool’s mate
黑白棋以两套 64 位掩码表示黑白棋子。开局可查既定走法,中局以开放度、边缘、稳定子与行动自由度加权估分,残局则更容易展开到终局。图 4.8 从角与边的结构估计未来不会被翻转的子。图 4.9 的小规模对战里,与即时数子相比,稳定子和机动性组合表现较好。步数多的阶段在相同预算下往往只能搜浅一些。愚者自将将双方任务改为合作消灭白子,短期保留白子有时有利于之后集中翻转。原书的先手步数受初始布子是否计入以及双方回合计数影响。
相关讲解见行动自由与棋子稳定性、合作型谜题改写双方目标。
4.4 A*马里奥
实时平台动作中,左右、跑和跳的组合是分支。节点需要保留位置与速度等可以影响下一帧的量,用简化运动模型估算向前最多能走多远及到终点的时间。图 4.12 展示当前位置及若干动作后继。书中的小样本实验表明,同样的节点配额下,深度搜索尤其依赖动作排列;A* 与物理估分配合在该实验中更稳定。示例中的加速与衰减代码应当作为模拟基准,不能脱离实际运行状态比较拟合精度。
相关讲解见运动状态决定可达范围。
原书依据 · 1 处
4.5 蒙特卡罗树搜索
平坦蒙特卡罗给每个候选着法固定若干盘随机模拟,比较频率估计。三次模拟的例子观察到 1/3、3/3 和 2/3,样本极少,也受到模拟对手会走错棋的系统性影响。树搜索则反复执行选择、扩展、模拟及回传:模拟次数多的热门分支最终显式分开若干后继,再单独比较。UCT 在树的每次选择中加入探索奖励,避免早期遇到偶然坏结果的分支被永久冷落。
相关讲解见随机模拟胜率依赖对手模型、用回传结果分配模拟预算。
4.6 立体四子棋
球在杆上受重力支撑,只能落在该杆当前最高球之上。潜在四连只剩一格时,还要检查能否立刻落到那一格,可以利用必须先填下层这一条件判断陷阱。对战中,UCT 在部分评价函数对手面前随模拟数增加而改善;能识别有效威胁的极大极小搜索仍可抗衡。浅层最优着法可以优先放进深一层搜索。用固定节点配额替代固定深度可在早期降深、残局加深。
相关讲解见重力约束改变三连威胁、按节点预算调整搜索深度。
4.7 黑白棋的蒙特卡罗算法和NegaScout算法
NegaScout 的动机是:若棋步排序靠谱,多数后续分支只需验证能否改善当前最好结果。先搜第一步得到候选值,对后来动作采用整数分值下的一格窗口。若未越过 α,直接继续;若达到 β,剪去该分支的余项;中间情况再扩大窗口核实。原书列式首条的 α≤x 与下一条重叠,按判定目的应为 x≤α。三秒对战中,所设 NegaScout 版本赢下 20 局;当限制其深度后,UCT 能取得部分胜局。
相关讲解见用窄窗先判断能否改进。
原书依据 · 1 处
4.8 如何赢得博弈
多臂老虎机将每个选择建模为未知平均回报,有限次数内兼顾学习和收益。贪婪容易被头几次噪声锁在次优选择。ε-贪婪固定比例随机试,UCB 为试得少的选项增加奖励,通常形如平均值加 c·√(ln n/nᵢ)。标准有界独立回报假设下,次优臂的尝试次数及累计期望损失可受对数增长约束。书中正态报酬与伯努利报酬的小规模实验排序不同;理论条件和实验设置应分别记录。
相关讲解见上置信界给少试选项机会、遗憾衡量试错的累计成本。
4.9 消灭幽灵:AI吃豆人
强力道具会暂时把幽灵从威胁变成可以得分的目标,因此状态需要包含阶段时间和道具。不同版本的随机移动、屏幕捕捉延迟或能否直接读状态会影响竞赛可比性。节中先用简化交替行动环境试极大极小和剪枝,再把随机环境压成路口决策。路口不变可复用前一帧的树,以简化的幽灵模型执行模拟。模拟中生存、清豆与驱除幽灵的终止规则会改变得分偏好。表 4.14 以得分、每帧得分及消灭幽灵数比较,限制树深可换取稳定性。
相关讲解见只在分岔处展开动作。
原书依据 · 1 处
第5章 学习、进化和游戏AI
章题页记录围棋界对非惯例棋路的惊讶。以下各节讨论从棋谱、对弈奖励和行为结果取得决策知识。
5.1 来自AlphaGo的震撼
围棋的合法着点和对弈长度使穷举不可行。早期 AlphaGo 将人类棋谱用于预测着法,用自我对弈改进策略,再用自我对弈结果训练价值估计。树选择使用策略产生的先验与已访问统计,叶估值融合快速模拟和价值网络;策略负责将试验集中到更有希望的动作,价值预测让部分评估提前结束。相邻棋谱局面高度相似,新鲜自对弈局面有助于缓解记忆棋谱的问题。
AlphaGo Zero 的输入改用当前及历史棋盘和待落子颜色,以一个网络给出策略与价值,用搜索得到的访问分布和对局结果循环训练。AlphaZero 把这种办法用于围棋、国际象棋和将棋。学习曲线、训练时间和棋力比较来自不同实验设定;书中对版本名称和硬件的写法不用于直接推断训练成本。
5.2 DQN和街机游戏
奖励晚到意味着正确动作没有现成标签。Q 学习把动作价值向即时回报加折扣的下一状态最大动作价值拉近,终局去掉未来项。探索用于收集贪心路径之外的经历。当状态变为像素,不能为所有局面存表,DQN 用卷积网络对每个动作输出一个估计。经验回放把相邻转移拆开后随机采小批量,减少更新序列的相关性。得分变化是反馈,回合到失败或完成才结束。图 5.10 的训练曲线说明两个示例的得分会在交互中改善,不能据此断言全部游戏都达到同样水平。
相关讲解见用后继价值更新当前动作、经验回放打散连续训练样本。
5.3 进化的马里奥
控制器将七个相对格的敌人与物体标志加上可跳与着地状态编码为 16 位索引。每个索引对应一个五位动作组合。利用关卡前进距离给每条策略表打分,执行选择、交叉和变异。从例子的 8451 号表项读到 11 后,可解成跳、向右、冲刺的组合。局部观察有歧义时,相同索引可能对应不同行动需求。
相关讲解见遗传搜索可直接优化动作表。
原书依据 · 1 处
5.4 神经进化
NEAT 让节点和连接结构与权重共同进化。从较小网络开始,可以添一条连接,也可以停用一条旧连接并在中间插节点。基因型保留输入、隐藏、输出及连接端点、启用状态、权重、创新编号;表现型只执行当前有效的网络。交叉时按编号找到共同突变,不依赖基因在列表中的位置。
相关讲解见创新编号对齐异构网络基因。
原书依据 · 1 处
5.5 吃豆人的神经进化
本节区分外部研究中的模块化 NEAT 和书中根据连接端点坐标用遗传编程产生权重的实验。控制器为每个方向评分,输入含敌我距离、追近状态、路口、豆与时间等可行动特征。OFNJ 数下一路口后安全可达的路口,帮助提前识别出路。诱饵策略主动引近敌人才吃强力道具,能得到连续奖励,却可能在时限前来不及完成。该实验的分数比较依赖模拟条件。
相关讲解见用可逃路径识别包围风险、模块切换可适应阶段任务。
5.6 充满好奇心的马里奥
奖励稀疏时,ICM 从交互中生成额外反馈。逆模型看动作前后两帧的编码并预测做了什么,促使编码关注可被行动影响的变化。正模型用当前编码和真实动作预测下一编码,预测误差作为内在奖励。策略优化内外奖励之和。遇到一长串协调动作才能越过的瓶颈,前段熟悉以后误差趋低,单靠好奇心仍难继续。
迁移实验比较新关卡从零训练、直接运行旧策略、预训练后微调。同样的预训练对第二和第三关的收益不同;背景、可达瓶颈及剩余探索信号都影响成绩。状态计数近似法是书中提到的另一种内在奖励思路。
相关讲解见预测误差可作探索奖励、好奇心迁移受新关卡制约。
第6章 游戏AI与类人化
霍夫施塔特借一段邀请对弈又提议吟诗的想象对话,把棋力和人们赋予行为的意义区分开。
6.1 为什么需要类人化的AI
玩法教学、难度调节和练习对手都可能需要可理解、有变化的行为。单纯追求胜率,可能忽略对手是否看得到行动理由,或是否有机会练习。书中的有意失误例还提示改变难度和改变失误的外观是两件事。
相关讲解见玩法体验也是控制器目标。
原书依据 · 1 处
6.2 通用游戏是什么
通用游戏玩家在运行时接收声明式规则,推导当前事实、合法动作、后继、终局和得分,再将这些通用接口交给自身搜索。原始 GDL 用于有限、确定、信息公开且固定玩家的游戏。GDL-II 扩展随机和隐信息。竞赛多用模拟,因为陌生游戏很难预先手工定估分,也可以从规则和交互自动造特征。通用视频游戏是相关方向,动作和观察接口与棋类规则语言有所不同。
相关讲解见运行时规则与搜索解耦。
原书依据 · 1 处
6.3 图灵测试和最类人化的AI
Lovelace 提出的程序受人指令之惑引到 Turing 的可观察行为评估。原型通过文字交互让评判者辨认机器,游戏版本可以让评判者只看录像,或亲自对战。录像中可见的只有动作、局面和时序,结果只能支持在这类信息条件下难以区分,身份误判也可能来自文本或操作细节。书中的聊天竞赛叙述是历史叙述。棋谱评判及两个游戏实验进一步展示观察条件的重要性。
相关讲解见盲评只能测可观察的类人性。
原书依据 · 1 处
6.4 不使用“类人化”函数的类人化游戏AI
根据人类状态和动作记录训练预测器,可以用近邻重放,也可以做监督学习。书中先训练 DQN,再用不同时间位置的动作价值向量压缩最近 16 帧,由另一网络学习人类实际动作。这样部署时可以直接输出动作,无需逐帧模拟。实验比较 DQN、直接模仿、压缩后模仿、随机以及人类,另外检查动作分布与匿名片段判断。躲避球中减少抖动并出现与人类相似的停顿,平台游戏里动作价值偏向向右,空中与地面的差异可能在压缩中丢失。动作分布相近也不足以说明整体顺序和技术水平相近。
相关讲解见用动作价值压缩模仿输入、动作频率一致仍需看时序。
6.5 使用“类人化”函数的类人化游戏AI
另一条路线把行为偏好引进树选择,用 UCB*=UCB+αH 同时考虑任务和行为风格。问卷中容易量化的描述包括动作迟缓、移动范围大和避免死亡。把它们写成停顿、探索和风险项后,用不同游戏与人类、普通树搜索和赛事控制器比较。Bait 中通关时长接近人类,某些其他游戏却出现无用停顿或左右摇摆。单项行为频率贴近人类时,连贯目的、达成率与所用时间仍可能暴露差异。
相关讲解见类人评分会奖励意外行为。
原书依据 · 1 处
参考文献
书目 [1]–[87] 提供算法、竞赛、数学谜题、强化学习与类人化的研究入口。可按问题相邻阅读:滑块估计查模式数据库 [18],矛盾表示查 de Kleer [55],树模拟查 Coulom [53],学习与树搜索查 [78]、[79],好奇心与探索查 [50]、[70],行为模拟查 [24]、[34]、[61]。这些条目描述原书的参考来源,具体出版年份、版本和实验条件应以相应出版物为准。
跨章联系
搜索与学习可以互相支持。手工启发式将问题知识编进搜索次序,策略网络把同样的职责变成从数据学习的行动先验。搜索得到的结果又可以成为训练信号。一条路线用已知规则精确排除不可能状态,另一条路线用可观测表现选择值得继续的分支。前者的保证来自约束或下界,后者的效果依赖训练与模拟条件。
还要区分三个量。解谜的路径代价用于回答一条路线有多短;博弈估值用于回答对手会应对时哪一步更可取;类人化评分用于回答行动看起来是否像指定样本。在实践中先锁定行动粒度和评价目标,再比较节点数、时间和行为结果,才有可能说明某种办法究竟改善了什么。
实践计划
- 追踪 A* 如何保留最短路,以固定版本的 NetworkX 对照出队终止、路径松弛和无启发式情形。
- 追踪树搜索的预算分配,以固定版本的 OpenSpiel 区分树内采样与最终落子决策。
两项均完成首轮源码定位与跟读计划。实验结果待执行后记录。