计算机博弈问题的复杂性、理论解及相关搜索算法研究

摘要

计算机博弈就是计算机下棋。图灵测试便是要通过下棋检测计算机智能水平的高低。计算机博弈属于人工智能领域的一个重要分支。计算机的博弈水平代表了计算机的智能水平。让计算机能够战胜人类高手，并处于不败之地，一直是国内外学者们致力于研究的目标。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×8西洋跳棋以及围棋的残局被求解的思路以及所采用的核心技术。以牛角棋为例，分析了求解牛角棋应该采取的求解策略，实现了对牛角棋的求解。 提出了一种基于连珠类型的六子棋求解策略，阐述了该求解策略的算法构成，主要包括基于连珠类型的走法生成器、一种基于迫着数的算法（即alpha-beta剪枝和TSS的混合算法）调用策略和证据计数法。以7×7棋盘规模的六子棋开局为例，验证了这一求解策略具有较强的求解能力。 在搜索算法方面，详细阐述了基于与或树的证据计数法原理，综述了证据计数法在一些落子类博弈系统中的应用;论述了证据计数法和PN2算法的缺陷，基于PN2算法，本文提出了一种两级的PN算法，即PN-DFPN，通过实验证明，PN-DFPN在搜索效率和求解能力上都要优于PN2;此外，论述了非合作动态博弈问题的复杂度和理论解以及两者的关系，并综述了该类博弈问题的基本搜索算法和一些基于alpha-beta的高级搜索算法，还详细阐述了当前广泛应用于非合作动态博弈问题中的几种新算法。 本文对提出的算法、方法和结论给出了理论证明，并且通过了实验验证，这对今后实现求解复杂度更高的博弈问题提供了理论支持和有益方法。

目录

声明

摘要

第一章绪论

1．1研究背景与动机

1．2国内外相关研究的现状与分析

1．2．1机器博弈研究的现状与分析

1．2．2机器博弈问题计算复杂性研究的现状与分析

1．2．3机器博弈问题理论解研究的现状与分析

1．2．4证据计数法研究现状与分析

1．3研究内容

1．3．1博弈问题的计算复杂性

1．3．2博弈问题的状态复杂度和博弈树复杂度

1．3．3证据计数法

1．3．4博弈问题的理论解

1．4本文组织结构

第二章面向非合作动态博弈问题的搜索算法综述

2．1引言

2．2非合作动态博弈问题的复杂性与可解性

2．2．1非合作动态博弈问题的复杂性

2．2．2非合作动态博弈问题的可解性

2．3基本搜索算法

2．3．2 A1pha-Beta搜索(Alpha-Beta Search)

2．3．3负极大值算法(Nega-Max Algorithm)

2．4基于Alpha-Beta剪枝的高级搜索算法

2．4．1迭代加深搜索(Iterative deepening search)

2．4．2面向着法排序的alpha-beta搜索

2．4．3面向窗口大小的alpha-beta搜索

2．4．4几种启发式搜索

2．5几种新算法

2．5．1基于蒙特卡洛模拟的博弈树搜索

2．5．2基于威胁的搜索(TSS-Threat Space Search)

2．5．3证据计数搜索(PN-Proof Number Search)

2．6本章小结

第三章计算复杂性研究

3．1引言

3．2有关计算复杂性

3．2．1可判定问题

3．2．2语言

3．2．3有穷自动机与下推自动机

3．2．4确定型图灵机及非确定型图灵机

3．2．5映射可归约性

3．3时间复杂性

3．3．1 P(确定型多项式时间复杂性)

3．3．2 NP(非确定型多项式时间复杂性)

3．3．3 NP问题是非多项式时间问题

3．3．4 NP-complete(NP的完全问题)

3．3．5 EXPTIEM(指数时间复杂性)

3．4空间复杂性

3．4．1 PSPACE(确定型多项式空间复杂性)

3．4．2 NPSPACE

3．4．3 PSPACE-complete(PSPACE的完全问题)

3．5各种复杂性类之间的关系

3．5．1 P与NP的关系

3．5．2时间复杂性(P和NP)与空间复杂性的关系

3．5．3空间复杂性与EXPTIME的关系

3．6本章小结

第四章中国象棋计算复杂性研究

4．1引言

4．1．1 EXPTIME-complete问题

4．1．2 G3游戏

4．2中国象棋计算复杂性的证明

4．2．2n×n中国象棋的计算复杂性

4．3归约模型的构建

4．3．1归约模型中各构件的说明

4．3．2赢棋策略

4．4不恰当走法分析

4．4．1布尔控制器(RBC)中可能存在的不恰当走法

4．4．2开关中可能存在的不恰当走法

4．4．3子句通道与文字通道的交叉点处可能存在的不恰当走法

4．5结论

4．6本章小结

第五章博弈问题状态复杂度和博弈树复杂度估算方法研究

5．1引言

5．2博弈问题的状态复杂度

5．2．1博弈问题的状态复杂度定义

5．2．2亚马逊棋的状态复杂度

5．2．3苏拉卡尔塔棋的状态复杂度

5．3博弈问题的博弈树复杂度

5．3．1博弈树搜索算法原理

5．3．2博弈树复杂度的定义

5．3．3六子棋的博弈树复杂度

5．3．4点格棋的博弈树复杂度

5．4本章小结

第六章证据计数法研究

6．1引言

6．2．1一种与或树模型

6．2．2证据计数法的定义及工作原理

6．2．3证据计数法的特点及应用

6．3证据计数法在落子类机器博弈中的应用

6．3．2证据计数法在六子棋中的应用

6．3．3证据计数法在围棋中的应用

6．4证据计数法存在的缺陷及PN2算法

6．4．1证据计数法的缺点

6．4．2 PN2搜索算法

6．5一种改进的两级PN算法

6．5．1 PN-DFPN算法的定义

6．5．2应用于求解六子棋的PN-DFPN算法设计

6．6实验

6．7本章小结

第七章计算机博弈问题的理论解研究

7．1引言

7．2计算机博弈问题理论解的相关知识

7．2．1博弈问题被求解等级的分类

7．2．2博弈问题的复杂度与求解方法的关系

7．3一些已被求解的常见博弈问题

7．3．1五子棋(Go-Moku)

7．3．2西洋跳棋

7．3．3围棋残局

7．4求解牛角棋

7．4．1牛角棋的走棋规则

7．4．2牛角棋的状态复杂度及博弈树复杂度

7．4．3牛角棋求解采用的搜索策略

7．4．4结果

7．5一种基于连珠类型的六子棋求解策略

7．5．1基于连珠类型的着法产生器

7．5．2搜索策略

7．5．3用到的一些主要的辅助算法

7．5．4一种基于迫着数的搜索算法调用策略

7．5．5实验

7．6本章小结

第八章结束语

8．1本文的主要贡献

8．2未来研究工作的展望

参考文献

致谢

攻博期间参加的科研项目

攻读博士期间发表的论著