在线玩游戏:here

github:here

本文适合对于对极大极小值有一些理解,单不明白具体实现的人阅读。

女朋友的人工智能作业要求实现一个井字棋,前段时间我一边膜拜一边看完了女朋友班里大神的C++代码,但是无奈自己C++并不行,于是我决定用js重新实现一遍。刚刚做完,把我对算法的理解写在这里。

井字棋的核心是极大极小值算法,正是这个算法帮助电脑找到了所有对人最有利的走法中对人对不利的那个(我觉得这句话这么说会好理解一些,网上很多说的并不很好理解)。

极大极小值算法在井字棋中是这么驱使AI工作的:

AI:这一步我下在A点。

AI:如果我下在了A点,那么人类可能会下在a点,当人类下在a点的时候,对人类的有利程度是这个值。

AI:人类还可能下在b点,此时对人类的有利程度是这个值,和上一步的比比,我保留对人类比较有利的那个值。

AI:我记下了当我下在A点的时候,人类下在哪一点对人类最有利,以及多么有利。

AI:我再下在B点试试……

……重复一遍以上过程

AI:我记下了如果我下在B点,人类下在哪一点对人类最有利,以及多么有利,我对比一下和我下在A点的时候,保留对人类比较不利的那个。

……重复以上过程

AI:我把棋盘上所有能下棋的点都尝试完了,记下了这样的一个点:我下在这里,人类无论怎样下,都不会对人类太有利。

AI:下棋。

(如果AI在上面的过程中发现下在某一点直接会赢,那么他会放弃所有判断,直接下在那里)

注意上文的加粗字体。

这是我对AI的思考方式的理解,接下来就是代码实现了,在聊实现思路之前,我们需要明确这样一点:对人类不利就是对AI有利,这是等价的。我为什么要这样说明,因为我曾经困在了这样的困境中,我认为AI要做两件事,第一件事考虑怎样防守:找到对人类最不利的,第二件事是考虑怎样进攻:怎样布局进攻,然后取舍一下,后来我知道井字棋的AI其实没有这么智能。

首先:我们需要量化“有利”,不然你不可能比较这样走和那样走谁更有利,怎样量化呢?井字棋中,AI是这样计算的:

AI将目前的棋盘复制一份,然后将所有空白位置都填上AI的棋子,这样看看AI横着竖着斜着一共有多少根三子连线,然后再将当前棋盘重新复制,所有的位置都填上人类的棋子,看看人类横着竖着斜着有多少根三子连线。上面得到的两个值做差,差越小,表示对AI越有利,反之则对人类越有利。

可见这种量化方式是井字棋独有的,如果象棋就不是简单的三子连珠,想必会复杂得多。

然后,我们还需要对有利程度进行记录。设定两个变量,max和min,max表示对AI最有利(对人类最不利,我刚刚说了,这两种说法是等价的)的值,max越大,对AI越有利。min则相反,他表示对AI最不利(对人类最有利)的值,min越小,对人类越有利。也就是说,人类追求min越小越好,AI追求max越大越好。

将max的初始值设为-999,他会在计算中选取最大值并覆盖自己。将min初始值设为999,他会在一波计算中选取最小值并覆盖自己,AI为什么要计算min的最小值,min越小对人类越有利,AI要知己知彼。

这个函数还有一个参数,参数的名称叫做“深度”,这个参数会告诉函数要模拟多少次,在井字棋中,我们模拟了两次,即模拟AI下一次,然后在AI下在这里的情况在,模拟人类下一次。你可以模拟更多次,但是可以想象,计算次数会随着模拟次数的增多呈指数增长。(好像在入门级象棋对战中,AI模拟2次,而专家级象棋对战中则是5次)

我觉得知识要点基本讲全了,其中的精髓就是极大极小算法的:下在所有对你有利的位置中对你最不利的那个位置,简直冷血。