国庆假期，我用 Flutter 写了个我自己都玩不赢的五子棋 AI🤣
作者：编程的平行世界
- 2023-10-05 浙江
本文字数：20024 字
阅读完需：约 66 分钟
前言
在上一篇文章中，讲解了如何实现双人在本地对战的五子棋，但是只有一个人的时候就不太好玩，同时博主也没有把五子棋相关的文章写过瘾。那么这篇文章，我们来实现一个功能更加丰富的五子棋吧！在设计五子棋的算法方面，我们将引入一些经典的算法，如最大最小搜索（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: (${position.dx},${position.dy}), owner: ${owner == Player.black ? "black" : "white"}, score: $score, numberId: $numberId}'; }}
复制代码
全局通用参数
//初始化一个玩家，掌握黑棋Player firstPlayer = Player.black;//存放所有的棋子List<Chessman> chessmanList = [];//存放胜利的棋子List<Chessman> 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;//根据屏幕大小与行列数，计算得出每个格子的宽高，初始化先为0double 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); } ...}
复制代码
绘制棋盘上的线条（格子）
@overridevoid 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绘制，每下一颗子，触发setStateif (chessmanList.isNotEmpty) { for (Chessman c in chessmanList) { _drawChessman(c); }}
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); }}
复制代码
绘制棋子编号（非主要功能，可以跳过这步）
//在棋子上绘制它的idif (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( "[落子成功], 棋子序号:${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 { // 如果不存在特定的棋子，清空胜利结果列表，并将计数器重置为0 winResult.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 剪枝算法这两个算法的难度大多了，本文的算法部分主要参考了这几篇文章：
前提条件：本文的规则只涉及****无禁手的五子棋
大部分的棋类游戏，先手都有一个优势。以五子棋为例，先达成五子连珠者胜，由于黑方先走了一步，五子棋几乎是先手必胜的局面。所以假设五子棋的胜负条件会变成：如果黑方达成五子连珠之后，白棋也可在一步之内达成五子连珠，判定平手。这样的话就公平了，但是也失去了对弈的一些乐趣和意义，因为白棋只要一直跟着黑棋下，最后一定会为平局。所以为了平衡先手优势，大部分棋类都有一个补偿规则。如五子棋的禁手以及三手交换五手两打。在此不作过多解释，有兴趣可以自行百度，本文的规则及算法对先手无任何限制。
相较于象棋、围棋，五子棋的局面并不复杂，估值还算比较简单，我们简单的用一个整数表示当前局势，分数越大，则自己优势越大，分数越小，则对方优势越大，分数为 0 是表示双方局势相当。可以先把几种情况定义出来：
其中的解释中，x 代表白棋，o 代表黑棋，我们从黑棋的角度去评分
static const int WIN = 10000;
//低级死二 xooxstatic const int DEEP_DEATH2 = 2;
//死二 xoostatic const int LOWER_DEATH2 = 4;//低级死三 xoooxstatic const int DEEP_DEATH3 = 3;//死三 xooostatic const int LOWER_DEATH3 = 6;
//低级死四 xooooxstatic const int DEEP_DEATH4 = 4;//死四 xoooostatic const int LOWER_DEATH4 = 32;
//活二 oostatic const int ALIVE2 = 10;//跳活二 o ostatic const int JUMP_ALIVE2 = 2;//活三 ooostatic const int ALIVE3 = 100;//跳活三 oo ostatic const int JUMP_ALIVE3 = 10;//活四 oooostatic const int ALIVE4 = 5000;//跳活四 （1跳3或者3跳1或2跳2） o ooo || ooo o || oo oostatic const int JUMP_ALIVE4 = 90;
复制代码
在实现估值算法前，我们还需要实现一个泛型类 BufferMap，实现一个缓冲区的功能，BufferMap 的用处在于记录和管理最近的几个棋盘状态。借助它可以用于实现游戏的一些功能，例如：
悔棋功能：如果玩家想要悔棋，可以通过 BufferMap 中的历史记录回退到之前的棋盘状态，从而实现悔棋操作。
撤销操作：当玩家进行某些操作后，发现操作结果不符合预期，可以利用 BufferMap 中的历史记录撤销该操作，恢复到之前的棋盘状态。
历史记录展示：通过 BufferMap 中保存的棋盘状态，可以展示游戏的历史记录，供玩家回顾以及分析棋局发展。
AI 训练：对于 AI 算法的训练过程中，可以使用 BufferMap 来保存训练数据中的棋盘状态，以便进行样本回放、经验重放等技术。
class BufferMap<V> { //设置缓冲区为3 num maxCount = 3; final Map<num, 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<V> 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 Map<num, V> toMap() { return Map<num, V>.from(buffer); }
// 获取所有元素的值 Iterable<V> 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; }
// 获取键值最小的元素 MapEntry<num, 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<num> 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 类型的实例。 MapEntry<num, 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<Offset> 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<Offset> 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<Offset> 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<Offset> 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("该子分值为: $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<Offset> ourBetterPosition({maxCount = 5}) { Offset offset = Offset.zero; BufferMap<Offset> 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<Offset> enemyBetterPosition({maxCount = 5}) { Offset offset = Offset.zero; BufferMap<Offset> 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("查找敌方最优落子位置耗时：$time"); } if (enemyMap.minKey() < score) { enemyMap.put(score, Offset(offset.dx, offset.dy)); } } } } print("查找敌方最优落子位置次数：$count"); return enemyMap;}
复制代码
基础版本 AI
Future<Offset> nextByAI({bool isPrintMsg = false}) async { //如果评分出现ALIVE4的级别，直接下 Offset pos = needDefenses(); if (pos != const Offset(-1, 0)) { return pos; }
// 取我方,敌方 各5个最优点位置, // 防中带攻: 如果判断应该防守,则在敌方5个最优位置中找出我方优势最大的点落子 // 攻中带防: 如果判断应该进攻,则在己方5个最优位置中找出敌方优势最大的点落子 BufferMap<Offset> ourPositions = ourBetterPosition(); BufferMap<Offset> enemyPositions = enemyBetterPosition();
Offset position = bestPosition(ourPositions, enemyPositions); return position;}
Offset needDefenses() { BufferMap<Offset> 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<Offset> ourPositions, BufferMap<Offset> 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 算法相关文章：
在基础版本的 AI 中，我们已经取得了下一步较好的 maxCount 个位置，有每个位置有着对应的分数，那么我们就可以把这些位置都落子一次，这个时候我们需要给每一种结果一个分数，就是下图中的 Utility（下图是井字棋游戏，整体逻辑差不多）。这个分数是站在 Max 的角度评估的，比如上图中我赢了就是＋1，输了是－1，平局时 0。所以，我希望最大化这个分数，而我的对手希望最小化这个分数。(MaxMin 算法在有限深度的范围内进行搜索，假定博弈双方都是最精明的，也就是每次都会选择可能获胜的最大值。那么对于我方来说，对方每次都会选取使我方获胜的最小值 MIN；我方会选择使我方获胜的最大值 MAX。)
大部分游戏是不太可能把所有结果都列出来的，因为计算量会过于庞大，所以我们可能只能往前推 7，8 步（根据算力），所以这个时候分数就不只－1，0，1 这么简单了。那么我们如何如何确定最后的落子地点呢？就是模拟棋盘，往后模拟几步，生成这颗博弈树，再向上反推，找到双方最优的落子地点。
具体的算法细节可以看下上面参考的几篇文章，在看这个算法之前需要了解基础的广度优先搜索(BFS)，深度优先搜索(DFS)。
回到我们的编码部分
在开始具体的算法编写前，我们还需要一些前置的参数：
enum ChildType { /// 标记当前节点为对手节点，会选择使我方得分最小的走势 MIN,
/// 标记当前节点为我方节点，会选择使我方得分最大的走势 MAX}
class ChessNode{ /// 当前节点的棋子 Chessman current; /// 当前节点的父节点 ChessNode parentNode; /// 当前节点的所有子节点 List<ChessNode> childrenNode = []; /// 当前节点的值 num value = double.nan; /// 当前节点的类型(我方/敌方) ChildType type; /// 当前节点值的上限 num maxValue; /// 当前节点值的下限 num minValue; /// 当前节点的层深度 int depth = 0; /// 用于根节点记录选择的根下子节点 Chessman checked;}
复制代码
使用算法相较于前面的基础版本 AI 就是多了模拟棋盘的步骤：
生成临时棋局
/// 生成临时棋局List<Chessman> createTempChessmanList(ChessNode node) { //growable是一个可选参数，用于指定是否允许在列表中添加或删除元素。 //当growable为false时，列表的长度是固定的，并且不能添加或删除元素；当growable为true时，列表的长度是可变的，可以随时添加或删除元素。 List<Chessman> 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<Chessman> 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<Offset> 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<Offset> 对象。这些位置将用于创建第一层子节点。 BufferChessmanList enemyPosList = enemyBestPosition(chessmanList, maxCount: 5);
OffsetList list = OffsetList()..addAll(enemyPosList.toList()); List<Offset> 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<ChessNode> 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<ChessNode> 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 版本就完成了！
划线
评论
复制
发布于: 2023-10-05阅读数: 5
版权声明: 本文为 InfoQ 作者【编程的平行世界】的原创文章。
原文链接:【http://xie.infoq.cn/article/724d0db15283faeb34a412b85】。文章转载请联系作者。
编程的平行世界
关注
他日若遂凌云志 敢笑黄巢不丈夫 2020-10-15 加入
曾许少年凌云志，誓做人间第一流. 一起加入Flutter技术交流群532403442 有好多好多滴学习资料喔～ 小T目前主攻Android与Flutter, 通常会搞搞人工智能、SpringBoot 、Mybatiys等.
评论