博弈这类游戏来讲,计算机的特点决定了它在解空间中寻找答案的能力比人类更强。今天不讲阿尔法狗,而是了解一种通过博弈树来实现下棋程序的算法。

一盘棋子从第一步到结束整个过程可以看作是一个庞大的树,每下一步都可以看成为树又向下推进了一层。因为针对敌方的走棋,我方的选择有非常多应对的策略,每一个选择都可以看成这一层的若干节点(分支),这样粗略评估一下如果每盘棋子要走100步(树深度),每步平均有10个选择(分支因子),那么这个棵树多大规模呢?10的100次方种走法,如果是围棋每步的选择更多所以深蓝也无法处理。博弈的过程就是双方在这个树(解空间)中找最优选择的过程。每个人都会选择对自己价值最大的那步,这课树也叫博弈树(如下图)。

人工智能通识决策树算法(计算机是如何下棋的)(1)

图 博弈树,MAX最优是往8走,MIN最优往1走,结果是去2了,2就是博弈的结果

要赢就需要在这个博弈树中找到价值最大路径的过程,就是博弈过程的模型,本质上也是一种搜索。如果试图每走一步就要遍历整个解空间,基本上就崩溃了,因为对于10的100次方这个级别你需要动用全宇宙的原则来计算也不够。所以基本的策略是对树进行剪枝,缩小解空间的范围。如何剪枝呢?如上图中MIN在2-7中会选择2,1-8中选择1,而MAX在2-1中会选择2,这样看来其实树最底层的节点8就没必要访问了,相当于只需要比较2,7,1三个节点博弈树就可以上一层。所以我们看到,最优路径是在2那条分支上,所以博弈的结果是趋向均衡的,不下错的情况下和棋的概率最高。如果其中一方能比对方多看几步,那么他就能站在更深的层评估占据从而更有可能赢的比赛。所以高手下棋一是比谁不出错、二是比谁能看的更远。这个深度也是格局,和做人一样格局越大成功的可能性就越大。

人工智能通识决策树算法(计算机是如何下棋的)(2)

,