穷举法

从逻辑上说，下棋是一种简单的活动，因为它的可能性是有限的。可用穷举法，考虑所有的可能性，一直思考到棋局结束。

具体如何用穷举法，还要进一步考虑。下棋是你来我往，你一步我一步，不但要考虑自己的选择，还要考虑对手的选择，而我们又不知道对手接下来会怎么下。一种常用的方法是假设对手总是做出最优的选择，在这前提下自己做出最优选择，这叫极大极小法。

用穷举法加极大极小法，就能完美地解决象棋问题了。

但是除了特别简单的棋，我们人类无法使用这个方法，下象棋就不能。即使计算机下棋也不能使用穷举法，因为可能性太多，需要耗费极长的时间。

有限深度搜索

在实际下棋时，我们思考的深度是有限的，能思考到10个回合已经很厉害了。只能思考到一定深度的叫有限深度搜索，计算机同样是有限深度搜索。

有限深度搜索有时会出现地平线效应，比如十个回合后，自己比对方多一个车，计算机认为是好局，所以选择这种下法，但其实对手是弃车进攻，在十五回合后，不但夺回一只车，而且占尽优势。这时由于超出计算深度，计算机就发现不了。

减少计算量

即使是有限深度搜索，可能性还是非常多。比如轮到自己下时，有20种选择，轮到对手也有20种选择，这样一个回合就有20 x 20种下法，10个回合下来，就有20²⁰这么多种不同的下法。如果用博弈树表示，博弈树的深度是20，有20²⁰条路径。在短时间内，生成博弈树并且进行搜索，也是很困难的，何况下棋时理论上可以选择的下法常远远多于20种。

可用剪枝方法来减少计算量。比如有的下法，几个回合之后局势就很劣，丢了一个车，而没任何回报。那就不考虑这条路径，把它剪掉。

还有一些其他方法用来减少计算量。事先存储大量的开局库和残局库，遇到相同的局面时，就不用计算，直接调用就行了。

局面评价函数

刚才的讨论，一直忽略了一个问题。如果计算到终局，计算机知道是赢是输还是平局。但如果只是有限深度搜索，那计算机怎么知道这局面对自己有利还是不利呢。我们人类凭经验可以知道这一点，而计算机则依赖局面评价函数，这个函数对每个局面给出一个分数，高分数就是对自己有利的局面。

理论上说，有了局面评价函数后，计算机就不用再进行深度思考，只思考一步就行了，选择下一步分数最高的局面。但实际上局面函数无法完全真实地反映局面形势，当越接近终局时它才越准确，所以还要深度搜索。

设计象棋程序的关键是给出一个合理的局面评价函数。我们先根据经验尝试性地给出一个评价函数，然后让程序在训练中改进这个函数。具体方法有很多，下面给出其中一个方法。

评价函数的训练

1、评价函数

先假设局面评价函数是这样的：

V(b)=w₀+w₁x₁+w₂x₂+……+w_nx_n

b表示局面，x1、x2、……xn分别表示影响局面形势的因素，比如x1表示车的个数，x2表示炮的个数，……，xn表示棋子可以走的位置数量（表示机动性），x_n+1表示直接攻击到对方的棋子数，等等。而w0、w1、w2、……、wn等是参数，这些参数的值确定后，评价函数就确定了。我们根据经验，先给参数赋值，这样就得到一个评价函数。

2、训练样例

计算机通过下棋（可以是自己和自己下），获得很多经验，我们把这称之为训练样例，即很多局面状态以及相应的分数。局面评价函数要拟合这些训练样例。

但是，在训练过程中，那些棋盘状态的分数是那里来的呢？确定终局状态的分数很容易，中间状态就比较难了。因为一盘棋就算最后输了，它中局时可能本来是优势，只是后来走了臭棋才输掉了，不能说输棋就是它本来的局面不行。解决方法如下：

V_train(b)← V (successor(b))

successor(b)表示在局面b的状态下，在程序走了一步和对手回应一步后的局面。用假设的评价函数V对训练样例赋值，这看起来有点奇怪。但棋局越接近终局V越精确，事实证明用这种方法给训练样例赋值是相当有效的。在特定条件下还可证明这种方法是接近完美的。

3、调整参数

使用最小均方法算法（LMS）：

w_i ←w_i + h( V_train(b)—V (b))x_i

h是一个小的常数（比如0.1）。

在经过反复的训练后，评价函数能很好地拟合训练样例。即下面的E趋向于零：

E = S ( V_train(b)—V (b))²

4、效果

这样训练出来程序是不是有很高的棋力呢？难说，因为我们假定了评价函数是简单的线性函数。为了训练出很强的程序，往往需要更复杂的函数。而训练方法是多种多样的，这里只是其中一种。

围棋编程的困难

写围棋程序更难，原因有两个：

1、围棋落子的选择比象棋多，搜索的空间更大，所以更难进行有效的搜索。

2、另一个更重要的因素，很难给出合理的局面评价函数。象棋有个极重要的棋子，将，它被吃掉棋局就结束了。而且不同类型的棋子对局势的影响很不相同。这些因素都导致更容易给出不错的评价函数。而围棋只有一种类型的棋子，棋子位置稍有不同局面形势有极大的变化，很难给出好的评价函数。

围棋编程使用了新的思路才取得了突破：蒙特卡罗算法和深度学习。