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