THUWC/SC 常考的 UCT（信心上限树）你学会了嘛？

免责声明

1. 本文标题仅为形式上的表述，不具有任何实质性含义。无论清华大学（THU）今年是否举行相关考试，均与本文作者无关，作者对此不承担任何责任。
2. 本文内容仅代表作者个人观点，不代表任何组织、机构或个人的立场。
3. 本文旨在对 UCT（信心上限树）算法进行解释与说明，仅供读者参考。文中所述内容不构成任何形式的建议或承诺，读者应自行判断并承担相应的风险。
4. 作者不对因使用本文内容而产生的任何直接或间接损失承担责任。

特此声明。

学会了这个，我能获得什么？

你能够通过 THUWC 2024 的 Day2 工程题：四子棋，

以及 THUSC 2024 的 Day2 工程题：wordle。

UCT 均为这两题的官方正解（讲题人说的），可见近几次来 THU 非常喜欢在他的营中放 UCT。

或许过几周之后这个列表又会更新？

博弈问题的定义

在下文中我们所要解决的博弈问题定义如下：

• 双人
• 一人一步
• 双方信息完备（博弈双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。）
• 零和（属非合作博弈。 它是指参与博弈的各方，在严格竞争下，一方的收益必然意味着另一方的 损失，博弈各方的收益和损失相加总和永远为“零”，故双方不存在合作的可能。 零和博弈的结果是一方获利而另一方损失，且一方的所得正是另一方的所失，整个社会的利益并不会因此而增加一分。）

alpha-beta 搜索

博弈问题可以贪心嘛？

如何贪心？——极大-极小模型。

由于博弈是零和的，所以我们建出一颗价值树，树上的节点储存这个点对于我方的价值，有利则非常大，无利则非常小。

那么每一次则为先选择价值最大的，然后选择价值最小的，然后选择价值最大的，然后选择价值最小的……

这样显然不对，因为有可能某一步暂时对我方不利的，里面可以走向对我方非常有利的。

结论：不能贪心。

博弈问题可以穷举嘛？

以中国象棋为例：

时间：总状态数约为\(10^{150}\)，假设 \(1\) 微毫秒走一步，约需要 \(10^{134}\) 年。而宇宙年龄 \(1.38\times 10^{10}\) 年。

空间：如果一个原子储存一个状态，需要 \(10^{100}\) 个地球。

结论：不可能。

可以在有限步数内穷举嘛？

深蓝走一步需要搜索 \(12\) 步，如果全部搜完，时间确实短了很多——需要 \(17\) 年。

结论：不可能。

alpha-beta 剪枝则为综合了上述两种算法，对于明确无利的一种状态不去选择的算法。

由于这不是这篇文章的重点，所以一笔带过。

alpha-beta 剪枝的局限性

alpha-beta 剪枝在围棋上会失效？

是因为状态多嘛？不是本质原因。

本质原因是，我们需要对于局面进行估价。

估价需要：大量的专家知识；知识的统一性问题（围棋怎么走才算好，目前没有定论）；人工整理（人力物力财力）。

蒙特卡洛方法

蒲丰投针问题：设我们有一个以平行且等距木纹铺成的地板（如概述图），随意抛一支长度比木纹之间距离小的针，求针和其中一条木纹相交的概率。 并以此概率，蒲丰提出的一种计算圆周率的方法——随机投针法。 这就是蒲丰投针问题。

我们同样可以用在博弈上：

• 从当前局面的所有可落子点中随机选择一个点落子

• 重复以上过程

• 直到胜负可判断为止

• 经多次模拟后，选择胜率最大的点落子

蒙特卡洛树搜索：

• 建出搜索树
• 选择：随机选择一个已经搜索过的节点进行搜索
• 拓展：随机选择这个节点的下一步
• 估价：计算这个节点的权值（随机模拟向下走直到胜负可判断为止），计算收益
• 回传：回传收益（每次回传一个节点要将收益乘以 \(-1\)，因为对后手有利的局面则对于先手无利）
• 重复若干次后选择最有利的节点走

蒙特卡洛树搜索的局限性与信心上限

• 对尚未充分了解的节点的探索

• 对当前具有较大希望节点的利用

我们可以引入信心上限（UCB，Upper Confidence Bound）一概念来处理。

定义一个节点的信心上限为： \[ I_v=\overline{X_v}+\sqrt{\dfrac{2\ln(T_u)}{T_v}} \] 其中 \(\overline{X_v}\) 为节点 \(v\) 所有收益的平均值，而 \(T_v\) 则表示这个节点的访问次数。

信心上限树

将 UCB 算法应用于蒙特卡洛树搜索中，用于选择可落子点：

• 在选择操作时，节点不是随机选择，而是根据 UCB 选择信心上限值最大的节点

• 一般使用时，我们会加入一个参数 \(c\)，调节算法选择探索需求还是选择利用需求：

\[ I_v=\overline{X_v}+c\sqrt{\dfrac{2\ln(T_u)}{T_v}} \]

参考资料

• AdversarialSearch.pdf（THUWC 2024 Day2 工程题下发文件，很遗憾，我暂时不能将其上传）
• https://blog.csdn.net/u014397729/article/details/27366363