拱墅区建设局网站,轻量级网站开发,可以做超链接或锚文本的网站有哪些,免费企业网站模板html前言 在上一篇文章中#xff0c;讲解了如何实现双人在本地对战的五子棋#xff0c;但是只有一个人的时候就不太好玩#xff0c;同时博主也没有把五子棋相关的文章写过瘾。那么这篇文章#xff0c;我们来实现一个功能更加丰富的五子棋吧#xff01;在设计五子棋的算法方面讲解了如何实现双人在本地对战的五子棋但是只有一个人的时候就不太好玩同时博主也没有把五子棋相关的文章写过瘾。那么这篇文章我们来实现一个功能更加丰富的五子棋吧在设计五子棋的算法方面我们将引入一些经典的算法如最大最小搜索Max-Min算法和Alpha-Beta剪枝算法。这些算法将帮助我们创建一个智能的对手使游戏更具挑战性和趣味性。除了算法的介绍本文还将深入探讨五子棋的基本玩法和规则。我们将详细解释如何落子、如何判断胜负以及如何对各种局面进行评分估值。通过学习这些基础知识您将能够更好地理解和享受五子棋游戏。 效果图
仓库地址https://github.com/taxze6/flutter_game_collection/tree/main/gomoku_ai release apk下载体验https://github.com/taxze6/flutter_game_collection/tree/main/gomoku_ai/release 棋盘绘制 本次采用的棋盘绘制与上篇文章的方式不同上篇文章中采用的是GridView这样的基础组件使用简单无需手动编写绘制逻辑。利用GridView的布局特性可以很方便地进行排列和调整。但是它也有缺点就是不够灵活当我们想实现更多的棋盘细节时实现起来就不是很方便了所以在本篇文章中我们采用CustomPaint绘制的方式。 那在绘制棋盘之前我们需要先定义游戏所需要的一些参数和实体类 玩家类 //玩家 class Player { static final Player black Player(Colors.black); static final Player white Player(Colors.white); late Color color;
Player(this.color);
override String toString() { return ‘Player{${this black ? “black” : “white”}}’; } } 单颗棋子类 class Chessman { //坐标 late Offset position;
//该棋子的所属人 late Player owner;
//棋子id int numberId chessmanList.length;
//棋子的分数默认为0 int score 0;
Chessman(this.position, this.owner);
Chessman.white(this.position) { owner Player.white; }
Chessman.black(this.position) { owner Player.black; }
override String toString() { return ‘Chessman{position: ( p o s i t i o n . d x , {position.dx}, position.dx,{position.dy}), owner: ${owner Player.black ? “black” : “white”}, score: $score, numberId: $numberId}’; } } 全局通用参数 //初始化一个玩家掌握黑棋 Player firstPlayer Player.black; //存放所有的棋子 List chessmanList []; //存放胜利的棋子 List winResult []; 那么所需的参数及实体类编写完成后就可以开始棋盘的绘制啦 游戏页面整体布局结构 override Widget build(BuildContext context) { return Scaffold( appBar: AppBar( title: Text(“五子棋AI版”), ), body: Padding( padding: EdgeInsets.only(top: 50, left: 20, right: 20), child: Column( children: [ //棋盘 GestureDetector( child: CustomPaint( painter: ChessmanPaint(), size: Size(400, 400), ), onTapDown: (details) { onTapDown(details); setState(() {}); }, ), //底部操作项目 Padding() ], ), ), ); } 棋盘绘制主体 ● 定义所需绘制参数 //默认棋盘的行列数 const int LINE_COUNT 14; //根据屏幕大小与行列数计算得出每个格子的宽高初始化先为0 double cellWidth 0, cellHeight 0; ● 绘制黄褐色背景 在绘制背景这里canvas.drawRect(Offset.zero size, painter)用了个dart的语法糖有些朋友可能会有些疑惑drawRect方法第一个参数不是Rect类型的吗这里传了个Offset.zero size是什么鬼这里单独解释下Offset.zero表示矩形范围的左上角坐标为原点(0,0)size表示矩形的大小。这个表达式使用符号将两个对象合并成了一个Rect对象作为canvas.drawRect()方法的第一个参数。实际上符号在这里是Dart语言中的语法糖等效于使用Rect.fromLTWH(0, 0, size.width, size.height)来创建一个矩形。因此这里的语法Offset.zero size可以通过Rect.fromLTWH(0, 0, size.width, size.height)来替代。 class ChessmanPaint extends CustomPainter { late Canvas canvas; late Paint painter; //用于控制打印在棋子上的id static const bool printLog true;
override void paint(Canvas canvas, Size size) { this.canvas canvas; //计算单个格子的宽高 cellWidth size.width / LINE_COUNT; cellHeight size.height / LINE_COUNT;
painter Paint()..isAntiAlias true..style PaintingStyle.fill..color Color(0x77cdb175);
//绘制背景
canvas.drawRect(Offset.zero size, painter);
}
...} ● 绘制棋盘上的线条格子 override void paint(Canvas canvas, Size size) { … painter …style PaintingStyle.stroke …color Colors.black87 …strokeWidth 1.0;
for (int i 0; i LINE_COUNT; i) {double y cellHeight * i;canvas.drawLine(Offset(0, y), Offset(size.width, y), painter);
}for (int i 0; i LINE_COUNT; i) {double x cellWidth * i;canvas.drawLine(Offset(x, 0), Offset(x, size.height), painter);
}} ● 绘制五子棋盘上的五个交叉点
这5个点称为“星”。中间的星也称天元表示棋盘的正中心其他4个星也叫小星。星在棋盘上起标示位置的作用利于在行棋、复盘、记录等时更清晰、迅速地找到所需位置。 //绘制棋盘上的5个黑点 void _drawMarkPoints() { // 通过多次调用_drawMarkPoint方法来绘制标记点 _drawMarkPoint(const Offset(7.0, 7.0)); _drawMarkPoint(const Offset(3.0, 3.0)); _drawMarkPoint(const Offset(3.0, 11.0)); _drawMarkPoint(const Offset(11.0, 3.0)); _drawMarkPoint(const Offset(11.0, 11.0)); }
void _drawMarkPoint(Offset offset) { painter …style PaintingStyle.fill …color Colors.black;
// 计算标记点在画布上的具体位置 Offset center Offset(offset.dx * cellWidth, offset.dy * cellHeight);
// 在计算得到的位置绘制一个半径为3的圆形标记点 canvas.drawCircle(center, 3, painter); } ● 绘制棋子 这里使用min(cellWidth / 2, cellHeight / 2) - 2计算出较小的一边长度减去2作为圆的半径可以使得所有棋子的大小一致并且不会越出格子范围。 //遍历chessmanList绘制每下一颗子触发setState if (chessmanList.isNotEmpty) { for (Chessman c in chessmanList) { _drawChessman©; } }
void _drawChessman(Chessman chessman) { painter …style PaintingStyle.fill //根据owner取得每课棋子对应的颜色 …color chessman.owner.color;
Offset center Offset( chessman.position.dx * cellWidth, chessman.position.dy * cellHeight); canvas.drawCircle(center, min(cellWidth / 2, cellHeight / 2) - 2, painter); //如果当前棋子的编号是最后一枚棋子则使用painter绘制一个描边的蓝色圆圈表示这是最后下的一枚棋子。 if (chessman.numberId chessmanList.length - 1) { painter …color Colors.blue …style PaintingStyle.stroke …strokeWidth 3.0; canvas.drawCircle( center, min(cellWidth / 2, cellHeight / 2) - 2, painter); } } ● 绘制棋子编号非主要功能可以跳过这步 //在棋子上绘制它的id if (printLog) { _drawText((i.toString()), Offset(-19, y - _calcTrueTextSize(i.toString(), 15.0).dy / 2)); }
void _drawText(String text, Offset offset, {Color? color, double? textSize}) { // 创建ParagraphBuilder对象用于构建文本段落 ui.ParagraphBuilder builder ui.ParagraphBuilder(ui.ParagraphStyle( textAlign: TextAlign.center, ellipsis: ‘…’, maxLines: 1, ));
// 使用pushStyle方法设置文本风格包括颜色和字体大小 builder.pushStyle( ui.TextStyle(color: color ?? Colors.red, fontSize: textSize ?? 15.0));
// 添加文本到builder对象中 builder.addText(text);
// 构建一个Paragraph对象 ui.Paragraph paragraph builder.build();
// 对paragraph进行layout指定宽度为无限大 paragraph.layout(const ui.ParagraphConstraints(width: double.infinity));
// 在Canvas上绘制paragraph对象位置为offset canvas.drawParagraph(paragraph, offset); }
//根据给定的文本字符串和字体大小计算出该文本所占据的实际宽度和高度以便在UI布局中更好地控制文本的位置和尺寸。 Offset _calcTrueTextSize(String text, double textSize) { // 创建ParagraphBuilder对象并设置字体大小 var paragraph ui.ParagraphBuilder(ui.ParagraphStyle(fontSize: textSize)) …addText(text);
// 构建Paragraph对象并进行layout指定宽度为无限大 var p paragraph.build() …layout(const ui.ParagraphConstraints(width: double.infinity));
// 返回Paragraph对象的最小内在宽度和高度作为偏移量 return Offset(p.minIntrinsicWidth, p.height); } 用户交互下棋 取得用户点击的位置 通过GestureDetector的onTapDown取得用户点击的位置 GestureDetector( child: CustomPaint( painter: ChessmanPaint(), size: Size(400, 400), ), onTapDown: (details) { onTapDown(details); setState(() {}); }, ), 点击事件 //棋盘点击事件 void onTapDown(TapDownDetails details) { //游戏胜利后再点击棋盘就无效 if (winResult.isNotEmpty) { return; } double clickX details.localPosition.dx; //计算点击点所在列的索引值 floorX。通过将 clickX 除以格子的宽度 cellWidth 并向下取整可以得到点击点所处的列索引值 int floorX clickX ~/ cellWidth; //计算了当前列横坐标网格线中点的横坐标值 offsetFloorX。通过将 floorX 乘以格子的宽度 cellWidth再加上格子宽度的一半 cellWidth / 2可以得到当前列横坐标网格线中点的横坐标值。 double offsetFloorX floorX * cellWidth cellWidth / 2; //判断点击点在哪一列并将结果赋值给变量 x。如果 offsetFloorX 大于点击点的 x 坐标 clickX则说明点击点在 floorX 列否则说明点击点在 floorX 1 列。如果点击点在 floorX 1 列则通过 floorX 来获取 floorX 1 的值。 int x offsetFloorX clickX ? floorX : floorX;
//y轴同理 double clickY details.localPosition.dy; int floorY clickY ~/ cellHeight; double offsetFloorY floorY * cellHeight cellHeight / 2; int y offsetFloorY clickY ? floorY : floorY;
//触发落子 fallChessman(Offset(x.toDouble(), y.toDouble())); } 落子函数 void fallChessman(Offset position) { if (winResult.isNotEmpty) { return; } //创建棋子 Chessman newChessman; //棋子的颜色 if (chessmanList.isEmpty || chessmanList.length % 2 0) { newChessman firstPlayer Player.black ? Chessman.black(position) : Chessman.white(position); } else { newChessman firstPlayer Player.black ? Chessman.white(position) : Chessman.black(position); } //判断是否能落子 bool canFall canFallChessman(newChessman); if (canFall) { //可以落子 //打印下落子棋子的信息 printFallChessmanInfo(newChessman); //此处还需完成: //1.棋子估值、ai相关逻辑 //2.对游戏胜利的校验对游戏和棋的校验 }else{ print(“此处无法落子!”); } }
void printFallChessmanInfo(Chessman newChessman) { print( “[落子成功], 棋子序号: n e w C h e s s m a n . n u m b e r I d , 颜色 : {newChessman.numberId} ,颜色: newChessman.numberId,颜色:{newChessman.owner Player.WHITE ? “白色” : “黑色”} , 位置 :(${newChessman.position.dx.toInt()} , ${newChessman.position.dy.toInt()})”); } 该坐标能否落子的判断 bool canFallChessman(Chessman chessman) { //定义一个不可能生成到棋盘上的棋子 Chessman defaultChessman Chessman(Offset(-1, 0), Player.black); if (chessmanList.isNotEmpty) { Chessman cm chessmanList.firstWhere((Chessman c) { //如果找到位置相同的棋子那么cm就等于这棋子的信息 return c.position.dx chessman.position.dx c.position.dy chessman.position.dy; }, orElse: () { //没找到就把该棋子添加到列表中然后返回一个不可能在棋盘上的棋子用作校验 chessmanList.add(chessman); return defaultChessman; }); // 如果找到了相同位置的棋子这里就会返回false否则返回true return cm defaultChessman; } else { //如果为空直接添加 chessmanList.add(chessman); return true; } } 棋盘校验规则 相较于棋子估值和ai的实现对棋子胜利、和棋的校验会比较简单从简到难让我们先完成对游戏规则的定义 胜利判断 bool checkResult(Chessman newChessman) { int currentX newChessman.position.dx.toInt(); int currentY newChessman.position.dy.toInt();
int count 0;
///横 /// o o o o o /// o o o o o /// x x x x x /// o o o o o /// o o o o o winResult.clear(); // 循环遍历当前行的前后四个位置如果存在检查是否有特定的棋子连成五子相连 //判断 currentX - 4 0 时它的意思是判断左侧第 4 个位置是否在棋盘内。 //如果 currentX - 4 大于 0则表示左侧第 4 个位置在棋盘内 //否则即 currentX - 4 0表示左侧第 4 个位置已经超出了棋盘边界。 for (int i (currentX - 4 0 ? currentX - 4 : 0); i (currentX 4 LINE_COUNT ? currentX 4 : LINE_COUNT); i) { // 计算当前位置的坐标 Offset position Offset(i.toDouble(), currentY.toDouble());
// 检查当前位置是否存在胜利的棋子
if (existSpecificChessman(position, newChessman.owner)) {// 将该棋子添加到胜利结果列表中并增加计数器winResult.add(Chessman(position, newChessman.owner));count;
} else {// 如果不存在特定的棋子清空胜利结果列表并将计数器重置为0winResult.clear();count 0;
}// 解析如果计数器达到5表示有五子相连输出胜利者信息并返回true
if (count 5) {print(胜利者产生: ${newChessman.owner Player.white ? 白色 : 黑色});//游戏胜利的提示弹窗winDialog(胜利者产生: ${newChessman.owner Player.white ? 白色 : 黑色});return true;
}}
//竖、正斜、反斜的逻辑代码请查看源码和横的校验差不多… winResult.clear(); return false; }
// 检查给定位置是否存在特定的棋子并且这个棋子的所有者是否与指定玩家相同 bool existSpecificChessman(Offset position, Player player) { //定义一个不可能生成到棋盘上的棋子 Chessman defaultChessman Chessman(Offset(-1, 0), Player.black); // 检查棋子列表是否非空 if (chessmanList.isNotEmpty) { // 在棋子列表中查找匹配给定位置的棋子 var cm chessmanList.firstWhere((Chessman c) { return c.position.dx position.dx c.position.dy position.dy; }, orElse: () { return defaultChessman; });
// 如果找到匹配的棋子检查其所有者是否是指定的玩家
return cm ! defaultChessman cm.owner player;} // 如果棋子列表为空或不存在棋子匹配给定位置则返回false return false; } existSpecificChessman函数看起来和前面判断该坐标能否落子的canFallChessman函数差不多这两个函数的主要区别在于作用和调用时机不同existSpecificChessman校验的是当前位置是否存在特定棋子且所有者是否相符而canFallChessman校验的是当前位置是否可以落子。 和棋判断 判断是否和棋其实非常简单只要没有胜利同时棋盘满了就代表和棋了。 //判断棋盘是否满了 bool isHaveAvailablePosition() { return chessmanList.length 255; } 到这里为止呢已经完成了五子棋的基本玩法你可以邀请你的朋友和你一起对战了
棋子估值 对每颗棋子进行打分是完成一切算法的基础条件如果没有分数那么算法也就无法生效。 估值算法也是本文的核心个人觉得估价函数比MinMax算法和Alpha-Beta剪枝算法这两个算法的难度大多了本文的算法部分主要参考了这几篇文章 五子棋估值算法 基于博弈树的五子棋 AI 算法及其 C 实现 前提条件本文的规则只涉及无禁手的五子棋 大部分的棋类游戏先手都有一个优势。以五子棋为例先达成五子连珠者胜由于黑方先走了一步五子棋几乎是先手必胜的局面。所以假设五子棋的胜负条件会变成如果黑方达成五子连珠之后白棋也可在一步之内达成五子连珠判定平手。这样的话就公平了但是也失去了对弈的一些乐趣和意义因为白棋只要一直跟着黑棋下最后一定会为平局。所以为了平衡先手优势大部分棋类都有一个补偿规则。如五子棋的禁手以及三手交换五手两打。在此不作过多解释有兴趣可以自行百度本文的规则及算法对先手无任何限制。 相较于象棋、围棋五子棋的局面并不复杂估值还算比较简单我们简单的用一个整数表示当前局势分数越大则自己优势越大分数越小则对方优势越大分数为0是表示双方局势相当。可以先把几种情况定义出来 其中的解释中x代表白棋o代表黑棋我们从黑棋的角度去评分 static const int WIN 10000;
//低级死二 xoox static const int DEEP_DEATH2 2;
//死二 xoo static const int LOWER_DEATH2 4; //低级死三 xooox static const int DEEP_DEATH3 3; //死三 xooo static const int LOWER_DEATH3 6;
//低级死四 xoooox static const int DEEP_DEATH4 4; //死四 xoooo static const int LOWER_DEATH4 32;
//活二 oo static const int ALIVE2 10; //跳活二 o o static const int JUMP_ALIVE2 2; //活三 ooo static const int ALIVE3 100; //跳活三 oo o static const int JUMP_ALIVE3 10; //活四 oooo static const int ALIVE4 5000; //跳活四 1跳3或者3跳1或2跳2 o ooo || ooo o || oo oo static const int JUMP_ALIVE4 90; 在实现估值算法前我们还需要实现一个泛型类BufferMap实现一个缓冲区的功能BufferMap的用处在于记录和管理最近的几个棋盘状态。借助它可以用于实现游戏的一些功能例如 ● 悔棋功能如果玩家想要悔棋可以通过BufferMap中的历史记录回退到之前的棋盘状态从而实现悔棋操作。 ● 撤销操作当玩家进行某些操作后发现操作结果不符合预期可以利用BufferMap中的历史记录撤销该操作恢复到之前的棋盘状态。 ● 历史记录展示通过BufferMap中保存的棋盘状态可以展示游戏的历史记录供玩家回顾以及分析棋局发展。 ● AI训练对于AI算法的训练过程中可以使用BufferMap来保存训练数据中的棋盘状态以便进行样本回放、经验重放等技术。 class BufferMap { //设置缓冲区为3 num maxCount 3; final Mapnum, V buffer {};
BufferMap();
BufferMap.maxCount(this.maxCount);
// 添加元素key存的是每个棋子的分数value是每个棋子的offset void put(num key, V value) { buffer.update(key, (V val) { return value; }, //当缓冲区中不存在指定键时会执行该回调函数来添加新的键值对。 ifAbsent: () { return value; }); _checkSize(); }
// 批量添加元素 void putAll(BufferMap map) { for (var entry in map.buffer.entries) { buffer[entry.key] entry.value; } }
// 检查并缩减缓冲区大小 void _checkSize() { //将缓冲区的所有键转换成列表并赋值给变量 list按照从大到小排列 var list buffer.keys.toList() …sort((num a, num b) { return b.compareTo(a); }); while (buffer.length maxCount) { buffer.remove(list.last); } }
// 将缓冲区转为Map Mapnum, V toMap() { return Mapnum, V.from(buffer); }
// 获取所有元素的值 Iterable values() { return buffer.values; }
// 获取缓存元素个数 int size() { return buffer.length; }
// 转为字符串表示 override String toString() { StringBuffer sb StringBuffer(); sb.write(“{”); var keys buffer.keys.toList() …sort((num a, num b) { return b.compareTo(a); });
for (var i in keys) {sb.write([$i , ${buffer[i]}] ,);
}return ${sb.toString().substring(0, sb.toString().length - 2)}};}
// 获取第一个元素的值 V? get first buffer[buffer.keys.toList() …sort((num a, num b) { return b.compareTo(a); }) …first];
// 获取键的最小值 num minKey() { if (buffer.isEmpty) { return double.negativeInfinity; } var list buffer.keys.toList() …sort((num a, num b) { return b.compareTo(a); }); return list.isNotEmpty ? list.last : double.negativeInfinity; }
// 获取键值最小的元素 MapEntrynum, V? min() { if (buffer.isEmpty) { return null; } var list buffer.keys.toList() …sort((num a, num b) { return b.compareTo(a); }); return list.isNotEmpty ? MapEntry(list.last, buffer[list.last]!) : null; }
// 获取所有键的列表 List get keySet { if (buffer.isEmpty) return [];
var sortedKeys buffer.keys.toList()..sort((num a, num b) {return (b - a).toInt();});return sortedKeys;}
// 通过键访问元素的值 V? operator [](Object? key) { return buffer[key]; }
// 获取键的最大值 // 最优位置得分 num maxKey() { if (buffer.isEmpty) { return double.negativeInfinity; } var list buffer.keys.toList() …sort((num a, num b) { return b.compareTo(a); }); return list.isNotEmpty ? list.first : 0; }
// 获取键值最大的元素 // MapEntry 提供了 key 和 value 两个只读属性来获取键和值分别返回对应键值对的键和值。在 Map 中使用迭代器遍历时每个元素都是 MapEntry 类型的实例。 MapEntrynum, V? max() { if (buffer.isEmpty) { return null; } var list buffer.keys.toList() …sort((num a, num b) { return b.compareTo(a); }); return list.isNotEmpty ? MapEntry(list.first, buffer[list.first]!) : null; } } 判断是那种棋局情况 需要对活二、跳活二、活三…这些不同的棋局状态定义校验规则规则太多文章中只看活二的校验规则其余请查看源码。 bool isAlive2(List list) { assert(list.length 2); //把两颗棋子传入 Offset offset1 nextChessman(list[1], list[0]); Offset offset2 nextChessman(list[0], list[1]);
return isEffectivePosition(offset1) isEffectivePosition(offset2) isBlankPosition(offset1) isBlankPosition(offset2); }
//输入的first和second返回下一个棋子的位置偏移量。 Offset nextChessman(Offset first, Offset second) { //检查first和second的dy值是否相等。 //如果相等表示棋子在水平方向上移动。那么下一个棋子的位置偏移量将在水平方向上向右或向左移动一格取决于first的dx是否大于second的dx。 //如果first.dx second.dx则向左移动一格即second.dx - 1否则向右移动一格即second.dx 1。纵坐标保持不变即为first.dy if (first.dy second.dy) { return Offset( first.dx second.dx ? second.dx - 1 : second.dx 1, first.dy); } //如果first.dx和second.dx相等表示棋子在垂直方向上移动。那么下一个棋子的位置偏移量将在垂直方向上向上或向下移动一格取决于first的dy是否大于second的dy。如果first.dy second.dy则向上移动一格即second.dy - 1否则向下移动一格即second.dy 1。横坐标保持不变即为first.dx。 //如果以上两种情况都不满足那么表示棋子在斜对角线方向上移动。根据first.dx和second.dx的大小关系以及first.dy和second.dy的大小关系决定下一个棋子的位置偏移量。 else if (first.dx second.dx) { return Offset( first.dx, first.dy second.dy ? second.dy - 1 : second.dy 1); } else if (first.dx second.dx) { if (first.dy second.dy) { return Offset(second.dx - 1, second.dy - 1); } else { return Offset(second.dx - 1, second.dy 1); } } else { if (first.dy second.dy) { return Offset(second.dx 1, second.dy - 1); } else { return Offset(second.dx 1, second.dy 1); } } }
//判断该位置是否有效。 bool isEffectivePosition(Offset offset) { return offset.dx 0 offset.dx LINE_COUNT offset.dy 0 offset.dy LINE_COUNT; }
//isBlankPosition是用于判断某个位置上是否没有棋子写法逻辑和用户交互能否落子差不多 bool isBlankPosition(Offset position) { if (chessmanList.isNotEmpty) { Chessman defaultChessman Chessman(Offset(-1, 0), Player.black); var cm chessmanList.firstWhere((Chessman c) { return c.position.dx position.dx c.position.dy position.dy; }, orElse: () { return defaultChessman; }); return cm ! defaultChessman; } return true; } 对每一种情况进行估分 这里只展示了两颗棋子的情况。 //将给定的数限制在最大值为2的范围内 int limitMax(int num) { return num 2 ? 2 : num; } //对每种棋局加分 int scoring(Offset first, List myChessman, Player player, {required String printMsg, bool isCanPrintMsg false}) { if (myChessman.length 5) { return WIN; } int score 0; switch (myChessman.length) { case 1: break; case 2: if (isAlive2(myChessman)) { score ALIVE2; score limitMax(getJumpAlive3Count(myChessman, player)) * JUMP_ALIVE3; score limitMax(getJumpAlive4Count(myChessman, player)) * JUMP_ALIVE4; if (isCanPrintMsg) {print($printMsg 活2成立, 得分$ALIVE2);}} else if (isLowerDeath2(myChessman)) {score LOWER_DEATH2;if (isCanPrintMsg) {print($printMsg 低级死2成立 ,得分$LOWER_DEATH2);}} else {score DEEP_DEATH2;if (isCanPrintMsg) {print($printMsg 死2成立 ,得分$DEEP_DEATH2);}}break;
case 3:...case 4:...case 5:
default:score WIN;} return score; } 对单颗棋子估分 在棋盘中某一块范围内只有一颗棋子时就都不能满足上方的几种棋局那我们还需要对单颗棋子进行一个打分。 ///位置得分(越靠近中心得分越高) int positionScore(Offset offset) { //这个值是通过对(offset.dx - 7.5)^2 (offset.dy - 7.5)^2进行运算得到的。 //其中^表示乘方操作即取平方可以把棋盘上每颗棋子的位置想成一个圆锥越靠近中心位置越高 //参考点被设定为(7.5, 7.5)棋盘的中心 double z -(pow(offset.dx - 7.5, 2) pow(offset.dy - 7.5, 2)) 112.5; z / 10; return z.toInt(); }
///孤子价值 int scoringAloneChessman(Offset offset) { int score 0; List list [ Offset(offset.dx - 1, offset.dy), Offset(offset.dx 1, offset.dy), Offset(offset.dx, offset.dy 1), Offset(offset.dx, offset.dy - 1), Offset(offset.dx - 1, offset.dy - 1), Offset(offset.dx - 1, offset.dy 1), Offset(offset.dx 1, offset.dy - 1), Offset(offset.dx 1, offset.dy 1), ]; for (offset in list) { if (offset.dx 0 offset.dy 0 isBlankPosition(offset)) { score; } }
return score positionScore(offset); } 计算某一颗棋子对于玩家的评分 只分析横向上的棋子其他方向的代码请查看源码。 ///计算某个棋子对于 ownerPlayer 的分值 int chessmanGrade(Offset chessmanPosition, {required Player ownerPlayer, bool isCanPrintMsg false}) { int score 0; List myChenssman []; Offset offset; Offset first chessmanPosition; Player player ownerPlayer; player ?? computerPlayer;
///横向 //横向(左) offset Offset(first.dx - 1, first.dy); myChenssman …clear() …add(first); while (existSpecificChessman(offset, player)) { myChenssman.add(offset); offset Offset(offset.dx - 1, offset.dy); }
//横向(右) offset Offset(first.dx 1, first.dy); while (existSpecificChessman(offset, player)) { myChenssman.add(offset); offset Offset(offset.dx 1, offset.dy); } myChenssman.sort((a, b) { return (a.dx - b.dx).toInt(); }); score scoring(first, myChenssman, player, printMsg: “横向”, isCanPrintMsg: isCanPrintMsg);
...int ss score scoringAloneChessman(first); if (isCanPrintMsg) { print(“该子分值为: s s , 其中单子得分 : ss ,其中单子得分: ss,其中单子得分:{scoringAloneChessman(first)}, 组合得分:$score”); }
int jumpAlive4Count getJumpAlive4Count([first], player); int jumpAlive3Count getJumpAlive3Count([first], player); int jumpAlive2Count getJumpAlive2Count([first], player); score limitMax(jumpAlive4Count) * JUMP_ALIVE4 limitMax(jumpAlive3Count) * JUMP_ALIVE3 limitMax(jumpAlive2Count) * JUMP_ALIVE2;
return score scoringAloneChessman(first); } 计算我方下一步较好的位置 BufferMap ourBetterPosition({maxCount 5}) { Offset offset Offset.zero; BufferMap ourMap BufferMap.maxCount(maxCount); for (int i 0; i LINE_COUNT; i) { for (int j 0; j LINE_COUNT; j) { offset Offset(i.toDouble(), j.toDouble()); if (isBlankPosition(offset)) { int score chessmanGrade(offset, ownerPlayer: Player.black); if (ourMap.minKey() score) { ourMap.put(score, Offset(offset.dx, offset.dy)); } } } } return ourMap; } 计算敌方下一步较好的位置 BufferMap enemyBetterPosition({maxCount 5}) { Offset offset Offset.zero; BufferMap enemyMap BufferMap.maxCount(5); print(“查找敌方最优落子位置”);
int count 0; for (int i 0; i LINE_COUNT; i) { for (int j 0; j LINE_COUNT; j) { offset Offset(i.toDouble(), j.toDouble()); if (isBlankPosition(offset)) { DateTime start DateTime.now(); int score chessmanGrade(offset, ownerPlayer: computerPlayer Player.black ? Player.white : Player.black); DateTime end DateTime.now(); count; int time end.millisecondsSinceEpoch - start.millisecondsSinceEpoch; if (time 5) { print(“查找敌方最优落子位置耗时KaTeX parse error: Expected EOF, got } at position 17: …ime); }̲ if (en…count”); return enemyMap; } 基础版本AI Future nextByAI({bool isPrintMsg false}) async { //如果评分出现ALIVE4的级别直接下 Offset pos needDefenses(); if (pos ! const Offset(-1, 0)) { return pos; }
// 取我方,敌方 各5个最优点位置, // 防中带攻: 如果判断应该防守,则在敌方5个最优位置中找出我方优势最大的点落子 // 攻中带防: 如果判断应该进攻,则在己方5个最优位置中找出敌方优势最大的点落子 BufferMap ourPositions ourBetterPosition(); BufferMap enemyPositions enemyBetterPosition();
Offset position bestPosition(ourPositions, enemyPositions); return position; }
Offset needDefenses() { BufferMap enemy enemyBetterPosition(); late Offset defensesPosition; for (num key in enemy.keySet) { print(“key:${key}”); if (key ALIVE4) { defensesPosition enemy[key]!; break; } else { defensesPosition const Offset(-1, 0); } } return defensesPosition; }
//基础AI没有涉及算法//遍历当前棋盘上的空位置然后逐个计算该空位的得分(位置分组合分)然后取分数最高的点落子 Offset bestPosition( BufferMap ourPositions, BufferMap enemyPositions) { late Offset position; double maxScore 0;
///当对手的最优位置得分 / 我方最优位置得分 1.5 防守反之进攻
if (enemyPositions.maxKey() / ourPositions.maxKey() 1.5) {for (num key in enemyPositions.keySet) {int attackScore chessmanGrade(enemyPositions[key]!, ownerPlayer: computerPlayer);double score key * 1.0 attackScore * 0.8;if (score maxScore) {maxScore score;position enemyPositions[key]!;}}
} else {for (num key in ourPositions.keySet) {int defenseScore chessmanGrade(ourPositions[key]!, ownerPlayer: computerPlayer);double score key * 1.0 defenseScore * 0.8;if (score maxScore) {maxScore score;position ourPositions[key]!;}}
}
return position;}
这个时候一个基础的五子棋AI就实现啦它也能和五子棋入门的选手碰一碰了玩了3把稍微没注意就输了一把给它… 基于Max-Min算法 本文算法内容参考多篇与Max-Min算法相关文章 井字游戏/一字棋——Max-Min智能算法 AI MinMax算法 计算机博弈 基本算法 极大极小算法 在基础版本的AI中我们已经取得了下一步较好的maxCount个位置有每个位置有着对应的分数那么我们就可以把这些位置都落子一次这个时候我们需要给每一种结果一个分数就是下图中的Utility下图是井字棋游戏整体逻辑差不多。这个分数是站在Max的角度评估的比如上图中我赢了就是1输了是1平局时0。所以我希望最大化这个分数而我的对手希望最小化这个分数。(MaxMin算法在有限深度的范围内进行搜索假定博弈双方都是最精明的也就是每次都会选择可能获胜的最大值。那么对于我方来说对方每次都会选取使我方获胜的最小值MIN我方会选择使我方获胜的最大值MAX。)
大部分游戏是不太可能把所有结果都列出来的因为计算量会过于庞大所以我们可能只能往前推78步根据算力所以这个时候分数就不只101这么简单了。那么我们如何如何确定最后的落子地点呢就是模拟棋盘往后模拟几步生成这颗博弈树再向上反推找到双方最优的落子地点。 具体的算法细节可以看下上面参考的几篇文章在看这个算法之前需要了解基础的广度优先搜索(BFS)深度优先搜索(DFS)。
回到我们的编码部分 在开始具体的算法编写前我们还需要一些前置的参数 enum ChildType { /// 标记当前节点为对手节点会选择使我方得分最小的走势 MIN,
/// 标记当前节点为我方节点会选择使我方得分最大的走势 MAX }
class ChessNode{ /// 当前节点的棋子 Chessman current; /// 当前节点的父节点 ChessNode parentNode; /// 当前节点的所有子节点 List childrenNode []; /// 当前节点的值 num value double.nan; /// 当前节点的类型(我方/敌方) ChildType type; /// 当前节点值的上限 num maxValue; /// 当前节点值的下限 num minValue; /// 当前节点的层深度 int depth 0; /// 用于根节点记录选择的根下子节点 Chessman checked; } 使用算法相较于前面的基础版本AI就是多了模拟棋盘的步骤 生成临时棋局 /// 生成临时棋局 List createTempChessmanList(ChessNode node) { //growable是一个可选参数用于指定是否允许在列表中添加或删除元素。 //当growable为false时列表的长度是固定的并且不能添加或删除元素当growable为true时列表的长度是可变的可以随时添加或删除元素。 List temp List.from(chessmanList, growable: true); temp.add(node.current!);
ChessNode? current node.parentNode; while (current ! null current.current ! null) { temp.add(current.current!); current current.parentNode; } return temp; } 生成博弈树子节点 /// 生成博弈树子节点 void createChildren(ChessNode parent) { if (parent null) { return null; }
// 判断是否达到最大深度如果是则计算棋局估值并返回 if (parent.depth maxDepth) { List list createTempChessmanList(parent); var start DateTime.now(); parent.value statusScore(our, list); var value DateTime.now(); return; }
// 确定当前玩家和子节点类型 Player currentPlayer parent.current!.owner Player.black ? Player.white : Player.black; ChildType type parent.type ChildType.MAX ? ChildType.MIN : ChildType.MAX;
// 创建临时棋子列表 var list createTempChessmanList(parent);
// 查找最优落子位置 var start DateTime.now(); BufferChessmanList enemyPosList enemyBestPosition(list, maxCount: 5); var value DateTime.now();
// 将最优落子位置放入列表中 OffsetList offsetList OffsetList()…addAll(enemyPosList.toList()); List result offsetList.toList();
// 遍历最优落子位置生成子节点 for (Offset position in result) { Chessman chessman Chessman(position, currentPlayer);
ChessNode node ChessNode()..parentNode parent..current chessman..type type..depth parent.depth 1..maxValue parent.maxValue..minValue parent.minValue;parent.childrenNode.add(node);// 递归调用 createChildren 方法生成子节点的子节点直到达到最大深度或无法再生成子节点为止。
createChildren(node);} } 生成五子棋博弈树 //生成五子棋博弈树 ChessNode createGameTree() { //创建根节点 root设置其属性值深度为0估值为NaN节点类型为 ChildType.MAX最小值为负无穷最大值为正无穷。 ChessNode root ChessNode() …depth 0 …value double.nan …type ChildType.MAX …minValue double.negativeInfinity …maxValue double.infinity;
//确定当前玩家 currentPlayer //如果棋子列表 chessmanList 为空则当前玩家为黑色 //否则根据棋子列表中最后一个棋子的颜色设置当前玩家为另一个颜色。 Player currentPlayer; if (chessmanList.isEmpty) { currentPlayer Player.black; } else { currentPlayer chessmanList.last.owner Player.black ? Player.white : Player.black; }
//查找敌方最优落子位置并将结果存储在 enemyPosList 变量中。 //然后将 enemyPosList 转换为 OffsetList 对象 //再将其转换为普通列表类型 List 对象。这些位置将用于创建第一层子节点。 BufferChessmanList enemyPosList enemyBestPosition(chessmanList, maxCount: 5);
OffsetList list OffsetList()…addAll(enemyPosList.toList()); List result list.toList();
int index 0; //通过遍历 result 列表为每个位置 position 创建一个新的棋子 chessman 和一个新的子节点 node //然后将子节点 node 添加到根节点的子节点列表 root.childrenNode 中 for (Offset position in result) { Chessman chessman Chessman(position, currentPlayer);
ChessNode node ChessNode()..parentNode root..depth root.depth 1..maxValue root.maxValue..minValue root.minValue..type ChildType.MIN..current chessman;root.childrenNode.add(node);
var start DateTime.now();
createChildren(node);
var create DateTime.now();print(创建第一层第$index个节点耗时${create.millisecondsSinceEpoch - start.millisecondsSinceEpoch});
index;} return root; } Max-Min算法实现 num maxMinSearch(ChessNode root) { if (root.childrenNode.isEmpty) { return root.value; // 返回叶子节点的估值 } List children root.childrenNode; if (root.type ChildType.MIN) { // 如果是对手执行操作 for (ChessNode node in children) { if (maxMinSearch(node) root.maxValue) { // 判断子节点的估值是否小于当前节点的最大值 root.maxValue node.value; // 更新当前节点的最大值 root.value node.value; // 更新当前节点的估值 root.checked node.current!; // 更新当前节点的选择步骤 } else { continue; // 否则继续遍历下一个子节点 } } } else { // 如果是自己执行操作 for (ChessNode node in children) { if (maxMinSearch(node) root.minValue) { // 判断子节点的估值是否大于当前节点的最小值 root.minValue node.value; // 更新当前节点的最小值 root.value node.value; // 更新当前节点的估值 root.checked node.current!; // 更新当前节点的选择步骤 } else { continue; // 否则继续遍历下一个子节点 } } } return root.value; // 返回当前节点的估值 } 基于alpha-beta剪枝算法 如果在比赛中假设使用极小极大的算法计算机能往前评估7步加上剪枝算法计算机就能往前评估14步! num alphaBetaSearch(ChessNode current) { count; // 搜索次数累加
if (current.childrenNode.isEmpty) { // 如果当前节点没有子节点即为叶子节点 return current.value; // 返回该节点的值 }
if (current.parentNode ! null !current.parentNode!.childrenNode.contains(current)) { ChessNode parent current.parentNode!;
// 如果父节点存在且父节点的子节点不包含当前节点说明该枝已经被剪掉返回父节点的最大/最小值
return parent.type ChildType.MAX ? parent.minValue : parent.maxValue;}
List children current.childrenNode; // 获取当前节点的子节点
if (current.type ChildType.MIN) { // 当前节点为MIN节点 num parentMin current.parentNode?.minValue ?? double.negativeInfinity; // 获取父节点的最小值若不存在父节点则设置为负无穷大 int index 0; // 索引计数器
for (ChessNode node in children) {index; // 索引递增num newCurrentMax min(current.maxValue, alphaBetaSearch(node)); // 计算当前子节点的最大值if (newCurrentMax parentMin) {// 如果当前子节点的最大值小于等于父节点的最小值则说明该枝可以被完全剪掉current.childrenNode current.childrenNode.sublist(0, index); // 将当前节点的子节点列表截断至当前索引位置return parentMin; // 返回父节点的最小值}if (newCurrentMax current.maxValue) {// 如果当前子节点的最大值小于当前节点的最大值则更新当前节点的最大值、值和经过路径的位置信息current.maxValue newCurrentMax;current.value node.value;current.checked node.current!;}
}if (current.maxValue parentMin) {// 如果当前节点的最大值大于父节点的最小值则更新父节点的最小值、值和经过路径的位置信息current.parentNode?.minValue current.maxValue;current.parentNode?.value current.value;current.parentNode?.checked current.current!;
}return current.maxValue; // 返回当前节点的最大值作为该节点在搜索树中的价值} else { // 当前节点为MAX节点 num parentMax current.parentNode?.maxValue ?? double.infinity; // 获取父节点的最大值若不存在父节点则设置为正无穷大 int index 0; // 索引计数器
for (ChessNode node in children) {index; // 索引递增num newCurrentMin max(current.minValue, alphaBetaSearch(node)); // 计算当前子节点的最小值if (parentMax newCurrentMin) {// 如果父节点的最大值小于当前子节点的最小值则说明该枝可以被完全剪掉current.childrenNode current.childrenNode.sublist(0, index); // 将当前节点的子节点列表截断至当前索引位置return parentMax; // 返回父节点的最大值}if (newCurrentMin current.minValue) {// 如果当前子节点的最小值大于当前节点的最小值则更新当前节点的最小值、值和经过路径的位置信息current.minValue newCurrentMin;current.value node.value;current.checked node.current!;}
}if (current.minValue parentMax) {// 如果当前节点的最小值小于父节点的最大值则更新父节点的最大值、值和经过路径的位置信息current.parentNode?.maxValue current.minValue;current.parentNode?.value current.value;current.parentNode?.checked current.current!;
}return current.minValue; // 返回当前节点的最小值作为该节点在搜索树中的价值} } Max-Min和剪枝算法曾在IBM开发的国际象棋超级电脑深蓝Deep Blue中被应用并且两次打败当时的世界国际象棋冠军。文章到这里五子棋的AI版本就完成了
关于我 Hello我是Taxze如果您觉得文章对您有价值希望您能给我的文章点个❤️有问题需要联系我的话我在这里 。如果您觉得文章还差了那么点东西也请通过关注督促我写出更好的文章~万一哪天我进步了呢
