1、前沿 state of art

学习经典游戏的原因

• 规则简单，细思又很深入
• 历史悠久，已经被研究了几百年
• 对IQ测试有意义
• 是现实世界的问题的缩影

已经有很多RL案例，战胜了人类，例如

2、游戏理论 game theory

游戏的最优性

对于石头剪刀布来说，最优策略，显然和对手agent策略相关，我们期望找到一种一致的策略策略，对所有对手都有效 什么是第i个玩家的最优策略$\pi$

• 最佳响应 best response $\pi^i_*(\pi^{-i})$ 是针对其他agent的最优策略
• 纳什平衡点 Nash equilibrium是针对所有对手的联合策略

v\pi(s) = \mathcal E_\pi [G_t|S_t= s]$$

• 最小、最大化价值函数，是在降低其他代理表现的同时，最大化自己的价值

• 最小、最大搜索存在纳什平衡点

• 通过深度优先树搜索，找到极值

从下往上找： 一步找max，一步找min 缺点是，运算量指数增长，不能求解整个树的分支 Solution：

• 用值函数估计器，估计叶节点
• 根据节点值，限制搜索深度

Example

二进制 线性组合 值函数

• 每 个状态特征，只有0、1
• 每个特征对应权重 w
• 线性组合

深蓝 Deep blue，并不是真正的学习，手动权重

• 知识 Knowledge
  • 8k个手动特征
  • 二进制线性组合价值函数
  • 人工个调参 权重
• 搜索 Search
  • 高性能平行字母搜索
  • 40步预测
  • 每秒
• 结果 Results
  • 击败了世界冠军

Chinook

• 知识 Knowledge
  • 二进制线性组合价值函数
  • 21个经验权重（位置、流动性）
  • 四象限
• 搜索 Search
  • 高性能平行字母搜索
  • 逆向搜索
    • 从赢的位置从后向前搜索
    • 存储所有决胜点位置在 lookup 表中
    • 在最后n步，表现完美
• 结果 Results
  • 击败了世界冠军

4、自驱动强化学习 self-play reinforcement learning

Introduction

应用 Value-based RL，完成游戏自学

• MC 向$G_t$更新 $\Delta \mathbf{w}=\alpha\left(G_{t}-v\left(S_{t}, \mathbf{w}\right)\right) \nabla_{\mathbf{w}} v\left(S_{t}, \mathbf{w}\right)$

• TD（0）向$v(s_t +1)$更新 $\Delta \mathbf{w}=\alpha\left(v\left(S_{t+1}, \mathbf{w}\right)-v\left(S_{t}, \mathbf{w}\right)\right) \nabla_{\mathbf{w}} v\left(S_{t}, \mathbf{w}\right)$

• TD（$\lambda$）向$\lambda$-return $G_t^\lambda$更新 $\Delta \mathbf{w}=\alpha\left(G_{t}^{\lambda}-v\left(S_{t}, \mathbf{w}\right)\right) \nabla_{\mathbf{w}} v\left(S_{t}, \mathbf{w}\right)$

策略提升 Policy improvement

规则的定义决定了后继者的状态 $succ(s,a)$

对于确定性的游戏，估计价值函数是足够的

\begin{aligned} v_{+}\left(S_{t}, \mathbf{w}\right) & \leftarrow v_{+}\left(S_{t+1}, \mathbf{w}\right) \ \Longrightarrow v\left(l_{+}\left(S_{t}\right), \mathbf{w}\right) & \leftarrow v\left(l_{+}\left(S_{t+1}\right), \mathbf{w}\right) \end{aligned}