小项目|【c语言五子棋】简单ai算法（理论）人工智能|算法|c语言

学习参考

五子棋对弈的相关算法：
博弈树
极大极小值搜索
α ─ β 剪枝（Alpha-Beta剪枝）
渴望搜索算法
估价函数（估值函数）
静态估值函数（不做介绍，详细可看参考文献）
威胁空间搜索（不做介绍，详细可看参考文献）
基于哈希表的置换表搜索（不做介绍，详细可看参考文献）
??????计算机五子棋博奕系统的研究与实现 - 中国知网 (cnki.net)
(20条消息) 博弈基础——极大极小搜索_大田二十-CSDN博客_博弈搜索
我们知道，显然（业余无复杂规则）五子棋属于零和博弈，非公平博弈，完备信息博弈

将堆栈用第三维数组改进

一、博弈树
1.为什么要使用博弈树计算棋局
计算机要选择有利于它的最佳下法，就要能判断哪种形势对它最有利·但往往对
一个形势的判断是很难做到准确的，特别是一盘棋刚开始的时候，棋盘的形势不明
朗，即使是专家也不能做出准确的判断。为了判断哪种下法最有利，我们往往需要
向后面计算几步，看看在走了几步棋之后，局面的形势如何。这被称为“多算胜”，
也就是说，谁看得越深远，谁就可以获胜。这种思维方式被用到了计算机上。前面
我们说过，棋局的不断向后计算，形成一棵博弈树，“多算胜”的思想即是对博弈树
的搜索过程，这就是博弈树的极小极大搜索算法。

二、极大极小值搜索-博弈树的深度优先搜索
假设：A和Ｂ对弈，轮到Ａ走棋了，那么我们会遍历A的每一个可能走棋方法，然后对于前面A的每一个走棋方法，遍历B的每一个走棋方法，然后接着遍历A的每一个走棋方法，如此下去，直到得到确定的结果或者达到了搜索深度的限制。当达到了搜索深度限制，此时无法判断结局如何，一般都是根据当前局面的形式，给出一个得分，计算得分的方法被称为评价函数，不同游戏的评价函数差别很大，需要很好的设计。
在搜索树中，表示A走棋的节点即为极大节点，表示B走棋的节点为极小节点。
如下图：A为极大节点，B为极小节点。称A为极大节点，是因为A会选择局面评分最大的一个走棋方法，称B为极小节点，是因为B会选择局面评分最小的一个走棋方法，这里的局面评分都是相对于A来说的。这样做就是假设A和B都会选择在有限的搜索深度内，得到的最好的走棋方法。

文章图片

int MinMax(int depth) { // 函数的评估都是以白方的角度来评估的　if (SideToMove() == WHITE) {　// 白方是“最大”者 return Max(depth); 　} else {// 黑方是“最小”者 return Min(depth); 　} } int Max(int depth) { 　int best = -INFINITY; 　if (depth <= 0) { return Evaluate(); 　} 　GenerateLegalMoves(); 　while (MovesLeft()) { MakeNextMove(); val = Min(depth - 1); UnmakeMove(); if (val > best) { best = val; } 　} 　return best; } int Min(int depth) { 　int best = INFINITY; 　// 注意这里不同于“最大”算法　if (depth <= 0) { return Evaluate(); 　} 　GenerateLegalMoves(); 　while (MovesLeft()) { MakeNextMove(); val = Max(depth - 1); UnmakeMove(); if (val < best) {// 注意这里不同于“最大”算法 best = val; } 　} 　return best; }

三、α ─ β 剪枝算法
举例来说，考虑下面的例子：

文章图片

图-alpha-beta搜索
极小极大搜索是一个深度搜索，当搜索到第二层的第二个绿色的节点时，已知其第一个子节点返回值为2，因为这是一个极小节点，那么这个节点得到的值肯定是小于2的，而第二层的第一个绿色节点的值为7，因此这个节点后面即使都搜索了，也不会超过2，更不会超过7，因此这个节点后面的节点可以忽略，即图中第三册没有数字的节点。这属于Alpha剪枝，可能是剪掉的节点是极大节点的原因吧。相应的也有Beta剪枝，图中忽略了。
下面的维基百科伪代码，其中两个值，α表示搜索到的最好的值，β表示搜索到的最坏的值。

function alphabeta(node, depth, α, β, Player) ifdepth = 0 or node is a terminal node return the heuristic value of node ifPlayer = MaxPlayer // 极大节点 for each child of node // 极小节点 α := max(α, alphabeta(child, depth-1, α, β, not(Player) )) if β ≤ α // 该极大节点的值>=α>=β，该极大节点后面的搜索到的值肯定会大于β，因此不会被其上层的极小节点所选用了。对于根节点，β为正无穷 break(* Beta cut-off *) return α else // 极小节点 for each child of node // 极大节点 β := min(β, alphabeta(child, depth-1, α, β, not(Player) )) // 极小节点 if β ≤ α // 该极大节点的值<=β<=α，该极小节点后面的搜索到的值肯定会小于α，因此不会被其上层的极大节点所选用了。对于根节点，α为负无穷 break(* Alpha cut-off *) return β (* Initial call *) alphabeta(origin, depth, -infinity, +infinity, MaxPlayer)

【小项目|【c语言五子棋】简单ai算法（理论）】