专栏名称: 唤之

动手写一个 DQN 的棋牌 AI

唤之 · 掘金 · 程序员 · 2018-02-01 10:22

正文

1. 深度强化学习和DQN 算法
2. 棋类游戏和七鬼五二三
3. DQN 算法求解七鬼五二三
4. 实验结果和分析
5. 结论

深度强化学习是学术界研制游戏 AI 的主流算法。这篇文章我们将用深度强化学习早期代表算法 DQN 算法探索棋牌 AI。

1. 深度强化学习和DQN 算法

机器学习分为三个部分：表示、目标和优化。深度学习 (Deep Learning, DL) 属于表示范畴，能够自动抽取事物的特征，将之表达成计算机能理解数据。强化学习 (Reinforcement Learning, RL) 则属于目标范畴，能够用设定奖励函数和自动探索将模型训练到期望的目标。深度强化学习 (Deep Reinforcement Learning，DRL) 是将深度学习与强化学习结合起来的算法，利用深度学习强大的特征抽取表示能力，利用强化学习的目标能力，从而实现更通用的人工智能。

Deep Q Network (DQN) 是深度学习和传统强化学习算法 Q-Learning 的方法，是深度强化学习早期代表算法之一。Q-Learning 算法其实是状态-动作价值版本的时差学习 (Temporal Difference, TD) 算法。Q-Learning 利用马尔科夫性质，只利用了下一步信息。Q-Learning 让系统按照策略指引进行探索，在探索每一步都进行状态价值的更新，更新公式如下所示。

$\begin{eqnarray*} q(s,a) = q(s,a) + \alpha {r + max_{a'}{\gamma q(s',a')} - q(s,a)} \end{eqnarray*}$

s 为当前状态，a 是当前采取的动作，s’ 为下一步状态，a’ 是下一个状态采取的动作，r 是系统获得的奖励， $\alpha$ 是学习率， $\gamma$ 是衰减因子。在深度学习时代，深度学习和 Q-Learning 的结合，再加上 replay-memory、doubble-network 的技巧，便诞生了 DQN。

2. 棋类游戏和七鬼五二三

棋牌游戏是棋类游戏和牌类游戏的统称。棋类游戏和牌类游戏不同，它们有各自鲜明的特点。棋类游戏是明牌，专业说法是完全信息游戏，典型的棋类游戏有中国象棋、国际象棋和围棋等。牌类游戏是暗牌，专业说法是非完全信息游戏，典型的牌类游戏有斗地主、七鬼五二三、桥牌和德州扑克等。

这次我们要用的游戏是七鬼五二三。在中国各地的七鬼五二三有不同的版本，我们在非完美信息游戏 AI 环境 —— RoomAI 实现的七鬼五二三游戏采用了一位同事（哈大王）家乡的版本：多人使用一副或者多副扑克，一开始随机每人五张牌，牌的大小排列——7、大王、小王、5、2、3、A、K、Q、J、10、9、8、6、4；游戏分为两个阶段，准备阶段和出牌阶段；在准备阶段，玩家出了几张牌补回几张牌.(手上确认一直都是5张牌)；在出牌阶段，先打完手上牌的玩家获胜。

RoomAI 是非完美信息游戏 AI 环境。在 RoomAI 中，选手获得游戏环境给出的信息，当前选手选择合适的动作，游戏环境根据该动作推进游戏逻辑；重复上述过程，直到分出胜负；整个过程如下所示。

近年来，人工智能在棋牌游戏 AI 领域进步神速。1997 年，国际象棋首先被计算机系统深蓝攻陷; 2016 年 3 月，棋类游戏的巅峰围棋被计算机系统 AlphaGo 攻破；不想不满一年，2017 年 1 月，计算机系统 Libratus 攻克了德州扑克。连围棋都被攻克了，完全信息的棋类游戏没有什么学术价值了，但非完全信息的牌类游戏还有一些问题值得我们探究。虽然 Libratus 在德州扑克中超越了人类，但只是两位选手对局情况。如果是多人对局的德州，我们就没有办法使用 CRM 了，需要设计不同的算法框架。按照 Tuomas Sandholm 教授本人的观点，那就是一个 “totally different story”。更进一步的情况，某些牌类游戏不仅允许多人对局，还允许或者要求某些选手之间合作。比如，斗地主有三位选手，两位农民对战一位地主。再比如桥牌和四国军棋，两位选手组成一队，两队进行对局。这些情况也是现有没有考虑过的问题。

3. DQN 算法求解七鬼五二三

我们在非完美信息游戏 AI 环境 —— RoomAI 提供的三个玩家的七鬼五二三游戏上开发 DQN 算法，进行实验。为了简单起见，我们只在三个玩家的七鬼五二三开发我们的 AI, 得到的模型不适用于其他个数的七鬼五二三游戏。在 RoomAI 上实现 DQN 时，有两点需要特别注意。1) DQN 算法接收的数据为 s,a,r,s’，其中 s’ 为 s 的下一个状态。但是因为要支持非完美信息游戏，当前玩家出了一个动作之后，当前玩家不知道下一个玩家面对的信息。因此 s’ 只能是当前玩家下一次面对的信息。中间其他玩家的反应可以认为是系统的组成部分。2) DQN 算法接收的数据为 s,a,r,s’，在动作空间固定的情况下，就可以根据公式 1 更新模型。但是在 RoomAI 中，当前玩家的可选动作空间不是固定的。因此需要接受数据 s,a,r,s’,A’，其中 A’ 表示当前玩家可选动作空间，由 RoomAI 的 API 提供。实现一个七鬼五二三的 AI 需要三步。

3.1 第一步,网络结构

动手写一个棋牌 AI 的第一步就是确定网络结构。我们实现的 DQN 如下所示：当前状态 s 和可选动作 a, 分别经过 CNN 网络转换成向量，然后将两个向量拼接起来，最后通过 DNN 得到一个实数值 Q(s,a)。

3.2 第二步,特征工程

第二步是确定特征。我们需要抽取状态和动作的特征。状态特征是 15 * 5 大小的 8 层图片，15 * 5 中每行对应一个点数和每列代表一个花色，花色一共有 4 个正常花色和大小王的虚拟花色。8 层中其中有 4 层是准备阶段启用，另外 4 层是出牌阶段启用。4 层分别是当前的手牌，玩家历史中打出去的牌，上家历史中打出去的牌，下家历史中打出去的牌。动作特征则是 15 * 5 大小的 2 层图片，其中 1 层准备阶段启用，另外 1 层是出牌阶段启用，每层都是牌。