五子棋AI 算法——极大极小搜索

1. // player = 1 表示轮到己方， player = 0 表示轮到对方  
2. // cur_node 表示当前局面(结点)  
3. maxmin(player, cur_node)  
4. {  
5.     if 达到终结局面  
6.         return 该局面结点的估价值 f  
7.     end  
8.     if player == 1 // 轮到己方走  
9.         best = -oo // 己方估价值初始化为 -oo  
10.         for 每一种走法 do  
11.             new_node = get_next(cur_node) // 遍历当前局面 cur_node 的所有子局面  
12.             val = maxmin(player^1, new_node); // 把新产生的局面交给对方，对方返回一个该局面的估价值  
13.             if val > best  
14.                 best = val;  
15.             end  
16.         end  
17.         return best;  
18.     else // 轮到对方走  
19.         best = +oo // 对方估价值初始化为 +oo  
20.         for 每一种走法 do  
21.             new_node = get_next(cur_node) // 遍历当前局面 cur_node 的所有子局面  
22.             val = maxmin(player^1, new_node); // 把新产生的局面交给对方，对方返回一个该局面的估价值  
23.             if val < >
24.                 best = val;  
25.             end  
26.         end  
27.         return best;  
28.     end  
29. }  

1. // player = 1 表示轮到己方， player = 0 表示轮到对方  
2. // cur_node 表示当前局面(结点)  
3. maxmin(player, cur_node, alpha, beta)  
4. {  
5.     if 达到终结局面  
6.         return 该局面结点的估价值 f  
7.     end  
8.     if player == 1 // 轮到己方走  
9.         for 每一种走法 do  
10.             new_node = get_next(cur_node) // 遍历当前局面 cur_node 的所有子局面  
11.             val = maxmin(player^1, new_node, alpha, beta); // 把新产生的局面交给对方，对方返回一个新局面的估价值  
12.             if val > alpha  
13.                 alpha = val;  
14.             end  
15.             if alpha > beta  
16.                 return alpha;  
17.             end  
18.         end  
19.         return alpha;  
20.     else // 轮到对方走  
21.         for 每一种走法 do  
22.             new_node = get_next(cur_node) // 遍历当前局面 cur_node 的所有子局面  
23.             val = maxmin(player^1, new_node, alpha, beta); // 把新产生的局面交给对方，对方返回一个新局面的估价值  
24.             if val < >
25.                 beta = val;  
26.             end  
27.             if alpha > beta  
28.                 return beta;  
29.             end  
30.         end  
31.         return beta;  
32.     end  
33. } 

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览35128 人正在系统学习中