机器博弈是人工智能研究领域的一大热点,博弈树搜索则是机器博弈的引擎。本文在博弈树搜索算法和博弈树优化技术等方面做了深入研究,将理论和实践紧密结合,取得了以下的主要创新成果:⑴提出并成功验证了一种新的博弈树搜索算法:基于广度优先的接力式空窗探测搜索算法。实验证实该方法在实际应用中的平均搜索效率,高于目前公认搜索效率最高、也是最流行的PVS和MTD(f)搜索方法;在迭代深化搜索中,该方法也具有相对优势;并且该算法的最小搜索极限小于极小树。因此,该方法具有广阔的应用前景。⑵给出了一种新的博弈树优化技术—“子树复用”技术。该技术在几乎不需要额外时间开销的情况下,就能使深层博弈树搜索的效率提高10%以上,并随着搜索深度的加大,效率提高得愈多。“子树复用”技术在限定用时或必胜局面的对弈中还具有额外的实用价值,因而“子树复用”技术无疑具有极好的应用价值。⑶给出了极小搜索树叶结点数定理的新的证明方法,指出了以前的有关证明的缺陷。针对很多人对极小树的不准确理解,以及对窗口搜索效率的有关误解,给出了正确的结论。⑷开发了高水平的五子棋人机对弈系统,该系统在估值函数设计上,探索了不同颗粒度估值函数的应用效果,证实粗颗粒度估值函数在深度搜索中可以具有更好的综合效果;部分局面下的估值函数延伸评估技巧,同样可以替代搜索,来减少地平线效应;这些为同行提供了很好的借鉴。证实借助棋类知识的走法生成函数,在五子棋对弈系统中具有很好的效果。在博弈树优化方面,挖掘出极小极大值搜索算法的优势,应用收到了良好的效果。