步步为营-墙棋AI人机对战(Android)

放纵了三天了,之前写了一半懒得去动的墙棋,反而在这几天间隙断断续续完成了,也是挺可笑的。

简介-关于墙棋

路墙棋(Quoridor),或译墙棋、步步为营,是由Mirko Marchesi(米尔科·迈凯西)设计、Gigamic
Games发行的两到四人对战的棋类游戏(桌面游戏),并在1997年被门萨国际评选为门萨推荐的游戏。1998年游戏杂志(Games
Magazine)年度游戏大奖。

先将各棋子放置在棋盘各边的中间格。两人玩时,两子需放在相对侧。
轮到回合的玩家,须作以下两动作之一:
动子:移动至邻边四格之一。若有其他玩家的棋子相邻,则可跳过后者至后方格,但不能一次跳过两子以上的棋子。若跳过的棋子后方为木板,则可以跳至后者左方或右方。棋子
不可穿过墙。
放墙:放木片至沟槽,需正对棋格边,也不可把棋子完全围住以至不能到达对边[2]。在游戏结束前,所有已被放置的木片不能再次移动或拿回。
以本方棋子先抵达对边为胜。
(cp于维基百科)

效果图

这里写图片描述

这里写图片描述

项目结构

GameView 游戏界面绘图部分
GameService 游戏逻辑部分
Robot AI部分
。。。 android项目的部分结构

GameService

游戏逻辑部分主要负责:

  1. 游戏信息:
    如玩家(电脑)的位置坐标,所剩墙的数量,已放墙的位置,游戏是否结束等等。

  2. 游戏规则
    这是比较棘手的一部分,首先来说走棋,有 当对方棋子与自己相邻时、当旁边有墙时等等情况,不同情况下,可走的目标点不同 。所以我实现了一个函数直接
    根据目标位置自身位置、对方位置、棋盘信息来判断走法是否合法 来解决。
    再来说放墙,这个游戏之所以这么吸引人,最大的亮点在于墙,而墙的存在的一个很大的前提是 不能将对方用墙堵死,也就是说放的墙不能令对方无法到达对面
    。所以每次放墙的时候都要进行判断,确定墙放的位置是否合法。这个问题我解决的方案是,
    每次放墙时,先假设墙合法更新棋盘信息,然后使用A*来计算双方棋子到达对面所花的最小步数,若无法到达,则返回-1,即放墙操作不合法

类的结构

public class GameService{

    //玩家棋子位置
    private int playerX;
    private int playerY;
    //电脑棋子位置
    private int robotX;
    private int robotY;
    //玩家墙数量
    public int playerWallCnt;
    //电脑墙数量
    public int robotWallCnt;
    //储存棋盘信息
    public boolean[][] boardA = new boolean[10][10];
    public boolean[][] boardB = new boolean[10][10];
    //标记游戏是否结束及胜方是电脑还是玩家
    public int isEnd;
    //AI
    public Robot robot;

    //判断走棋是否合法
    public boolean isChessMan(int x, int y, int userMeX, int userMeY, int otherX, int otherY) {

    //走棋
    public boolean putChessMan(boolean flag, int x, int y);
    //放墙A
    public boolean putWallA(boolean flag, int x, int y);
    //放墙B
    public boolean putWallB(boolean flag, int x, int y);
    //判断墙是否合法
    public boolean isCanGo();
    //判断玩家是否可以到达终点
    int a_start(boolean flag);

GameView

这一部分是花费时间最多的部分,之前写五子棋时界面显示部分几乎不到一小时就完成了,而这个界面完成的时间是五子棋的好多倍。
原因很简单,五子棋的棋盘绘制时,确定棋盘的左上角,然后根据行列值直接就能确定到在何处绘制棋子。
而墙棋的棋盘中间的空隙要用于放墙,数值就比较繁琐,而且为了 令项目可以根据不同屏幕自适应,所有的数值都是根据屏幕参数按比例动态计算而来
,写的时候很让人烦心。
还有一个难点(对我来说)是放墙的操作,因为要让用户用手指可以将墙拖动到目标位置,在此同时,还要根据拖动的位置模糊匹配相邻的沟槽。因为android方面实在是
半桶水,这部分实现起来还是挺麻烦的。

类的结构

/**
 * Created by shiyi on 16/7/3.
 */
public class GameView extends View {

    //游戏逻辑层
    private GameService gameService;
    //定义画笔
    private Paint paint;
    //屏幕尺寸
    private int screenWidth;
    private int screenHeight;
    //棋盘格子尺寸
    private float d;
    private float e;
    //棋盘绘制起点
    private float startX;
    private float startY;
    //墙体绘制起点
    private float startAX;
    private float startAY;
    private float startBX;
    private float startBY;
    //是否放墙
    private boolean isWallA;
    private boolean isWallB;
    //是否走棋
    private boolean isGo;
    //触摸位置
    private int lastX;
    private int lastY;
    private int wallX;
    private int wallY;
    //触摸坐标
    private float nowX;
    private float nowY;

    //初始化控件坐标以及定义触屏事件监听函数
    public GameView(Context context, AttributeSet attrs);
    //重绘函数
    @Override
    protected void onDraw(Canvas canvas);
    //绘制墙数量信息
    public void drawWallMess(Canvas canvas);
    //绘制棋子
    public void drawChessMan(Canvas canvas, int color, int x, int y);
    //绘制地图中的墙
    public void drawWall(Canvas canvas);
    //绘制横墙
    public void drawWallA(Canvas canvas, int x, int y);
    //绘制竖墙
    public void drawWallB(Canvas canvas, int x, int y);
    //绘制棋盘
    public void drawChess(Canvas canvas);

Robot

本部分只有个alpha_beta剪枝函数,就不贴类结构了

AI部分应该算是人机对战的灵魂所在。
我仍然是使用alpha_beta剪枝搜索加上评估函数来确定走法。
关于alpha_beta剪枝搜索这里不再赘述,有兴趣的可以看这篇文章。 Alpha-Beta搜索
评估函数部分,我只用了简单的A*来求出棋子到达对面所需的最小步数,通过玩家与AI的评估值相减后的结果来作为局面评估值。
事实上这样做并不好,例如,如果一方一味的用墙来围堵对方,那么当它墙用光后且堵的效果并不好的话,几乎已经注定了它会输。
尝试了将剩余墙数联系到评估值中,但是效果并不好。
而且 偶尔会出现AI棋子左右循环移动的情况,调试多次找不出原因,若有知晓原因的人看到,还望不吝告之
能力有限,AI部分实现的效果一般般,只能日后再说了。

小结

因为代码篇幅过多,已上传至git,有兴趣的可以去看。 墙棋AI人机对战app
apk文件还没有进行真机测试,因为之前安装过的问题,可能是卸载不彻底的问题,再安装时总显示替换安装,但又无法替换,因为之前的已经卸载了,总之好乱好乱,等解决
了,再在此处更新链接吧。

如果本文对你有用,可以请作者喝杯茶~
0%