游戏中的计算智能

Computational Intelligence for GamesCPSC 474/574耶鲁Fall 2022免费

博弈论蒙特卡洛树搜索值迭代进化计算程序化内容生成

这门课学什么

这门课用游戏做 AI 实验场。内容包括组合博弈与经典博弈论、逆向归纳与值迭代、蒙特卡洛树搜索、进化计算、神经网络、通用博弈和程序化内容生成。网站提供讲师自编讲义 PDF、示例代码和编程作业。

内容摘要

这门课把游戏当作 AI 的实验场，讲师是 James Glenn。Fall 2022 每周 2 次课，课程网站按日期列出 24 次课的示例与讲义。主线从“能精确求解的小游戏”走到“只能近似求解的大游戏”，最后讲 AlphaGo 和游戏设计辅助工具。

前 9 次课讲能精确求解的游戏。先从 Nim 和组合博弈论入手，证明 Sprague-Grundy 定理和 Nim 和规则。再把 Yahtzee、Shut the Box、Pig 这类带骰子的游戏建模为马尔可夫决策过程，用动态规划、策略迭代和值迭代求最优策略。

中间 8 次课讲同时行动和不完全信息的游戏，以及大型游戏的搜索。内容有混合策略均衡、用线性规划求解、Blotto 游戏、反事实遗憾最小化（CFR），然后是 minimax、迭代加深、置换表、α-β 剪枝、蒙特卡洛树搜索（MCTS）及其变体和 Scout 算法。最后 7 次课讲学习方法：遗传算法、TD(0) 与 Q-learning、线性函数逼近、分类器、神经网络、DQN 与 AlphaGo，以及游戏设计辅助工具。

编程作业共 5 次：Cribbage（克里比奇牌）、Shut the Box、Blotto、蒙特卡洛树搜索和 QFL，合计占 65%。另有期末项目占 15%，2 次课堂考试占 20%。作业在耶鲁 Zoo 服务器上自动测试，部分作业可以用任意语言写。学完后学员能为桌游设计最优或接近最优的 AI 玩家。

为什么值得学

课程以编程为主线，讲清 AlphaGo 一类博弈 AI 背后的搜索与学习方法。讲师的完整讲义可以免费下载。

课程信息

学校: 耶鲁（Yale）
课程号: CPSC 474/574
讲师: 詹姆斯·格伦（James R. Glenn）
学期: Fall 2022
平台: 课程官网
费用: 免费
难度: 中级
学时: 1 学期，每周 2 讲 × 75 分钟
先修: 需要离散数学（CPSC 202）和数据结构（CPSC 223）或同等基础。
材料: 讲义、作业、代码
许可证: 未注明

去课程主页 ↗

课程是英文的。本页的介绍、摘要和大纲由极客教育原创撰写，讲次标题为中文意译。开课时间、收费和链接以官方页面为准。

课程大纲 · 共 24 节

大纲依据：Fall 2022 Examples and Notes 页（24 个日期条目）（查看原始页面 ↗）

1
Nim 游戏Nim
用 Nim 引入组合博弈：两人轮流行动、信息完全、没有随机性时，怎样判断哪一方必胜。
2
组合博弈Combinatorial Games
讲组合博弈的形式定义、必胜局面与必败局面，以及游戏的和。
3
回溯、A* 与 minimaxBacktracking, A*, Minimax
复习回溯搜索和 A*，引出两人博弈的 minimax 算法。
4
组合博弈中的动态规划与值迭代Dynamic Programming and Value Iteration for Combinatorial Games
用动态规划和值迭代算出组合博弈中每个局面的胜负。
5
Sprague-Grundy 定理的引理与应用Lemmas for and Application of Sprague-Grundy
讲 Sprague-Grundy 定理需要的引理，并用 Grundy 数求解复合游戏。
6
Sprague-Grundy 定理证明；把 Yahtzee 建模为 MDPProof of Sprague-Grundy and Nim-sum Rule; Yahtzee as Markov Decision Process
完成 Sprague-Grundy 定理和 Nim 和规则的证明，再把 Yahtzee 建模为马尔可夫决策过程。
7
有限时域 MDPFinite-time MDPs (Yahtzee, Shut the Box)
用 Yahtzee 和 Shut the Box 讲步数有限的 MDP 怎样用逆向归纳求解。
8
有限时域 MDP 的计算问题Computational concerns for finite-time MDPs
讨论状态数爆炸时怎样压缩状态表示、减少计算量。
9
策略迭代与值迭代Policy iteration and Value iteration
讲求解 MDP 的两种迭代算法，并用单人 Pig 骰子游戏演示。
10
同时行动博弈Simultaneous Games
进入经典博弈论：玩家同时出招的矩阵博弈、纯策略和纳什均衡。
11
混合均衡、图解法与线性规划Mixed equilibria, Graphical Method, Linear Programming
讲混合策略均衡，用图解法和线性规划求解零和博弈。示例代码用 Python 的 scipy。
12
Blotto 与不完全信息博弈Blotto; Imperfect Information Games
分析 Blotto 兵力分配游戏，再引入玩家看不到全部信息的博弈。
13
反事实遗憾最小化Counterfactual Regret Minimization
讲 CFR 算法，用 Kuhn 扑克演示怎样逼近不完全信息博弈的均衡。
14
minimax、启发函数、迭代加深与置换表Minimax, Heuristics, Iterative Deepening, Transposition Tables
讲大型游戏中限制深度的 minimax 搜索，以及让搜索更快的工程技巧。
15
α-β 剪枝与蒙特卡洛树搜索Alpha-Beta Pruning, Monte Carlo Tree Search
讲 α-β 剪枝，再引入基于随机模拟的蒙特卡洛树搜索。
16
MCTS 的变体MCTS Variations
讲蒙特卡洛树搜索的改进版本，例如 RAVE 和不同的模拟策略。
17
Scout 算法Scout
讲 Scout 算法：先用零窗口搜索试探，加快 α-β 搜索。
18
遗传算法Genetic Algorithms
讲用选择、交叉和变异进化游戏策略或评估函数。
19
TD(0) 与 Q-learningTD(0) and Q-learning
讲时序差分学习和 Q-learning，让智能体从对局经验中学习局面价值。
20
线性函数逼近Linear Approximators
状态太多时，用特征的线性组合近似价值函数。
21
分类器Classifiers
讲监督学习分类器，并演示用贪心法构建决策树。
22
人工神经网络Artificial Neural Networks
讲神经网络基础，用 Keras 搭建网络，并讨论怎样编码输入特征。
23
DQN 与 AlphaGoDQN, AlphaGo
讲深度 Q 网络，以及 AlphaGo 怎样结合策略网络、价值网络和 MCTS。
24
辅助游戏设计的工具Tools to Aid Game Design
讲用 AI 方法辅助游戏设计，联系程序化内容生成。

耶鲁的其他AI课

人工智能 · Artificial Intelligence
自动化决策系统 · Automated Decision Systems
图结构数据上的深度学习 · Deep Learning on Graph-Structured Data
可信深度学习 · Trustworthy Deep Learning

← 返回全部AI课　·　← 只看耶鲁