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 剪枝在围棋上会失效？

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

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

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

蒙特卡洛方法

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

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

蒙特卡洛树搜索：

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

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

定义一个节点的信心上限为：

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

其中 \overline{X_v} 为节点 v 所有收益的平均值，而 T_v 则表示这个节点的访问次数。

信心上限树

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

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

参考资料