用游戏串起程序员的基本功（四）
2004-03-23■作者：潇潇■出处： YESKY
对于麻将牌的玩法来说,重要的就是要有吃、碰、杠、胡等四种功能.呢么再游戏中怎样编码实现呢?
吃牌,就是比较对方打出的牌,和自家的牌是否可以连成一串.而碰牌就是比较对方打出的牌和自家的牌是否有2张相同的.如果有三种牌和对方打出的牌相同,就可以杠.胡牌则是至少要有一对相同的牌,除此之外,也可以有三张三张的相同的牌或连成串的牌.
所以这里我们仅以谈谈胡牌的实现.
对于吃、碰、杠、胡，我们可以分解为，查找两张连续的牌，查找两张相同的牌，查找三张相同的牌 ，对于胡牌，还要确定有且只能有一对相同的牌，其他的可以是三种相同的牌，或三张连续的牌。可见在此查找是算法的关键。
我们先来看一下有关查找的知识。
第一种查找的方法叫“线性查找法”，是从数据中的第一个数值开始查找比较，如果找到就返回该值或该值所在的位置。
示例如下：
13 25 16 23 57 66 为一个整型数组。
如果要在这样一个数组中找到57，
步骤1：得到第一个数13，不相等，取得下一个数
步骤2：得到第二个数25，不相等，取得下一个数
步骤3：得到第三个数16，不相等，取得下一个数
步骤4：得到第三个数23，不相等，取得下一个数
步骤5：得到第三个数57，相等，返回所在位置5
代码如下：
int chazhao(int key)//用线性查找法 ,key表示要查找的数值
{
int i=0; //指示在数组中的位置
while(i<14) // 直到结尾
{
if (key==apai[i]) //如果找到，
return i; //返回所在位置
i++; //没找到，继续向后搜索
}
return -1; //没找，返回失败
}
可以看到这种方法，不管数据是否有顺序，也不管数据的多少，都是按顺序挨个的搜索，直到找到或搜索完成，当数据很多时,尤其是要查找的数据排的比较靠后,就会很费时间。所以，对于已经排好顺序的数据，如果还用线性查找法来查找的话，一定是很浪费时间的。有什么好的方法呢？
大家一定都查过英语词典吧，当你要查一个以S开头的单词时，缺先翻到了P开头的一页，我们一定会继续向后翻，而不必再查前面的页码。所以，我们可以用“折半查找法”。它的原理是：先用欲查找的数值和该组数据的中间位置上的数值比较，当小于中间值时，再向前查询，大于中间值时向后查询，继续取前面（或后面）一半数据的中间值进行比较，如果小于再向前查询，大于就向后查询，一直到找到或查询完毕为止。
示例如下：
5 7 12 25 34 37 43 46 58 //是要查找的数据段，其中要查找46，
步骤一：中间值34<46,向后查找
步骤二：得到后半部分的中间值43<46,再向后查找
步骤三: 得到剩余部分的中间值46,返回
可见,这种方法明显的减少了比较的次数.
下面是源代码:
void chaxun(int key)//用折半查询法,key表示要查询的数值
{
int left=o; //待查询数据段的左边界
int right=12; //待查询数据段的右边界
int mid; //待查询数据段的中间值
while(left<=right) //只要没查询完
{
mid=(right+left)/2; //取得待查询数据段的中间值
if(key<apai[mid]) //中间值大于待查询的数值
right=mid-1; //再查找前半段
else if (key>apai[mid]) //中间值小于待查询的数值
left=mid+1; //再查找后半段
else if(key= = apai[mid]) //中间值等于待查询的数值
return mid; //返回位置
}//end while
return –1;
}//end
查询数据是数据结构中的又一重要知识,再实际应用中也很重要,如果有兴趣可在深入的研究.我们只能到此为止.
回过头来,我们再来看一看,这样判断吃,碰,杠,胡.在此我们只以万牌为例.
下面是数和牌对应关系:
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
一 二 三 四 五 六 七 八 九 （万） 东
很明显同一张牌是再小于40的数据段中,并且个位相同的数.并且它还对应着牌上的数.
所以判断是否为同一张牌的方法,我们可以这样写:
tempa=apai[i]%10;
tempb=apai[i+1]%10;
if(tempa==tempb)
// 因为我们是排好序的,所以同类牌中相邻的牌不是相同,就是相近(注意这种牌和数得对应关系,在排序时,一定要以各位为准,而不是以实际的数值大小)
判断是否可碰,则可以这样:
tempa=apai[i]%10;
tempb=apai[i+1]%10;
tempc=apai[i+2]%10;
if(tempa==tempb && tempb==tempc)
判断是否可杠,可以这样:
tempa=apai[i]%10;
tempb=apai[i+1]%10;
tempc=apai[i+2]%10;
tempd=apai[i+3]%10;
if(tempa==tempb && tempb==tempc && tempc==tempd)
是否为顺,则可以这样判断:
tempa=apai[i]%10;
tempb=apai[i+1]%10;
tempc=apai[i+2]%10;
if(tempa==tempb+1 && tempb==tempc+1)
很简单吧,相信你应该也会判断对方出的牌,自己是否可以碰,杠,吃了吧.在此我们就多罗嗦了.
胡牌稍麻烦些,要判断各种副牌的方式,这里我们一起看看一条龙的胡法.
下面是源程序:
void yitiaolong ()
{ int wan,bing,tiao;//wan,bing,tiao 分别代表三种牌
int temp;
for(int I=0;I<13;I++)
{
temp=apai[I];
if(0<temp<40)
wan++;
if(40<temp<80)
bing++;
if(80<temp<120)
tiao++;
if(wan=8)//万牌一条龙
for(int I=1;I<9;I++) //比较这8张牌
if(apai[i]=api[I+1]) //是否後一张等于前一张
if (chaxun(I)==-1))//这里我省略了对11-19以及21-29的比较
//找到所缺的牌
if (I=duifangchupai)比较是否和对家大的牌相等
……..//胡了
if(wan=9)
……….
}
if(bing>=8)
…..//饼牌一条龙
if(tiao>=8)
…… //条牌的一条龙
}
}
由于篇幅所限以及文章的重点不在于此,这仅给出一个框架,聪明的读者,可以发挥自己的才智,将他补充完整.
下面我们简单谈一下人工智能,毕竟我们再游戏中还需要一个对手.
作为程序员,我们不可能做出一个具有高超智慧的对手,而且我们也不可能将游戏中种种可能的打牌方法都写入程序.那么就需要一种可操作的方法,是你的对少不至于太傻.
对于给策略性的游戏添加人工智能主要有这么几步:
(1) 要找出所有获胜的可能性
(2) 建立获胜表,
(3) 每一步的玩法给出一个恰当的评价分值,其中包括给对手制造的麻烦所得的分,和给自己带来的获胜机会所带来的分
(4) 根据所给的分值,确定其中所有可能的玩法中,分值最高的一种玩法,也就是最好的一步走法.
具体到麻将游戏下面是具体的分析:
假设a1,a2,... an 是手上当前牌序列,其中包括吃 碰 杠后的牌,
步骤1: 计算 玩家 离胡牌还有几步. 如果 玩家 已经听牌, 它离胡牌的步数是 1, 如果是一上一听, 步数是 2, 以此类推;
步骤2: 如果步数是 m , 计算所有能使 玩家 到达胡牌的序列也就是所有胡牌的可能玩法 {b11,b12,....b1m}, {b21,b22,...b2m}, ....,{bt1,bt2,....,btm}
步骤3: 对于每个一个 {bt1,bt2,...,btm}, 计算胡牌的点数, 以及到达胡牌时要打出去的牌: {ci1,ci2,....,cim}
步骤4: 对于每一个 {bt1,bt2,...,btm} 计算胡牌的点数;
步骤5: 选取收益最大的方案 {bji,bj2,....bjm}
步骤6: 从{cj1,cj2,....cjm} 中按照跟熟原则打一张
动动脑筋相信你会做出更智能化的得对手。
