首页 > 极客资料 博客日记
五子棋AI:实现逻辑与相关背景探讨(下)
2024-09-07 16:30:05极客资料围观29次
前文回顾
在上篇文章中,我们约定了一种衡量格子价值的方式,如下表。
综合价值排序 | 己方价值 | 敌方价值 | 对应的奖励数值 |
---|---|---|---|
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)是一种模拟自然选择和遗传机制的优化算法。它用于寻找问题的最优解,特别适用于复杂的优化问题和搜索问题。遗传算法基于达尔文的自然选择理论,通过模拟生物进化过程来逐步改进解决方案。
遗传算法的基本步骤如下:
-
初始化:创建一个初始种群,种群中的每一个个体(通常称为染色体或解)是问题的一个潜在解。
-
评估:计算种群中每个个体的适应度值,这通常通过一个目标函数来进行,适应度值表示个体的优劣。
-
选择:根据适应度值选择个体进行繁殖,优良个体有更高的概率被选择,以生成下一代种群。
-
交叉(Crossover):通过将两个个体的部分基因交换,生成新的个体。这一步模仿了生物的交配过程,可以产生新的解。
-
变异(Mutation):在某些个体中随机改变基因,以引入新的基因变异。这一步帮助算法跳出局部最优解,增加解的多样性。
-
替换:将一部分个体替换为最优良的个体,保留最优秀的基因,使得种群的型状不会出现下降或震荡。
-
终止:判断算法是否满足终止条件,如达到最大迭代次数或找到足够好的解。如果满足条件,算法终止,返回最优解;否则,返回第2步。
遗传算法实现思路
初始化
本文所设计的AI决策方案共包含12个参数,其中11个是奖励权重\(R_i\),1个是对劣质选项接受度\(K\)。
我们可以定义\(N\)个智能体,分别用初始权重进行初始化,一般来说,\(N\)可以取10~100,最好选择偶数,否则会有一些不必要的麻烦。
初始化过程可以用数学公式表示为:
其中,\(W_0\)表示初始权重,\(W_i^{t=0}\)表示第\(t\)代的第\(i\)个个体。
评估
本例中,采用让AI对弈的方式,根据AI在棋局中的表现评估AI得分,具体流程如下:
- 生成一个从1到N的随机排列,并将其按顺序分配给AI
- 将序号为1、3、5、...的AI与序号为2、4、6、...的AI对弈
- 将棋局结果记录到AI得分表内。
- 是否完成\(N_R\)轮对局,倘若未完成,则返回到1。
- 对AI进行排名。
交叉
当完成排名时,让排名后50%的AI及前50%的AI两两组合,其数学公式如下
其中:\(c\)为学习因子(交叉率),表示AI在学习过程中对新知识(权重)的接受程度,\(c\)越大,AI越倾向于接受新权重,\(c\)越小,AI越倾向于保留旧权重。交叉率\(c\)一搬可取\(0.01\sim0.3\)
替换
首先定义局部最优个体和全局最优个体。
-
局部最优\(W_b^t\):如果一个个体在本轮中的综合成绩排名为第一名(胜场最多),那么称其为局部最优个体。
-
全局最优\(W_B\):当只进行一轮迭代时,全局最优个体等于局部最优个体,即:\(W_B=W_b^{t=0}\)。当进行了不止一局游戏时,将新的局部最优个体与全局最优个体进行\(N_R\)轮对局,倘若全局最优个体获胜,则其依旧为全局最优个体,倘若其失败,则局部最优个体成为新的全局最优个体。可以用数学公式表示为:
为了保留最优的性状,将排名靠后的部分个体替换为全局最优个体,记替换率为\(s\),一般取\(0.02\sim 0.1\)
变异
在变异过程中,个体的基因发生随机的改变。定义变异系数\(m\),其绝对了变异的程度,一般来说\(m\)的范围在\(0.01\sim0.1\)数学公式如下:
其中\(W_{i,j}^{t}\)表示第\(t\)代的第\(i\)个个体的第\(j\)个权重,\(m_j\)是在\((-m,m)\)内的随机数。
流程汇总
以下给出遗传算法学习的流程
-
初始化种群
-
创建棋局,各个个体互相对战,统计得分并进行排名
-
判断是否达到停止条件,若不是则继续。
-
依排名将个体两两匹配,进行交叉操作
-
将排名靠后的个体分别替换为局部最优个体和全局最优个体
-
进行变异操作
-
转至步骤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 |
标签:
相关文章
最新发布
- Nuxt.js 应用中的 prerender:routes 事件钩子详解
- 【问题解决】Tomcat由低于8版本升级到高版本使用Tomcat自带连接池报错无法找到表空间的问题
- 【FAQ】HarmonyOS SDK 闭源开放能力 —Vision Kit
- 六、Spring Boot集成Spring Security之前后分离认证流程最佳方案
- 《JVM第7课》堆区
- .NET 8 高性能跨平台图像处理库 ImageSharp
- 还在为慢速数据传输苦恼?Linux 零拷贝技术来帮你!
- 刚毕业,去做边缘业务,还有救吗?
- 如何避免 HttpClient 丢失请求头:通过 HttpRequestMessage 解决并优化
- 让性能提升56%的Vue3.5响应式重构之“版本计数”