博弈树搜索博弈树搜索l所谓双人完备信息，就是两位选手对垒，轮流走步，这时每一方不仅都知道对方过去已经走过的棋步，而且还能估计出对方未来可能的走步。对弈的结果是一方赢（另一方则输），或者双方和局。这类博弈的实例有：一字棋、余一棋、西洋跳棋、国际象棋、中国象棋、围棋等。对于带机遇性的任何博弈，因不具有完备信息，不属这里讨论范围，但有些论述可推广到某些机遇博弈中应用。l博弈问题可以用产生式系统的形式来描述，例如中国象棋，综合数据库可规定为棋盘上棋子各种位置布局的一种描述，产生式规则是各类棋子合法走步的描述，目标则可规定为将（帅）被吃掉，规则作用于数据库的结果便生成出博弈图或博弈树。下面举一个简单的例子说明博弈问题可用与或图表示，并讨论搜索策略应考虑的实际问题。中国象棋中国象棋l一盘棋平均走50步，总状态数约为10的161次方。l假设1毫微秒走一步，约需10的145次方年。l结论：不可能穷举。博弈树是与博弈树是与/或树或树l双方都希望自己能够获胜。因此，当任何一方走步时，双方都希望自己能够获胜。因此，当任何一方走步时，都是试图选择都是试图选择对自己最为有利，而对另一方最为不利对自己最为有利，而
