avatar
阳生。
风毛丛劲节，只上尽头竿。

Connect6框架学习

在大三学年的秋季学期，人工智能导论课堂上开发了一个AI六子棋的项目，整个开发依托于一个开源的框架，在这里对框架与实现思路做一些简单的记录

基本框架

比赛如何开始？

主函数AITester()->oucLeague()->GameEvent根据HostID调用函数hostGames()，开始一场比赛；

关于hostGames:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void hostGames(int hostId) throws CloneNotSupportedException {
   ArrayList<Game> games = new ArrayList();
   Player host = this.getHost(hostId);
   Iterator var4 = this.players.iterator();

   while(var4.hasNext()) {
      Player player = (Player)var4.next();
      if (!player.equals(host)) {
         games.add(new Game((Player)host.clone(), (Player)player.clone()));
      }
   }

   this.runGames(games);
}
  1. 简单来说就是读取properties文件中的hostId，作为host；
  2. 读取Players列表，选择除了host以外的作为自己的对手；
  3. games.add()创建对应比赛，最终形成一个比死列表，然后在runGames()中依次完成比赛，得到结果列表；

配置文件中相关项如下：

1
2
3
4
5
#the Ids of each player. corresponding ClassName, for example "stud.g77.AI"
Player_Ids = 2,14
#the group who hosts the games with each other groups.
#at every game, the host plays first, i.e. who uses the white stone.
Host = 2
  1. runGames会遍历当前的games列表，对于其中的每个元素转换为Game对象，使用game.start()开始一次对局；
  2. 上述函数在Game类中，最终的效果是将一局游戏启动为一个Thread，并运行该game.run()；

Game类中相关函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public void run() {
    if (Configuration.GUI) {
       this.referee.setUi(this);
    }

    int steps = 1;

    Move move;
    for(Move currMove = null; this.running(); currMove = move) { //running()布尔值判断游戏是否还在运行

      //处理游戏结束的逻辑，不同的结束原因给出对应的提示；
       if (this.referee.gameOver()) {
          this.endingGame("F", (Move)null);
          break;
       }

       if (steps > Configuration.MAX_STEP) {
          this.endingGame("M", (Move)null);
          break;
       }

      //检查当前是谁在下棋，创建对应的Player实例以应用对应的算法
       Player currPlayer = this.referee.whoseMove();
       currPlayer.startTimer();
       move = null;

       try {
          move = currPlayer.findMove(currMove);
       } catch (Exception var6) {
          //由于Player实例出错导致的游戏结束；
          this.endingGame("E", (Move)null);
          break;
       }

       currPlayer.stopTimer();
       if (Thread.interrupted()) {
          break;
       }

      //由于当前Player实例犯规导致的游戏结束；
       if (!this.referee.legalMove(move)) {
          this.endingGame("N", move);
          break;
       }

      //观战者相关的逻辑，或许与GUI的绘制有关；
       this.setChanged();
       this.notifyObservers(move);
       ++steps;
    }

 }
  1. anyway，最核心的方法实际上就是我们的AI要继承Player类，去按照六子棋的合法规则，实现findMove()方法；
  2. 那么首要的，要明确findMove()的返回值，Move类是怎样的；

作为一个框架，其内容纷繁，我们看它的核心部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Move {
   public static final int SIDE = 19;//规定棋盘大小
   public static final char MAXCHAR = 'S';//字符索引最大值，19*19的棋盘，用'A'到'S'来对印索引
   static final int MAX_INDEX = 360;//二维棋盘19*19 = 361后压缩到一维数组中（从0开始）对应的最大索引值，这个360就是(19,19)的位置
   private static final int STEP_C = 1;//数字索引最小值
   private static final int STEP_R = 19;//数字索引最大值
   private static final int INDEX_ORIGIN = -1300;
   private int _index0;//表示当前Move的数字索引，一维数组的，一个数字就可以代表二维的一个坐标
   private int _index1;
   private char _col0;//表示当前Move的字符索引，二维数组的，结合_row0，一起代表一个坐标
   private char _row0;
   private char _col1;
   private char _row1;

关键点是明确一个Move对象的属性值是如何对应到具体的落子位置的，有两种规则：

  1. 字符规则col,row分别取A到S的某个字符
  2. 整型规则index，取一个数字直接对应到转换后的一维数组
    （index计算规则也很简单，不用看代码就可以想到：index = 列号 + (行号-1)*19 - 1，注意行列号从1开始最大到19，最后再减1是因为一维数组从0开始）

明确了Move之后，我们还应该知道，每个Player实际上自己维护了一个Board；
在findNextMove()中会用如下规则更新：

1
2
3
4
5
6
7
8
board.makeMove(opponentMove);

BoardPro board = getBoard();
bestMoveCandidate = board.findwinMoves();
if (bestMoveCandidate != null) {
	board.makeMove(bestMoveCandidate);
	return bestMoveCandidate;
}

进一步查看makeMove()也可以体会到前面关于Move到说明

1
2
3
4
5
6
7
8
public void makeMove(Move mov) {
   assert this.legalMove(mov);

   this.moveList.add(mov);
   this.set(mov.col0(), mov.row0(), this._whoseMove);
   this.set(mov.col1(), mov.row1(), this._whoseMove);
   this._whoseMove = this._whoseMove.opposite();
}

当然Board肯定也是一个绕不过去的数据结构，接下里对其进行说明。

Board对象中比较关键的数据结构如下：

1
private final PieceColor[] _board;//这就是实际代表board的一维数组；

上述数组是一个PieceColer的对象，这个类型就是界定了当前的黑方棋子、白方棋子、空格；

1
2
3
4
5
public enum PieceColor {
   EMPTY,
   BLACK,
   WHITE;
//...

在这一节的最后在简单说明一下findNextMove()的逻辑；

  1. 维护board，使用opponentMove更新自己的board；
  2. 维护board，用自己决定的Move，更新自己的board；
  3. 将自己的Move返回；
    （自己的Move自己更新，将自己的返回給对手，对手用来更新）

博弈算法

判断是否有必胜招式，逻辑集成在findWinMoves()中；

在开始具体的算法之前，我们要明确一个关键的数据结构，即路Road与路表RoadTable
先从一个高度的概念范畴理解：

  1. Road：在六子棋中，任何连续的 6 个位置（横、竖、斜）都可能连成六子。
  2. RoadTable：RoadTable 预先计算并存储了棋盘上所有这些可能的 6 连位置。
  3. 好处：这使得 AI 无需遍历整个棋盘去寻找连珠，而是通过 O(1) 的时间复杂度直接从集合中获取威胁信息。

好处的例子（结合后面的说明很好理解）；

1
2
3
4
roadSetsByStoneCount[blackCount][whiteCount] 存储了所有包含 blackCount 个黑子和 whiteCount 个白子的“路”。
即时威胁识别：
如果 roadSetsByStoneCount[5][0] 不为空，说明黑方已经有“五连”，下一手必胜。
如果 roadSetsByStoneCount[0][4] 不为空，说明白方有“四连”，黑方必须防守。

关于Road，从其数据结构进行把握

1
2
3
4
5
6
7
8
9
10
11
   //主要是根据 起始位置 方向 黑白子数量来界定一个路；
   //默认的前提是一个路最多6个棋子；
public Road(int startPos, int dir, int blackNum, int whiteNum, boolean active) {
	super();
	this.startPos = startPos;//起始位置，对应的就是一维board的index
	this.dir = dir;//方向，数字0～3，后面的路表初始化也可以体现（分别是横、竖、左斜、右斜）
       //不用考虑前后，仅管往前，因为不同的startPos会覆盖到当前位置“往后的情况”
	this.blackNum = blackNum;//黑子数量
	this.whiteNum = whiteNum;//白子数量
	this.isLegal = active;//是否合法
}

关于RoadTable

1
2
//基本路表
private Road[][] roadsByStartPos = new Road[SIDE * SIDE][4];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 初始化路表 (伪代码)
function iniRoadTable():
	for i from 0 to SIDE-1: // 遍历行
		for j from 0 to SIDE-1: // 遍历列
			for k from 0 to 3: // 遍历4个方向 (横, 纵, 斜上, 斜下)
				
				// 1. 预判终点：计算当前点往方向k延伸5步后的坐标
				endCol = i + FORWARD[k].x * 5
				endRow = j + FORWARD[k].y * 5
				
				// 2. 合法性检查：判断终点是否还在棋盘内
				active = isValidSquare(endCol, endRow)
				
				// 3. 索引转换：二维坐标转一维
				startIndex = getIndex(i, j)
				
				// 4. 创建路对象：记录起点、方向、初始棋子数(0,0)、是否激活
				road = new Road(startIndex, k, 0, 0, active)
				
				// 5. 存入全量表：无论是否合法都存入 roadsByStartPos
				roadsByStartPos[startIndex][k] = road
				
				// 6. 存入分类表：只有合法的路才加入"0黑0白"的集合中
				if active is true:
					roadSetsByStoneCount[0][0].add(road)
	}