Android 黑白棋游戏实现

黑白棋

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

黑白棋游戏规则

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

2

黑白棋大师游戏截图

游戏启动界面。

1

游戏过程中的一个截图。

3

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

4

几个关键的类

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的实现

提供几个关于游戏规则的静态方法。

判断某一个位置是否位于棋盘内

判断某一方在某个位置落子是否合法

即判断该子是否能与己方棋子在某个方向上夹住敌方棋子。

某一方走一步子

将各个方向上被翻转的棋子的颜色改变,并返回这些棋子在棋盘的位置,方便显示翻转动画。

获取某一方当前全部合法的落子位置

统计玩家和AI的棋子个数

游戏算法类Algorithm的实现

极大过程和极小过程

这两个过程的函数形式为:

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的较大值。

alpha-beta剪枝原理

先解释下alpha和beta的物理含义,alpha表示max节点迄今为止的最佳局面评分,beta表示min节点迄今为止的最佳局面评分。
举个例子见下图(数值为虚构),假设深度是两层,每个结点有两行数字,上方的两个数分别是alpha和beta,表示作为参数传到该层的alpha和beta。下方的数表示了该节点best的更新过程。

alpha

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

获得AI计算出的最佳走步

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

局面评估函数

局面评估函数决定了AI水平的高低。对应于不同的AI等级,设计了不同的评估函数。
菜鸟级别只关注棋子个数,新手、入门、棋手3个级别不仅关注棋子的个数,而且关注特殊位置的棋子(边、角),棋士和大师级别在棋子个数、边角之外还考虑了行动力,即对方下轮可选的下子位置的个数,宗师和棋圣考虑稳定度和行动力。稳定度将在下一小节介绍。

稳定度计算

我们知道,在黑白棋中,棋盘四角的位置一旦占据是不可能再被翻转的,因此这几个位置上的子必然是稳定子,而边上的子只有可能沿边的方向被翻转,稳定的程度高于中间的位置上的子。
因此,试图给每个子定义一个稳定度,描述该子不被翻转的稳定程度。
一共有四个方向,即左-右,上-下,左上-右下,右上-左下。举个例子,下面代码中的 (drow[0][0], dcol[0][0])表示向左移动一个单位的向量,(drow[0][1], dcol[0][1])表示向右移动一个单位的向量。
对于棋盘中某个子的位置,向左找到第一个不是该颜色的位置(可以是出界),再向右找到第一个不是该颜色的位置(可以是出界),如果这两个位置至少有一个出界,或者两个均为敌方棋子,稳定度加1。
对于另外三个方向作同样操作。可以看到,角上的棋子的稳定度必然为4,其他位置则根据具体情况并不恒定不变。

项目开源

完整项目已经开源到github上。
github项目主页: Reversi

1 1 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部