郑博宇

北京信息科技大学 北京 100085

引言

海克斯棋，也称作六贯棋[1]，最初在丹麦报纸Politiken发表的一篇文章里出现，当时称Polygon。1948年，John Nash却又将其重新独立发明出来，而热衷于此的玩家们随即就将其称作Nash。稍后1952年Parker Brothers发行了一个版本，将其称为Hex，从此这个名字就固定了下来。六贯棋通常使10×10或11×11的菱形棋盘，而JohnNash 采用的却是14 × 14 的棋盘。

海克斯棋的规则如下：

（1）一共两人参与海克斯棋博弈，棋盘由红蓝两色组成。棋盘边缘分别填上双方颜色；

（2）双方轮流下棋，一次只能下一棋子，且仅占领一处空格，在空格上方放上属于自己颜色的棋子；

（3）在比赛的过程中，禁止吃棋子的行为；

（4）第一个把棋盘两端属于自己颜色的棋盘边缘连通成一条线的人获胜。

1 深度强化学习的算法模型设计

深度强化学习Deep Q-Learning是将Q Learning与CNN卷积神经网络相结合，实现了从感知到动作的端到端的革命性算法。普通的Q-learning算法中，当项目的状态和动作空间是离散且维数不高时可使用Q-Table储存每个状态动作对的Q值，但是在海克斯棋的博弈过程中，13×13的棋盘状态和动作空间是高维连续时，使用Q-Table过于庞大，建立起来十分困难。本文将海克斯棋类博弈与Deep Q-learning深度增强学习算法结合起来，使得该棋类的博弈能力不断提升。

1.1 Q learning 算法的结构

Q Learning是一种在强化学习算法中基于value-based的算法。Q即为Q（s,a），Q（s,a）在某一时刻的 s 状态下(s∈S)，采取 动作a (a∈A)动作能够获得收益的期望，通过Q值进行学习，而环境将会根据agent的动作反馈相应的回报reward r，所以本算法的主要思想是将State与Action构建成一张Q-table来存储Q值，再根据Q值来选取能够获得最大的收益的动作。……