1
0

game10_sol.txt 2.0 KB

12345678910111213141516171819202122232425
  1. 空挡接龙可以用搜索解决,这个游戏最大的特点在于:游戏局面的确定性,没有未知因素(比如说在纸牌/蜘蛛纸牌中,你不知道所有牌的位置)。空挡接龙一开始获得的局面是确定的,所有牌的位置都知道。
  2. 搜索的目标:求可行解,因为最优解太变态了。
  3. 状态设计:把该记录的都记录下来,就像这样
  4. struct abb{
  5. short a1[61],a2[61],s[9],st1,st2,low,sp1,sp2;
  6. int step;
  7. }
  8. 牌的信息存在a1,a2两个数组里,a1存数值,a2存花色,游戏界面中,第一列的牌由上到下,对应s[0]+1~s[1],第二列的牌由上到下对应在a1,a2数组里的下标是s[1]+1~s[2]依次类推到第8列。a1,a2数组中下标53~56对应游戏界面左上角4个空挡,57~60对应游戏界面右上角的4个目标位置。sp1为游戏界面左上角的空挡数,sp2记录有多少空的列。low记录游戏界面右上角的4个目标位置上的4张牌中,最小的数字是多少(可以认为每张牌都有数字和花色2种属性),如果没有放牌,认为数字是0,如果low=13游戏成功。其他的step记录移动方案,st1,st2是2个特殊的参数,用于剪枝。
  9. 搜索的精髓在于状态和剪枝。状态也就这样了,关键是剪枝。
  10. 剪枝的目的是尽早搜到结果,所以要减小搜索量
  11. 为了尽早找到结果,采用深度优先搜索。
  12. 重要剪枝的清单如下:
  13. 1. 移动的批量处理。游戏中,有时可以一次移动连续的若干张牌。游戏里面可以移动的牌数和空挡数有关,还和空的列的数目有关。可以设计一个函数f(x,y)=z,意思是对于任意局面,有x个空挡,y个空的列时,最多可以移动连续的z张牌。值得一提的是:游戏里的f函数是错的!正确的是f(x,y)=(x+1)*2^y。这里本质上是青蛙过河的模型。
  14. 2.移动方式的分类。有些移动是可逆的,而另一些不行。同时如果进行了足够多次数的不可逆操作,游戏便成功了。所以在搜索时,要尽量避免可逆操作,具体优化是:先搜索不可逆操作,同时限制移动中的可逆操作的个数,st1,st2就起了这个作用。问题在于限制移动中的可逆操作的个数时,限制得太死,搜不出结果,限制太松,起不了剪枝的作用,于是可以进行迭代加深,逐步放宽限制。
  15. 3.hash判重。判重时,如果主板(就是游戏界面中,上面8个格子以下的部分)完全相同,就认为完全相同。还有,如果是通过可逆操作得到的当前状态,只判重,不更新hash表。
  16. 4.往空档里移牌时的特殊限制。很显然可以将一些牌移到游戏界面左上角的空挡中。我强行规定这种移动方法一定要是不可逆的。如何做到?对于每一列如果有一些牌是连续的,要么不移,要么全部移到空挡里去。
  17. 主要的剪枝就这些了。