【读书笔记】算法漫步 第12章

问题5 对弈游戏

下棋，从古至今，都会认为是一个智力游戏，而且是一个很需要“智力”的游戏。

让计算机会下棋，而且还能赢，甚至能赢职业棋手，是非常能体现出计算机有“智能”的，也是人工智能应用的一个重要方向。如果关心一些计算机下棋的新闻，不难知道，现在基本上流行的各种棋，会下棋的计算机已经能够完胜职业棋手了。

让计算机会下棋，或者说计算机表现出的任何智能的核心都是算法。这些算法，有的是若干经验规则的编码，有的是基于自然界或社会生活带来的启发，有的需要先从大量数据中学习出一些模式，还有的则可能是基于对问题的深刻理解形成的小巧精妙的算法。

本章介绍了一个两人对弈的游戏。

给定m堆棋子，每堆棋子数都不小于1个。两个玩家轮流从中取棋子，每次只能从一堆拿，至少拿一颗，谁拿最后一颗谁为胜。是否存在先手胜的条件？如果存在，它是什么？

书中，详细从两堆棋子的一个具体例子开始介绍，推广到m堆棋子，介绍了要赢得对弈的逻辑（读者注，这个逻辑感觉像博弈论，如果是，作者为了科普，简化了问题，同时用大白话介绍了算法逻辑，而不是博弈论中得定理和数学推导）

在介绍这个游戏的算法的计算机实现时，介绍了一种重要的逻辑运算—异或运算。

因为，能对弈，能写一个程序和人对弈，甚至能赢，建议耐心读读，理解其中的逻辑，而且建议有编程基础的读者，能写一个程序，让它真的和人比试一下，很爽的。

【作者感受】

在读本章时，一开始，以为会介绍某个棋类的“智能”算法，可惜没有。

智能，这个现在很火的词，在非计算机专业、或者非人工智能从业者以外的人，听起来，很神奇，很神秘的东西，其实没有那么“智”。