Android游戏开发之黑白棋

黑白棋介绍

黑白棋，又叫苹果棋，最早流行于西方国家。游戏通过相互翻转对方的棋子，最后以棋盘上谁的棋子多来判断胜负。黑白棋非常易于上手，但精通则需要考虑许多因素，比如角边这样的特殊位置、稳定度、行动力等。本游戏取名为黑白棋大师，提供了8种难度等级的选择，从菜鸟、新手、入门、棋手到棋士、大师、宗师、棋圣，助你不断提升棋力。

黑白棋游戏规则

游戏规则见黑白棋大师中的截图。

黑白棋大师游戏截图

游戏启动界面。

游戏过程中的一个截图。

开新局时的选项，选择先后手以及ai的水平。

几个关键的类

rule

rule类实现游戏规则相关的方法，包括

    1.判断某一步是否合法

    2.获取所有的合法走步

    3.走一步并翻转敌方棋子

    4.统计两方棋子个数

algorithm

algorithm类实现极小极大算法，包括

    1.局面评估函数，对当前局面打分，越高对max越有利，越低对min越有利

    2.min()方法

    3.max()方法

    4.获得一个好的走步

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> move(byte[][] chessboard, move move, byte chesscolor) {
  int row = move.row;
  int col = move.col;
  int i, j, temp, m, n, dirx, diry;
  list<move> moves = new arraylist<move>();
  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<move> getlegalmoves(byte[][] chessboard, byte chesscolor) {
  list<move> moves = new arraylist<move>();
  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<move> 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 chesscolor, int difficulty) {
  if (depth == 0) {
    return new minimaxresult(evaluate(chessboard, difficulty), null);
  }
  list<move> 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 max(chessboard, depth, alpha, beta, (byte)-chesscolor, difficulty);
  }
  byte[][] tmp = new byte[8][8];
  util.copybinaryarray(chessboard, tmp);
  int best = integer.max_value;
  move move = null;

  for (int i = 0; i < legalmovesme.size(); i++) {
    beta = math.min(best, beta);
    if(alpha >= beta){
      break;
    }
    rule.move(chessboard, legalmovesme.get(i), chesscolor);
    int value = max(chessboard, depth - 1, alpha, math.min(best, beta), (byte)-chesscolor, difficulty).mark;
    if (value < best) {
      best = value;
      move = legalmovesme.get(i);
    }
    util.copybinaryarray(tmp, chessboard);
  }
  return new minimaxresult(best, move);
}

alpha-beta剪枝原理

先解释下alpha和beta的物理含义，alpha表示max节点迄今为止的最佳局面评分，beta表示min节点迄今为止的最佳局面评分。

举个例子见下图（数值为虚构），假设深度是两层，每个结点有两行数字，上方的两个数分别是alpha和beta，表示作为参数传到该层的alpha和beta。下方的数表示了该节点best的更新过程。

看图中第一个红色的叉号，该位置处会更新beta为正无穷和2的较小值，即2，导致alpha大于等于beta成立，发生剪枝，对应于min方法中相应位置处的break操作。

获得ai计算出的最佳走步

该方法用于ai走步以及提示功能。

public static move getgoodmove(byte[][] chessboard, int depth, byte chesscolor, int difficulty) {
    if (chesscolor == constant.black)
      return max(chessboard, depth, integer.min_value, integer.max_value, chesscolor, difficulty).move;
    else
      return min(chessboard, depth, integer.min_value, integer.max_value, chesscolor, difficulty).move;
}

局面评估函数

局面评估函数决定了ai水平的高低。对应于不同的ai等级，设计了不同的评估函数。

菜鸟级别只关注棋子个数，新手、入门、棋手3个级别不仅关注棋子的个数，而且关注特殊位置的棋子（边、角），棋士和大师级别在棋子个数、边角之外还考虑了行动力，即对方下轮可选的下子位置的个数，宗师和棋圣考虑稳定度和行动力。稳定度将在下一小节介绍。

private static int evaluate(byte[][] chessboard, int difficulty) {
    int whiteevaluate = 0;
    int blackevaluate = 0;
    switch (difficulty) {
    case 1:
      for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
          if (chessboard[i][j] == white) {
            whiteevaluate += 1;
          } else if (chessboard[i][j] == black) {
            blackevaluate += 1;
          }
        }
      }
      break;
    case 2:
    case 3:
    case 4:
      for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
          if ((i == 0 || i == 7) && (j == 0 || j == 7)) {
            if (chessboard[i][j] == white) {
              whiteevaluate += 5;
            } else if (chessboard[i][j] == black) {
              blackevaluate += 5;
            }
          } else if (i == 0 || i == 7 || j == 0 || j == 7) {
            if (chessboard[i][j] == white) {
              whiteevaluate += 2;
            } else if (chessboard[i][j] == black) {
              blackevaluate += 2;
            }
          } else {
            if (chessboard[i][j] == white) {
              whiteevaluate += 1;
            } else if (chessboard[i][j] == black) {
              blackevaluate += 1;
            }
          }
        }
      }
      break;
    case 5:
    case 6:
      for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
          if ((i == 0 || i == 7) && (j == 0 || j == 7)) {
            if (chessboard[i][j] == white) {
              whiteevaluate += 5;
            } else if (chessboard[i][j] == black) {
              blackevaluate += 5;
            }
          } else if (i == 0 || i == 7 || j == 0 || j == 7) {
            if (chessboard[i][j] == white) {
              whiteevaluate += 2;
            } else if (chessboard[i][j] == black) {
              blackevaluate += 2;
            }
          } else {
            if (chessboard[i][j] == white) {
              whiteevaluate += 1;
            } else if (chessboard[i][j] == black) {
              blackevaluate += 1;
            }
          }
        }
      }
      blackevaluate = blackevaluate * 2 + rule.getlegalmoves(chessboard, black).size();
      whiteevaluate = whiteevaluate * 2 + rule.getlegalmoves(chessboard, white).size();
      break;
    case 7:
    case 8:
      /**
       * 稳定度
       */
      for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          int weight[] = new int[] { 2, 4, 6, 10, 15 };
          if (chessboard[i][j] == white) {
            whiteevaluate += weight[getstabilizationdegree(chessboard, new move(i, j))];
          } else if (chessboard[i][j] == black) {
            blackevaluate += weight[getstabilizationdegree(chessboard, new move(i, j))];
          }
        }
      }
      /**
       * 行动力
       */
      blackevaluate += rule.getlegalmoves(chessboard, black).size();
      whiteevaluate += rule.getlegalmoves(chessboard, white).size();
      break;
    }
    return blackevaluate - whiteevaluate;
}

稳定度计算

我们知道，在黑白棋中，棋盘四角的位置一旦占据是不可能再被翻转的，因此这几个位置上的子必然是稳定子，而边上的子只有可能沿边的方向被翻转，稳定的程度高于中间的位置上的子。

因此，试图给每个子定义一个稳定度，描述该子不被翻转的稳定程度。

一共有四个方向，即左-右，上-下，左上-右下，右上-左下。举个例子，下面代码中的 (drow[0][0], dcol[0][0])表示向左移动一个单位的向量，(drow[0][1], dcol[0][1])表示向右移动一个单位的向量。

对于棋盘中某个子的位置，向左找到第一个不是该颜色的位置（可以是出界），再向右找到第一个不是该颜色的位置（可以是出界），如果这两个位置至少有一个出界，或者两个均为敌方棋子，稳定度加1。

对于另外三个方向作同样操作。可以看到，角上的棋子的稳定度必然为4，其他位置则根据具体情况并不恒定不变。

private static int getstabilizationdegree(byte[][] chessboard, move move) {
    int chesscolor = chessboard[move.row][move.col];
    int drow[][], dcol[][];
    int row[] = new int[2], col[] = new int[2];
    int degree = 0;

    drow = new int[][] { { 0, 0 }, { -1, 1 }, { -1, 1 }, { 1, -1 } };
    dcol = new int[][] { { -1, 1 }, { 0, 0 }, { -1, 1 }, { -1, 1 } };

    for (int k = 0; k < 4; k++) {
      row[0] = row[1] = move.row;
      col[0] = col[1] = move.col;
      for (int i = 0; i < 2; i++) {
        while (rule.islegal(row[i] + drow[k][i], col[i] + dcol[k][i])
            && chessboard[row[i] + drow[k][i]][col[i] + dcol[k][i]] == chesscolor) {
          row[i] += drow[k][i];
          col[i] += dcol[k][i];
        }
      }
      if (!rule.islegal(row[0] + drow[k][0], col[0] + dcol[k][0])
          || !rule.islegal(row[1] + drow[k][1], col[1] + dcol[k][1])) {
        degree += 1;
      } else if (chessboard[row[0] + drow[k][0]][col[0] + dcol[k][0]] == (-chesscolor)
          && chessboard[row[1] + drow[k][1]][col[1] + dcol[k][1]] == (-chesscolor)) {
        degree += 1;
      }
    }
    return degree;
}

以上就是android黑白棋游戏实现过程及代码解析的全部内容，相信本文对大家开发android黑白棋游戏很有帮助，谢谢大家对的支持。