计算机博弈就是计算机下棋。图灵测试便是要通过下棋检测计算机智能水平的高低。计算机博弈属于人工智能领域的一个重要分支。计算机的博弈水平代表了计算机的智能水平。让计算机能够战胜人类高手,并处于不败之地,一直是国内外学者们致力于研究的目标。1997年的“深蓝”战胜了国际象棋大师卡斯帕洛夫,这在世界上反响巨大,它表明计算机可以战胜人类天才。这在一定程度上说明计算机思考问题的能力已经更加接近于人脑了。冯诺依曼和摩根斯坦早在1944年,就在他们的《博弈论及经济行为》一书中提出了二人零和博弈理论。而棋类博弈问题是这一理论的具体表现。实现计算机博弈问题的理论解(即不败解)一直都是全世界机器博弈研究学者梦寐以求的事情。近年来,随着计算机硬件水平的不断提高,一些博弈问题已被求解,比如:四子棋(Connect Four)、五子棋(Go-moku)和西洋跳棋(Checkers)等等。但是对于一些复杂度很高的棋类问题(如:中国象棋、日本将棋和围棋等),学者们在研究这些问题的理论解时,还停留在求解这些棋类的残局问题上。尽管现在硬件水平在迅速的提高,但还是需要将研究重点放在博弈问题的理论上,诸如:博弈问题的计算复杂性、状态复杂度和博弈树复杂度、理论解求解途径及相关搜索算法等。本文主要围绕求解计算机博弈问题做了深入的研究工作,为了从理论角度探讨求解计算机博弈问题的难易程度,全面研究了计算复杂性理论并实现了对中国象棋的计算复杂性证明;研究了博弈问题的状态复杂度和博弈树复杂度的估算方法,并根据这两个数值来决定各种博弈问题应该采取哪一种求解策略;针对当前求解博弈问题比较常用的一种搜索算法-证据计数法(PNS,Proof-number search),提出了一种改进的PNS算法;以牛角棋和六子棋为例,研究了求解这两个博弈问题应该采取的具体方法。此外,还从全局的角度研究和综述了博弈问题的主流搜索算法。概括起来本文主要研究成果有以下几点:介绍并分析了计算理论的一些基本概念,论述了时间复杂性和空间复杂性中的各个主要分类(包括:P、NP、NP-complete、PSPACE、PSPACE-complete、EXPTIME、EXPTIME-complete等),分析了各个复杂性类之间的关系;并给出了NP问题为非多项式时间问题的推论;重点研究了中国象棋的计算复杂性,构建了一个n×n的中国象棋归约模型,在该模型上模拟进行G3游戏,并最终证明了 G3游戏可多项式时间内归约到n×n的中国象棋,进而证明了中国象棋属于EXPTIME-complete问题。阐述了计算机博弈问题的状态复杂度和博弈树复杂度的估算方法。在常见的复杂度估算方法的基础上,根据不同博弈问题的走棋特点,对估算过程中可能存在的一些非法局面进行了分析和排除,并详细地估算了亚马逊棋、苏拉卡尔塔棋的状态复杂度和六子棋、点格棋的博弈树复杂度。介绍了计算机博弈问题理论解相关的一些理论知识,并且综述了五子棋、8 X8西洋跳棋以及围棋的残局被求解的思路以及所采用的核心技术。以牛角棋为例,分析了求解牛角棋应该采取的求解策略,实现了对牛角棋的求解。提出了一种基于连珠类型的六子棋求解策略,阐述了该求解策略的算法构成,主要包括基于连珠类型的走法生成器、一种基于迫着数的算法(即alpha-beta剪枝和TSS的混合算法)调用策略和证据计数法。以7X7棋盘规模的六子棋开局为例,验证了这一求解策略具有较强的求解能力。在搜索算法方面,详细阐述了基于与或树的证据计数法原理,综述了证据计数法在一些落子类博弈系统中的应用;论述了证据计数法和PN2算法的缺陷,基于PN2算法,本文提出了一种两级的PN算法,即PN-DFPN,通过实验证明,PN-DFPN在搜索效率和求解能力上都要优于PN2;此外,论述了非合作动态博弈问题的复杂度和理论解以及两者的关系,并综述了该类博弈问题的基本搜索算法和一些基于alpha-beta的高级搜索算法,还详细阐述了当前广泛应用于非合作动态博弈问题中的几种新算法。本文对提出的算法、方法和结论给出了理论证明,并且通过了实验验证,这对今后实现求解复杂度更高的博弈问题提供了理论支持和有益方法。