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黑白棋游戏很有帮助,谢谢大家对我们的支持。

(0)

相关推荐

  • Android游戏开发 自定义手势--输入法手势技术

    进行软件开发时,通常我们都喜欢使用较新版本的工具,但这里我为什么使用低版本的SDK来开发Android游戏呢?这里介绍下原因: 1.Android SDK 属于向下兼容!那么低版本可以运行的,高版本基本上更是没问题!(当然每次SDK的更新也会带来新功能,或者修改了一些原来的BUG等等,那么其实对于游戏开发来说,如果你的游戏中不需要更高的SDK版本的支持情况下,完全不必去追求最新的SDK!) 2.使用低版本进行游戏开发这样能兼顾更多的机型,获取更多的用户! 3.大家都知道Android SDK 每

  • Android 游戏开发入门简单示例

    在Android系统上开发游戏是Android开发学习者所向往的,有成就感也有乐趣,还能取得经济上的报酬.那怎样开发Android游戏呢?下面介绍一个简单的入门实例.        一.创建新工程 首先,我们在Eclipse中新建一个名为Movement的工程,并且选择合适的Android SDK,在这里,我们选用的API是比较低的1.5版本,这样可以让其适应性更强.接下来,我们新建两个类,一个是UpdateThread类,一个是SurfaceView类,它们在项目中分别是负责处理线程和画面的两

  • Android 重力传感器在游戏开发中的应用

    手势操作可以说是智能手机的一种魅力所在,前两节给大家讲解了两种有趣的手势操作,将它们置于游戏当中,大大提升了游戏的可玩性和趣味性.本节将继续介绍智能手机的另一种神奇之处:传感器.    一.何为传感器 所谓传感器就是能够探测如光.热.温度.重力.方向等等的装置.    二.Android提供了哪些传感器 1.加速度传感器(重力传感器) 2.陀螺仪传感器 3.光传感器 4.恒定磁场传感器 5.方向传感器 6.恒定的压力传感器 7.接近传感器 8.温度传感器 今天我们给大家介绍的是游戏开发中最最常见

  • Android游戏开发:实现手势操作切换图片的实例

    对于Android 的手势不光在软件中会经常用到,比如浏览器中的翻页,滚动页面等等;当然其实在我们开发Android游戏的时候加上了Android手势操作更会让游戏增加一个亮点,比如一般的CAG.PUZ等类型的游戏选择关卡.简单背景的移动等,都可以使用手势来操作即可,类似前段时间很火的<愤怒的小鸟>,小鸟这个游戏确实不错,我所看到的唯一的亮点是这款游戏的创意!说实话,现在的游戏没有做不出来的只有想不出来的好创意.回到话题来,那么下面我们来了解下什么是Android 手势!        手势识

  • Android游戏开发学习②焰火绽放效果实现方法

    本文实例讲述了Android游戏开发学习②焰火绽放效果实现方法.分享给大家供大家参考.具体如下: 本节介绍在游戏开发中常用到的数学物理应用--粒子系统.粒子系统与上一节的小球有类似的地方,都是通过数学方法和物理公式模拟客观世界中的物体的运动轨迹.不同的是小球更强调个体运动,而焰火粒子等粒子系统更注重整体感觉. 一.焰火粒子效果 1.粒子对象类Particle类和粒子集合类ParticleSet类 每个粒子都为一个Particle类的对象,程序中产生的所有Particle对象都由一个Particl

  • Android游戏开发学习之引擎用法实例详解

    本文实例讲述了Android游戏开发学习之引擎用法.分享给大家供大家参考.具体如下: 汽车引擎是汽车的心脏,其决定了汽车的性能和稳定性,是人们在购车时相当关注的.而游戏中的物理引擎就如汽车的引擎一样,占据了非常重要的位置.一款好的物理引擎可以非常真实地模拟现实世界,使得游戏更加逼真,提供更好的娱乐体验. 一.JBox2D简介 JBox2D是开源物理引擎Box2D的Java版本,可以直接用于Android.由于JBox2D的图形渲染使用的是Processing库,因此在Android平台上使用JB

  • Android 游戏开发之Canvas画布的介绍及方法

    Canvas,在英语中,这个单词的意思是帆布.在Android中,则把Canvas当做画布,只要我们借助设置好的画笔(Paint类)就可以在画布上绘制我们想要的任何东西:另外它也是显示位图(Bitmap类)的核心类.随用户的喜好,Canvas还可设置一些关于画布的属性,比如,画布的颜色.尺寸等.Canvas提供了如下一些方法:    Canvas(): 创建一个空的画布,可以使用setBitmap()方法来设置绘制具体的画布.    Canvas(Bitmap bitmap): 以bitmap对

  • Android游戏开发学习①弹跳小球实现方法

    本文实例讲述了Android游戏开发学习①弹跳小球实现方法.分享给大家供大家参考.具体如下: 在学习了一点点Android之后,觉得有必要记录下来,于是就开了这个新坑,慢慢来填吧. 1.运动体Movable类 本例主要模拟了一组大小不一的球以一定的水平初速度从高处落下的运动轨迹.其中的小球为一个可移动物体Movable对象,该类中除了包含小球图片对象之外,还包括了如位置坐标.水平速度.垂直速度等一系列用于模拟小球运动的成员变量和一些方法. Movable类: package com.ball;

  • 安卓(Android)游戏开发音效代码

    游戏音效就是我们在玩游戏时出现的音乐,这个也是每个游戏必备的一部分,但有是你做游戏的背景音乐有间断的感觉的话,我们可以用getCurrentPosition()这个方法来判断一下声音播放的偏移.其实这个也是非常简单的.只要我们在代码当中设置好(初始化声音)和(加载音效资源)就可以了,别的就和音乐播放器的代码差不多,像开始,停止.不多说了,我们还是先来看看代码当中是怎么实现音效的吧: 1.音效的音量 int streamVolume; //定义SoundPool 对象 private SoundP

  • Android游戏开发实践之人物移动地图的平滑滚动处理

    如图所示为程序效果动画图 地图滚动的原理 在本人之前博客的文章中介绍过人物在屏幕中的移动方式,因为之前拼的游戏地图是完全填充整个手机屏幕的,所以无需处理地图的平滑滚动.这篇文章我着重的向 大家介绍一下控制人物移动后地图滚动的处理方式.举个例子 如上图所示 比如人物向右移动,如果地图贴在屏幕左边边界 将先移动人物在地图的坐标,当人物在屏幕中超过三分之二后 则将地图向人物行走的反方向移动给玩家一种人物还在向右移动的假象,其实这时候人物只是播放向右行走的动画 在屏幕中的坐标不变 ,当地图向人物行走反方

随机推荐