并行计算在计算机博弈中的研究与应用

摘要

搜索在博弈方面的运用是非常重要的，是得出最优落子点最有效的方法。然而，当前的博弈搜索都是串行执行的，执行时间长，深度不够，不能在有限的、规定的时间内搜索出最佳落子点。因此，并行方法是博弈研究中的一个重要方向。　　为此，本文主要完成了如下两方面的工作：　　1.为了实现并行博弈搜索技术，以提高CPU使用率和搜索效率。文章首先分析了并行博弈搜索技术的可行性，构建了基于传统博弈搜索的并行博弈搜索策略架构；然后，提出了由主程序和子线程共同构成的博弈策略框架，设计了主程序、子线程的通信方法；最后，通过主程序选择多个子线程中的相对最优解，通过策略推送方式，为整个博弈提供相对优良的博弈对策。　　2.为了验证上述研究成果，作者改进了自己所在实验室的六子棋博弈平台，改进为并行的六子棋博弈平台，通过对比改进前后的博弈策略，证实了新的博弈策略是有效可行的，CPU的使用率得到提升，运用并行的一方获胜的概率增大了。

目录

封面

声明

中文摘要

英文摘要

目录

1 引言

1.1国内外研究的现实状况

1.2研究的目的和意义

1.3主要研究内容与研究成果

1.4 论文的组织结构

2 计算机博弈与六子棋平台

2.1完全信息博弈

2.2 博弈树

2.3四种搜索算法的比较与分析

2.4六子棋棋局的表示及变化趋势

2.5当前六子棋博弈流程

2.6 进程与线程

2.7 六子棋获胜局面

3 并行程序设计

3.1 并行技术

3.2串行算法与并行算法访存模型

3.3计算机的体系结构

3.4 共享存储器与多处理机关系

3.5并行编程模型

3.6并行程序设计

3.7 影响并行算法性能的因素

4 并行算法设计

4.1几种windows平台下的并行编程模式

4.2几种相关并行算法

4.3 并行程序的编程模式

4.4 OpenMP编程模型

4.5 OpenMP性能分析

4.6博弈搜索算法的并行化

5六子棋博弈的并行系统设计

5.1 两种并行方法

5.2引入并行的多线程的解决思路

5.3任务的分解，评判及其回收

5.4并行博弈系统中最佳落子点的选择

5.5六棋博弈并行算法的设计

5.6多线程并行搜索的伪代码

6 实验分析

6.1系统实现

6.2 实验分析

7 总结与展望

致谢

参考文献

个人简历、在学期间发表的学术论文及取得的研究成果