象棋和五子棋的AI开发（四）
相较于象棋，五子棋的走法相当简单，也就是空白的地方都可以走。但五子棋的棋局判断，也就是估值函数比较复杂。另外，在一开始的时候，五子棋的可走步数是254、252、250，而象棋基本都是40多，所以五子棋每一层的运算量都会更大。后面我们会说到一些五子棋的优化方法。
4.1 估值核心
这是五子棋AI算法里面最复杂的一部分。五子棋的得分是基于线的，这些线可以是横的、竖的，也可以是斜的。为了计算方便，我们一开始就初始化了所有的这些线：
-
internal class Position
-
{
-
public Position(int r, int c)
-
{
-
row = r;
-
col = c;
-
}
-
-
public int row;
-
public int col;
-
}
-
-
internal class Line
-
{
-
public Line()
-
{
-
line = new List<Position>();
-
score白 = 0;
-
score黑 = 0;
-
}
-
-
public List<Position> line;
-
public int score白;
-
public int score黑;
-
}
-
-
LineList = new List<Line>();
-
//横
-
for (int i = 0; i < Row; i++)
-
{
-
Line l = new Line();
-
LineList.Add(l);
-
for (int j = 0; j < Col; j++)
-
{
-
l.line.Add(new Position(i, j));
-
}
-
}
-
//竖
-
for (int i = 0; i < Col; i++)
-
{
-
Line l = new Line();
-
LineList.Add(l);
-
for (int j = 0; j < Row; j++)
-
{
-
l.line.Add(new Position(j, i));
-
}
-
}
-
//右斜
-
for (int i = Row - 1; i >= 1 - Col; i--)
-
{
-
Line l = new Line();
-
LineList.Add(l);
-
-
int r = i >= 0 ? i : 0;
-
int c = i < 0 ? -i : 0;
-
while (r < Row && c < Col)
-
{
-
l.line.Add(new Position(r, c));
-
-
r++;
-
c++;
-
}
-
}
-
//左斜
-
for (int i = 0; i <= Row + Col - 2; i++)
-
{
-
Line l = new Line();
-
LineList.Add(l);
-
-
int r = i < Col ? 0 : i - Col + 1;
-
int c = i >= Col ? Col - 1 : i;
-
while (r < Row && c >= 0)
-
{
-
l.line.Add(new Position(r, c));
-
-
r++;
-
c--;
-
}
-
}
这样处理的话，我们后面寻找一行有多少个子不需要再分几种情况去处理了。
然后我们需要做的，就是分析一条线上，各种子排成的序列，应该值多少分。我们用_代表空，用O代表白子，用X代表黑子，如果一行是这样______XXOO____OXO___OOOX___XOOX__，那白子应该是多少分，黑子又是多少分呢？
我考虑了几种方案，有必要在这里说一下思路。一开始，我想统计出有多少种XOOO、_OOO、XOOOO、_OOOO这样的模式，累加作为分数。但我马上发现，如果是OOO__和OOO_O，或是OOO__O，或是OOO_X，它们的分值应该都是不一样的吧。
由于把不同颜色的棋子混在一起考虑比较复杂，我想先扫描一次整个串，然后分成同一颜色的段（空白属于所有颜色）。例如一开始的例子可以这样分：______XX、OO____O、X、O___OOO、X___X、OO、X__。这样对于每一段的分析就会简单一些。我考虑一个这样的问题：如果整个串是O_OOO_OOO，那应该怎么切分呢？是O_OOO + _OOO？还是O_O + OOO_OOO？我认为这里涉及到一个动态规划的问题。就是一个串，按不同的切分方法，能得到的最高分的组合。但是这样算下来的话，每一行需要的计算时间都会很长。我只能考虑使用贪婪算法。也就是说，先挑出最高分的序列，然后在剩下的序列里找出最高分的序列，直到剩下序列分数为0。
对于每一种序列，我对他们的分数安排是这样的：
计算一条线分数的核心代码如下：
-
private void CalcLineScore(Line l)
-
{
-
Chess pre_chess = new Chess(ChessColor.无, ChessType.有);
-
List<bool> list = new List<bool>();
-
List<bool> last_space = new List<bool>();
-
int list_type = 0;
-
-
int score白 = 0;
-
int score黑 = 0;
-
for (int j = 0; j < l.line.Count; j++)
-
{
-
Position p = l.line[j];
-
Chess c = board[p.row, p.col];
-
if (c.type == ChessType.空)
-
{
-
list.Add(false);
-
last_space.Add(false);
-
}
-
else
-
{
-
if (pre_chess.color == ChessColor.无)
-
{
-
list.Add(true);
-
list_type = (c.color == ChessColor.白 ? 1 : 2);
-
pre_chess = c;
-
}
-
else if (c.color == pre_chess.color)
-
{
-
list.Add(true);
-
}
-
else
-
{
-
if (list_type != 0)
-
{
-
int value = GetSequenceValue(list);
-
if (list_type == 1)
-
{
-
score白 += value;
-
}
-
else
-
{
-
score黑 += value;
-
}
-
}
-
-
list.Clear();
-
list.AddRange(last_space);
-
list.Add(true);
-
list_type = (c.color == ChessColor.白 ? 1 : 2);
-
pre_chess = c;
-
}
-
-
last_space.Clear();
-
}
-
}
-
-
if (list_type != 0)
-
{
-
int value = GetSequenceValue(list);
-
if (list_type == 1)
-
{
-
score白 += value;
-
}
-
else
-
{
-
score黑 += value;
-
}
-
}
-
-
l.score白 = score白;
-
l.score黑 = score黑;
-
}
4.2 终局判断
五子棋的终局判断并不简单，需要把所有线都扫描一遍。因为终局判断调用频率极高，它的性能对于整个算法的性能影响是很大的。其实，终局只会由最终下棋所在的线决定，我们只需要计算四条线就可以了！
-
public override bool GameOver(Put[] pre_steps)
-
{
-
if (pre_steps == null)
-
{
-
return false;
-
}
-
-
Put step = pre_steps[pre_steps.Length - 1];
-
ChessColor c = board[step.ToRow, step.ToCol].color;
-
-
int num = 1;
-
int row = step.ToRow;
-
int col = step.ToCol;
-
while (row > 0)
-
{
-
row--;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
row = step.ToRow;
-
while (row < Row - 1)
-
{
-
row++;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
-
num = 1;
-
row = step.ToRow;
-
col = step.ToCol;
-
while (col > 0)
-
{
-
col--;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
col = step.ToCol;
-
while (col < Col - 1)
-
{
-
col++;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
-
num = 1;
-
row = step.ToRow;
-
col = step.ToCol;
-
while (row > 0 && col > 0)
-
{
-
row--;
-
col--;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
row = step.ToRow;
-
col = step.ToCol;
-
while (row < Row - 1 && col < Col - 1)
-
{
-
row++;
-
col++;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
-
num = 1;
-
row = step.ToRow;
-
col = step.ToCol;
-
while (row > 0 && col < Col - 1)
-
{
-
row--;
-
col++;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
row = step.ToRow;
-
col = step.ToCol;
-
while (row < Row - 1 && col > 0)
-
{
-
row++;
-
col--;
-
if (board[row, col].type != ChessType.空 && board[row, col].color == c)
-
{
-
num++;
-
if (num >= 5)
-
{
-
wincolor = c;
-
return true;
-
}
-
}
-
else
-
{
-
break;
-
}
-
}
-
-
return false;
-
}
4.3 每层搜索数量的优化
五子棋一般使用15*15的棋盘，也就是说有225个格子。一开始，每一层的搜索数量是224、222、220，即使使用了历史启发，搜索的数量还是相当巨大。
其实我们可以用一个最小矩形来优化。假如敌方第一步把棋子下在了中心(7,7)，那最优的下法会出现在哪里呢？一般就是在这棋子的四周。假如我们把所有棋子都圈在一个矩形里面，然后适当考虑一个阈值（这里我们定的是3），在这个阈值之外的棋子根本就不需要考虑。这样我们的计算速度能得到极大的提高。例如在只有一个棋(7,7)的情况下，我们的最小矩形是(L7,R7,T7,B7)，加上阈值，就是(L4,R10,T4,B10)，这样需要考虑的棋子只有48颗！
经过测试，使用最小矩形，算法速度能提高10倍以上。