来源书籍

AI游戏开发和深度学习进阶

Skill 版本:v24 66 张卡片

伊庭齐志 · 曹旸 译 · 机械工业出版社 · 2021-08-01 · ISBN 9787111688464

全书导读

本书用谜题和游戏解释一条渐进路线。先把问题写成可以计算的状态与操作,再用规则、估计和采样决定有限预算下先看什么,最后学习原先靠人编写的决策线索。能赢、能证明、能解释局面和能像人一样操作,是几种不同的检验任务。

  1. 第 1 章用游戏史和战略盗用区分竞赛表现、胜负理论与可执行策略。
  2. 第 2 章比较按深度、步数和代价估计扩展状态,突出代价与启发式的约定。
  3. 第 3 章把冲突变成约束、剪枝条件和可追溯的假设,展示怎样减少无用分支。
  4. 第 4 章让对手也能选择,引出极大极小、上下界剪枝、随机模拟与实时预算。
  5. 第 5 章从专家棋谱、游戏回报、进化适应度与预测误差学习策略和评估。
  6. 第 6 章将规则泛化和行为类人性变成不同的目标,并讨论观察方式会怎样改变评价结果。

译者序

译者用围棋说明学习与搜索的分工。策略模型从棋盘估计值得尝试的落子,树搜索再比较这些落子可能带来的后果。序言也把这一取舍与 A* 搜索联系起来,并引出全书最后讨论的类人表现。

前言

前言将游戏和谜题作为观察搜索、学习和优化的场景。正文会结合规则明确的游戏实例解释技术,涉及深度学习、强化学习和进化计算。作者把讲清通用方法作为写作目标,并说明实例部分来自系统工程课程及实验室研究。

第1章 谜题与游戏AI的过去和现在

题页用羽生善治设想改变将棋规则的说法,引出规则固定的游戏被计算机掌握后,人类还能如何继续探索。

1.1 关于AI的预言成真了吗

本节从西蒙和纽厄尔对棋类、定理证明、音乐和心理理论的早期预测切入,比较这些方向的发展速度,并说明正文把游戏与谜题作为讲解 AI 方法的主要场景。

1.2 游戏AI的历史和背景

本节把早期棋类程序、跳棋经验学习和人机对弈放在同一条历史线上。早期设备限制棋盘和搜索深度。后来的系统用更好的盘面表示、评估和学习来提升棋力。图 1.1 是 Travel Mate II 商用电子棋机的实物照片,作为早期可供家庭使用的对弈设备案例。深蓝比赛的叙述还表明,人的压力与对机器能力的先入判断会影响比赛表现。

相关讲解见棋力受搜索预算约束、跳棋程序从经验学习。

对弈系统赢下某场比赛,只给出了该次比赛的结果。求解一个游戏至少要确定从指定初始局面出发,双方采用最优策略时会发生什么。书目 [73] 列出 2007 年的跳棋论文,本节正文却写作 2017 年。魔方叙述也突然切换到扑克,因此这里分别保留全搜索与均衡策略的例子,日期与残缺过渡留作版本问题。竞猜式博弈的均衡允许随机选择,猜拳中均匀分配三种动作便是一个例子。

原书依据 · 2 处

1.3 游戏AI是否会剥夺人类的乐趣

本节讨论棋谱数据库和固定开局如何影响创造性。Chess960 用受约束的随机初始局面减少背谱优势。深蓝案例引出另一问题,即棋力测评与对人类思考的解释各自需要什么证据。 棋力与认知是两项指标。

相关讲解见随机开局减少背谱优势。

原书依据 · 2 处

1.4 游戏AI的意义

高级国际象棋允许棋手在对弈时查阅软件分析,并保存搜索树以供复盘。随后以数学计算实验说明,计算机还能帮助形成猜想,证明仍需另行给出。 协作流程影响组合棋力。

相关讲解见计算实验帮助形成猜想。

原书依据 · 2 处

1.5 游戏的深奥程度与“先下手为强”定理

Chomp 的玩家选定一块还在棋盘上的巧克力,同时移除该块以及相对它坐标都不小于它的剩余格。图 1.2 用 4×6 棋盘示范两次操作。以左下格为 (1,1),先取 (5,4),清除顶部最右两格,再取 (4,2),清除仍存在且列号至少为 4、行号至少为 2 的格子。左下毒格仍保留。正文由特殊尺寸的开局过渡到一般尺寸的战略盗用证明,再把约数游戏的质因数指数配对成二维棋盘。两种游戏都按同一条规则删除后续合法选项。约数游戏对应巧克力棋盘说明如何从整除关系得到这条规则。在有限的双人完全信息确定性对局中,若终局按先手胜、后手胜、和棋排序,可以从终局倒推:先手节点选对先手最好的一项,后手节点选对先手最差的一项。初始节点因此得到确定的理论结果。若规则允许无限重复,就需要先按实际规则处理和棋或循环,才能直接使用有限树的倒推说明。 这一分类说明理论结果存在,求出初始节点的值和可执行策略仍可能需要大量计算。 战略盗用证明先手必胜。

原书依据 · 2 处

第2章 解谜的AI

章题页用一个缺少具体棋局的问题引出本章。要让计算机回答怎样走,先给出局面、合法动作和目标条件。

2.1 搜索树

把谜题转换成状态空间,有两个步骤。先判断初始状态和目标是否在同一可达范围,再规定怎样生成下一状态。15 谜题的具体初局交换了 14 和 15,空格仍在同一位置。由于每次空格和相邻滑块交换,从同一格出发并回到同一格需要偶数步,所以这一个奇置换无法由合法移动完成。渡河题用两岸人数和船的位置表示状态。每一步先枚举船上组合,再剔除人数守恒或安全条件不满足的情况。同一状态可以由不同路线到达,甚至返回原点,图搜索需要识别这些重复状态。

图 2.1 展示 14–15 谜题的历史插画。图 2.2 给出初始人数和船的位置。图 2.3 的两条末端路线共用同一个目标局面,图 2.4 则展示每个非根节点只有一个父节点的树。 相关讲解见空格回原位限制滑块奇偶性、用约束生成渡河状态、搜索路径会汇入同一状态。

原书依据 · 3 处

2.1.2 深度优先搜索

深度优先搜索先扩展刚生成的后继。无新状态时,回到此前留下的候选。图 2.5 用编号区分生成顺序与扩展顺序;结合公式 (2.22)–(2.24),应当是 k₂ 已扩展、k₃ 待展开,新加入的是 k₆。图 2.6 说明深度上限使另一条通往终点的分支有机会被探索。图 2.7 的 8 谜题在编号 41 处抵达目标,编号表示生成次序。

相关讲解见栈决定深度优先扩展、前沿和已扩展集消除重复、逐步加深避开无限分支。

原书依据 · 3 处

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 时更新队列,对不一致启发式允许重开。标准计数的八数码曼哈顿距离只加编号滑块,每一步最多减少一,因此确实是下界。原文示例将空格算进错位数、又称距离和可能超过界限,不能用于证明标准版本的最优性。

相关讲解见按已付代价与余程排序、下界如何保证最优解、更紧的启发式压缩搜索。

原书依据 · 3 处

2.2 推箱子

搜索动作以推箱一格计费,玩家的走动用可达区域表示。从玩家所在格开始,穿过空格做四邻域填充,便知道能从哪一侧推箱。启发式忽略箱体占位与终点分配冲突,把每个箱到最近目标的墙内距离相加。不可达后方会使一些箱子永久卡死。书中进一步把暂时可推的箱子移除,再检查冻结箱和封闭目标;这是检测部分死局的办法。图 2.13 的实例三种算法都以 6 次推动完成。正文写 A* 生成 16 个节点,表 2.2 首个例列 12;比较时分别引述。表内 44 步案例中,广度和迭代加深均受内存限制。

相关讲解见放宽规则得到代价下界、先识别无解状态再扩展。

原书依据 · 2 处

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 基只截取了开头。

相关讲解见先填候选最少的格子、把数独改写为多项式系统。

原书依据 · 2 处

第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 处

3.5 解开国际象棋谜题

过渡节把皇后回溯扩展到两个目标类型:放尽可能多的棋子,或让既定数量的棋子攻击指定格。两种目标都能先利用棋盘结构压缩分支。

3.5.1 尽可能放置多个棋子

求最大放置数时,以当前子数加仍可放置格子数得到上界。上界低于已知最好解即可停止这一支,保留等号才能枚举同样好的答案。图 3.25 汇集互不攻击或不共线的例子。骑士总落在另一颜色的格子,故单色可放满 32 个;图 3.26 将盘面分成 2×4 块,每块可用四对互攻格覆盖,补出至多 32 个的论证。国王在每个 2×2 块至多出现一个,全盘至多 16 个,按两方向隔一格摆放可达到 16。

相关讲解见分支上界低于现解就剪枝、用分块证明摆放上限。

原书依据 · 2 处

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 处

4.3 黑白棋与Fool’s mate

黑白棋以两套 64 位掩码表示黑白棋子。开局可查既定走法,中局以开放度、边缘、稳定子与行动自由度加权估分,残局则更容易展开到终局。图 4.8 从角与边的结构估计未来不会被翻转的子。图 4.9 的小规模对战里,与即时数子相比,稳定子和机动性组合表现较好。步数多的阶段在相同预算下往往只能搜浅一些。愚者自将将双方任务改为合作消灭白子,短期保留白子有时有利于之后集中翻转。原书的先手步数受初始布子是否计入以及双方回合计数影响。

相关讲解见行动自由与棋子稳定性、合作型谜题改写双方目标。

原书依据 · 2 处

4.4 A*马里奥

实时平台动作中,左右、跑和跳的组合是分支。节点需要保留位置与速度等可以影响下一帧的量,用简化运动模型估算向前最多能走多远及到终点的时间。图 4.12 展示当前位置及若干动作后继。书中的小样本实验表明,同样的节点配额下,深度搜索尤其依赖动作排列;A* 与物理估分配合在该实验中更稳定。示例中的加速与衰减代码应当作为模拟基准,不能脱离实际运行状态比较拟合精度。

相关讲解见运动状态决定可达范围。

原书依据 · 1 处

4.5 蒙特卡罗树搜索

平坦蒙特卡罗给每个候选着法固定若干盘随机模拟,比较频率估计。三次模拟的例子观察到 1/3、3/3 和 2/3,样本极少,也受到模拟对手会走错棋的系统性影响。树搜索则反复执行选择、扩展、模拟及回传:模拟次数多的热门分支最终显式分开若干后继,再单独比较。UCT 在树的每次选择中加入探索奖励,避免早期遇到偶然坏结果的分支被永久冷落。

相关讲解见随机模拟胜率依赖对手模型、用回传结果分配模拟预算。

原书依据 · 2 处

4.6 立体四子棋

球在杆上受重力支撑,只能落在该杆当前最高球之上。潜在四连只剩一格时,还要检查能否立刻落到那一格,可以利用必须先填下层这一条件判断陷阱。对战中,UCT 在部分评价函数对手面前随模拟数增加而改善;能识别有效威胁的极大极小搜索仍可抗衡。浅层最优着法可以优先放进深一层搜索。用固定节点配额替代固定深度可在早期降深、残局加深。

相关讲解见重力约束改变三连威胁、按节点预算调整搜索深度。

原书依据 · 2 处

4.7 黑白棋的蒙特卡罗算法和NegaScout算法

NegaScout 的动机是:若棋步排序靠谱,多数后续分支只需验证能否改善当前最好结果。先搜第一步得到候选值,对后来动作采用整数分值下的一格窗口。若未越过 α,直接继续;若达到 β,剪去该分支的余项;中间情况再扩大窗口核实。原书列式首条的 α≤x 与下一条重叠,按判定目的应为 x≤α。三秒对战中,所设 NegaScout 版本赢下 20 局;当限制其深度后,UCT 能取得部分胜局。

相关讲解见用窄窗先判断能否改进。

原书依据 · 1 处

4.8 如何赢得博弈

多臂老虎机将每个选择建模为未知平均回报,有限次数内兼顾学习和收益。贪婪容易被头几次噪声锁在次优选择。ε-贪婪固定比例随机试,UCB 为试得少的选项增加奖励,通常形如平均值加 c·√(ln n/nᵢ)。标准有界独立回报假设下,次优臂的尝试次数及累计期望损失可受对数增长约束。书中正态报酬与伯努利报酬的小规模实验排序不同;理论条件和实验设置应分别记录。

相关讲解见上置信界给少试选项机会、遗憾衡量试错的累计成本。

原书依据 · 2 处

4.9 消灭幽灵:AI吃豆人

强力道具会暂时把幽灵从威胁变成可以得分的目标,因此状态需要包含阶段时间和道具。不同版本的随机移动、屏幕捕捉延迟或能否直接读状态会影响竞赛可比性。节中先用简化交替行动环境试极大极小和剪枝,再把随机环境压成路口决策。路口不变可复用前一帧的树,以简化的幽灵模型执行模拟。模拟中生存、清豆与驱除幽灵的终止规则会改变得分偏好。表 4.14 以得分、每帧得分及消灭幽灵数比较,限制树深可换取稳定性。

相关讲解见只在分岔处展开动作。

原书依据 · 1 处

第5章 学习、进化和游戏AI

章题页记录围棋界对非惯例棋路的惊讶。以下各节讨论从棋谱、对弈奖励和行为结果取得决策知识。

5.1 来自AlphaGo的震撼

围棋的合法着点和对弈长度使穷举不可行。早期 AlphaGo 将人类棋谱用于预测着法,用自我对弈改进策略,再用自我对弈结果训练价值估计。树选择使用策略产生的先验与已访问统计,叶估值融合快速模拟和价值网络;策略负责将试验集中到更有希望的动作,价值预测让部分评估提前结束。相邻棋谱局面高度相似,新鲜自对弈局面有助于缓解记忆棋谱的问题。

AlphaGo Zero 的输入改用当前及历史棋盘和待落子颜色,以一个网络给出策略与价值,用搜索得到的访问分布和对局结果循环训练。AlphaZero 把这种办法用于围棋、国际象棋和将棋。学习曲线、训练时间和棋力比较来自不同实验设定;书中对版本名称和硬件的写法不用于直接推断训练成本。

相关讲解见策略先验与价值评估分工、自我对弈把搜索变成老师、连续棋局会放大训练冗余。

原书依据 · 3 处

5.2 DQN和街机游戏

奖励晚到意味着正确动作没有现成标签。Q 学习把动作价值向即时回报加折扣的下一状态最大动作价值拉近,终局去掉未来项。探索用于收集贪心路径之外的经历。当状态变为像素,不能为所有局面存表,DQN 用卷积网络对每个动作输出一个估计。经验回放把相邻转移拆开后随机采小批量,减少更新序列的相关性。得分变化是反馈,回合到失败或完成才结束。图 5.10 的训练曲线说明两个示例的得分会在交互中改善,不能据此断言全部游戏都达到同样水平。

相关讲解见用后继价值更新当前动作、经验回放打散连续训练样本。

原书依据 · 2 处

5.3 进化的马里奥

控制器将七个相对格的敌人与物体标志加上可跳与着地状态编码为 16 位索引。每个索引对应一个五位动作组合。利用关卡前进距离给每条策略表打分,执行选择、交叉和变异。从例子的 8451 号表项读到 11 后,可解成跳、向右、冲刺的组合。局部观察有歧义时,相同索引可能对应不同行动需求。

相关讲解见遗传搜索可直接优化动作表。

原书依据 · 1 处

5.4 神经进化

NEAT 让节点和连接结构与权重共同进化。从较小网络开始,可以添一条连接,也可以停用一条旧连接并在中间插节点。基因型保留输入、隐藏、输出及连接端点、启用状态、权重、创新编号;表现型只执行当前有效的网络。交叉时按编号找到共同突变,不依赖基因在列表中的位置。

相关讲解见创新编号对齐异构网络基因。

原书依据 · 1 处

5.5 吃豆人的神经进化

本节区分外部研究中的模块化 NEAT 和书中根据连接端点坐标用遗传编程产生权重的实验。控制器为每个方向评分,输入含敌我距离、追近状态、路口、豆与时间等可行动特征。OFNJ 数下一路口后安全可达的路口,帮助提前识别出路。诱饵策略主动引近敌人才吃强力道具,能得到连续奖励,却可能在时限前来不及完成。该实验的分数比较依赖模拟条件。

相关讲解见用可逃路径识别包围风险、模块切换可适应阶段任务。

原书依据 · 2 处

5.6 充满好奇心的马里奥

奖励稀疏时,ICM 从交互中生成额外反馈。逆模型看动作前后两帧的编码并预测做了什么,促使编码关注可被行动影响的变化。正模型用当前编码和真实动作预测下一编码,预测误差作为内在奖励。策略优化内外奖励之和。遇到一长串协调动作才能越过的瓶颈,前段熟悉以后误差趋低,单靠好奇心仍难继续。

迁移实验比较新关卡从零训练、直接运行旧策略、预训练后微调。同样的预训练对第二和第三关的收益不同;背景、可达瓶颈及剩余探索信号都影响成绩。状态计数近似法是书中提到的另一种内在奖励思路。

相关讲解见预测误差可作探索奖励、好奇心迁移受新关卡制约。

原书依据 · 2 处

第6章 游戏AI与类人化

霍夫施塔特借一段邀请对弈又提议吟诗的想象对话,把棋力和人们赋予行为的意义区分开。

6.1 为什么需要类人化的AI

玩法教学、难度调节和练习对手都可能需要可理解、有变化的行为。单纯追求胜率,可能忽略对手是否看得到行动理由,或是否有机会练习。书中的有意失误例还提示改变难度和改变失误的外观是两件事。

相关讲解见玩法体验也是控制器目标。

原书依据 · 1 处

6.2 通用游戏是什么

通用游戏玩家在运行时接收声明式规则,推导当前事实、合法动作、后继、终局和得分,再将这些通用接口交给自身搜索。原始 GDL 用于有限、确定、信息公开且固定玩家的游戏。GDL-II 扩展随机和隐信息。竞赛多用模拟,因为陌生游戏很难预先手工定估分,也可以从规则和交互自动造特征。通用视频游戏是相关方向,动作和观察接口与棋类规则语言有所不同。

相关讲解见运行时规则与搜索解耦。

原书依据 · 1 处

6.3 图灵测试和最类人化的AI

Lovelace 提出的程序受人指令之惑引到 Turing 的可观察行为评估。原型通过文字交互让评判者辨认机器,游戏版本可以让评判者只看录像,或亲自对战。录像中可见的只有动作、局面和时序,结果只能支持在这类信息条件下难以区分,身份误判也可能来自文本或操作细节。书中的聊天竞赛叙述是历史叙述。棋谱评判及两个游戏实验进一步展示观察条件的重要性。

相关讲解见盲评只能测可观察的类人性。

原书依据 · 1 处

6.4 不使用“类人化”函数的类人化游戏AI

根据人类状态和动作记录训练预测器,可以用近邻重放,也可以做监督学习。书中先训练 DQN,再用不同时间位置的动作价值向量压缩最近 16 帧,由另一网络学习人类实际动作。这样部署时可以直接输出动作,无需逐帧模拟。实验比较 DQN、直接模仿、压缩后模仿、随机以及人类,另外检查动作分布与匿名片段判断。躲避球中减少抖动并出现与人类相似的停顿,平台游戏里动作价值偏向向右,空中与地面的差异可能在压缩中丢失。动作分布相近也不足以说明整体顺序和技术水平相近。

相关讲解见用动作价值压缩模仿输入、动作频率一致仍需看时序。

原书依据 · 2 处

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 区分树内采样与最终落子决策。

两项均完成首轮源码定位与跟读计划。实验结果待执行后记录。

生成进度与管理记录

AI游戏开发和深度学习进阶

Skill 版本:v24

执行模式:light

建档进度:done

全书评级:经典原理。A* 的代价界、约束回溯、α–β 剪枝与 UCT 的预算分配跨题复用,信息浓度高、稳定性高。竞赛参数和版本沿革作为当时的案例。

生成后复核:轻量模式跳过。

阅读整书笔记

章节进度追踪表

章节号 章节标题 状态 卡片数
01 译者序 done 0
02 前言 done 0
03 第1章 谜题与游戏AI的过去和现在 done 0
04 1.1 关于AI的预言成真了吗 done 0
05 1.2 游戏AI的历史和背景 done 2
06 1.3 游戏AI是否会剥夺人类的乐趣 done 2
07 1.4 游戏AI的意义 done 2
08 1.5 游戏的深奥程度与“先下手为强”定理 done 2
09 第2章 解谜的AI done 0
10 2.1 搜索树 done 3
11 2.1.2 深度优先搜索 done 3
12 2.1.3 宽度优先搜索 done 1
13 2.1.4 A*搜索 done 3
14 2.2 推箱子 done 2
15 2.3 数字连线 done 1
16 2.4 日式华容道 done 1
17 2.5 孔明棋 done 1
18 2.6 尝试用数学知识解决数独问题 done 2
19 第3章 依赖约束的谜题和非单调推理 done 0
20 3.1 纵向搜索与回溯 done 0
21 3.2 数学家弄错的国际象棋谜题 done 1
22 3.3 线条图的解释与错觉画 done 1
23 3.4 ATMS与四色问题 done 3
24 3.5 解开国际象棋谜题 done 0
25 3.5.1 尽可能放置多个棋子 done 2
26 3.5.2 尽可能攻击多个区域 done 1
27 3.6 Knuth的谜题与位棋盘 done 1
28 第4章 会玩游戏的AI done 0
29 4.1 井字棋与树 done 0
30 4.2 游戏的树搜索 done 4
31 4.3 黑白棋与Fool’s mate done 2
32 4.4 A*马里奥 done 1
33 4.5 蒙特卡罗树搜索 done 2
34 4.6 立体四子棋 done 2
35 4.7 黑白棋的蒙特卡罗算法和NegaScout算法 done 1
36 4.8 如何赢得博弈 done 2
37 4.9 消灭幽灵:AI吃豆人 done 1
38 第5章 学习、进化和游戏AI done 0
39 5.1 来自AlphaGo的震撼 done 3
40 5.2 DQN和街机游戏 done 2
41 5.3 进化的马里奥 done 1
42 5.4 神经进化 done 1
43 5.5 吃豆人的神经进化 done 2
44 5.6 充满好奇心的马里奥 done 2
45 第6章 游戏AI与类人化 done 0
46 6.1 为什么需要类人化的AI done 1
47 6.2 通用游戏是什么 done 1
48 6.3 图灵测试和最类人化的AI done 1
49 6.4 不使用“类人化”函数的类人化游戏AI done 2
50 6.5 使用“类人化”函数的类人化游戏AI done 1
51 参考文献 done 0

非正文排除

spine项 类型 排除理由
titlepage.xhtml 封面 封面图页
0000.xhtml 阅读平台宣传 仅有平台标识及宣传语
0001.xhtml 版权页 出版和发行信息
0002.xhtml 作者简介 作者履历
0003.xhtml 译者简介 译者履历

待关联术语

术语名 出现章节 一句话语境
Herbert Alexander Simon 04 早期人工智能预测与认知科学
Allen Newell 04 早期人工智能预测与 Logic Theorist
Logic Theorist 04 早期定理证明程序,脚注提名
Marvin Minsky 05 讨论早期棋类程序的意外行为
位棋盘 05 早期高速盘面表示的延伸阅读,正文转引 3.6 节
反事实遗憾最小化(CFR) 05 脚注提名的近似均衡计算方法
纳什均衡 05 脚注用猜拳举例,正文只提及近似均衡策略
Bobby Fischer 06 批评依赖固定开局与棋谱数据库
John Searle 06 追问棋力能否解释棋手思考
Douglas Richard Hofstadter 06 用飞行类比区分任务表现与实现方式
中文房间 06 脚注提名的强人工智能思想实验

引用文献

标题 类型 出现章节 一句话语境
とっておきの数学パズル 书 08 Chomp 案例出处 [13]
マーチン·ガードナーの数学ゲーム2 书 08 Chomp 与战略盗用证明的出处 [19]
必勝法の数学 书 08 策梅洛定理与棋类胜负讨论的参考 [30]
Checkers is solved 论文 08 西洋跳棋双方最优时和棋的依据 [73]
Heuristic Problem Solving: The Next Advance in Operations Research 论文 04 早期人工智能预测 [77]
Cybernetics 书 05 可下棋的机器与人类智能 [11]
Programming a Computer for Playing Chess 论文 05 分支逻辑树与早期棋类程序 [76]
Some studies in machine learning using the game of checkers 论文 05 跳棋程序的经验学习 [74]
Deep Thinking 书 05 深蓝比赛与棋手复盘 [17]
完全なるチェス―天才ボビー·フィッシャーの生涯 书 06 固定开局与依赖棋谱的批评 [38]
人工知能と人工生命の基礎 书 06 中文房间与强人工智能讨论 [5]
サイエンス21 书 06 Hofstadter 对棋力与思考的评论 [15]
決定力を鍛える チェス世界王者に学ぶ生き方の秘訣 书 07 人机协作流程 [16]
近世数学史談·数学雑談 书 07 高斯计算实验 [28]
プログラミングで愉しむ数理パズル 书 07 计算机解数学问题与谜题 [8]
Deep Thinking 书 07 高级国际象棋的搜索分析 [17]
人間に勝つコンピュータ将棋の作り方 书 05 Bonanza 学习评价函数 [41]
Checkers is solved 论文 05 正文援引西洋跳棋求解成果 [73],书目列 2007 年
The Emotion Machine 书 05 脚注提名并用于讨论机器异常行为的类比
Gödel, Escher, Bach: An Eternal Golden Braid 书 06 Hofstadter 简介中提名
それでも人生にイエスと言う 书 09 章题页引文;书目 [39] 用日译书名,章题页标 Man’s Search for Meaning
ガードナーの数学パズル·ゲーム 书 10 滑块谜题与置换奇偶性 [20]
サム·ロイドの「考える」パズル 书 10 15 谜题传播及起源 [33]
パターンデータベースを利用した箱入り娘型スライディングパズルの最適解の探索 论文 16 用模式数据库估计 [18]
Sage 框架 18 图 2.24 用符号代数求解
Gröbner Basis Representations of Sudoku 论文 18 数独的代数表示 [46]
「数独」を数学する 书 18 数独研究 [45]
人工知能と人工生命の基礎 书 18 代数方法参考 [5]
人工知能の方法―ゲームからWWWまで― 书 18 代数方法参考 [6]
Searching for Bobby Fischer 书 19 章题页引文 [12]
Nクィーン問題の解について 论文 21 八皇后解的数量 [1]
mario-astar-robinbaumgarten 源码项目 32 原书提供 A* 平台动作实例及代码路径
Ms. Pac-Manにおけるモンテカルロ木探索 论文 37 路口决策和模拟 [3]
Mastering the game of Go with deep neural networks and tree search 论文 39 原书 [78] 的策略、价值与树搜索
Mastering the game of Go without human knowledge 论文 39 自我对弈训练 [79]
Human-level control through deep reinforcement learning 论文 40 DQN 玩 Atari 的结果 [66]
AkitoSeki/marioAI 源码项目 41 实现局部观察到动作的遗传策略表
Evolving Neural Networks through Augmenting Topologies 论文 42 NEAT 结构演化 [81]
Curiosity-driven Exploration by Self-supervised Prediction 论文 44 ICM 和迁移实验 [70]
General game playing: Game description language specification 论文 47 基础规则语言 [64]
A general game description language for incomplete information games 论文 47 不完全信息扩展 [83]
Computing machinery and intelligence 论文 48 图灵的行为检验 [85]
チューリングテストによるゲームAIの客観的評価 论文 48 游戏行为盲评 [44]
Deep Q-Networkを用いた状態表現による人間行動を模倣するゲーム 论文 49 用价值输出压缩观察 [34]
MCTSの補正に基づく一般ゲームにおける人間らしさの実現 论文 50 为 UCB 添加行为评分 [24]
Modifying MCTS for Human-like General Video Game Playing 论文 50 从人类动作习惯修订搜索 [61]

资金安全问题案例

问题标题 问题卡 解决方案卡 出现章节 一句话说明

实践卡进度

序号 实践标题 实践方式 状态 关联章节 产出
001 追踪 A* 如何保留最短路 实现深读 done 13 计划与首轮源码映射
002 追踪树搜索的预算分配 实现深读 done 33、36、39 计划与首轮源码映射

实践候选筛选:done

未采用完整训练 AlphaZero 与类人盲评。前者需要明显增大的计算和实验范围,后者需要额外设计参与者、匿名片段与评价条件。保留两项可用固定版本源码、在小样例中独立追踪的实践。实践已经规划,尚无执行结果。

相关主题

从本书的主题进入跨书阅读,对照其他书籍的讲解。下方数量包含主题关联的全部卡片与书籍。

暂无公开主题。