基于Intel多核多处理器的两个经典游戏AI算法的并行化研究

摘要

目前，随着多核处理器的迅速发展，单核时代已经成为历史，尤其是由多个多核处理器组成的多处理器系统，更是为应用软件性能改善提供了硬件基础。然而我们的软件却大多停留在单核时代，并没有充分利用多核多处理器架构所带来的优势，对自身性能加以提升。对现有软件的改进以及并行程序的开发势在必行。因此与多核技术相结合，把过去串行化的程序并行化将能充分利用多核多处理器的性能优势，提高程序的效率。
　　 现今，游戏产业也是迅猛发展，在多核多处理器架构的PC上应用很广泛，然而现在的很多游戏没能充分发挥多核多处理器架构的优势。本文以棋类游戏中的五子棋和球类游戏中的足球作为例子，对这两个游戏的两种经典AI算法-博弈树搜索算法和遗传算法进行并行化研究。
　　 有关提高树搜索算法的性能的研究，一直以来都是学术界的热点问题，新的算法层出不穷。而研究树搜索算法最重要的实验温床是在研究如何在二人棋类游戏中找到最优解，即游戏树的搜索。白上世纪90年代以来，学者和研究员们对于树搜索算法的研究转向了并行化并提出了数量众多的并行树搜索算法。同时，遗传算法在人工智能中发挥了重要作用，遗传算法的并行化研究也日趋重要。我国有关遗传算法和并行计算的研究，从20世纪90年代以来一直不断地发展，特别是近年来，遗传算法和并行计算的应用在许多领域取得了很好的效果，成就瞩目。
　　 本文首先分析了多核多处理器架构的特点，提出了线程绑定到核的并行技术。在此基础上对博弈树搜索算法中的Alpha-Beta剪枝搜索算法和遗传算法进行了并行化研究，并分别在五子棋游戏和足球游戏中对这两个进行了实现和验证。最后，论文对多核多处理器结构下的PLCN模型进行了进一步的研究，对其适应范围作了描述。

目录

文摘

英文文摘

第一章 绪论

1.1 研究背景及意义

1.2 研究现状

1.3 本文的主要工作

1.4 论文组织

第二章 多核多处理器架构下的并行技术

2.1 Intel多核多处理器架构概述

2.1.1 Intel双核处理器

2.1.2 Intel双核双处理器

2.1.3 Intel四核双处理器

2.2 OpenMP并行编程模式

2.2.1 OpenMP指令格式

2.2.2 对for循环并行化

2.2.3 私有变量声明

2.2.4 部分OpenMP函数

2.3 多核多处理器的PLCN模型

2.4 线程绑定核并行技术

2.4.1 线程分配模型

2.4.2 线程绑定核实现方法

2.5 本章小结

第三章 并行Alpha-Beta剪枝搜索算法及其在五子棋中的应用

3.1 基本搜索技术

3.1.1 博弈树

3.1.2 极大极小值算法

3.1.3 Alpha-Beta剪枝算法

3.2 Alpha-Beta剪枝搜索算法并行化的途径

3.2.1 并行渴望搜索

3.2.2 并行子树估值

3.3 基于线程绑定核技术的BC-Alpha-Beta剪枝搜索算法

3.3.1 算法思想

3.3.2 BC-Alpha-Beta剪枝搜索算法

3.3.3 BC-Alpha-Beta剪枝搜索算法的关键问题

3.4 BC-Alpha-Beta剪枝搜索算法在五子棋中的应用

3.4.1 棋盘表示

3.4.2 静态估值

3.4.3 走法产生

3.5 并行Alpha-Beta剪枝搜索算法的测试与分析

3.6 本章小结

第四章 并行遗传算法在足球游戏中的应用

4.1 遗传算法基本原理

4.1.1 遗传算法术语说明

4.1.2 遗传因子

4.1.3 遗传算法的特点

4.1.4 遗传算法的步骤

4.2 并行遗传算法的并行模型

4.2.1 主从模式

4.2.2 粗粒度模型

4.2.3 细粒度模型

4.3 基于线程绑定核技术的并行遗传算法BC-Genetic

4.3.1 算法思想

4.3.2 算法步骤

4.4 BC-Genetic算法在足球游戏中的应用

4.4.1 足球游戏环境和规则

4.4.2 染色体编码

4.4.3 遗传算子

4.4.4 估值模块

4.4.5 球员位置产生的并行遗传算法的实现

4.5 并行遗传算法的测试与实验

4.6 本章小结

第五章 对PLCN模型的进一步研究

5.1 基于PLCN模型的线程绑定核技术再分析

5.2 PLCN模型下不同并行技术对并行算法性能改善程度的分析

5.2.1 现有的K-means算法介绍

5.2.2 K-means算法描述

5.2.3 多核多处理器下的K-means并行算法

5.2.4 多核多处理器下的并行算法测试结果

5.3 本章小结

第六章 总结与展望

6.1 论文工作的总结

6.2 进一步的研究展望

致谢

参考文献

作者简介