【作者】 闵文杰；

【导师】 廖晓峰；

【作者基本信息】 重庆交通大学 ， 计算机应用技术， 2010， 硕士

【摘要】 人工智能是计算机科学的一个重要分支,与能源技术、生物工程、空间技术等并称为当今世界的尖端科技。计算机博弈是人工智能研究的一个重要方面,人类对计算机博弈的研究衍生了大量的研究成果,这些成果对更广泛的领域产生了重要影响。随着计算机博弈在Othello、Checker和国际象棋等棋类上的成功,全世界的学者又把目光投到了中国象棋、日本将棋、围棋等更为复杂的棋类上面。六子棋(Connect6)作为一种二人零和完备信息博弈,与围棋有着相近的复杂度,成为学者们研究的焦点之一。六子棋计算机博弈的关键技术包括状态表示、走法生成、状态评估、搜索引擎、开局库建立、参数优化等,本文的主要工作是围绕走法生成、状态评估、搜索引擎、开局库建立等进行研究和改进,具体的工作内容和成果如下:1.比较研究常用的棋盘状态表示法的优缺点后,借鉴比特棋盘的思想,提出了一种适用于六子棋的改进后的比特棋盘。使用该数据结构,可通过位运算快速判断各种棋型。2.深入地研究了各种Alpha-Beta搜索及改进技术后,通过编程实现了这些算法,并比较了六子棋博弈程序中这些算法间的性能差异,发现其中MTD(f)算法的性能最好。3.通过分析搜索算法的工作过程,并结合六子棋走法生成的特殊性,提出了将走法生成模块中的预置表与搜索引擎中的置换表融合在一起的改进措施,极大地避免了在搜索过程中频繁地生成走法。同时还比较了改进前后的MTD(f)算法的性能差异,证明了改进措施的有效性。4.认真研究六子棋的特点后,提出了对六子棋棋型的新定义。使用该定义可极大地降低棋形的分类难度,从而提高估值函数的运行速度。5.针对新的棋型定义,设计了一种简单可行的棋型识别方法。同时还结合改进后的比特棋盘技术实现了基于该方法的快速而有效的估值算法。6.利用哈希技术设计了一个简单的开局库,搜集并录入了31种常见开局及其对称形式,同时还录入了4个开局的关键走法及其变化。本文的创新之处有以下几点:1.在状态表示中,改进比特棋盘,使之适用于六子棋博弈程序。2.在搜索引擎中,融合预置表与置换表,降低生成走法的时间耗费,提高了搜索算法的效率。3.在六子棋理论方面,提出了新的六子棋棋型定义,简化了棋型分类。4.在棋局评估中,提出了6-8窗口法,该方法可快速有效的判断各种棋型。该方法同时也利用在走法生成中,评估各空点的价值。更多还原

【Abstract】 Artificial Intelligence is an important branch of computer science, with energy technology, biotechnology, space technology, known as the world’s most advanced technology. Computer games are an important aspect of artificial intelligence research, a large number of research results have been made because of studies about computer game, these results had an important impact in wider areas. After the computer game has successed in Othello, Checker , chess and so on, scholars around the world again eyeing on the Chinese chess, Shogi, Go and other more complex chess. Connect6 as a two-person zero-sum perfect information game, has the similar complexity with Go, and become to the focus of research.The key technologies of Connect6 computer game include data structure, generating moves, evaluating state, search engine, opening bank and optimization of parameters, this paper’s main task is to research and improve generating moves, evaluating state, search engine, opening bank, the specific content of the work and results are as follows:1. Having a comparison of advantages and disadvantages of the current board state representations, and studying bit board’s thinking, a new improved bit board has been submitted and applied to the Connect6. Various chess-types can be quickly distinguished using‘and’operation provided by the new bit board.2. After having in-depth study of some varieties of Alpha-Beta Search and technology used to improve it, I programed these algorithms, and compared the difference of performance between these algorithms while be used in the Connect6 game program, and founded that MTD(f) algorithm has the best performance.3. By analyzing the work process of the MTD(f) search, and the special moves generation in the Connect6, I proposed to make the preset table in the moves generation module and the transposition table in the search engines together as a improvement, this improvement can reduce the frequent of generating moves in the search process. And by comparing the performance of different MTD(f) algorithms before and after improved, proved the effectiveness of the improvement measures.4. Through seriously studying the characteristics of Connect6, raised some new definitions of Connect6 chess-type. Using the definitions can greatly reduce the difficulty of chess-type classification, and improve the operating speed of the evaluation function.5. Basing on the new chess-type definitions, designed a simple and feasible method of chess-type identification, and proved the correctness of the method. Also realized a rapid and efficient evaluation algorithm basing on the method and the improved bit board.6. A simple opening bank has been designed and realized using hashing table technology, including 31 kinds of openings and their symmetrical forms, and also including the key moves to four bad openings among them and some diversifications following the key moves.The innovations of this paper are as follow:1. In the state representation aspect, A new bit board which was improved from the chess bit board was raised to apply to the Connect6 game program.2. In the search engine aspect, by using the preset table and the transposition table together, reduced the time spent to generate moves, and improved the efficiency of the search algorithm.3. In the Connect6 theory aspect, put forward some new definitions of Connect6 chess-type, and simplified the chess-type classification.4. In the Connect6 game situation evaluation aspect, proposed a 6-8 window method, this method can be used to quickly and effectively identify the chess-type. This method is also used in the generating moves and the evaluation of the value of the empty spots.更多还原