首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

五子棋AI:实现逻辑与相关背景探讨(下)

编程知识
2024年09月07日 15:16

前文回顾


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

综合价值排序 己方价值 敌方价值 对应的奖励数值
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^t\times(1-c)+W_{i-50}^t\times c, &N/2 \leq &t \leq N \\ W_{i}^{t+1}&=W_i^t\times(1-c)+W_{i+50}^t\times c, &0 \leq &t \leq N/2 \end{align*} \]

其中:\(c\)为学习因子(交叉率),表示AI在学习过程中对新知识(权重)的接受程度,\(c\)越大,AI越倾向于接受新权重,\(c\)越小,AI越倾向于保留旧权重。交叉率\(c\)一搬可取\(0.01\sim0.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.02\sim 0.1\)

变异


在变异过程中,个体的基因发生随机的改变。定义变异系数\(m\),其绝对了变异的程度,一般来说\(m\)的范围在\(0.01\sim0.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
From:https://www.cnblogs.com/SXWisON/p/18401356
本文地址: http://www.shuzixingkong.net/article/1812
0评论
提交 加载更多评论
其他文章 Java是值传递还是引用传递,又是怎么体现的
关于Java是值传递还是引用传递,可以从代码层面来实现一下拿到结果 执行下面的代码: public static void main(String[] args) { int num = 10; String name = "Tom"; modify(num, name); Sy
跳跃表
概述 跳跃表(SkipList)是链表加多级索引组成的数据结构。链表的数据结构的查询复条度是 O(N)。为了提高查询效率,可以在链表上加多级索引来实现快速查询。跳跃表不仅能提高搜索性能。也能提高插入和删除操作的性能。索引的层数也叫作跳跃表的高度 查找 在跳跃表的结构中会首先从顶层开始查找,当顶层不存
跳跃表 跳跃表 跳跃表
设计模式之模板方法模式(三分钟学会一个设计模式)
模板方法模式(Template Method Pattern)也称之为模板模式(Template Pattern),是设计模式中最简单的模式之一。 先来看定义:定义一个操作中算法的骨架(模板),将一些步骤延迟到子类中,模板方法使得子类可以不改变算法的结构即可重新定义算法某些特定的步骤。这个定义还是有
设计模式之模板方法模式(三分钟学会一个设计模式) 设计模式之模板方法模式(三分钟学会一个设计模式)
事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire)
原文:Transactional Outbox in .NET Cloud Native Development via Aspire 作者:Oleksii Nikiforov 总览 这篇文章提供了使用 Aspire、DotNetCore.CAP、Azure Service Bus、Azure SQ
事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire) 事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire) 事务发件箱模式在 .NET 云原生开发中的应用(基于Aspire)
使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释
之前写过两篇关于Roslyn源生成器生成源代码的用例,今天使用Roslyn的代码修复器CodeFixProvider实现一个cs文件头部注释的功能, 代码修复器会同时涉及到CodeFixProvider和DiagnosticAnalyzer, 实现FileHeaderAnalyzer 首先我们知道修
使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释 使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释 使用 `Roslyn` 分析器和修复器对.cs源代码添加头部注释
线性dp:LeetCode516 .最长回文子序列
LeetCode516 .最长回文子序列 题目叙述: 力扣题目链接(opens new window) 给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。 子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 示例 1: 输入:s = &quot
线性dp:LeetCode516 .最长回文子序列 线性dp:LeetCode516 .最长回文子序列 线性dp:LeetCode516 .最长回文子序列
XGBoost模型 0基础小白也能懂(附代码)
XGBoost 是 eXtreme Gradient Boosting 的缩写称呼,它是一个非常强大的 Boosting 算法工具包,优秀的性能(效果与速度)让其在很长一段时间内霸屏数据科学比赛解决方案榜首,现在很多大厂的机器学习方案依旧会首选这个模型。
XGBoost模型 0基础小白也能懂(附代码) XGBoost模型 0基础小白也能懂(附代码) XGBoost模型 0基础小白也能懂(附代码)
Kafka原理剖析之「Topic创建」
一、前言 Kafka提供了高性能的读写,而这些读写操作均是操作在Topic上的,Topic的创建就尤为关键,其中涉及分区分配策略、状态流转等,而Topic的新建语句非常简单 bash kafka-topics.sh \ --bootstrap-server localhost:9092 \ // 需
Kafka原理剖析之「Topic创建」 Kafka原理剖析之「Topic创建」 Kafka原理剖析之「Topic创建」