Android游戲開(kāi)發(fā)之黑白棋

更新時(shí)間：2016年08月01日 11:36:41 投稿：daisy

本文主要介紹Android黑白棋游戲?qū)崿F(xiàn)過(guò)程及代碼解析，將著重介紹黑白棋實(shí)現(xiàn)過(guò)程中用到的算法。對(duì)于Android游戲開(kāi)發(fā)很有幫助。

黑白棋介紹

黑白棋，又叫蘋(píng)果棋，最早流行于西方國(guó)家。游戲通過(guò)相互翻轉(zhuǎn)對(duì)方的棋子，最后以棋盤(pán)上誰(shuí)的棋子多來(lái)判斷勝負(fù)。黑白棋非常易于上手，但精通則需要考慮許多因素，比如角邊這樣的特殊位置、穩(wěn)定度、行動(dòng)力等。本游戲取名為黑白棋大師，提供了8種難度等級(jí)的選擇，從菜鳥(niǎo)、新手、入門(mén)、棋手到棋士、大師、宗師、棋圣，助你不斷提升棋力。

黑白棋游戲規(guī)則

游戲規(guī)則見(jiàn)黑白棋大師中的截圖。

黑白棋大師游戲截圖

游戲啟動(dòng)界面。

游戲過(guò)程中的一個(gè)截圖。

開(kāi)新局時(shí)的選項(xiàng)，選擇先后手以及AI的水平。

幾個(gè)關(guān)鍵的類

Rule

Rule類實(shí)現(xiàn)游戲規(guī)則相關(guān)的方法，包括

1.判斷某一步是否合法

2.獲取所有的合法走步

3.走一步并翻轉(zhuǎn)敵方棋子

4.統(tǒng)計(jì)兩方棋子個(gè)數(shù)

Algorithm

Algorithm類實(shí)現(xiàn)極小極大算法，包括

1.局面評(píng)估函數(shù)，對(duì)當(dāng)前局面打分，越高對(duì)max越有利，越低對(duì)min越有利

2.min()方法

3.max()方法

4.獲得一個(gè)好的走步

ReversiView

ReversiView繼承自SurfaceView，實(shí)現(xiàn)棋盤(pán)的界面，在該類定義棋盤(pán)界面的繪制、更新等操作。

RenderThread

RenderThread繼承自Thread，是控制ReversiView以一定fps更新、重繪界面的線程。

具體實(shí)現(xiàn)

棋盤(pán)表示

byte[][]二維數(shù)組存儲(chǔ)棋盤(pán)，-1表示有黑子，1表示有白子，0表示棋格為空

游戲規(guī)則類Rule的實(shí)現(xiàn)

提供幾個(gè)關(guān)于游戲規(guī)則的靜態(tài)方法。

判斷某一個(gè)位置是否位于棋盤(pán)內(nèi)

public static boolean isLegal(int row, int col) {
  return row >= 0 && row < 8 && col >= 0 && col < 8;
}

判斷某一方在某個(gè)位置落子是否合法

即判斷該子是否能與己方棋子在某個(gè)方向上夾住敵方棋子。

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;
}

某一方走一步子

將各個(gè)方向上被翻轉(zhuǎn)的棋子的顏色改變，并返回這些棋子在棋盤(pán)的位置，方便顯示翻轉(zhuǎn)動(dòng)畫(huà)。

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;
}

獲取某一方當(dāng)前全部合法的落子位置

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;
}

統(tǒng)計(jì)玩家和AI的棋子個(gè)數(shù)

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的實(shí)現(xiàn)

極大過(guò)程和極小過(guò)程

這兩個(gè)過(guò)程的函數(shù)形式為：

復(fù)制代碼代碼如下:

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為棋盤(pán)；depth為博弈樹(shù)搜索深度；alpha和beta用于alpha-beta剪枝，在max方法中alpha不斷更新為局面評(píng)分的較大值，在min方法中beta不斷更新為局面評(píng)分的較小值，當(dāng)alpha >= beta時(shí)就進(jìn)行剪枝；chessColor表示棋子顏色；difficulty表示游戲難度，對(duì)應(yīng)于不同的AI水平。

由于黑子先行，黑子總是調(diào)用max()方法，白子調(diào)用min()方法。

下面以極大過(guò)程為例。

如果深度為0，只要返回當(dāng)前局面評(píng)分即可。如果雙方均沒(méi)有步可走，表示已經(jīng)達(dá)到最終局面，返回該局面評(píng)分。如果僅單方無(wú)處可走，調(diào)用min遞歸即可。

正常情況下有步可走，遍歷每個(gè)合法的走步，如果alpha大于等于beta，剪枝直接break，否則走步并遞歸。

best是當(dāng)前max節(jié)點(diǎn)維護(hù)的一個(gè)最佳值，調(diào)用的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節(jié)點(diǎn)迄今為止的最佳局面評(píng)分，beta表示min節(jié)點(diǎn)迄今為止的最佳局面評(píng)分。

舉個(gè)例子見(jiàn)下圖（數(shù)值為虛構(gòu)），假設(shè)深度是兩層，每個(gè)結(jié)點(diǎn)有兩行數(shù)字，上方的兩個(gè)數(shù)分別是alpha和beta，表示作為參數(shù)傳到該層的alpha和beta。下方的數(shù)表示了該節(jié)點(diǎn)best的更新過(guò)程。

看圖中第一個(gè)紅色的叉號(hào)，該位置處會(huì)更新beta為正無(wú)窮和2的較小值，即2，導(dǎo)致alpha大于等于beta成立，發(fā)生剪枝，對(duì)應(yīng)于min方法中相應(yīng)位置處的break操作。

獲得AI計(jì)算出的最佳走步

該方法用于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;
}

局面評(píng)估函數(shù)

局面評(píng)估函數(shù)決定了AI水平的高低。對(duì)應(yīng)于不同的AI等級(jí)，設(shè)計(jì)了不同的評(píng)估函數(shù)。

菜鳥(niǎo)級(jí)別只關(guān)注棋子個(gè)數(shù)，新手、入門(mén)、棋手3個(gè)級(jí)別不僅關(guān)注棋子的個(gè)數(shù)，而且關(guān)注特殊位置的棋子（邊、角），棋士和大師級(jí)別在棋子個(gè)數(shù)、邊角之外還考慮了行動(dòng)力，即對(duì)方下輪可選的下子位置的個(gè)數(shù)，宗師和棋圣考慮穩(wěn)定度和行動(dòng)力。穩(wěn)定度將在下一小節(jié)介紹。

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:
      /**
       * 穩(wěn)定度
       */
      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))];
          }
        }
      }
      /**
       * 行動(dòng)力
       */
      blackEvaluate += Rule.getLegalMoves(chessBoard, BLACK).size();
      whiteEvaluate += Rule.getLegalMoves(chessBoard, WHITE).size();
      break;
    }
    return blackEvaluate - whiteEvaluate;
}

穩(wěn)定度計(jì)算

我們知道，在黑白棋中，棋盤(pán)四角的位置一旦占據(jù)是不可能再被翻轉(zhuǎn)的，因此這幾個(gè)位置上的子必然是穩(wěn)定子，而邊上的子只有可能沿邊的方向被翻轉(zhuǎn)，穩(wěn)定的程度高于中間的位置上的子。

因此，試圖給每個(gè)子定義一個(gè)穩(wěn)定度，描述該子不被翻轉(zhuǎn)的穩(wěn)定程度。

一共有四個(gè)方向，即左-右，上-下，左上-右下，右上-左下。舉個(gè)例子，下面代碼中的 (drow[0][0], dcol[0][0])表示向左移動(dòng)一個(gè)單位的向量，(drow[0][1], dcol[0][1])表示向右移動(dòng)一個(gè)單位的向量。

對(duì)于棋盤(pán)中某個(gè)子的位置，向左找到第一個(gè)不是該顏色的位置（可以是出界），再向右找到第一個(gè)不是該顏色的位置（可以是出界），如果這兩個(gè)位置至少有一個(gè)出界，或者兩個(gè)均為敵方棋子，穩(wěn)定度加1。

對(duì)于另外三個(gè)方向作同樣操作?？梢钥吹?，角上的棋子的穩(wěn)定度必然為4，其他位置則根據(jù)具體情況并不恒定不變。

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黑白棋游戲?qū)崿F(xiàn)過(guò)程及代碼解析的全部?jī)?nèi)容，相信本文對(duì)大家開(kāi)發(fā)Android黑白棋游戲很有幫助，謝謝大家對(duì)腳本之家的支持。

您可能感興趣的文章: