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

发布时间：2017-04-20 21:04

  本文关键词：并行计算在计算机博弈中的研究与应用，由笔耕文化传播整理发布。

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

• 摘要4-5
• ABSTRACT5-9
• 1 引言9-15
• 1.1 国内外研究的现实状况9-10
• 1.1.1 六子棋当前博弈算法的状态9
• 1.1.2 六子棋目前的研究上的不足9-10
• 1.2 研究的目的和意义10-11
• 1.3 主要研究内容与研究成果11-13
• 1.4 论文的组织结构13-15
• 2 计算机博弈与六子棋平台15-21
• 2.1 完全信息博弈15
• 2.2 博弈树15
• 2.3 四种搜索算法的比较与分析15-16
• 2.4 六子棋棋局的表示及变化趋势16-17
• 2.5 当前六子棋博弈流程17-19
• 2.6 进程与线程19-20
• 2.7 六子棋获胜局面20-21
• 3 并行程序设计21-31
• 3.1 并行技术21-22
• 3.1.1 并行技术的发展21
• 3.1.2 伪并行21
• 3.1.3 并行计算21-22
• 3.2 串行算法与并行算法访存模型22-24
• 3.2.1 串行算法存储模型22-23
• 3.2.2 并行算法存储模型23-24
• 3.3 计算机的体系结构24-25
• 3.4 共享存储器与多处理机关系25-27
• 3.4.1 多指令流多数据流机器(MIMD)存储类型25-26
• 3.4.2 共享存储器与多处理器的几种主要连结26-27
• 3.5 并行编程模型27-28
• 3.5.1 共享变量模型27-28
• 3.5.2 消息传递模型28
• 3.5.3 数据并行模型28
• 3.6 并行程序设计28
• 3.7 影响并行算法性能的因素28-31
• 3.7.1 充分发掘可以并行的程序段28-29
• 3.7.2 负载平衡问题29
• 3.7.3 数据通信与同步29-31
• 4 并行算法设计31-43
• 4.1 几种windows平台下的并行编程模式31-32
• 4.1.1 Windows多线程31
• 4.1.2 OpenMP31-32
• 4.1.3 MPI32
• 4.2 几种相关并行算法32-36
• 4.2.1 遗传算法及并行性分析32-35
• 4.2.2 贪心算法及并行性分析35
• 4.2.3 禁忌算法及并行性分析35-36
• 4.2.4 Memetic算法及其并行性分析36
• 4.2.5 各种算法的并行与通信36
• 4.3 并行程序的编程模式36-38
• 4.4 Open MP编程模型38-39
• 4.5 Open MP性能分析39-40
• 4.6 博弈算法的并行化40-43
• 5 六子棋博弈的并行系统设计43-51
• 5.1 两种并行方法43-44
• 5.2 引入并行的多线程的解决思路44-45
• 5.3 任务的分解，评判及其回收45
• 5.4 并行博弈系统中最佳落子点的选择45-46
• 5.5 六棋博弈并行算法的设计46-47
• 5.6 多线程并行搜索的伪代码47-51
• 6 实验分析51-59
• 6.1 系统实现51-54
• 6.2 实验分析54-59
• 7 总结与展望59-61
• 致谢61-63
• 参考文献63-65
• 个人简历、在学期间发表的学术论文及取得的研究成果65

【参考文献】

中国期刊全文数据库 前1条

1 李建江,舒继武,陈永健,王鼎兴,郑纬民;Analysis of Factors Affecting Execution Performance of OpenMP Programs[J];Tsinghua Science and Technology;2005年03期

  本文关键词：并行计算在计算机博弈中的研究与应用，由笔耕文化传播整理发布。

，

本文编号：319502