《RLChina2022-强化学习暑期课程-博弈搜索算法》的学习笔记
主讲人：中科院自动化 林舒老师

序列决策问题

定义与模型

通过一系列的（多步）决策来达到某种目标，而不是像DL分类中的单步决策。每一步决策都会影响后续决策。
现实生活中的例子：

• 路线规划
• 游戏博弈
• 机械控制
• 语言理解：语音的识别；文本的理解。目前的方式都是通过上下文的理解分析。
• …

序列决策问题一般可以用马尔可夫决策（MDP）模型描述。MDP包含以下组成部分：
简单起见，后续主要使用确定性的转移函数。

MDP 模型将序列决策问题统一为最优路径问题：将状态视为结点，转移函数视为边，要求从起点$s_0$ 出发到达任意终点$s_t\in T$，使得路径上奖励之和最大。

序列决策问题示例：推箱子游戏

$R(s,a)\equiv -1$表示目标是想让移动步数最少。

通用求解算法：搜索

搜索分类

• 暴力搜索：枚举算法、随机游走
• 盲目搜索：深度优先搜索、广度优先搜索
• 启发式搜索：在盲目搜索的基础上，加入一些对问题的理解。如$A^{\ast }$和$ID{A}^{\ast }$
• 对抗搜索：$\alpha -\beta$剪枝，蒙特卡洛树搜索

前三种搜索一定能达到最优解，而对抗搜索是提高了效率，在解的最优性上有些取舍

盲目搜索

• 深度优先搜索
• 广度优先搜索

1.深度优先搜索-DFS

DEEP-FIRST-SEARCH （DFS）

算法思想

回溯法并没有在暴力搜索的基础上，进行任何改进。依旧是全局遍历。

这就涉及到搜索核心优化技术：剪枝

优化思路

剪枝

剪枝分类举例：

• 上述的推箱子的游戏中，如果将箱子推到一个死胡同，那么这个路径肯定无法到达最终状态，那么就减掉。即为可行性剪枝
• 如果当前路径的未来的奖励已经无法大于当前最优解，那么直接返回。即为最优性剪枝。
  
  

其他优化

• 去除重复状态
• 迭代加深

2.广度优先搜索-BFS

Breadth-First-Search（BFS）

算法思想

基础：泛洪填充法

改进

其他基本优化

深度优先搜索与广度优先搜索对比

推箱子游戏的广度优先搜索算法代码实现

• https://github.com/jidiai/SummerCourse2022/blob/main/course2/examples/bfs-sokoban/submission.py
• https://gitee.com/rlchina/summercourse2022/blob/main/course2/examples/bfs-sokoban/submission.py

与强化学习的区别：
搜索算法不需要与环境交互，这样就省了建立环境模型这样的步骤

启发式搜索

启发搜索只是改变了搜索的顺序，指导更快找到最优解

1.$A^{\ast }$算法

算法基础：最优优先搜索

在广度优先的基础上，最先访问较好的节点

特性

局限性

2.$ID{A}^{\ast }$算法

简介

I：Iteration
D：Deep

因为我们的目的是要找奖励最大值，所以我们设定一个f下限。

算法框架

对抗搜索

1.简介

2.$\alpha -\beta$剪枝

最优性剪枝

搜索框架

翻转棋实现思路

翻转棋$\alpha -\beta$剪枝代码实现：

• https://github.com/jidiai/SummerCourse2022/blob/main/course2/examples/
  alphabeta-reversi/submission.py
• https://gitee.com/rlchina/summercourse2022/blob/main/course2/examples/
  alphabeta-reversi/submission.py

不足

此外，评估函数也不好写。

3.蒙特卡洛树搜索MCTS

实现步骤

模拟：也叫蒙特卡洛方法。随机。重复玩多次游戏，记录结果，然后在回溯进行更新

代码实践：翻转棋游戏的蒙特卡洛树搜索实现

• https://github.com/jidiai/SummerCourse2022/blob/main/course2/examples/mcts-reversi/submission.py
• https://gitee.com/rlchina/summercourse2022/blob/main/course2/examples/mcts-reversi/submission.py

应用

AlphaGo就是RL + MCTS

参考

1.http://rlchina.org/topic/500