这是一个全新的系列--隔三岔五聊算法。这个系列充满不确定性,什么时间更新全靠自己的心情,今天的文章也有能是最后一篇,内容方面会用通俗易懂的方式聊一下自己学过的算法。
最近学校的课程设计自己做了个五子棋的游戏,今天就聊一聊五子棋游戏中用到的极小极大算法(The Minimax Algorithm)。
Minimax算法又名极小化极大算法,是一种找出失败的最大可能性中的最小值的算法。Minimax算法常用于棋类等由两方较量的游戏和程序,这类程序由两个游戏者轮流,每次执行一个步骤。我们众所周知的五子棋、象棋等都属于这类程序,所以说Minimax算法是基于搜索的博弈算法的基础。该算法是一种零总和算法,即一方要在可选的选项中选择将其优势最大化的选择,而另一方则选择令对手优势最小化的方法。
基本思路:
一般解决博弈类问题的自然想法是将格局组织成一棵树,树的每一个节点表示一种格局,而父子关系表示由父格局经过一步可以到达子格局。Minimax也不例外,它通过对以当前格局为根的格局树搜索来确定下一步的选择。而一切格局树搜索算法的核心都是对每个格局价值的评价。Minimax算法基于以下朴素思想确定格局价值:
说白了,这个算法就是一个树形结构的递归算法,每个节点的孩子和父节点都是对方玩家,所有的节点被分为极大值节点和极小值节点。
代码演示:
function minimax(node, depth)
if node is a terminal node or depth = 0
return the heuristic value of node
if the adversary is to play at node
let α := +∞
foreach child of node
α := min(α, minimax(child, depth-1))
else {we are to play at node}
let α := -∞
foreach child of node
α := max(α, minimax(child, depth-1))
return α
上述代码depth是最多预测层数限制,函数递归有两个出口,一是到达层数限制即depth 为 0,二是已经递归到叶子节点,在游戏中体现为“死棋“或者有一方已经确定胜利获失败
图解算法:
假设我们有如下图的游戏,我是先手,我应该如何利用Minmax算法来选出第一步怎么走呢?
这个时候我们就要从结果看起,也就是第4步。图中标注第四步是我的对手下的,所以他要做的是最小化这个分数,于是对手根据结果可以反推出如下选择
继续从后往前看到第3步,当我们知道了对手的选择以后,我们可以根据对手的结果反推出自己的选择,我们要做的是最大化这个分数,如图
重复这个步骤,我们最终可以发现第一步的最优选择,如图
以上就是极小极大算法(Minimax)。
这只是一个简单的案例,对于一个复杂的游戏来说,比如五子棋,肯定是需要非常多步才能完成的。因为minimax的算法是树形结构,不断地向下拓展该树会导致计算量的倍数增加(多少倍取决于所剩可选的当前支孩子节点的数量),也就是说,如果这个游戏每一步都有n个选择,那么在x步以后,将会有n^x个选择。当选择多的时候,就需要采取剪枝算法(Alpha-Beta)来减少运算量。从剪枝算法这个名字我们就能看出,这个算法能让我们剪掉树状图中的一些分支,从而减少运算量
【参考资料】
http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html
http://web.cs.ucla.edu/~rosen/161/notes/minimax.html
http://blog.codinglabs.org/articles/2048-ai-analysis.html
我是小王,
如果有下一篇的话,
我们下一篇再见。
完