人工智能通识决策树算法（计算机是如何下棋的）

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

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

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

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