Flutter AI版本五子棋-阿里云开发者社区

前言

在上一篇文章中，讲解了如何实现双人在本地对战的五子棋，但是只有一个人的时候就不太好玩，同时博主也没有把五子棋相关的文章写过瘾。那么这篇文章，我们来实现一个功能更加丰富的五子棋吧！在设计五子棋的算法方面，我们将引入一些经典的算法，如最大最小搜索（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;
//根据屏幕大小与行列数，计算得出每个格子的宽高，初始化先为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(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);
  }
}

绘制棋子编号（非主要功能，可以跳过这步）

//在棋子上绘制它的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(
      "[落子成功], 棋子序号:${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剪枝算法这两个算法的难度大多了，本文的算法部分主要参考了这几篇文章：

五子棋估值算法

基于博弈树的五子棋 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<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算法相关文章：

井字游戏/一字棋——Max-Min智能算法

AI MinMax算法

计算机博弈基本算法极大极小算法

在基础版本的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版本就完成了！

Flutter AI版本五子棋

前言

棋盘绘制

玩家类

单颗棋子类

全局通用参数

游戏页面整体布局结构

棋盘绘制主体

用户交互（下棋）

取得用户点击的位置

点击事件

落子函数

该坐标能否落子的判断

棋盘校验规则

胜利判断

和棋判断

棋子估值

判断是那种棋局情况

对每一种情况进行估分

对单颗棋子估分

计算某一颗棋子对于玩家的评分

计算我方下一步较好的位置

计算敌方下一步较好的位置

基础版本AI

基于Max-Min算法

生成临时棋局

生成博弈树子节点

生成五子棋博弈树

Max-Min算法实现

基于alpha-beta剪枝算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

Flutter AI版本五子棋

前言

棋盘绘制

玩家类

单颗棋子类

全局通用参数

游戏页面整体布局结构

棋盘绘制主体

用户交互（下棋）

取得用户点击的位置

点击事件

落子函数

该坐标能否落子的判断

棋盘校验规则

胜利判断

和棋判断

棋子估值

判断是那种棋局情况

对每一种情况进行估分

对单颗棋子估分

计算某一颗棋子对于玩家的评分

计算我方下一步较好的位置

计算敌方下一步较好的位置

基础版本AI

基于Max-Min算法

生成临时棋局

生成博弈树子节点

生成五子棋博弈树

Max-Min算法实现

基于alpha-beta剪枝算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景