基于Qt的爱因斯坦棋游戏设计与实现

王历昊 黄为新 刘灏辰

摘要：近年来，新型棋类游戏层出不穷。爱因斯坦棋作为奥林匹亚电脑游戏程式竞赛指定棋类之一，虽然规则简单，但变化多样，富有趣味，对人工智能算法的探索也有一定的意义。利用C++语言实现爱因斯坦棋，结合Qt平台进行图形用户界面设计，以alpha-beta剪枝法优化博弈树进行决策，最终实现了人机对战功能，为棋类游戏的设计与实现提供了一个新的方式。

关键词：爱因斯坦棋；Qt；图形用户界面；价值估计；博弈

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）07-0095-02

Abstract： In recent years， new chess games have emerged in endlessly. Einstein chess， as one of the designated chess categories in Olympia computer game program competition， although its rules are simple， is still varied and interesting. And it is also meaningful to the exploration of artificial intelligence algorithms. Einstein chess is implemented by C++ language， whose GUI is designed with Qt platform， and game tree is optimized by alpha-beta pruning algorithm for decision-making， so that man-machine game function is finally realized， which provides a new way for the design and implementation of chess games.

Key words： Einstein chess； Qt； GUI； value estimation； game

1 背景

AlphaGo以4：1的战绩战胜围棋大师李世石的新闻再一次引起了人们对棋类博弈的关注。爱因斯坦棋作为近年来新兴的两人骰子棋类游戏，成为电脑游戏程式竞赛的指定棋类之一。它作为一种典型的博弈游戏，能对博弈结果直观反应，测试算法智能程度。

本文利用Qt平台来开发一个爱因斯坦棋游戏，设计时的重点为玩家进行操作的图形化界面和可以对棋局进行价值评估，判断行棋的算法。

2 爱因斯坦棋简介

棋盘大小为5×5，初始布置为将六枚己棋任意摆在棋盘己侧左上角的3*3的三角域。

双方每回合轮流掷骰子，然后选择一枚与骰点同样数字的己棋朝朝下、右、或右下方移动一格至任何棋位，若无同点棋则改为移动最接近该数的己棋之一。当移到任何方棋子，将原位棋子移除棋盘不再使用。以先抵达敌方角落位，或消灭所有敌棋为胜。

3 软件结构设计

本系统主要分为如下三个模块：玩家对棋子的控制模块，电脑对棋子的控制模块，系统的界面设计模块。软件总体框架如图2所示。

4 游戏的具体设计与实现

4.1.1 玩家对棋子的控制

玩家对棋子的控制模块主要包括鼠标事件的发生，玩家在用户界面的操作。鼠标事件的发生是玩家通过鼠标来输入给定的指令，如选取棋子移动，实现吃子等等，这需要在棋子与棋盘两个控件之中传递消息，并更新状态。而Qt中的信号和槽机制[1] ，可以有效解决这个问题。

信号和槽的声明：

private slots：

void changeState（int condition）；

void on_btn_clicked（）；

被选中的棋子发送信号：

if（e->button（）==Qt：：LeftButton）{

point=e->pos（）；

if（condition==0）{

this->setFlat（false）；

condition=1；

emit statechanged（condition）；

return；

}

}

接收信号并处理：

void Widget：：on_btn_clicked（）{

......

}

void Widget：：changeState（int condition）{

......

}

4.1.2 电脑对棋子的控制

电脑对棋子的控制主要依靠动态建立决策树，辅以alpha-beta剪枝法进行优化实现[2]。首先是对棋局的价值评估：评估函数需要考虑电脑方的进攻值，每个棋子对对方终点的威胁程度，故用每个棋子被选中的概率乘上其当前的棋子位置的value值并求和，为[attack=k=05p[k]?value1]；电脑方的防守值，即人方的进攻值，计算方法同上，为[defense=k=611p[k]?value2]。图3为对右下角一方来说，棋子在棋盘每个位置的一种value值。最后某一步走法的value为两数值相减所得结果，即[value=attack-defense]。若value值大于0则对己方有利，反之则不利。其中概率的求法则是用到了简单的搜索和遍历。

之后需要动态建立决策树，树的每一个节点代表某步棋的走法，决策树层数越多，電脑的落子越有威胁，游戏难度越大。

具体来说，双方对弈若干步后，从可能的走法中用极大极小搜索算法选择一步较好的走法。定义电脑方为Max方，玩家为Min方。当轮到Max方行棋时，决策树为极大层，Max方应考虑对自己利益值最大的走法；轮到Min方行棋时，决策树为极小层，Max方应考虑使Min方获得的利益最小。指定一个搜索深度，当达到该深度，或已出现胜负局面时，调用评估函数，返回评估值，通过对上述的两种方式交替递推，得出最终的最优走法。

通常决策搜索树的分支呈指数级增长，即使规定了一定的搜索深度，仍需要大量的计算，采用alpha-beta剪枝法优化后，就可以删去一些不必要的分支，从而加快计算过程。

定义极大层的下界为alpha，极小层的上界为beta，alpha-beta剪枝规则描述如下：

1）alpha剪枝。当搜索至任一极小值层某结点的beta值不大于它任一前驅极大值层结点的alpha值，即alpha（前驱层） [≥]beta（后继层），终止该Min结点以下的搜索。这个Min结点最终的倒推值即为所定义的beta值。

2）beta剪枝。当搜索至任一极大值层某结点的alpha值不小于它任一前驱极小值层结点的beta值，即alpha（后继层） [≤]beta（前驱层）时，终止该Max结点以下的搜索，这个MAX结点最终倒推值即为所定义的alpha值。

通过alpha-beta剪枝，会裁减掉很多不可能的情况，从而提升运算速度。

4.1.3 系统界面设计

在主界面中，玩家可查询游戏规则，选择游戏难度，或者开始人机对战。

在人机对战界面中，玩家可在开局时在己方区域任意摆放棋子，是否先手由游戏系统掷骰子随机决定，玩家每回合都可点击按钮得到骰子点数，根据提示以移动由此决定的棋子。如图4所示。

5 结束语

本游戏软件已经通过测试，基本上达到了本次软件设计开发的预期目的。此次设计开发的难点在于决策树的生成与优化，笔者选择了alpha-beta剪枝法作为优化方式，这虽然是一种传统算法，但已足够满足爱因斯坦棋等较简单棋种的需求。

参考文献：

[1] 仇国巍. Qt图形界面编程入门[M]. 北京： 清华大学出版社， 2017.

[2] 郑培铭， 何丽. 基于计算机博弈的五子棋AI设计[J]. 电脑知识与技术， 2016（33）： 80-81， 90.

【通联编辑：谢媛媛】