强化学习（2）：从乌鸦吃核桃到井字棋的 value 回传

小象实战讲义 · 机器学习算法精讲

人是怎么去学到的？我们为什么会去做这样的事？客观来讲，到今天仍然没有完全清晰。网上有很多关于 AI 的评论，曾经有一篇文章讲得比较有意思：今天的通用人工智能，连个乌鸦都没法比——所以先不要讲太多大话、泛泛的东西。本节（也是整门课的最后一节）就从这只乌鸦讲起：它怎么凭着一个最终的目标，自己找到一整套复杂的行为？这背后的范式就是 reinforcement learning——给机器设置分值、让它自己发现好坏。我们用井字棋把这整个过程走一遍：从状态的搜索，到跟人学的 policy function，再到靠自我博弈把输赢的分数一层层回传上去的 value function，最后看阿尔法狗怎么把两者加在一起。

💡 核心导读

• 乌鸦之谜：给定”吃到核桃仁”这一个 reward，乌鸦怎么自主找到一整套复杂行为——到今天仍是谜；今天的智能系统大多还没跳出”人预设好每一步”的范畴。
• RL 的一句话定义：给机器设置分值（欲望）——maximize 它的 utility 或 benefit、减少它的 penalty。
• state 与 action：状态是坐标、是棋盘；动作是东南西北、是落子——状态通过 action 进行更新，从旧状态过渡到新状态。
• value 的回传：终态的 +100 / −100 沿着路径每往上一层乘一次 0.9（90、81、−90、−81），任何状态都是它下面的 reward 或 penalty 往上传的结果；决策就是选分值最大的那一步。
• 阿尔法狗：$\text{score} = \alpha \cdot \text{policy} + (1-\alpha) \cdot \text{value}$——因为很多情况下状态不能全部展开，两个都用来取 trade off。

乌鸦吃核桃：一个到今天还没讲清的谜

有的科学家——不记得是神经学家、动物学家还是别的什么家，大家不要纠结这件事——曾经关注过乌鸦是怎么吃到核桃的。也许不是核桃，也许是榛子或者松果，总之是一个带硬壳的东西：它想吃里面那个仁，比如核桃，它吃不到。但是它会注意到，来来往往的街道上有很多车。于是有一些乌鸦会把核桃叼到路面上，等车碾过、把核桃压碎之后，再等没有车的时候，把里面的核桃仁拿去吃。

大家并没有搞清楚乌鸦是怎么学会这件事的。或者换个角度：如果你要做一个机器人，你怎么让这个机器人自己学会做这件事？到今天来讲，没有清晰的答案。

即使退一步，只在表面上实现”机器人捡核桃压碎”这件事，也是可以做到的：我可以让机器人去 pick up 一个核桃，把核桃放到指定的位置，等有车压过之后它的形变发生变化、散出很多碎的仁，在保证安全、不被车撞到的情况下，再把核桃仁捡回来。这些事情都可以做——但每一步都是我告诉它去怎么做的。目前的智能机器、智能系统，都没有逃脱这个范畴。

可是对乌鸦来讲，它自己的 reward 就是能吃到核桃仁。给定了这个 reward，它怎么在这么复杂的环境里找到这样一个反馈的？我们到今天仍然觉得是一个谜。这就是 reinforcement learning 要面对的问题——实际上这里边还有很多事需要做。

Reinforcement Learning：给机器设置欲望

你可以讲欲望——可以给机器设计欲望。Reinforcement learning 可以简单地讲就是：给机器设置分值，这个分值就是它的欲望，需要去 maximize 它的 utility（或者 benefit）、去减少它的 penalty——这是 reinforcement learning 最重要的一件事。

先看一个最简单的问题设置。

走房间与走格子：state 和 action 的基本设置

上一节我们已经很熟悉那张房间图了：一栋建筑里的几个房间，编号 0 到 4，户外的区域可以看成一个大房间（5 号）。门怎么开，决定了你能从哪个屋子走到哪个屋子：

• 0 和 4 互通，但 0 走不到其他任何地方；
• 3 是连接最多的房间：可以到 1、到 2、到 4——其中 3 和 2 互相可走；
• 按课件上的图，门 1 和门 4 都通向户外（从 5 号可以进来）；
• 也允许”绕圈”：你原来在 2，走一圈又回到 2，这是可以的。

目标就是走到 5 这个地方——它在门外，大家看那张房屋图，就像走迷宫一样：给定一个初始的房间，如何通过一条路径走到户外？走到户外，就是我们的 goal。有了这个目标、怎么自动地寻找路径——这就是一个最基础的 reinforcement learning 问题（上一节我们把这张图写成了 reward 矩阵、用 Q-learning 把它算完了；这一节换一个更一般的角度）。

reinforcement learning 把这个问题再深化了一步：我在一个状态（state）的时候，有几种可以选择的 action——action 就是一种执行、一个动作或行为。选了行为之后，会改变目前的状态，从一个旧的状态过渡到一个新的状态。

想象我们是机器人，给定一个空间，空间里有很多小格子：一个格子是 start（起点），一个格子是 goal（想出门到达的地方）。那么：

• state：就是目前的坐标，$S = (x, y)$；
• action：$A$ 的取值是 south、north、east、west 四个方位之一，代表往哪个方向走。

状态怎么更新？给定坐标 $(x, y)$，选择一个 action $a$，就过渡到下一个坐标：

# 状态是坐标 (x, y), 动作是东南西北四个方向
ACTIONS = {"north": (0, +1), "south": (0, -1), "east": (+1, 0), "west": (-1, 0)}

def step(state, action):
    dx, dy = ACTIONS[action]
    x, y = state
    return (x + dx, y + dy)

# 讲师的例子: 起点叫 (1,1)
s = (1, 1)
print(f"起点 state = {s}")
s = step(s, "east")    # 选择 action = east, 向右走一步
print(f"选择 east  -> {s}")
s = step(s, "north")   # 再选择 north, 向上走一步
print(f"再选 north -> {s}")

起点 state = (1, 1)
选择 east  -> (2, 1)
再选 north -> (2, 2)

起点叫 $(1,1)$，选择的 action 是 east、往右走一步，下一个位置就变成 $(2,1)$；之后向北走一步，就变成 $(2,2)$——状态是通过 action 进行更新的。当然，空间里可能存在一些障碍、有些格子过不去：在给定障碍的情况下，能不能选择一条比较好的路径、从 start 走到 goal？这就是状态和 action 之间的更新变化——reinforcement learning 的基本设置。

井字棋：一个庞大路径的搜索

还记得讲阿尔法狗的时候会讲下棋。现在从一个最简单的棋讲起——不下围棋，下井字棋：两人轮流在 $3 \times 3$ 的棋盘上画圈、画叉，谁先连成一条线谁赢。可以把它看成 $3 \times 3$ 棋盘上的”五子棋”，只不过连三就赢。如果你要写一个程序（用 reinforcement learning 或任何人工智能方法）去下这个棋，你该怎么下？如果连井字棋都不会下，也不用想下围棋或其他象棋这么难的棋了。

把问题描述一下。假设我是一个人，先下了一个红圈；机器决定下绿色的叉。给定这种状态，程序有几种选择？大家不用想——八种选择：所有状态都是先下了这一个红圈之后，程序可以下这里、下这里……一直到转一圈回来选择这里，共 8 个空位、8 种可能。

• 每一个棋盘就是前面所说的 state：这是 $S_0$ 的状态；下成了其中某一种，比如走到了这里，那就是 $S_1$ 的状态，依此类推到 $S_8$。
• $S_0$ 是怎么到 $S_1$ 的？是选择了 $A_1$；下到另一格是选了 $A_2$……一直到 $A_8$。选择了不同的 action，才过渡到目前的这个状态——这也是一个状态的变迁。

def empty_cells(board):
    return [(i, j) for i in range(3) for j in range(3) if board[i][j] == " "]

# 第一幕: 人(红圈 O)先下了一子, 这是 S0; 轮到程序(绿叉 X)
board = [[" "] * 3 for _ in range(3)]
board[1][1] = "O"
cells = empty_cells(board)
print(f"S0: 已落 1 子, 剩 {len(cells)} 个空位 -> {len(cells)} 种选择")
for k, (i, j) in enumerate(cells, 1):
    print(f"  A{k}: 落在 ({i}, {j}) -> 过渡到新状态 S{k}")

# 第二幕: 程序选了 A8 落 (2,2), 人又下了一步 -> 轮到程序
board[2][2] = "X"
board[0][0] = "O"
cells = empty_cells(board)
print(f"\n第二轮后: 已落 3 子, 剩 {len(cells)} 个合法位置 {cells}")

S0: 已落 1 子, 剩 8 个空位 -> 8 种选择
  A1: 落在 (0, 0) -> 过渡到新状态 S1
  A2: 落在 (0, 1) -> 过渡到新状态 S2
  A3: 落在 (0, 2) -> 过渡到新状态 S3
  A4: 落在 (1, 0) -> 过渡到新状态 S4
  A5: 落在 (1, 2) -> 过渡到新状态 S5
  A6: 落在 (2, 0) -> 过渡到新状态 S6
  A7: 落在 (2, 1) -> 过渡到新状态 S7
  A8: 落在 (2, 2) -> 过渡到新状态 S8

第二轮后: 已落 3 子, 剩 6 个合法位置 [(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

到这步，写程序的人看到这八种状态，该选择哪一种？到现在我们并不知道哪一种更好——也许就是随机的。比如程序随机选了一步；接下来轮到人。人会有自己的 action——我们先不关心人是怎么 act 的，先看整个机器面对人的 action 怎么去应对。

机器走了这一步、人又走了一步之后，程序还面临几种选择？这里现场就出现了歧义：

• 有人认为，所有合理的位置都可以存在——也许还有 6 种选择；
• 但更多的同学觉得不对：人已经走到这一步了，如果你不堵到那个位置，后面出现的情况就是输掉了。你第一步走到哪里都没有问题，可这一步要是走到别处，就输了；
• 不过从程序的角度数一数：一二三四五——这 6 个合法位置它都可以去下，而不只有”堵”那一个是唯一要下的。这 6 种可能里，有的不是让你赢、就是可以避免对方去赢——哪些会输、哪些不输，程序现在并不知道，这正是它要学的东西。

到这一步可以下结论了：整个下棋的过程，就是一个庞大路径的搜索过程。程序往下延伸：这一层的编号继续排下去（$S_9$、$S_{10}$……下标只是计数，不代表具体动作），对应的 action 也记作 $A_9$、$A_{10}$、$A_{14}$ 等等。其实 action 的集合非常简单——总共就 9 个动作：在哪一个格子上落子。$A$ 是一个固定的集合；$A_{10}$ 里的 10 只是一个计数，并不代表第 10 种动作。

跟人学：policy function 是监督学习

下棋变成了状态的搜索之后，第一个问题是：怎么变聪明？ 有一种情况是大家已经学过的——policy function。

给定一个状态 $S$（不用管它是 $S$ 几，讲师随手把它过渡到的那个状态记作 $S'$，“忘了命名了，随便写个名”），我们想知道：给定 $S$ 的时候，一般人是怎么选择的？做法是：把人下过井字棋的棋谱都调出来。对着某个局面——比如红圈已经落了两子、绿叉一子、还剩 6 种可能——把人下在这 6 个位置的概率画出来：这根柱子大概这么高、那根大概那么高……大部分人会集中在某一个位置上。给定状态，剩下所有可能发生的概率，这个概率可以根据人的选择概率来算——这个就叫 policy function。

其实大家会发现，阿尔法狗里面第一个用的叫 policy network，跟这个是类似的。

但要停下来想一件事：这个做法属于普通的 supervised learning——它的本质是”告诉了大家有什么好、什么坏”，从人的棋谱里学人的选择。那我们怎么让机器自己发现好坏？这就是 reinforcement learning 的正题了，接着往下讲。

自己发现好坏：value 的回传

假设程序随机选择了一步。你会发现：人从来没客气——你不瞎走吗？人就顺势走到这一步，这局直接结束了。当然也有可能程序正好堵上了，人就往下一步走。无论如何，棋局接着往下分叉、分叉、再分叉——但无论怎么下，最后只有三种结局：赢、输或者和局。

现在定义最终的分值：这一局是人赢了、机器输了，就给机器 −100 分——代表这是一个非常不好的状态，你这棋下错了；机器下对、赢了的时候，给 +100 分。这个作为一个奖赏，叫 reward。

关键的问题：reward 是从哪里来的？ 从终态来的。而终态前面还有一串状态——把 reward 沿着路径往回传，每往上一层乘一次 0.9（上一节 Q-learning 公式里的衰减系数 $\gamma$，讲师在这张棋盘上取 0.9）：

• 终态 +100，往上一层就是 $100 \times 0.9 = 90$ 分；
• 再往上一层就是 $100 \times 0.9 \times 0.9 = 100 \times 0.9^2 = 81$ 分——最后它得了 81 分，中间那层得了 90 分。当然 81 还可以再往上继续衰减；
• 输的分支同样：−100 往上变成 −90，再往上变成 −81。

GAMMA = 0.9

def backprop(terminal, depth):
    v = terminal
    print(f"  终态: {v:+.0f} 分")
    for d in range(depth):
        v = v * GAMMA
        print(f"  往上第 {d+1} 层: {v:+.0f} 分")
    return v

print("赢的分支 (+100):")
backprop(+100, 2)
print("输的分支 (-100):")
backprop(-100, 2)
print("和局分支 (0):")
backprop(0, 1)

赢的分支 (+100):
  终态: +100 分
  往上第 1 层: +90 分
  往上第 2 层: +81 分
输的分支 (-100):
  终态: -100 分
  往上第 1 层: -90 分
  往上第 2 层: -81 分
和局分支 (0):
  终态: +0 分
  往上第 1 层: +0 分

别忘了：81 会继续往上传，正分负分都会往上传。任何一个状态，都是它下边终态里的 reward 或 penalty 一路往上传的结果。对中间某一个状态，就可以这样赋值：它底下接进来的分支里既有正分、又有负分，最后合在一起——可能变成了 −8，也可能变成了 +16（本课口径到”合在一起”为止，具体怎么合计，不同算法有不同的规则）。

这套打分怎么来？不用跟人下棋——“人”也可以是一个程序模拟的：红色的圈和绿色的叉都是程序，它们之间互相你下一步、我下一步，并不告诉它们什么是对、什么是错；但总之到最后，会告诉你赢了还是输了——赢的给正 100 分，输的给负分。通过这样自己跟自己博弈、对弈，把状态不断地优化，每个状态就都有了自己的分值。这个分数在不断地 back propagate：从反馈往上去返，返到每一个状态。这个分值就叫 value——给定状态的 value function。

value 训练得比较好之后，事情就变得非常简单：给定一个状态（无论这步是轮到跟人下还是跟机器下），刚才说了下面有 6 种选择——选 6 种里分值最大的那个选择，这件事就完了。

但这里有一个代价：它需要把所有可能考虑到的值都考虑到——一路下到最后的节点，把赢、输的值返回去，和局返回 0。要对这个问题把所有可能的分值都算到——可以想象这个计算量非常大，空间复杂度非常高。这是这个朴素做法面临的问题。

阿尔法狗：policy 与 value 的加权和

阿尔法狗下围棋，最开始用的思想跟刚才一模一样。但围棋的展开空间特别特别大、很难去搜索，所以它实际上用了两个部分：一部分就是刚才说的 policy function，同时用了 value function——两者都用了。最后得到的分值 score 是一个加权和（讲师口播原话略有绕口，按语义整理如下）：

$$\text{score}(S) = \alpha \cdot \text{policy}(S) + (1 - \alpha) \cdot \text{value}(S)$$

把这个 score 作为挑选下一个状态的依据——选备选里 score 最大的那个状态。考虑这两个的 trade off，就是因为在很多情况下，我们并不能把状态全部展开。（至于”怎么在展开不动的树上搜索”，需要另一个概念——上一节已经拆解过的蒙特卡洛树搜索：selection 选值最大的 → expansion 延伸分支 → simulation 采样估值 → 反馈回传。）

收尾：什么棋下得完，什么棋下不完

最后比较一下几盘棋的搜索空间。$3 \times 3$ 的井字棋，完全展开就可以了——普通计算机完全能算得到。五子棋呢（$15 \times 15$ 的棋盘）？步骤数已经非常非常大——任何一点都可以下——但可以加一些假设：很少有人在下五子棋时，把棋子下到离”主体”超过两步的地方（主体就是目前连在一起的那些叉和圈）；不会有人突然把子下到很远处——那完全是合理的假设之外的事。所以五子棋的实际搜索空间比想象中小得多，也是可以去做的。

而围棋不一样：我下不过你中间这块地方，我可以开辟一个新战场——所以它的搜索空间确实非常巨大。那我们怎么进行搜索？——讲到这里，整门课就到这里了。这个开放的问题，留给屏幕前的你。

📝 动手练一练

1. 手算 value 回传：终态机器赢 +100，衰减系数 0.9。（a）往上一层（离终局还差一步）的 value 是多少？（b）再往上一层呢？（c）若终态是机器输 −100，这两层分别是多少？（d）和局的终态往上传多少？

2. α 的两个极端：阿尔法狗的 $\text{score} = \alpha \cdot \text{policy} + (1-\alpha) \cdot \text{value}$。α 取 1 时 score 完全由谁决定？α 取 0 呢？结合本节内容说说：为什么阿尔法狗要把两个都留下、取 trade off，而不是只用其中一个？

本章小结

本节（全课最后一节）四件事。乌鸦之谜：给定”吃到核桃仁”这一个 reward，乌鸦自主找到了一整套复杂行为——到今天仍是谜；今天的智能系统大多还停留在”人告诉它每一步怎么做”的范畴。RL 的定义与基本设置：给机器设置分值（欲望）——maximize utility、减少 penalty；state 是坐标、是棋盘，action 是方向、是落子，状态通过 action 更新（代码块 1：$(1,1)$ 选 east 到 $(2,1)$、再选 north 到 $(2,2)$）。井字棋与两个 function：下棋是一个庞大路径的搜索（代码块 2：$S_0$ 下 8 种选择 $A_1$–$A_8$，第二层 6 个合法位置都可以下、不只是”堵”那一个）；跟人学棋谱概率的是 policy function——监督学习、阿尔法狗的 policy network 与之类似；让机器自己发现好坏的，是自我博弈 + value 的回传（代码块 3：+100 沿 0.9 传成 +90、+81，−100 传成 −90、−81，和局传 0；任何状态都是底下 reward/penalty 往上传的结果），训练好后选分值最大的那步”就完了”，代价是计算量、空间复杂度非常高。阿尔法狗：$\text{score} = \alpha \cdot \text{policy} + (1-\alpha) \cdot \text{value}$，取 trade off 是因为状态不能全部展开；配合上一节的蒙特卡洛树搜索。收尾：井字棋完全展开算得到；五子棋加”不离主体两步”的假设后空间比想象小、可以做；围棋能开辟新战场、空间巨大——怎么搜索，留给你。

📋 行动清单

• 手推回传链：从 +100 出发、每层乘 0.9，把前四层写出来（90、81、72.9、65.61），体会”每远一步打一次九折”。
• 画一棵小博弈树：3 层深、带赢/输/和局各一个终态，给每个状态标上回传后的 value。
• 改衰减重跑：把代码块 3 的 0.9 改成 0.5，重跑一遍，观察 81 变成多少（50、25）——衰减越快，远处的输赢对现在的影响越小。
• 下一盘井字棋：每走一步，试着问自己”这个局面的 value 是多少”——用本节的眼光重新看这盘棋。

—— 小象教研组