跳棋ai设计.txt

beyond linux from scratch 6.1, blfs是lfs功能的扩展版

发信人: CityYard (呼呼猫◎要做与时俱进，继往开来的研究生), 信区: Programming
标  题: 跳棋AI设计
发信站: BBS 水木清华站 (Tue Mar  2 12:08:12 2004), 转信

跳棋程序的设计思路：
===================================================

没事做了个跳棋程序，把大概思路和部分代码贴在这里
让大家帮忙看看顺便指点一下。

功能：一人和一个电脑对战，每人10个子，可以任意连跳
      但是只能跳过一个自己或者对方的子，先跳齐为胜
      的一分，可以悔棋一步，可以让电脑先走。

首先生成一个覆盖整个棋盘的矩阵，实时记录期盼的局面
ybvisible=new Array(3,3,3,3,3,3,3,3,3,2,3,3,3,
                     3,3,3,3,3,3,3,3,2,2,3,3,3,
                      3,3,3,3,3,3,3,2,2,2,3,3,3,
                       3,3,3,0,0,0,2,2,2,2,0,0,0,
                        3,3,3,0,0,0,0,0,0,0,0,0,3,
                         3,3,3,0,0,0,0,0,0,0,0,3,3,
                          3,3,3,0,0,0,0,0,0,0,3,3,3,
                           3,3,0,0,0,0,0,0,0,0,3,3,3,
                            3,0,0,0,0,0,0,0,0,0,3,3,3,
                             0,0,0,1,1,1,1,0,0,0,3,3,3,
                              3,3,3,1,1,1,3,3,3,3,3,3,3,
                               3,3,3,1,1,3,3,3,3,3,3,3,3,
                                3,3,3,1,3,3,3,3,3,3,3,3,3);
                                //本数表记录了棋盘的状况
然后生成一个数表规定每一个位置的权重来指导子粒的移动方向
powerfulman=new Array( 0,-1,-1,-1,-1,-1,-1,-1,-1,124,-1,-1,-1,
                       -1,-1,-1,-1,-1,-1,-1,-1,121,121,-1,-1,-1,
                        -1,-1,-1,-1,-1,-1,-1,114,113,114,-1,-1,-1,
                         -1,-1,-1, 0,12,70,106,104,104,106,70,12, 0,
                          -1,-1,-1, 0,72,92,97,99,97,92,72, 0,-1,
                           -1,-1,-1,22,77,87,94,94,87,77,22,-1,-1,
                            -1,-1,-1,60,76,84,87,84,76,60,-1,-1,-1,
                             -1,-1,16,58,70,77,77,70,58,16,-1,-1,-1,
                              -1, 0, 5,54,59,57,59,54, 5, 0,-1,-1,-1,
                                0, 1, 2,44,47,47,44, 2, 1, 0,-1,-1,-1,
                                -1,-1,-1,37,38,37,-1,-1,-1,-1,-1,-1,-1,
                                 -1,-1,-1,20,20,-1,-1,-1,-1,-1,-1,-1,-1,
                                  -1,-1,-1, 0,-1,-1,-1,-1,-1,-1,-1,-1, 0);
                                  //本数表用来规定权重
powerfulcmp=new Arra(169);
for(i=0;i<169;i++)
{
        powerfulcmp[i]=powerfulman[168-i];
}
//人和电脑的权重数表是一样的，只是顺序相反，因为走向是对着的

计算机思考过程：
一、判断当前局面是否符合棋谱走法
若符合，则按照棋谱来走

二、找不到对应的棋谱
        
        1、根据上面的三个数表计算人和电脑当前的权重值   
        
        2、计算当前人与电脑的最长的跳法，所谓的最长跳法是指有效长度最长。
           也就是在ybvisible跨越的实际行数最多，而不是算连跳多少次。
        
        3、对棋盘上每一个电脑的子粒，计算出所有它可能走得到的点
           出于优化的考虑，其中子粒往回跳的直接剪枝不予考虑
        
        4、试走一步，也就是把数表ybvisible的对应位暂时互换一下，但不刷新棋盘
        
        5、计算走了一步之后，计算机和人的最长跳法，算出导致人的最长跳法的变化量dltmanlongjmp
        
                manlongjmpnow=findlongjmp(1);//人现在最长跳法
                cmplongjmpnow=findlongjmp(2);//电脑现在最长跳法
                dltmanlongjmp=manlongjmp-manlongjmpnow;//人最长跳法的变化量
                cmpjmplength=callength(pos,posablepos[num]);//电脑试走的这一步的长度
                
            说明：dltmanlongjmp为正则说明这一步给人“搭了桥”，反之是“堵了路”
                      其数值大小反映了堵路或者搭桥的程度
                  cmpjmplength的数值反映的是当前的这一步能跳多远
                  cmplongjmpnow反映的实际是下一步计算机有可能跳多远
                      这个数值变大说明在为自己“搭桥”
            计算电脑此时的权重值
            计算电脑权重值增加量。
        
        6、计算公式：
                stepscore=cmplongjmpnow*2.1+cmpjmplength*2.7+dltmanlongjmp*3.2;
                其中的2.1，2.7，3.2是可以自己规定或者修改的权重
                他的大小体现了电脑对什么更加偏好，比如上面这个电脑更偏好堵死对手。
                也可以把电脑设定成偏好搭桥（这个比较危险，可能反而给对手搭桥）或者
                偏好速攻（这个也有被对手利用的机会）。
        
        7、从上面的stepscore值当中选出最高的几个，选取的原则是
           设定一个临界stepscore
           
                a、若已存在一个stepscore高于临界值，那么要替代它必须同时满足stepscore的
                数值高于当前的值而且电脑权重的增加两高于这个跳法。
                b、若还没有找到高于临界值的stepscore，那么任何一种跳法只要stepscore高就可以
                进行替换。
        
        8、如果电脑的权重增加量不是正数，那么也暂时把它保存下来，放在badpos中。
           修正上面的公式为
           badstepscore=cmplongjmpnow*4.5+cmpjmplength*1.0+dltmanlongjmp*2.5;
           这是为了万一6、7找不到一种跳法，也就是自己的局面陷入拥堵的状况的解决办法
           这里加大了电脑进攻的权重，电脑更倾向于快速往前冲。
           这里选择的替换原则简单的规定为badstepscore大则替换badpos中的点。
        
        9、如果通过步骤5，6，7能找到至少一种方法，则从找到的几种方法中选择一种，若差别不大
           就随机选择。如果5，6，7都无法找到任何一种满足条件的走法，说明我方子力被堵塞了
           那么只好退而选择8存储的走法了。
           
        10、根据9决定的走法，刷新ybvisible数组合棋盘显示。

对人的合法判断：
        当人走了棋之后。对出发点计算其所有可能到达的点。再看终点是否在其中

悔棋
        用一个数组专门存储每一步的走棋，悔棋任意步都是可以的，但悔过一次棋就设定一个标志位
        禁止不停悔棋。如果是第一步就悔棋则清除后面说的让先标志位，等于重开一局。

让先：
        原来是人走一步触发计算机思考函数，让先后，计算机直接去读取开局的棋谱，走一步之后，后面的
        算法和前面相同。让先后设定标志位，不能在开始游戏后再让先。

对胜利的判断
        如果是人先走，且电脑先完成则电脑胜利，若最后一个回合电脑和人同时完成，则平局，否则人胜利
        若电脑先走，则人先完成人胜利，电脑先完成则再等一回合，若人可以在这一回合完成，平局
        否则人失败。
        
        这个算法好坏的关键和powerfulman，powerfulcmp的取值有关系，和            
        stepscore=cmplongjmpnow*2.1+cmpjmplength*2.7+dltmanlongjmp*3.0
        的系数取值由直接关系。
        本算法没有进行多步的计算。

--

※ 来源:·BBS 水木清华站 smth.org·[FROM: 159.226.224.*]