AI学习笔记——浅谈强化学习应用于游戏博弈

DeepMind 最近又上了新闻，他们最新的AlphaStar在星际争霸的游戏中与人类顶级星际玩家打成了11比1，几乎完胜人类玩家。这篇文章就结合DeepMind的创始人之一David Silver的最后一节强化学习课程，简单探讨一下AI是如何在游戏领域学习并战胜人类的。

1.完全信息双人零和博弈

首先，将游戏简化为双人零和博弈的游戏，即为

• 游戏参与者只有两方，你和计算机，或者计算机和计算机。
• 一方的收益必然意味着另一方的损失，博弈各方的收益和损失相加总和永远为“零”，(双方奖励：R1+R2=0)

有的游戏, 在任意时刻，双方是知道游戏的完全状态的，这样的游戏是完全信息的游戏，或者说是Markov的游戏，比如象棋，国际象棋，围棋等。

有的游戏是非完全信息的，比如扑克游戏，你是不知道对方手里的牌的。

这里我们研究的是完全信息游戏，当然我们也假设游戏的状态是有限的，游戏最终会分出胜负，或者是平局。

2.Minmax和Minmax搜索

知道游戏的全部状态+有限状态意味着，玩家可以通过暴力枚举，来计算所有可能的下法，形成一棵搜索树（习惯称为“Game tree”）

假设游戏只有4步，不妨令自己先手，枚举所有可能得走法，得到最后一步的价值如图：

然后从最后第4步反推第3步。第3步是自己行动，当然要Max(最大化)奖励，于是反推得到第三步的价值：

第2步是对方行动，由于是零和博弈，所以对方一定是要Min(最小化)奖励，以此类推就可以得到整个Game tree:

可以看出树的根是-2，是个负数，这就意味着如果对手能够算出这个Game tree的话，你投子的一瞬间就已经输了。

3.Minmax的局限性和改进方法

理论上来说计算机只要足够强大，就能通过Minmax搜索出整个Game tree，从而彻底打败人类。然而，即便是对于很简单的游戏，这也是几乎是不可能的。

一个游戏的复杂程度是由其深度，也就是树的层数，以及其分支数目决定的。可以令特征深度为d，分支因子为b，那么其复杂程度是随着b和d的大小成指数型增长的。

改进Minmax的方法有很多，这里重点介绍两个，值函数近似和剪枝方法。

4. Alpha-beta剪枝

剪枝顾名思义就是减掉多余的分支，优化分支因子的数目。Alpha-beta剪枝算法是应用最广的剪枝方法，其原理就是剪掉明显非最优策略的分支。举一个简单的例子就可以理解了。

如上图，当我们再做game tree 搜索的时候，已知第"1"层Min节点左分支的值函数为"8"，那么第"0"层Max节点的值函数就必然">=8"。已知"第"2"层Max节点左分支值函数为"5"，那么第"1"层Min节点的右分支就必然"<=5"，所以我们可以直接剪掉这个分支，这个分支剩下的部分就不用搜索了。

Alpha-beta剪枝不仅直接减小了分支因子b，同时还能间接减小深度因子b，比如上面的例子，如果这是一个完整的三层game tree, 减掉之后就变成了二层game tree 了。

5.值函数近似

值函数近似的方法实际上在之前的强化学习文章已经介绍过了，与其让计算机记住每一个状态，不如抽取出一些特征(feature) s和对应的权重(W)，将这些特征和权重代替状态作为V函数或者Q函数的输入，然后过迭代和学习得到近似的最优的V函数和Q函数。

近似函数可以是简单的线性函数，也可以是复杂的神经网络。有了近似函数我们就可以用我们熟悉的强化学习算法MC，TD等来学习游戏了。

6.尾巴

当然这边文章只是粗浅地介绍了人工智能在游戏中的基本原理，希望在今后的文章中能够更加深入地探讨人工智能在游戏领域的应用。

---

同样的本文主要的参考资料来自于David Silver 教授(DeepMind 的创始人)在UCL的课程以及Richard S. Sutton and Andrew G. Barto的经典书籍:Reinforcement Learning: An Introduction

同步到我的简书
https://www.jianshu.com/u/bd506afc6fc1