人机博弈-吃子棋游戏（三）走法生成

我们可以根据吃子棋的规则，创建走法生成器，主要的逻辑是，如果己方存在一气的棋串，则可以无需紧对方的气，也就是可以不用贴着对方的棋子落子。其他情况下，必须贴

着对方的棋子落子，考虑到某些特殊情况，当己方能提对方棋子时，己方就可以下到没有气的地方，并且一般的吃子棋，先提子者胜，无法形成劫争。所以走法生成器就相对非

常简单。

对于如何确定己方是不是存在一气的棋串，可以利用上一节介绍的算气算法。

  1 int CMoveGenerator::CreatePossibleMove(BYTE position[GRID_NUM][GRID_NUM], int nPly, int nSide)
  2 {
  3     m_nMoveCount = 0;
  4     
  5     BYTE antiSide = (nSide + 1) % 2;
  6     cleanGlobal();
  7     setGo(position);
  8 
  9     
 10     
 11     //检测己方是否有一气的棋窜，有则输出相应走法。
 12     
 13     for (int i = 0; i < GRID_NUM; i++)
 14     for (int j = 0; j < GRID_NUM; j++){
 15         
 16         if(go[i][j]==nSide&&g_gozi[i][j]==0){
 17            str_lib(i,j,go[i][j]);
 35          
 36            if (goqi==1)
 37                 {
 38                 
 39                 for (int k = 0; k < GRID_NUM; k++)
 40                 for (int w = 0; w < GRID_NUM; w++){
 41 
 42                 if (gokong[k][w] == 1){
 43                 AddMove(k, w, nPly);
 44 
 45                 }
 46 
 47 
 48                 }
 49 
 50                 
 51                 }
 52         
 53         }
 54        
 58     }
 59     64     
 65     //正常情况下，寻找敌方棋子周边的空位，紧其气
 67 
 68             for (int i = 0; i < GRID_NUM; i++)
 69             for (int j = 0; j < GRID_NUM; j++)
 70             {
 71             
 72 
 73             if (go[i][j] == antiSide)
 74             {
 75                 
 76                 if (i > 0 && go[i - 1][j] == NOSTONE){
 77                     
 79                     AddMove(i - 1, j, nPly);
 80                     
 81                     
 82                 }
 83                     
 84                 if (i < GRID_NUM - 1 && go[i + 1][j] == NOSTONE){
 85                   
 87                     AddMove(i + 1, j, nPly);
 88                     
 89                 }
 90                     
 91                 if (j>0 && go[i][j - 1] == NOSTONE){
 92                   
 94                     AddMove(i, j - 1, nPly);
 95                     
 96                     
 97                 }
 98                     
 99                 if (j < GRID_NUM - 1 && go[i][j + 1] == NOSTONE){
100                   
102                     AddMove(i, j + 1, nPly);
103                    
104                 }
105                     
106                 
107             }
108             
109             
110 
111         }
112 
113 
114     
115     return m_nMoveCount;
116 }

可以优化此算法，以后方便后续的搜索引擎进行剪枝。给走法设定一个分数，能够提子则此步设为30+提子数。能够打吃则为20+打吃棋子数（打吃未必是好棋，不这么做了）。能够长气，则为10+长气的棋子数。其他暂时设计为0。可以用一个额定长度的优先队列，保留几个分数最佳的走法。或是必要时进行排序。

搜索时优先优先搜索得分较高的走法，这样大幅度提高搜索算法剪枝的效率。

这段是走法启发的代码

伪码如下：

 1 for(int i=0;i<Grid_Num;i++)
 2 for(int j=0;j<Grid_Num;j++)
 3 {
 4     cleanupGlobal();
 5     if(go[i][j]==NOSTONE)
 6     {
 7     bool isVilid=false;
 8     if(i>0&&go[i-1][j]==antiSide)
 9     {
10 
11        go[i][j]=nSide;
12 
13        if(g_gozi[i-1][j]==0)
14        {
15           isVilid=true;
16           str_lib(i-1,j,antiSide);
17           if(goqi==0){....}
18 
19        }
20 
21     }
22      if(i<Grid_Num-1&&go[i+1][j]==antiSide)
23      {
24 
25 
26        go[i][j]=nSide;
27 
28 
29        if(g_gozi[i-1][j]==0)
30        {
31           isValid=true;
32           str_lib(i-1,j,antiSide);
33           if(goqi==0){....}
34        }
35 
36 
37     }...
38          if(isValid)
39          {
40           sumScore(i,j,nSide);
41           addMove(i,j,nSide);
42           }
43 44 
45 
46 
47     }
48 }
49 std::sort();
   random_shuffle(begin+offset,end);

这个算法是走法启发，学名为静态启发，而不是历史启发，历史启发并不需要棋类的知识属于动态启发，而走法启发则与棋类知识相关联。

现在的思路是，长气和提子的走法绝对的好走法，而把对方打成1气的走法未必是好的走法，要考虑到自身有没有受到攻击，以及我方有人没有薄弱的地方，以及能否征吃。所以我们只需要将吃子的下法，按吃子多少排序即可。这样也可以提高剪枝效率，并且不至于把坏的走法提高的前面。

最近，无意中写出了一个新的功能，由于棋盘的对称性或非对称估值核心返回值碰巧相同，会导致一些走法的分数是相同的，我们的搜索算法会认为分数一样，优先选择排在前面的走法。其实我们应该对分数一直的走法随机的进行选择，这样我们的程序就不会变得死板。那么如何实现呢？我们在生成走法时，将绝对好的走法排在最前面，将看起来差不多的走法乱序一下，这样当返回时，分数一样的走法的排序也是乱序的，由于我们的搜索算法总是选择已经乱序过后的第一个，那么走法也是随机的。