基于回溯算法的接龙游戏自动实现

基于回溯算法的接龙游戏的自动实现

[摘要] 接龙游戏是一种在民间广泛流传的棋牌类游戏。因其益智性和娱乐性，深受群众所喜爱。本文介绍了一直回溯算法，可以快速计算出一种在得分最大情况下的接龙排列。该算法为接龙游戏移植到互联网游戏平台提供了理论研究基础。 [关键字] 回溯，牌九，接龙，棋牌游戏

一、引言

1．接龙游戏介绍

接龙游戏是使用牌九牌进行娱乐的一种棋牌类游戏。因为其玩法简单，娱乐性强，有具有益智性，所以在民间广泛流传。随着互联网技术的不断发展，大多数棋牌游戏已经被搬上了网络游戏平台，比如大家所熟知的斗地主、麻将等游戏。但是至今，本文所介绍的接龙游戏还未在各大网络游戏平台出现。所以本文的研究内容将可以为接龙游戏移植到互联网游戏平台提供相关的理论研究基础。

下面开始介绍接龙游戏的玩法和规则。

牌九，又称骨牌。牌九每副为32张，用骨头、象牙、竹子或乌木制成，每张呈长方体，正面分别刻着以不同方式排列的由2到12的点子。牌九起源于中国，在民间流传较广，属于娱乐消遣用具。牌九一般为4个人玩，玩法多种，变化也较多。 一副完整的牌九牌一共分21类牌， 每张牌都标有不同的点数，且有各自的名称。每张牌又分为上下两个点数图形部分，如图(一)所示。比如图(一)中的“鹅”牌，上部为1点，下部为3点。

图(一)

接龙游戏是牌九一种的玩法。首先，随机分配给每位玩家图(一)中的8张牌，然后玩家把其中的6张牌或7张牌按牌的上下部图形首尾相接连成一个排列，其中点数图形部分相同才可以连接，最后取剩余的1或2张牌为得分牌，再与其他玩家比较大小。如图（二）中为一个已经完成的接龙排列。

图(二)

在传统玩法中，计算得分的规则是：取最后的得分牌，若得分牌为一对（即两张牌都一样)，则总比非一对的牌大，然后比较各类对牌之间的大小；若牌不为一对， 则计算剩余两张牌的点数和并取10的模，也可以是剩余一张牌的点数，点数大的则判为赢；另外，也有可能是8张牌中的任意6张都不能连接成一串，则判为最小。所以，玩家总是希望在能够连接成6张牌得情况下，使得剩余的两张牌为最大的对牌。当无法取得对牌时，就交换牌的连接次序，使得最后剩余牌的得分尽可能大。

2．回溯算法介绍

如果使用计算机呈现来模拟实现上述游戏规则，并使得最后的得分牌尽可能大，则比人工计算要方便很多。

我们首先想到的是使用枚举法来完成上面的任务，即遍历每一种可以使得6或7张牌连接成一串的情况，然后根据剩余的得分牌计算出得分，与前一次计算结果进行比较，保留最大得分那种情况。所以，我们可以使用回溯算法来完成。

回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。其基本思想是，从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤：

1) 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。 2) 确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。

3) 以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

二、接龙游戏的自动实现算法

编写通过计算机自动接龙的算法的一个难点是：每一张牌都包括前后两个点数图形部分，调转左右两部，又成为一种新的情况。

所以在具体实现过程中，我们对回溯算法进行一些修改。下面介绍该算法的主要思想。为了便于调试和图形化表示，该算法使用javasctipt 脚本语言实现,其流程图见图(三)。

图(三)

首先定义牌的数据结构：

function Node(name, left, right, value){

this.name = name; //名称，用于标记不同类型的牌 this.left = left; //左部点数 this.right = right; //右部点数 this.value = left + right; //牌的点数

this.flag = 0; //flag 为1时，调转牌; }

//对象复制函数

Node.prototype.copy = function(){

node = new Node(this.name, this.left,this.right,this.value); node.flag = this.flag; return node; }

另外，本算法主要由计算最大解函数calucateMax，判断是否可以连接函数canput和回溯算法解决问题函数solve 三个函数主成。

calucateMax函数在连接过程中只剩余两张牌的时候进行调用，分两种情况进行判断是否当前情况为最大解：

1) 根据游戏规则，判断两张牌是否为对牌或计算两牌模10后的得分，与之前的结果进行比较，判断此时是否是最大解；

2) 若不是对牌，则判断其中的一张牌是否还可以与当前接龙队列想连接，若可以，则计算剩余的另一张牌是否为最大解。

其实现函数为：

function calucateMax(){ //剩余两个

var n1 = input_nodes[0]; //获取剩余的第一张牌 var n2 = input_nodes[1]; //获取剩余的第二张牌 var v1 = n1.value; var v2 = n2.value;

/*判断对牌并比较部分已省略*/ var totalValue = (v1+v2); if(totalValue >= max){ max = totalValue;

result = copyArrayNodes(input_nodes); solution = copyArrayNodes(tmp_solution); }

//最右部点数

var rightValue = updateLeftValue(tmp_solution); var node = input_nodes[0];

//其中剩余的一张牌可以与原接龙队列相连接情况

if(canput(node, rightValue) && input_nodes[1].value>=max){ max = input_nodes[1].value; result =[];

result.push(input_nodes[1].copy());

solution = copyArrayNodes(tmp_solution); solution.push(node.copy()); }

node = input_nodes[1];

if(canput(node, rightValue) && input_nodes[0].value>=max){ max = input_nodes[0].value; result =[];

result.push(input_nodes[0].copy());

solution = copyArrayNodes(tmp_solution); solution.push(node.copy()); } }

canput函数的思想比较简单且已经在游戏规则中给出，所以该函数程序省略。最后，主要来看通过回溯算法解决问题的函数solve函数。

//popNodeName用来标记上一轮中已经被舍弃的牌名称 function solve(popNodeName){

if(tmp_solution.length == len-2){

}

//在最后剩余两张牌时，计算是不是当前的最大解 calucateMax(); }else{

//更新最右部点数

var n = updateLeftValue(tmp_solution); //找到可以插入的牌 var findNode = null;

for(i=0; i

if(node.name == popNodeName[j]){ recomputed = 1; break; } }

if(recomputed ==0 && canput(node, n)){ tmp_solution.push(node); input_nodes.splice(i,1); findNode = node; break; } }

if(null != findNode){ //继续放下一张牌 solve();

//弹出前一张牌

if(tmp_solution.length>0){

if(tmp_solution.length==1 && tmp_solution[0].flag ==0){ //若是第一张牌，则调换牌，使左右点数互换 tmp_solution[0].flag =1; solve(); }

var node = tmp_solution.pop(); node.flag = 0;

input_nodes.push(node);

popNodeName.push(node.name); solve(popNodeName); } } }

该回溯算法的关键是在最后剩余牌数只有两张的情况下，进入计算最大解函数calucateMax。当遇到一张牌不能继续连接下去时，把该张牌的名字保存在popNodeName数组中，表示在下次回溯计算时不再考虑到popNodeName数组中的牌，然后向上回溯。如果回溯到的是接龙队列的首张牌时，则需要调转这一张牌并重新计算，通过牌数据结构中的flag字段进行标记是否已经调转。

三、实验及结果

本实验程序通过javascript编写，并通过相关web技术在网页中进行演示。如图 （四）所示，为初始界面。

图（四）

只要把所展示的牌依次拖入下方虚线小框中，然后点击自己接龙，就可以计算出一个最大解。为了便于测试，也可以先点击随机取牌，随机分配八张牌到虚线小框中进行计算。计算结果，如图（五）所示。

图（五）

四、总结

牌九类游戏是民间广泛流传的一种棋牌类游戏，若可以把更多的此类游戏移植到各种互联网游戏平台，其带来的潜在商业价值将无法估量。本文使用回溯算法进行自动接龙为此游戏的移植提供了游戏机器人算法的理论研究基础。

另外，本实验程序基于脚本语言javascript实现，尚存在许多可以优化的地方。

参考文献：

1.科曼等。算法导论[M] 机械工业出版社 2006

本文来源：https://www.bwwdw.com/article/snqg.html