我们已经知道在地图和游戏之间存在着紧密的联系。由于很多棋类游戏的棋盘看起来和地图有些相似，所以人们对地图和游戏的这种紧密联系并不特别意外。事实上，这两者之间的联系要比我们最初猜想的更密切。博弈论对这种深层次的联系进行了清晰的论述，这将对普适框架的建立有很大帮助。
虽然棋类游戏非常古老，而且几个世纪以来，随机博弈在概率论的发展中扮演了重要角色，但是直到20世纪上半叶，真正意义上的博弈论才建立起来（von Neumann, Morgenstern, 1947）。从建立的那天起，博弈论就深刻影响着很多其他领域，如统计学、信息理论，特别是经济学，还包括近年来跨学科研究所产生的演化博弈论（Maynard-Smith, 1978; Axelrod, Hamilton, 1982）。博弈论的细节超出了本书的范围，但其中的几个概念对我们目前的讨论很有帮助。虽然这些概念中的大部分同样适用于随机博弈模型，但我们在这里分析的是非随机博弈模型，如国际跳棋、国际象棋和围棋。
状态
第一个概念就是博弈的状态（state of the game）。对于棋类游戏来说，状态就是指在下棋过程中任意时刻棋盘上所有棋子的布局。从那一刻开始，这盘棋的下法只取决于当时的棋盘布局，而不是取决于这个布局是怎样演变而来的。当然，有极少数的例外情况存在，如国际象棋中的王车易位和双陆棋中的转换倍率，但是这些例外也都可以通过增加一枚辅助棋子的方式解决，如双陆棋中的加倍骰子。简言之，在博弈过程中的任何时刻，博弈的状态是该时刻以前博弈过程的结果，这个结果具有足够多的信息，能够决定将来所有的可能性。在这里，博弈的状态同物理系统的状态非常相似。例如，我们用压力、温度和体积来记录装有压力气体的容器的状态，如车胎或潜水箱的状态。如果这时在容器上刺一个洞，下一步所发生的情况仅取决于上面所记录的状态。一个系统的状态确定下来以后，其未来的变化仅仅取决于它当前的状态。
一个棋类游戏中的状态空间（state space）指的是，在游戏规则的限定下，棋盘上所有允许出现的布局的集合（见图3-3）。在这里，“在游戏规则的限定下”这个限制条件很重要（见图3-4）。在国际象棋中，棋子被放置在棋盘上的方式是多种多样的，但在游戏规则的限定下，只有一小部分的布局是合规的。例如，在国际象棋中，“象”按规定只能从其开始所在的方格移到具有同一颜色的方格中，也就是说，它只能在棋盘上斜向移动。而且，任何一方的两个“象”开始时都要放在不同颜色的方格中。根据这两条规则我们马上就能够知道，任何情况下，同一方的两个“象”处于同颜色方格中的状态都是不符合规则的。更要注意的是，一个棋类游戏的初始布局是由游戏规则指定的；在游戏规则限定下的棋子重新布局就产生了游戏过程中的一步走棋，通常是移动一枚棋子。这样连续的走棋就是游戏的过程。这些在既定规则下得到的棋盘布局（状态）的集合就构成了博弈的状态空间（见图3-5）。
图3-3 一些简单的状态空间
图3-4 合规的布局
图3-5 井字游戏博弈树的一部分
博弈树
对本书而言，博弈论最重要的概念就是博弈树（tree of moves）。树的根节点（root）是博弈的初始状态，第一层分支通向的节点，就是那些从树的根节点所表示的初始状态进行一步博弈动作后所能得到的所有状态。在第一层节点上的分支（第二层分支）通向那些从树的根节点所表示的初始状态进行两步博弈动作后能得到的状态，如此依次向下直到树的叶节点（leaves）。树的叶节点表示博弈的最终状态。叶节点同时也决定了博弈的结果。正是从根节点到叶节点的连续的路径选择，使得博弈过程丰富而有趣。
相对于那些专门为理论研究而发明的小游戏，真正的棋类游戏的博弈树或多或少总会比树型结构要复杂。在博弈中，不同的分支可能通向同一个状态，于是可能的状态会比分支数量少，这与传统的树的概念不同。比如在国际象棋中，如果我们先移一步车，然后再移一步象，可能会得到与先移一步象，再移一步车完全相同的棋局。尤其值得注意的是，很多分支可能通向同样的叶节点（最终状态）。在国际象棋中，许多不同的博弈序列都能以同一方式结束，如王被对方的后和车逼到角落里将死。这种额外的复杂性，对我们目前的讨论影响并不是特别大，但是为了避免不必要的歧义，我将着重讨论“博弈的方法”，而不是“博弈的结果”。
总而言之，真正的博弈要比传统的树更加错综复杂。即使分支规则很简单，叶节点（最终状态）的数量也会增长很快。事实上，正是由于这种复杂性，才使得博弈不可预测、魅力十足。设想一个棋类游戏，从初始状态开始，每一个状态只有10种可能的移动方式（分支）。如果这个游戏在移动两次之后结束，那么就会有10×10=102=100种不同的结束方式；如果博弈在10次移动之后结束，那么就会产生1010=10 000 000 000种不同的方式。国际象棋常见棋局所用步数大约为50步，如果我们经过这么多步后结束博弈，就会产生1050种不同的博弈方式，这个数字已经远远超过了组成地球的所有原子数量。
现在我们可以看到，只用少量的规则就可以定义一种复杂游戏，复杂到我们永远不能穷尽它的所有可能性。如果不考虑那些过早结束或那些有意重下从而加以讲解的棋局，那么即使我们把若干世纪以来进行过的所有国际象棋博弈的棋局都记录下来，也很难从中找到两个完全相同的博弈序列。正是这种恒新性，使国际象棋和围棋这类经典游戏，即使在经过了几个世纪的仔细研究之后，仍能不断地向人们提出新挑战。同样，井字棋之所以只有小孩子才玩，就是因为人们一旦认识它的固定博弈模式后，很快就能预测出它的所有可能性。
策略
在复杂的博弈中，博弈计划或者说策略，对于有效的博弈来说至关重要。大致说来，策略就是这样一种方法，它告诉我们如何随着博弈的展开而采取相应的行动，制定出一系列决策。博弈树为博弈策略的表述提供了一个精确的方法。在博弈的过程中所做的一系列决策在博弈树上留下一条路径（见图3-6）。这样，根据决策序列在博弈树上所选定的分支，我们就能够定义出策略。在博弈论中，一个完整策略为每一个可能遇到的状态（棋盘上棋子的布局）指定了一个分支（下一个动作）。换句话说，一个完整策略能够告诉我们在任何可能的情况下应该采取的行动。需要注意的是，策略有好有坏。它仅仅是一些指令，描述应该采取的行动，也可能是导致失败的罪魁祸首。
图3-6 井字游戏中，相应策略在博弈树上确定的一条路径
函数在策略这个领域里也大有用处。我们可以使用函数来定义从博弈状态到策略所决定的动作之间的对应关系。函数先为初始状态指定下一步的动作，比如，“把从左边数第四个兵向前移动一步”；然后，在对手随之做出反应之后，函数为此时新的状态确定相应的动作，以此类推，直至博弈终结。对于每一个策略来说，都存在着描述这个策略的函数。
EMERGENCE
说得更正式一些就是，对于博弈状态集S中的每一个状态s，特定的策略g都会为其指定在博弈树上处于该状态时应采取的动作。也就是说，策略g为博弈树上的每个状态s指定了它的后续状态s> 多人博弈（multiperson game）是指有两个及以上参与者的博弈。在多人博弈中，我们分别为每个博弈参与者确定策略。一旦博弈各方都选定各自的策略，结果（博弈树的叶节点）便随之确定下来。这里不考虑随机选择的策略，比如说通过掷骰子确定动作。换句话说，各方策略的共同作用，就在博弈树上选定了一条路径，这条路径从根节点延伸到某个叶节点（见图3-6）。
如果博弈参与者从一开始就确定了各自的博弈策略，那么博弈的精彩和悬念也就荡然无存了，只剩下一种机械式演练，最终结果也必将毫无悬念。但是，这个推理过程忽略了一个因素，即博弈中的任何一方都不知道对手的策略。每个参与者都可以预先做好准备，去应对即将出现的种种可能情况，但由于无法预知对手的动作，他们也就无法预知到底会出现什么情况。因此，虽然博弈结果已经由双方的博弈策略事先决定了，但每个参与者无法预测最终结果，哪怕是最初几步的结果也很难预测。对一个博弈参与者而言，博弈过程将会显得峰回路转、无法预料。
当不断重复同一个博弈时，人们将有机会逐步了解原本一无所知的对手的策略。以两人博弈为例，假定对手已经确定其策略，通过观察对手在博弈过程中重复出现的动作，就可以了解对手在博弈树上不同分支处的做法（选择）。利用这些信息，我们可以为对手的策略建立模型。由于存在着太多可能的策略，事实上无法通过试错的方式获得一个完全详尽的描述，所以建立的模型往往缺少许多细节。虽然如此，只要模型在某些方面正确，我们就能借助它更好地选择相应的策略。
这些观察结果同样适用于比棋类游戏更具普遍性的“博弈”中。让我们看看人和大自然的博弈，比如人们为了改进生态系统（大自然）而执行一项计划（策略）。即使大自然的运行确实遵循一套固定的规则（规律），但博弈的结果仍然是难以预测的。然而，经过长期的观察，我们就能够逐渐为生态系统及其针对人类活动所做出的反应建立模型。这也是许多科学研究通常采取的方式。
这里有两个主要问题需要深入研究。
1．在现实情况下，我们并不能通过列举所有博弈状态以及为每种状态指定相应的动作来定义策略。即使是一个中等规模的博弈，它的状态数目也多得惊人。列举所有状态和相应动作，几乎是不可能实现的奢望。即使采用世界上最先进的计算机，即使这些计算机拥有足够的存储空间和运算速度，情况依然如此。前面我们曾经计算过博弈树的状态数目，这个数字大得惊人，以至于在可预见的未来都不可能有计算机能够存得下它们。对于这种情况，有些国际象棋博弈程序就是很好的例子。即使具有巨大的存储能力和运算速度，它们也没有使用列举所有状态及相应动作的方式来明确地表述博弈策略。相反，这些程序在博弈树上不断进行有选择性的捜索，而且会在博弈过程中不断变化搜索方式。这些程序只搜索了所有可能状态中非常小的一部分。
EMERGENCE
用数学语言描述就是，我们不可能采用为状态集S中所有状态s列出（状态，动作）对应关系[s, g（s）]的方式，来明确定义策略。
事实上，人们也并没有使用明确的策略定义方式，而是通过一系列规则来定义策略，就像用规则定义游戏一样。这些定义策略的规则通常都是经验法则。比如国际象棋中的“构建坚固的兵形”“控制中心”“捉双”等规则。这些规则描绘了经常出现的博弈特征，并且和博弈过程中不同时刻的决策紧密相关。这些规则把博弈状态划分到不同的簇中，在某一特定的簇里，所有状态具有同一特征。这一特征提醒我们，当处于该簇中的某一状态时，就应该采取某个相似的决策或动作。通过这种方式，我们大大缩减了博弈树的规模，从而有可能得到一个可以控制博弈过程的整体策略描述。在第4章，我们将详细讨论塞缪尔的国际跳棋程序，从而清晰地展现这个过程。
如上所述，我们通过重复博弈，发现并组合积木块（经验法则和博弈特征），从而构建起了一种可行的策略。与列举所有状态以及相应的动作来精确定义策略相比，这个方法要可行得多。即使策略的某些部分很难用积木块直接描述，上述方法仍不失为策略建模的一个有效起点。这个观点是以如下假设为前提的，即对手的策略也建立在有限数量的积木块之上。
如果对手是大自然的话，并且假设我们是科学家，我们也会采取同样的办法。虽然我们还没有找到足够的证据证明宇宙运行确实依照某些可行的策略，但我们仍然尝试着建立关于宇宙运行规则的模型。爱因斯坦的名言“量子力学令人印象至深，但我相信上帝不掷骰子”，显然是一种信念的表达，而非观测结果。在科学研究和博弈游戏中，以上策略建模的有效性为这种积木块假设的合理性提供了部分佐证。万有引力定律、麦克斯韦方程组、门捷列夫的元素周期表，以及孟德尔的遗传规律，都为我们揭示了大量关于宇宙运行的规律。
值得注意的是，即使我们能够找出一套固定的策略，可以推演出自然界的众多可能性，仍然还会有未知和神秘的事情发生。例如牛顿方程，经过数个世纪的不断挖掘之后，我们仍然能够发现它所蕴含的新的可能性，而且万有引力定律显然也还远没有包含自然界所有的可能性。
2．前面所提到的简化的假定，即对手遵循固定策略这一点，没有考虑博弈重复进行时可能发生的一种情况，即对手也是会不断学习的。有一个观点更实际，那就是所有博弈参与者都同时在试图为其他博弈参与者的行为建立模型。这样一来，情况就变得更为复杂了。即使是一个对博弈有着全局了解的观察者，他也和每个博弈参与者一样会遇到意想不到的事。尽管观察者了解初始策略以及每个博弈参与者学习过程的具体细节，他还是几乎不可能预测出博弈的整个过程。在参与者相互适应对方的博弈中，涌现以及恒新性是永远存在的。
