博弈这类游戏来讲,计算机的特点决定了它在解空间中寻找答案的能力比人类更强。今天不讲阿尔法狗,而是了解一种通过博弈树来实现下棋程序的算法。
一盘棋子从第一步到结束整个过程可以看作是一个庞大的树,每下一步都可以看成为树又向下推进了一层。因为针对敌方的走棋,我方的选择有非常多应对的策略,每一个选择都可以看成这一层的若干节点(分支),这样粗略评估一下如果每盘棋子要走100步(树深度),每步平均有10个选择(分支因子),那么这个棵树多大规模呢?10的100次方种走法,如果是围棋每步的选择更多所以深蓝也无法处理。博弈的过程就是双方在这个树(解空间)中找最优选择的过程。每个人都会选择对自己价值最大的那步,这课树也叫博弈树(如下图)。