对于极大极小算法。。。实现失败。。。求解

diablox0147

先上菜:

1. Move MinMax_AI::FindBestStep()
   
2. {
   
3.     int maxVal = -99999999;
   
4.     Move bestMove;
   
5.     int tmp=0;
   
6.     char* curStep;
   
7.     int cur;
   
8.     actionInfo info;
   
9.     for(int j=0; j<8 ;j++)
   
10.     {
    
11.         for(int i=0; i<8 ;i++)
    
12.         {
    
13.             if((_board->GetBoardInfo(i,j)^AI_PLAYER) < 0x10)//只控制是自己的棋子就够了。。。
    
14.             {
    
15.                 cur = 0;
    
16.                 info = _board->GetPieceBonusPoints(i,j);//获得棋盘上这个点的所有移动可能
    
17.                 curStep = (char*)&info.moveList;//moveList是short数组，前面8个字是x，后8个字是y
    
18.                     while(info.moveList[cur] != 0)//对所有可以移动的可能
    
19.                     {
    
20.                         _board->MovePieceWithOutCheck(i,j,*curStep,*(curStep+1));//直接无需检查就移动，因为这次移动是通过检查后得到的。
    
21.                         tmp = Min(_depth-1);//轮到对方走了。。。
    
22.                         if(tmp > maxVal)
    
23.                         {
    
24.                             maxVal = tmp;
    
25.                             bestMove.srcPt = MyPOINT(i,j);
    
26.                             bestMove.dstPt = MyPOINT(*curStep,*(curStep+1));
    
27.                         }
    
28.                         _board->MovePieceWithOutCheck(*curStep,*(curStep+1),i,j);//然后把棋子弄回来。
    
29.                         curStep+=2;//继续下个移动
    
30.                         cur++;
    
31.                     }
    
32.             }
    
33.         }
    
34.     }
    
35.     return bestMove;
    
36. }
    
37. 
    
38. int MinMax_AI::Min(int dp)
    
39. {
    
40.     if(dp==0)
    
41.     {
    
42.         //返回棋盘估价，2是代表 AI分-人类分，eval是一个类的实现
    
43.         //把棋盘传过去
    
44.         return _eval.GetVal(_board,2);
    
45.     }
    
46. 
    
47.     int min = 99999999;
    
48.     int tmp=0;
    
49.     char* curStep;
    
50.     int cur;
    
51.     actionInfo info;
    
52. 
    
53.     for(int j=0;j<8;j++)
    
54.     {
    
55.         for(int i=0; i<8; i++)
    
56.         {
    
57.             if((_board->GetBoardInfo(i,j)^HUMAN_PLAYER) < 0x10)//只用模拟人类防。。。
    
58.             {
    
59.                 cur = 0;
    
60.                 info = _board->GetPieceBonusPoints(i,j);
    
61.                 curStep = (char*)&info.moveList;
    
62.                 while(info.moveList[cur] != 0)
    
63.                 {
    
64.                     _board->MovePieceWithOutCheck(i,j,*curStep,*(curStep+1));
    
65.                     tmp = Max(dp-1);
    
66.                     if(tmp < min)
    
67.                     {
    
68.                         min = tmp;
    
69.                     }
    
70.                     _board->MovePieceWithOutCheck(*curStep,*(curStep+1),i,j);
    
71.                     curStep+=2;
    
72.                     cur++;
    
73.                 }
    
74.             }
    
75.         }
    
76.     }
    
77.     return min;
    
78. }
    
79. 
    
80. int MinMax_AI::Max(int dp)
    
81. {
    
82.     if(dp == 0)
    
83.         return _eval.GetVal(_board,2);
    
84. 
    
85.     int max = -99999999;
    
86.     int tmp=0;
    
87.     char* curStep;
    
88.     int cur;
    
89.     actionInfo info;
    
90. 
    
91.     for(int j=0; j<8 ;j++)
    
92.     {
    
93.         for(int i=0; i<8; i++)
    
94.         {
    
95.             if((_board->GetBoardInfo(i,j)^AI_PLAYER) < 0x10)
    
96.             {
    
97.                 cur = 0;
    
98.                 info = _board->GetPieceBonusPoints(i,j);
    
99.                 curStep = (char*)&info.moveList;
    
100.                 while(info.moveList[cur] != 0)
     
101.                 {
     
102.                     _board->MovePieceWithOutCheck(i,j,*curStep,*(curStep+1));
     
103.                     tmp = Min(dp-1);
     
104.                     if(tmp > max)
     
105.                     {
     
106.                         max = tmp;
     
107.                     }
     
108.                     _board->MovePieceWithOutCheck(*curStep,*(curStep+1),i,j);
     
109.                     curStep+=2;
     
110.                     cur++;
     
111.                 }
     
112.             }
     
113.         }
     
114.     }
     
115.     return max;
     
116. }
     

复制代码

对于上面的算法类，不知道为什么。在计算时会改变棋盘的布局，也就是没办法在模拟对战后把布局改回原来的样子。。
我觉得应该是下面这个的问题，因为我不记得除了MovePieceWithOutCheck这个函数外还调用过其他能改变棋盘布局的函数，，。。。

1. _board->MovePieceWithOutCheck(i,j,*curStep,*(curStep+1));
   
2.                     tmp = Min(dp-1);
   
3.                     if(tmp > max)
   
4.                     {
   
5.                         max = tmp;
   
6.                     }
   
7.                     _board->MovePieceWithOutCheck(*curStep,*(curStep+1),i,j);
   

复制代码

这个部分的问题。。。因为移动后的棋子因为深度的原因没有办法很好的回到它自己的原地。。。 [em17]

MovePieceWithOutCheck的实现：

1. void chessboard::MovePieceWithOutCheck(int srcX, int srcY, int dstX, int dstY)
   
2. {
   
3.     if(    _board[srcX][srcY]!=EMPTYPLACE)
   
4.     {
   
5.         _board[dstX][dstY] = _board[srcX][srcY];
   
6.         _board[srcX][srcY] = EMPTYPLACE;
   
7.     }
   
8.     else std::cout<<"!";//如果是错误的移动。。。也就是移动空格子就打印！
   
9. }

复制代码

而在深度为>=3的情况下打印了很多"!!!!!!!!!!!!!!"。。。也就是说很多错误的移动。。。
不知道哪里出问题了 哎 [em4]

luoqi

记得A*中的"权值",与,"父结点"吗,这都是很重要的,否则没有办法回退,就会造成无结果!