博弈的可解性

2.2.2　博弈的可解性

计算机博弈中的另一个重要概念是博弈的可解性。对某种博弈而言，其可解性指的是无论该博弈的局面如何变化，我们可以在数学上准确地预测该博弈的最终结果。如果我们无法在数学上准确地预测某种博弈的最终结果，该博弈也称为是“无法解决”的。在博弈可解性的讨论中，我们通常假设所有的对弈者总是采用其最佳策略。最佳策略指的是对于任意给定的一个博弈局面，如果存在可以导致最终胜利的棋子走法，最佳策略总会选择该棋子走法；如果不存在可以导致最终胜利的棋子走法，但存在可以导致最终平局的棋子走法，最佳策略总会选择该棋子走法。

我们可以在以下3个层次上定义博弈的可解决性。

①强可解。在最强的意义上，可解决性指的是存在已知算法，对于任意给定博弈局面，该算法等同于最佳策略，总可以生成最佳棋子走法。对于该给定博弈局面，即使前面棋子走法不是最佳的，但并不影响该算法总可以生成最佳棋子走法。

②弱可解。在相对弱一点的意义上，可解决性指的是存在已知算法，对于初始博弈局面，该算法等同于最佳策略，总可以生成最佳棋子走法。

③超弱可解。在最弱的意义上，可解决性指的是存在数学证明，证明对于初始博弈局面，如果双方都采用最佳策略，先行一方是否可以胜利或战平。由于数学证明并非一定是构造性证明，因此无法获得相应的生成最佳棋子走法的算法。

从理论上讲，根据第2.1节所讨论的博弈树模型及博弈树上的遍历算法，我们总是可以计算出博弈的最佳策略。但是由于有限计算资源的限制，以上的理论分析无法应用于实际的博弈策略计算中。对于很多博弈，除非过于简单，使用博弈树遍历的方法计算其最佳策略需要花费无法承受的时间。因此在博弈可解性的讨论中，理论上是否存在最佳策略的计算方法并不是重要的，更重要的是能否可以在现有的资源条件下有效地运行该计算方法。

到目前为止，可解决的最复杂的计算机博弈是西洋跳棋（Checkers），其状态空间复杂度是5×10²⁰。研究人员总共花了18年的计算时间，构造了对于西洋跳棋初始博弈局面的最佳策略，从而证明了西洋跳棋是弱可解的，在双方都使用最佳策略时，西洋跳棋的结果是平棋。