PC游戏编程——人机博弈.pdf

本书的写作意图源自于作者自己学习博弈稈厅设计的过程。作者于始 试图编写第一个人杌博弈程序的时候,几L乎找不到合适的参考资料。在国 內的几本人工智能书籍中找到的仅有最基本的搜索理论。而这离编写出实 用的人机博弈稈序相距甚远。无奈之下,我将寻求资料的眼光转向了国外, 开始阅读国外的书籍和论文以及技术叔告。在此期间,也有很多朋友表现 了对机器博弈的高度兴趣。在交流当屮,大家也都表示可资参考的屮文资 枓实在太少」。陆汝钤先生编著的《人工智能》一书,有40多页论述博弈搜 索的内容,大概是国内市场上买得到的对博弈搜索论述最多的著作,这是我 最初学习的主要的食粮。但该书由于论述的屮心是搜索理论,故而对于具 体的实现和博弈程序的其他重婁技术并未着墨、除此之外,我在这个领域 连一木翻译过来的中文书都未找到。 在参考了一些国外的资料之后,根据自己的设计实践,同时也对比了国 內其他爱好者的设计,我觉得有必要编写一本介绍博弈程序设计的一般方 法的书。因为博弈技术经历了这么多年的发展,有很多好的算法,技术已经 为国外的设计者所熟知。而凼内甚至还有爱好者在使用基本的极大极小算 法设計人机对弈程序。因此,限制程序性能的不是国人的能力,而是汲取新 知的管道。匮乏的中文资料成了学习人机博弈程序设计的一道障碍。当 然,作者不想乜没有能力将此书写成顶尖的埋论书籍。但却相信本书中所 介绍的实用可靠的内容一定可以让国内学习和编写博弈程序的人们在入门 的道路上稍微地加快步伐 作为人工钭能领域的重要实验室,博弈技术催生了一大批技术成果 乜正因为如此,博弈技术所涉及的内容极为广泛。一个人是不可能面面俱 到的,本书的目标在于能够让一般读者在掌握人机博弈的基本原理之余,也 能够完全」解此类程序的具体实现方法。而且对如何提高计算机的博弈性 能也能做到心中有数、运用自如。跟琏木书一步一步地实践下去,在很短的 时间里读者可以设计出自己的博弈程序。由于博弈技术与其乜研究领域 交义的边缘问题,大多处在探索阶段,而且这需要读者有其他领域的知识背 景,本书就不一一介绍 词汇 如前所述,由于本书在写作时参考的资料大多数是国外的,所以其中有 少量生僻的名词,作者在国内出版物上也找不到合适的译文,硬译过来则恐 怕词不达意,反而给读者造成理解上的障碍,因此直接使用了原文。不过在 书后的术语表中,作者给出了自己的翻译。对英语十分过敏的读者可以查 阅对照。 读者对象 本书面向任何对机器博弈有兴趣的读者。作者相信不论学习任何技 入,实战都是最快的方法。也正因为如此,本书最突出的特点就是实践。大 部分的重要内容都有程序范例。范例程序是用V isual c++写成的。虽然 对MFC熟悉的读者可以很快速地吃透例子的内容,但MFC的知识并不是 读者所必备的。本书范例的核心与MFC毫无关系,有一点程序设计经验的 读者可以轻易地将它移植到其他语言平台上,Jav或者P:s;程序员也不 必退避三舍,因为木书并未用到仁何C++狙有的技巧。为了能够降低读 者在阅读例子时理解上的困扰,作者对所有例子都刻意做了简化。精简代 码可以让读者看到更少与主题无关或次要的内容。 本书大多数的算法以伪代码的形式给出。之所以如此,是因为作者本 人,还有别人的学习纤历都表明:此种描述对于一个稈序员可能是最容易坦 解的。在人类的语言发生歧义,表达含混的时候,代码也许是程序员之间最 佳的沟通工具 感谢 首先我要感谢我的父母。没有他们的支持和协助,我根本无法有时间 和精力来撰写本书。 本书的问世是同许多友和同事讨论的结果,这些朋友在我学习博弈 程序的时候给了我很大的帮助。我要感射郭翡,她对机器的博弈原理有准 确的理解,在我开始触博弈的时候使我摆脱了死板的文字,她三言两语就 给我讲湑∫博弈树搜索的來龙去脉、接卜来应当感谢许少车、李德华两位 明友,同他们的讨论使我获益匪浅。并且许君正在研发的五子棋对奔软件 乜让人高度期待。还要感谢从未谋面的 Pham Hong nguyen。就是在他放在 多仑多相棋协会网站的对弈程序,使我在Java调试器中第一次见到了Zo brit哈希、历史启发、迭代深化、静止期搜索等不可或缺的技术。让我在日 后接触到论述相关问题的资料时都能够有清晰透彻的理解。这个绝佳范例 冋机器博弈领域先行者们的文軾仿佛是两面相互照亮的镜子,隔着吋间和 空间的河流,驱散了一个求知者眼中的迷茫。 2002年7月 第一章引言 1.1人机博弈的要点 录 1.2棋盘表示( Beard Represtnlalions)......... 走法产 1.4搜索技术( Search Techniques) 1.5佔值(Ev 1.6本书的布局.................................... 1.7其他话题 1.8关于范例程序... 第二章棋盘表示.................. 2.1基本表示方法.............................................8 2.2比特棋盘( Bit boaro 第二章走法产生 3.1如何产生..................... 3.2效率问题 13 3.3逐个产生V全部产生 3.4内存的使用... 第四章基本搜索技术 4.1博弈树 4.2极大极小值算法( Minimax algorithm)... 4.3深度优先搜索( Depth First Search).........20 4.4负极大值算法( Negamax Algorithm)........................22 第五章估值基础... 5.1棋子的价值评估......... 5.2棋子的灵活性与棋盘控制..................... 5.3棋子关系的评估 5.4与搜索算法配合..................... 第六章实例研究............................................................29 数据衣示......... 6.2走法产生器.........................................................32 6.3搜索引等 6.4估值核心 6.5操作界面....................................... 6.6试用... 第七章搜索算法的改进.............................................101 7.1 alpha-Beta拽索 范例裡序.................. 105 7.2Fail- soft alpha-beta.....................110 范例程序... 7.3渴望搜索( Aspiration Seareh) ...............·114 范例程序 115 7.4极小窗口搜索( Minimal window search/PVs)... 范例程序 119 7.5置挨表( Transposition Table) 122 7.6哈希表( Hash table)............... 123 应用置换表的其他问题....................................125 7.7 Zobrist哈希技术... 范例裡序............ .......................................128 7.8迭代深化( Iterative Deepening).....................138 范例程序......................................................139 7.9历史启发( The History Heuristic)...............142 范例程序 7.10杀手启发( Killer hcuristic)............... 7.11SSS*/DUAL*算法........................... 152 7.12SSS*与 Alpha-Bcta...... ............155 7.13MTD(f)算法 范例程序............ 7.14综合运用 第八章估值核心的优化 8.1估值函数的速度 172 8.2估值数与博弈性能 173 8.3估值瞅数的内容及其调试 第九章其他重要的话题... 9.1水平效应 180 9.1.1静上荆搜索( Quiescence searh)... 9.1.2扩展搜索( Search exleusiuns)...... ...·181 9.2开局库( Opening Book) 182 93残局厍( Endgame database) ........................183 9.4循环探测( Repetition Detection) 184 9.5代码的优化( Code Optimization) 185 9.5.1优化的阶段及地方......... 9.5.2函数周用的时间开销... 186 9.5.3查表代替计算... 186 9.5.4交叉递归... 9.5.5内存管理的时间开销 ...189 6其他方法................................................190 96.1轻视因子( Contempt Factor)...............190 96.2机器学习( Machine learning)... 中垂,中中 96.3并行搜索... 9.6.4围棋 191 第十章五子棋对弈的程序实例......... 10.1概述 194 10.2数据表 194 10.3走法产生器............ 196 搜索引擎 5估值核心 10.6操作界面...... 10.7试用 附录术语表.............................. 参考文献 253 决乐写游戏轻松学编程 PC游戏编程(人机博弈) 王小春编著 重庆大学出版社 内 容提要 本书是一本专论机器溥弈的作品。详细披露了编写人机对弈程序的原理,技术和各 种相关内容。包含个完整的中国象棋人机对弈程序和个完整的五」棋人机对弈程序 实例。毫保留的展示了估值核心,烂法产生,以及约十种不同的搜索引擎,彻底解析了 高性能博弈程序的秘密所在。实用性是本书的最人特点,本书的目标是让一个粗通程序 设汁的人在一个冂内写出令人惊讶的人机傅弈稈序。完全没有一般人工智能书籍晦涩难 懂的感觉 图书在版编目(CIP)数据 PC游戏编程(人机博弈)/王小春编著.一重庆:重庆大学出版社,2002.5 快乐写游戏轻松学编稈) ISBN7-5624-26449 I.P...II.王..III.游戏一应用程序一程序设计IV.G899 中国版本图书馆(P数据核字(2002)第0)35762 快乐写游戏轻松学编程 °C游戏编程(人机博弈) 陈其总策划 :小春 著 责任编辑:陈其 版式设计:吴庆渝 责仁校对:廖应碧 责仃印制:张永洋 重庆大学出版社出版发行 出版人:张鸽盛 社址:重庆市沙拌圳正街174号重仄大学(A区)内 邮编:400044 电话:(023)6510237865105781 传真:(023)6510368665105565 网计http://www.cqup.com.cn 邮箱:〔k@c甲.cum.cn(市场营销部) 全国新华书店经销 重庆升光电力印务有限公司印刷 开本:787×10921/16印张:16.25字数:418千 2002年6月第1版 2002年6月第1次印刷 印数:1~5000 ISBN7562426449TP·370定价:38.00元(含1CD) 本书如有印刷、装订等质量问题,本社负责调换 版权所有翻印必究 game o m Putel 第 引