五子棋AI：实现逻辑与相关背景探讨（下）

前文回顾

---

在上篇文章中，我们约定了一种衡量格子价值的方式，如下表。

综合价值排序	己方价值	敌方价值	对应的奖励数值
1	Lv1	?	(2^{20})
2	?	Lv1	(2^{16})
3	Lv2	?	(2^{12})
4	？	Lv2	(2^{8})
5	Lv3	？	(2^{4})
6	Lv4	？	(2^{0})

在该表中，对不同的情形，设计了不同的奖励数值，这些数值大多是采用经验公式，人为估计的数值，并不是最优良的数值。同样的，在上表中的除前两类为，其余都可根据实际情况进一步的细分权重，这里给出一个样例供大家参考/理解：

综合价值排序	己方价值	敌方价值	对应的奖励数值
3.1	Lv2	Lv2	(2^{13})
3.2	Lv2	Lv3	(2^{12})
3.3	Lv2	Lv4	(2^{11})

同样是能构成杀招(Lv2等级)，能顺便堵死对面杀招/优良的位置自然是更好的。

在附录中给出了详细的权重表

本篇中我们将基于遗传算法讨论如何让AI学习奖励值。

遗传算法概述

---

遗传算法（Genetic Algorithm, GA）是一种模拟自然选择和遗传机制的优化算法。它用于寻找问题的最优解，特别适用于复杂的优化问题和搜索问题。遗传算法基于达尔文的自然选择理论，通过模拟生物进化过程来逐步改进解决方案。

遗传算法的基本步骤如下：

1. 初始化：创建一个初始种群，种群中的每一个个体（通常称为染色体或解）是问题的一个潜在解。

2. 评估：计算种群中每个个体的适应度值，这通常通过一个目标函数来进行，适应度值表示个体的优劣。

3. 选择：根据适应度值选择个体进行繁殖，优良个体有更高的概率被选择，以生成下一代种群。

4. 交叉（Crossover）：通过将两个个体的部分基因交换，生成新的个体。这一步模仿了生物的交配过程，可以产生新的解。

5. 变异（Mutation）：在某些个体中随机改变基因，以引入新的基因变异。这一步帮助算法跳出局部最优解，增加解的多样性。

6. 替换：将一部分个体替换为最优良的个体，保留最优秀的基因，使得种群的型状不会出现下降或震荡。

7. 终止：判断算法是否满足终止条件，如达到最大迭代次数或找到足够好的解。如果满足条件，算法终止，返回最优解；否则，返回第2步。

遗传算法实现思路

初始化

---

本文所设计的AI决策方案共包含12个参数，其中11个是奖励权重(R_i)，1个是对劣质选项接受度(K)。

我们可以定义(N)个智能体，分别用初始权重进行初始化，一般来说，(N)可以取10~100，最好选择偶数，否则会有一些不必要的麻烦。

初始化过程可以用数学公式表示为：

[W_i^{t=0} = W_0 ]

其中，(W_0)表示初始权重，(W_i^{t=0})表示第(t)代的第(i)个个体。

评估

---

本例中，采用让AI对弈的方式，根据AI在棋局中的表现评估AI得分，具体流程如下：

1. 生成一个从1到N的随机排列，并将其按顺序分配给AI
2. 将序号为1、3、5、...的AI与序号为2、4、6、...的AI对弈
3. 将棋局结果记录到AI得分表内。
4. 是否完成(N_R)轮对局，倘若未完成，则返回到1。
5. 对AI进行排名。

交叉

---

当完成排名时，让排名后50%的AI及前50%的AI两两组合，其数学公式如下

[begin{align*} W_{i}^{t+1}&=W_i^ttimes(1-c)+W_{i-50}^ttimes c, &N/2 leq &t leq N \ W_{i}^{t+1}&=W_i^ttimes(1-c)+W_{i+50}^ttimes c, &0 leq &t leq N/2 end{align*} ]

其中：(c)为学习因子（交叉率），表示AI在学习过程中对新知识（权重）的接受程度，(c)越大，AI越倾向于接受新权重，(c)越小，AI越倾向于保留旧权重。交叉率(c)一搬可取(0.01sim0.3)

替换

---

首先定义局部最优个体和全局最优个体。

• 局部最优(W_b^t)：如果一个个体在本轮中的综合成绩排名为第一名（胜场最多），那么称其为局部最优个体。

• 全局最优(W_B)：当只进行一轮迭代时，全局最优个体等于局部最优个体，即：(W_B=W_b^{t=0})。当进行了不止一局游戏时，将新的局部最优个体与全局最优个体进行(N_R)轮对局，倘若全局最优个体获胜，则其依旧为全局最优个体，倘若其失败，则局部最优个体成为新的全局最优个体。可以用数学公式表示为：

[W_B= begin{cases} W_b^t &text{if};W_b^t ;text{win},\ W_B &text{otherwise}. end{cases} ]

为了保留最优的性状，将排名靠后的部分个体替换为全局最优个体，记替换率为(s)，一般取(0.02sim 0.1)

变异

---

在变异过程中，个体的基因发生随机的改变。定义变异系数(m)，其绝对了变异的程度，一般来说(m)的范围在(0.01sim0.1)数学公式如下：

[W_{i,j}^{t}=W^t_{i,j}times (1+m_j) ]

其中(W_{i,j}^{t})表示第(t)代的第(i)个个体的第(j)个权重，(m_j)是在((-m,m))内的随机数。

流程汇总

---

以下给出遗传算法学习的流程

1. 初始化种群

2. 创建棋局，各个个体互相对战，统计得分并进行排名

3. 判断是否达到停止条件，若不是则继续。

4. 依排名将个体两两匹配，进行交叉操作

5. 将排名靠后的个体分别替换为局部最优个体和全局最优个体

6. 进行变异操作

7. 转至步骤2

附录

行为优先级

• Lv1：下子直接取胜，或在一回合内取胜。
• Lv2：下在大概率在若干回合内取胜。
• Lv3：能够迫使对方一直防御。
• Lv4：收益较低。

初始权重表

综合价值排序	己方价值	敌方价值	对应的奖励数值
1	Lv1	?	(2^{20})
2	?	Lv1	(2^{16})
3.1	Lv2	Lv2	(2^{13})
3.2	Lv2	Lv3	(2^{12})
3.3	Lv2	Lv4	(2^{11})
4.1	Lv3	Lv2	(2^{9})
4.2	Lv4	Lv2	(2^{8})
5.1	Lv3	Lv3	(2^{6})
5.2	Lv3	Lv4	(2^{4})
6.1	Lv4	Lv3	(2^{2})
6.2	Lv4	Lv4	(2^{0})

符号说明

符号	意义	数值范围
(W)	个体（权重）	-
(R)	行动的奖励	-
(K)	对劣选项的接受程度	-
(N)	种群大小	10~100
(N_R)	评估时的对局轮数	10~100
(T)	迭代次数	20~500
(c)	交叉率	0.01~0.03
(s)	替换率	0.02~0.1
(m)	变异率	0.01~0.1