【项目案例】基于强化学习Q-Learning训练“汉诺塔Tower of Hanoi”游戏策略

1. 引言

汉诺塔游戏（Tower of Hanoi）是根据一个传说形成的数学问题，小规模汉诺塔问题也常常作为强化学习的入门案例。它的规则是，在游戏台上，有若干根杆子，在第一根杆子上有若干 $N\ge 1$ 个穿孔圆盘，圆盘的尺寸由下到上依次变小，需要按如下规则将第一根杆子上的圆盘转移到另一根杆子上：

1. 每次只能移动一个圆盘；
2. 在移动圆盘过程中，始终不能将大圆盘叠在较小圆盘的上面。

需要求出一个移动次数最少的方案。

为了方便演示，本文案例中，游戏台只有 $N\_pole=3$ 根杆子，以及总共只有 $N=3$ 个圆盘，分别为大圆盘 $L$，中圆盘 $M$，小圆盘 $S$，根据转移规则可知，$3$ 个圆盘在游戏台上的摆放组合一共有 $27$ 种，从大到小依次选择位置 $3^N$，底数 $3$ 是游戏台上的杆子数 N_pole，指数 $3$ 是游戏台上的圆盘数 N。当移动后的圆盘布局达到目标状态，则游戏结束。

尽管有数学家得到汉诺塔游戏的最短移动次数计算公式，但是这里我们还是用强化学习进行训练，且对于小规模问题而言，我们能够遍历所有的圆盘布局状态，因此可以在任意的圆盘起始状态，都移动到目标状态。

2. 基本要素定义

与前文《【项目案例】利用强化学习训练“井字棋”下棋策略的详细介绍》类似的是，训练汉诺塔游戏需要对各个状态进行定义，以及通过模拟采样的方式生成完整的状态序列，并不断地迭代更新动作价值函数 $Q$，最后更加训练好的 $Q$ 值表进行动作选择。由于Q-Learning是强化学习的基础值迭代算法，因此在后续内容并不会强调该算法的名称，为的是方便入门读者能更加关注强化学习的逻辑本身。

但仍有一些区别，例如，在井字棋游戏当中，每一轮动作都会使棋盘新增一个棋子，且每个棋盘有唯一的哈希值对应，因此在一个完整的状态序列中，不会出现有重复的状态；但在汉诺塔游戏当中，将某个圆盘从一个杠子上转移到另一个杠子上，接着再将圆盘转移回原来的杠子，这种做法符合游戏规则，使得在状态序列中，出现了多次相同的状态，为了惩罚这种行为，以保证训练的策略不会走“回头路”，需要将每个可以直接相连的状态的动作的即时奖励设为负数，这种显示即时奖励的问题可以通过求解最优动作价值函数来得到最优策略。

将汉诺塔游戏的状态定义为 State 类，每个状态对象都满足汉诺塔的游戏规则，因此对于本文的小规模案例而言，从大圆盘到小圆盘依次堆叠，可以得到 $27$ 种状态。这里对状态值的表示用三元列表进行表示，例如 $[1,0,0]$，依次表示 $L$ 圆盘在 $1$ 号杠子，$M$ 和 $S$ 圆盘在 $0$ 号杠子，这里的直接信息表示圆盘的分配，而同一根杠子上的多个圆盘的顺序，按照游戏规则只能按序排列。因此，判断一个状态是否能移动到另一个状态，需要判断移动的圆盘是否能取出（没有更小的同轴圆盘在顶上），以及是否能放得下（没有更小的同轴圆盘在底下）。这里定义圆盘的名称为 symbol_name = ["L", "M", "S"]，对应的值为圆盘在 symbol_name 当中的索引值，即为为 0 ,