Android黑白棋游戏实现过程及代码解析

澳门新葡亰3522平台游戏 4

黑白棋

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

本文将着重介绍黑白棋实现过程中用到的算法。

对博弈树的理解 简单而言就是对每一步可能的结果进行分析
之后对当前步骤的下一步的所有可能结果进行分析而创建的树

黑白棋游戏规则

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

澳门新葡亰3522平台游戏 1

专业表示极大极小博弈树:极大极小博弈树是因描绘这种结构的一种简单算法而得名。我们来对ttt游戏的结果分配一下分值。如果叉(X)获胜,则分值为1。如果圈(O)获胜,则分值为-1。现在,叉将试图获得最大化的分值,而圈将试图最小化分值。于是,第一位研究此问题的研究者决定把游戏者叉命名为max,并且把游戏者圈命名为min。因此,这个完整的数据结构就被命名为极大(Max)极小(Min)博弈树。

黑白棋大师游戏截图

游戏启动界面。

澳门新葡亰3522平台游戏 2

游戏过程中的一个截图。

澳门新葡亰3522平台游戏 3

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

澳门新葡亰3522平台游戏 4

例如:澳门新葡亰3522平台游戏 5

几个关键的类

对于博弈树的创立过程需要对于任意种可能结果设定权重:例如黑白棋中设立以下几种权重“

Rule

Rule类实现游戏规则相关的方法,包括

  1. 判断某一步是否合法
  2. 获取所有的合法走步
  3. 走一步并翻转敌方棋子
  4. 统计两方棋子个数

连三 100分

Algorithm

澳门新葡亰3522平台游戏,Algorithm类实现极小极大算法,包括

  1. 局面评估函数,对当前局面打分,越高对max越有利,越低对min越有利
  2. min()方法
  3. max()方法
  4. 获得一个好的走步

双连二 50分

ReversiView

ReversiView继承自SurfaceView,实现棋盘的界面,在该类定义棋盘界面的绘制、更新等操作。

平局 0分

RenderThread

RenderThread继承自Thread,是控制ReversiView以一定fps更新、重绘界面的线程。

不分胜负 1

具体实现

其中如果评分时不分胜负则还会继续搜索,直到找到其他三种状态、

棋盘表示

byte[][]二维数组存储棋盘,-1表示有黑子,1表示有白子,0表示棋格为空

利用博弈树时,由于结果可能很多 所以需要进行必要剪枝,算法思路如下:

游戏规则类Rule的实现

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

  1. min电脑AI下棋时,如果考虑步数为0,则代表直接返回当前棋盘估值w(值越大代表对max越有优势,越小则代表对min越有优势,w=maxW-minW)。

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

public static boolean isLegal(int row, int col) {
    return row >= 0 && row < 8 && col >= 0 && col < 8;
}
  1. 如果考虑步数为N,先获取min电脑可以下棋的位置steps。

  2. 对于可以下棋的一步step,电脑AI下棋到step的第row行,第column列。

  3. 如果这时候min电脑已经赢了,则把棋盘回退一步,返回棋盘估值和下棋位置,不用再考虑其他走法了。

  4. 否则,min需要在每一种走法里面,选择一种走法,令max人类走N-1步之后,自己的优势保持最大(即w值最小)。

  5. 什么是alpha-beta剪枝呢?就是如果max人类当前一种走法1至少可以获取alpha优势,而另一种走法2,min电脑的一步棋则可能让人类获取比alpha更小的优势,那么max人类肯定不会选择走法2,所以计算在计算min电脑的走法时,min电脑的其他走法就不用再计算了。

  6. 最后min电脑经过steps.length种走法对比之后,选择w值最小的一种走法,把棋盘回退一步,并返回棋盘估值和下棋位置。

  7. max走法类似,人类会选择w值最大的走法下棋,所以max函数和min函数分别代表人和AI下棋,互相递归调用,直到递归到步数为0时返回N步之后的估值。