(点击
上方公众号，可快速关注)
来源：zhikaizhang
链接：http://zhikaizhang.cn/2016/07/29/android黑白棋游戏实现/
黑白棋
黑白棋，又叫苹果棋，最早流行于西方国家。游戏通过相互翻转对方的棋子，最后以棋盘上谁的棋子多来判断胜负。黑白棋非常易于上手，但精通则需要考虑许多因素，比如角边这样的特殊位置、稳定度、行动力等。本游戏取名为黑白棋大师，提供了8种难度等级的选择，从菜鸟、新手、入门、棋手到棋士、大师、宗师、棋圣，助你不断提升棋力。
本文将着重介绍黑白棋实现过程中用到的算法。
黑白棋游戏规则
游戏规则见黑白棋大师中的截图。
![]()
黑白棋大师游戏截图
游戏启动界面。
![]()
游戏过程中的一个截图。
![]()
开新局时的选项，选择先后手以及AI的水平。
![]()
几个关键的类
Rule
Rule类实现游戏规则相关的方法，包括
判断某一步是否合法
获取所有的合法走步
走一步并翻转敌方棋子
统计两方棋子个数
Algorithm
Algorithm类实现极小极大算法，包括
局面评估函数，对当前局面打分，越高对max越有利，越低对min越有利
min()方法
max()方法
获得一个好的走步
ReversiView
ReversiView继承自SurfaceView，实现棋盘的界面，在该类定义棋盘界面的绘制、更新等操作。
RenderThread
RenderThread继承自Thread，是控制ReversiView以一定fps更新、重绘界面的线程。
具体实现
棋盘表示
byte[][]二维数组存储棋盘，-1表示有黑子，1表示有白子，0表示棋格为空
游戏规则类Rule的实现
提供几个关于游戏规则的静态方法。
判断某一个位置是否位于棋盘内
public static boolean isLegal(int row, int col) {
return row >= 0 && row 8 && col >= 0 && col 8;
}
判断某一方在某个位置落子是否合法
即判断该子是否能与己方棋子在某个方向上夹住敌方棋子。
public static boolean isLegalMove(byte[][] chessBoard, Move move, byte
chessColor) {
int i, j, dirx, diry, row = move.row, col = move.col;
if (!isLegal(row, col) || chessBoard[row][col] != Constant.NULL)
return false;
for (dirx = -1; dirx 2; dirx++) {
for
(diry = -1; diry 2; diry++) {
if (dirx == 0 && diry == 0) continue;
int x = col + dirx, y = row + diry;
if (isLegal(y, x) && chessBoard[y][x] == (-chessColor)) {
for (i = row + diry * 2,
j = col + dirx * 2; isLegal(i, j); i += diry, j += dirx) {
if (chessBoard[i][j] == (-chessColor)) {
continue;
} else if (chessBoard[i][j] == chessColor) {
return true;
} else {
break;
}
}
}
}
}
return false;
}
某一方走一步子
将各个方向上被翻转的棋子的颜色改变，并返回这些棋子在棋盘的位置，方便显示翻转动画。
public static List move(byte[][] chessBoard, Move move, byte chessColor) {
int row = move.row;
int col = move.col;
int i, j, temp, m, n, dirx, diry;
List
moves = new ArrayList();
for (dirx = -1; dirx 2; dirx++) {
for (diry = -1; diry 2; diry++) {
if (dirx == 0 && diry == 0)
continue;
temp = 0;
int x = col + dirx, y = row + diry;
if
(isLegal(y, x) && chessBoard[y][x] == (-chessColor)) {
temp++;
for (i = row + diry * 2, j = col + dirx * 2; isLegal(i, j); i += diry, j += dirx) {
if (chessBoard[i][j] == (-chessColor))
{
temp++;
continue;
} else if (chessBoard[i][j] == chessColor) {
for (m = row + diry, n = col + dirx; m row + temp && m >= row - temp && n col + temp
&& n >= col - temp; m += diry, n += dirx) {
chessBoard[m][n] = chessColor;
moves.add(new Move(m, n));
}
break;
} else
break;
}
}
}
}
chessBoard[row][col] = chessColor;
return moves;
}
获取某一方当前全部合法的落子位置
public static List getLegalMoves(byte[][] chessBoard, byte chessColor) {
List
moves = new ArrayList();
Move move = null;
for (int row = 0; row 8; row++) {
for (int col = 0; col 8; col++) {
move = new Move(row, col);
if (Rule.isLegalMove(chessBoard, move, chessColor))
{
moves.add(move);
}
}
}
return moves;
}
统计玩家和AI的棋子个数
public static Statistic analyse(byte[][] chessBoard, byte playerColor) {
int PLAYER = 0;
int AI = 0;
for (int i = 0; i 8; i++) {
for (int j = 0; j
8; j++) {
if (chessBoard[i][j] == playerColor)
PLAYER += 1;
else if (chessBoard[i][j] == (byte)-playerColor)
AI += 1;
}
}
return new Statistic(PLAYER, AI);
}
游戏算法类Algorithm的实现
极大过程和极小过程
这两个过程的函数形式为：
private static MinimaxResult max(byte[][] chessBoard, int depth
, int alpha, int beta, byte chessColor, int difficulty);
private static MinimaxResult min(byte[][] chessBoard, int depth, int alpha, int beta, byte chessColor, int difficulty);
chessBoard为棋盘；depth为博弈树搜索深度；alpha和beta用于alpha-beta剪枝，在max方法中alpha不断更新为局面评分的较大值，在min方法中beta不断更新为局面评分的较小值，当alpha >= beta时就进行剪枝；chessColor表示棋子颜色；difficulty表示游戏难度，对应于不同的AI水平。
由于黑子先行，黑子总是调用max()方法，白子调用min()方法。
下面以极大过程为例。
如果深度为0，只要返回当前局面评分即可。如果双方均没有步可走，表示已经达到最终局面，返回该局面评分。如果仅单方无处可走，调用min递归即可。
正常情况下有步可走，遍历每个合法的走步，如果alpha大于等于beta，剪枝直接break，否则走步并递归。
best是当前max节点维护的一个最佳值，调用的min方法的alpha是取得alpha和best的较大值。
private static MinimaxResult max(byte[][] chessBoard, int depth, int alpha, int beta, byte chessColor,
int difficulty) {
if (depth == 0) {
return new MinimaxResult(evaluate(chessBoard, difficulty), null);
}
List legalMovesMe = Rule.getLegalMoves(chessBoard, chessColor);
if (legalMovesMe.size() == 0) {
if (Rule.getLegalMoves(chessBoard, (byte)-chessColor).size() == 0
) {
return new MinimaxResult(evaluate(chessBoard, difficulty), null);
}
return min(chessBoard, depth, alpha, beta, (byte)-chessColor, difficulty);
}
byte[][] tmp = new byte[8][8];
Util.copyBinaryArray(chessBoard, tmp);
int best = Integer.MIN_VALUE;
Move move = null;
for (int i = 0; i legalMovesMe.size(); i++) {
alpha = Math.max(best, alpha);
if(alpha >= beta){
break;
}
Rule.move(chessBoard, legalMovesMe.get(i), chessColor);
int value = min(chessBoard, depth -
1, Math.max(best, alpha), beta, (byte)-chessColor, difficulty).mark;
if (value > best) {
best = value;
move = legalMovesMe.get(i);
}
Util.copyBinaryArray(tmp, chessBoard);
}
return new MinimaxResult(best, move);
}
private static MinimaxResult min(byte[][] chessBoard, int depth, int alpha, int beta, byte
