3.3 博弈树的搜索

　　这里所讲的博弈，指的是类似于象棋这样的游戏问题。这类问题有以下一些特点：
　　（1）双人对弈，对垒的双方轮流走步。
　　（2）信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。
　　（3）零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。
　　博弈问题为什么可以用与或图表示呢？可以这样来看待这个问题：当轮到我方走棋时，只需从若干个可以走的棋中，选择一个棋走就可以了。从这个意义上说，若干个可以走的棋是"或"的关系。而对于轮到对方走棋时，对于我方来说，必须能够应付对手的每一种走棋。这就相当于这些棋�"与"的关系。因此，博弈问题可以看成是一个与或图，但是与一般的与或图并不一样，是一种特殊的与或图。