一、基本原理

1. 强化学习

强化学习是指一类从（与环境）交互中不断学习的问题以及解决这类问题的方法。强化学习问题可以描述为一个智能体从与环境的交互中不断学习以完成特定目标（比如取得最大奖励值）。而强化学习的关键问题是在于每一个动作并不能直接得到监督信息，需要通过整个模型的最终监督信息（奖励）得到，并且有一定的延时性。所以我们要解决如何通过直接得到的监督信息，来获得每个状态中比较恰当的动作的问题。

在强化学习中，有两个可以进行交互的对象：智能体和环境。智能体可以感知外界环境的状态，并进行学习和决策。智能体的决策功能是指根据外界环境的状态来做出不同的动作，而学习功能是指根据外界环境的奖励来调整策略。环境是智能体外部的所有事物，并受智能体动作的影响而改变其状态，并反馈给智能体相应的奖励 。其要素包括：

• 状态$s$：对环境的描述，可以是离散的或连续的，其状态空间为$S$
• 动作$a$： 对智能体行为的描述，可以是离散的或连续的，其动作空间为$A$
• 策略$\pi (a|s)$ ：智能体根据环境状态$s$ 来决定下一步动作$a$ 的函数
• 状态转移概率$p(s^{\prime }|s,a)$ ：在智能体根据当前状态$s$做出一个动作$a$之后，环境在下一个时刻转变为状态$s^{\prime }$的概率
• 即时奖励$r(s,a,s^{\prime })$是一个标量函数，即智能体根据当前状态$s$做出动作$a$之后，环境会反馈给智能体一个奖励，这个奖励也经常和下一个时刻的状态$s^{\prime }$有关

给定策略$\pi (a|s)$，智能体和环境一次交互过程的轨迹$\tau$所收到的累积奖励为总回报：
$$G(\tau )=\sum _{t=0}^{T-1}{\gamma }^t{r}_{t+1}$$
其中，$\gamma$为折扣率，用于调整短期和长期回报的权重。强化学习为了学习到一个策略来最大化期望回报。 这样的目标函数只能针对一个完整序列来求期望回报，但是在某一个状态下，我们并不能得知未来结果的序列是什么，所以也就无法指导下一个动作的产生。因此我们需要引入值函数来评估策略$\pi$在某个状态和动作下的期望回报，寻求当前状态下的期望总回报（状态值函数）和当前状态下执行某一个动作的期望总回报（状态-动作值函数），又称Q函数：
$$Q^{\pi }(s,a)=E_{s^{\prime }\sim p(s^{\prime }|s,a)}[r(s,a,s^{\prime })+\gamma V^{\pi }(s^{\prime })]$$
贝尔曼最优方程下，最优状态-动作值函数为：
$$Q^{\ast }(s,a)=E_{s^{\prime }\sim p(s^{\prime }|s,a)}[r(s,a,s^{\prime })+\gamma \underset{a^{\prime }}{\max }{Q}^{\ast }(s^{\prime },a^{\prime })]$$

2. Q学习方法

函数是对策略$\pi$的评估。如果策略$\pi$有限（即状态数和动作数都有限），可以对所有的策略进行评估并选出最优策略$\pi \ast$。但这种方式在实践中很难实现，通过迭代的方法不断优化策略，直到选出最优策略。 针对如何学习一个最优的策略，我们可以这样做：先随机初始化一个策略，计算该策略的值函数，并根据值函数来设置新的策略，然后一直反复迭代直到收敛。

如果需要拿到完整的轨迹才能评估和更新策略，则效率较低，因此考虑模拟一段轨迹，每行动一步，就利用贝尔曼方程评估状态的价值，即时序差分方法。下面考虑使用Q学习算法估计Q函数：
$$Q(s,a)\leftarrow Q(s,a)+\alpha (r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a))$$
Q学习的算法不通过${\pi }^{\epsilon }$来选择下一步动作$a^{\prime }$，而直接选择最优Q函数，所以更新后的Q函数是关于策略$\pi$而非${\pi }^{ϵ}$的，因此是一种异策略算法。

---

2. 流程图和伪代码

考虑使用Q学习的方法来得到能下黑白棋的人工智能。下黑白棋需要先手和后手，因此考虑使用相同的方法训练两套模型，分别适用于黑棋和白棋。训练的流程图如下：

更新$Q(s,a)$要使用公式：
$$Q(s,a)\leftarrow Q(s,a)+\alpha (r+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })-Q(s,a))$$
也就是说，$Q(s,a)$的期望值为$r+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$。其中$r$为回报，是在执行动作前后的回报总和的差值。对于黑白棋的场景考虑设计回报函数：黑白棋要求场上棋子数越多者获胜，因此考虑设置基础回报：每颗同色棋子算回报为1。而黑白棋中，需要优先占到边界和角落，其中角落最为重要，自己努力占领角落的同时也要尽量不要让对方占领角落，因此角落旁的位置的分数可以设置得低一些。最终的回报与棋子位置的关系为：

这样，计算某一步的回报时，只要将执行这一步前后的整个棋盘的评价值计算出来并相减就能得到。

上面的公式给出的$\gamma \max a^{\prime }Q(s^{\prime },a^{\prime })$是在智能体单独执行决策时的下一步进行的，也就是说，是在只有一个智能体单独执行一系列步骤时才有用的，在黑白棋这种博弈游戏中，是博弈双方交替进行，可能不适用。然而，假设每一局棋盘都能下满再结束的话，整个棋盘的分数是一定的，可以看做是一种零和博弈，假设对方会采取对方认为最优的策略，也就是另一种颜色的训练的模型的决策。那么，原本公式中的加上$\gamma \max a^{\prime }Q(s^{\prime },a^{\prime })$可以看做是减去对方的$\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$值。在上述回报函数下，如果优先有角落位置可以占就需要优先占，因此考虑将$\gamma$值设为0.2，这样一来，整个模型就会更加看重短期回报，也就是更优先占领角落且更优先避免对方占领角落。

8*8的黑白棋有64个位置，每个位置可能为黑棋、白棋、空，最多有$3^{64}$种状态，难以全部列举，因此考虑使用神经网络进行Q函数的拟合。输入为棋盘的64个状态位置与1个策略位置。状态位置中，-1表示黑棋，1表示白棋，0表示空。策略位置为当前下棋的一方可以下的位置。每次对所有可以下的位置进行神经网络的推理，选取得到输出值最大的位置作为下一步的位置。每次下一步就对当前状态进行训练。则整个训练过程如下：

/* ai为当前执棋方的模型，ai2为对手方的模型, state为当前棋盘状态（落子情况） */
def train(ai, ai2, state)
	pos := validPos(ai, state)	/* 依据棋局和执棋方得到所有可以下的位置 */
	for each_pos in pos			/* 遍历所有可以下的位置 */
    	value = ai(state, pos)	/* 依据当前位置和棋局推理结果 */
    	if value > max_value then	/* 记录最大结果和对应的位置 */
    		max_value = value
    		next_pos = each_pos
    end
    /* 选取推理结果最大的位置作为下一步下的位置 */
    r1 = evaluate(state)			/* 执行该策略前的评价值 */
    new_state = putChess(state, ai, next_pos)	/* 执行策略，在该位置下棋得到新状态 */
    r2 = evaluate(state)			/* 执行该策略后的评价值 */
    pos := validPos(ai, state)	/* 依据棋局和执棋方得到所有可以下的位置 */
    /* 同样计算之后对方下棋的最优位置 */
	for each_pos in pos				/* 遍历所有可以下的位置 */
    	value = ai(new_state, pos)	/* 依据当前位置和棋局推理结果 */
    	if value > max_value then	/* 记录最大结果和对应的位置 */
    		max_value = value
    end
    /* 
    依据公式对原先状态对当前执棋的模型进行训练 
    其中，输入值为棋局state、决策next_pos，预期值为回报r2-r1减去0.2*对方的下一步的最大预测值
    */
    ai.train(state, next_pos, r2 - r1 - 0.2 * max_value)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

---

3. 代码展示

3.1 黑白棋逻辑部分

使用8*8的张量chesses表示当前棋局状态，每个位置对应棋盘上的一个位置。位置上的值为0表示为空，1表示为白棋，-1表示为黑棋。同时，变量color也用-1和1表示当前是白棋还是黑棋。

每次轮到某方下棋时，遍历其全部能下的位置：

def getNextStepPos(chesses, color):
    pos = []
    for i in range(8):
        for j in range(8):	# 遍历所有位置，如果那个位置可以下，则加入结果
            if isValidPos(i ,j, color, chesses):
                pos.append((i,j))
    return pos
1
2
3
4
5
6
7

判断某个位置能否下棋，首先需要判断该位置是否为空，如果不为空则一定不能下，否则需要进行进一步判断。黑白棋能否下某个位置，需要判断8个方向上是否有能将对方的棋子变为自己棋子的机会。只要有一个方向有，则可以下。定义变量dr和dc为下一步走某个方向时，坐标x和y的变换。则对当前位置的8个方向进行遍历即可。如果该方向的下一个位置为另一种颜色的棋，则继续沿该方向走。如果遇到的仍是对方的棋则继续走，直到遇到自己颜色的棋则为合法，否则遇到边界或空位置，不合法。

def isValidPos(x , y, color, chesses):
    # 若当前位置不为空则直接返回False
    if chesses[x][y] != 0:
        return False
    # 8个方向的x和y坐标的变化值
    dr = [0,   1, 1, 1, 0, -1, -1, -1]
    dc = [-1, -1, 0, 1, 1,  1,  0, -1]
    ans = False
    for i in range(8): # 对8个方向进行遍历
        if x+dr[i]<8 and x+dr[i]>=0 and y+dc[i]<8 and y+dc[i]>=0:	# 边界条件
            # 计算该方向的下一个位置
            r = x + dr[i]
            c = y + dc[i]
            # 如果颜色相反，则进一步进行判断
            if chesses[r][c] == -color:
                ans = ans or nextPos(r, c, i, dr, dc, chesses, color)
        if ans:	# 只要一个方向合法则该位置可下，直接返回True
            return ans
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在某个方向上查找棋子颜色，以判断该方向是否可以翻对方的棋是一个递归过程：

def nextPos(r, c, i, dr, dc, chesses, color):
    if r+dr[i]<8 and r+dr[i]>=0 and c+dc[i]<8 and c+dc[i] >= 0:	# 边界条件
        # 继续沿该方向走
        r += dr[i]
        c += dc[i]
        # 颜色仍相反，则看再下一个位置
        if chesses[r][c] == -color:
            return nextPos(r, c, i, dr, dc, chesses, color)
       	# 为自己的颜色，则返回True
        if chesses[r][c] == color:
            return True
    # 边界或空位置，返回False
    return False
1
2
3
4
5
6
7
8
9
10
11
12
13

由此一来就得到了当前颜色所有能下的位置。

类似上述逻辑，在实际落子时，也要对所有方向进行遍历，并将可以变色的棋全部变色。其中p为坐标：

def putChess(chesses, p, color):
    # 8个方向
    dr = [0, 1, 1, 1, 0, -1, -1, -1]
    dc = [-1, -1, 0, 1, 1, 1, 0, -1]
    x = p[0]
    y = p[1]
    chesses[x][y] = color	# 先在当前位置落子
    for i in range(8):  	# 遍历8个方向
        if x + dr[i] < 8 and x + dr[i] >= 0 and y + dc[i] < 8 and y + dc[i] >= 0:	# 边界条件
            r = x + dr[i]
            c = y + dc[i]
            # 判断该方向上是否会棋子翻面
            if chesses[r][c] == -color:
                if nextPos(r, c, i, dr, dc, chesses, color):
                    # 若是，则一直翻面直到遇到自己颜色的棋子为止
                    while chesses[r][c] == -color:
                        chesses[r][c] = color
                        r += dr[i]
                        c += dc[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.2 模型训练部分

因为黑白棋游戏中状态的多样性，对每种情况单独列出一个Q值不现实，因此考虑使用神经网络处理。输入为棋局上64个位置的情况和下一个落子的位置，输出为对当前位置的打分，每次选择分数最高的位置下棋。www.biyezuopin.vip

使用pytorch平台编写神经网络。网络结构如下：

        self.fc0 = nn.Linear(65, 128)
        self.relu0 = nn.ReLU()
        self.fc1 = nn.Linear(128, 256)
        self.relu1 = nn.ReLU()
        self.fc2 = nn.Linear(256, 512)
        self.relu2 = nn.ReLU()
        self.fc3 = nn.Linear(512, 256)
        self.relu3 = nn.ReLU()
        self.fc4 = nn.Linear(256, 64)
        self.relu4 = nn.ReLU()
        self.fc5 = nn.Linear(64, 1)
1
2
3
4
5
6
7
8
9
10
11

网络一共6层，每一层都是全连接层，通过ReLU函数进行激活，学习率设置为0.001。一共有两个神经网络模型，一个是先手的AI，记为first_ai，为黑棋；一个是后手的AI，记为last_ai，为白棋。每次两个AI的对局训练如下：

        while 1:
            flag = True
            # 查找黑方下一步可以下的全部位置
            pos = getNextStepPos(chesses, -1)
            if pos != []:
                flag = False
                play(-1, pos, chesses, first_ai, last_ai)
            # 查找拜访下一步可以下的全部位置
            pos = getNextStepPos(chesses, 1)
            if pos != []:
                flag = False
                play(1, pos, chesses, last_ai, first_ai)
            if flag:   # 双方都无处可下，直接结束游戏
                break
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在全部可以下的位置中，理应每个位置都作为参数，经神经网络学习得到最优的位置作为下一个落子的位置。然而，为了让AI能更好地探索空间，考虑20%的概率，AI会在所有可下的位置中随机选取一个进行落子，而80%的概率下才是正常地按照神经网络推理结果进行落子：

def play(color, pos, chesses, ai, _ai):
    size = len(pos)
    # 20%的几率在可以下的位置随机选择一个
    if random.randint(0, 99) < 20:
        p = pos[random.randint(0, size-1)]
            # 否则选择神经网络打分最大的位置
    else:
        max_res = -10000
        p = None
        for i in range(size):
            pos64 = pos[i][0] * 8 + pos[i][1]	# 将8*8的二维位置坐标变为0~63的一维坐标
            # 将棋局状态和落子位置作为参数输入得到结果
            res = ai(torch.cat((chesses.reshape(64),torch.FloatTensor([pos64])),0).reshape(65))
            # 记录最大结果对应的位置和结果
            if res > max_res:
                max_res = res
                p = pos[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

由此得到了下一个落子位置后，还需要进行学习。依据公式对Q(s,a)，即ai的参数进行更新。具体做法在上面详细讲过，这里不再赘述。

    # 计算回报值score2-score1
    score1 = evaluate(chesses, color)
    putChess(chesses, p, color)
    score2 = evaluate(chesses, color)
    # 计算对方能下的全部位置
    next_pos = getNextStepPos(chesses, -color)
    next_pos_max_res = 0
    # 计算对方的最大估计值
    for eachPos in next_pos:
        pos64 = eachPos[0] * 8 + eachPos[1]
        next_res = _ai(torch.cat((chesses.reshape(64),torch.FloatTensor([pos64])),0).reshape(65))
        if next_pos_max_res < next_res:
            next_pos_max_res = next_res
    pos64 = p[0] * 8 + p[1]
    # 样本输入：棋局状态和落子位置，期望输出：回报-0.2*对方最大估计值
    ai.train(torch.cat((chesses.reshape(64),torch.FloatTensor([pos64])),0).reshape(65), score2 - score1 - 0.2 * next_pos_max_res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

其中评估函数在上文已经进行了说明：

score_map = [
    [100, -35, 10, 5, 5, 10, -35, 100], 
    [-35, -35, 2, 2, 2, 2, -35, -35], 
    [10, 2, 5, 1, 1, 5, 2, 10], 
    [5, 2, 1, 2, 2, 1, 2, 5],
    [5, 2, 1, 2, 2, 1, 2, 5],
    [10, 2, 5, 1, 1, 5, 2, 10], 
    [-35, -35, 2, 2, 2, 2, -35, -35],
    [100, -35, 10, 5, 5, 10, -35, 100]
]

def evaluate(chesses, color):
    score = 0
    for i in range(8):
        for j in range(8):
            if chesses[i][j] == color:
                score += score_map[i][j]
    return score
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

实际游戏时，如果需要AI落子，则直接调用上述aiPlay函数即可。

---

4. 实验结果及分析

因为得到的模型无法像有监督学习里的分类任务一样有明确的指标衡量, 所以只能通过实战来粗略地验证模型的效果。这里我们以三个训练不同次数的模型为例, 分别训练了 15000 场、20000 场、30000 场。首先是 15000 场模型与 20000 场模型分别以黑棋和白棋对局 5 局, 结果如下:

可以看到, 20000 场的模型相较于 15000 场的模型, 还是略占优势的, 由于我们设计的模型中, 有 20% 的概率随机落子, 而且对局次数较少, 所以会出现 20000 场模型有时下不过 15000 场模型的情况。

然后是 30000 场模型与 15000 场模型分别以黑棋和白棋对局 5 局, 结果如下:

可以看出, 30000 场的模型相较于 20000 场的模型, 其实力更为强劲, 10 局之中获胜次数更多, 而且"碾压"局较 20000 场模型更多。

下面我们分析占住棋盘的 4 个角获胜的情况, 统计以上的 20 局, 发现

可以看出, 当占据了棋盘的 4 个角时, 基本上是必赢的局面; 而占据 3 个角时, 获胜的几率较大, 但也不是必胜的局面, 这是因为我们设计的评价函数, 四个角的分数与棋盘其他位置的分数相差并不是特别大, 从而告诉模型, 即使可以占据棋盘的角, 也不是一定要下的。

接下来我们结合具体的几个落子来评估模型训练的结果。

可以看到, 当黑棋落子 (2, 2) 位置后, 模型所执的白棋果断下到棋盘左上角的位置, 使得局势对白棋更有利。

可以看到, 模型所执的白棋落子到 (2, 4) 位置, 将其右方和下方的黑棋都翻为白棋, 这是因为在这个位置可以有两个方向上的交叠, 相较于其他位置, 对白棋局势更有利。www.biyezuopin.vip

可以看到, 这里白棋并没有在右上角落子, 而是选择在 (1, 3) 位置落子, 这是因为在此处落子可以翻 4 个黑棋为白棋, 而在右上角落子的话, 虽然可以翻 3 个黑棋为白棋, 但是在 (5, 8) 位置使得黑棋可下, 将会翻 2 个白棋为黑棋, 而最后的结果是此处并未被黑棋落子, 体现出我们训练的模型可以选择己方优势的位置。