计算机五子棋博奕系统的研究与实现

    人工智能是近年来很活跃的研究领域之一。计算机博弈是人工智能研究的一个重要分支,它的研究为人工智能带来了很多重要的方法和理论,产生了广泛的社会影响和学术影响。国内外对博弈的研究已经较为广泛,特别是IBM的国际象棋程序“深蓝”,已经达到了人类的世界冠军水平。“深蓝”的研究成果,特别是基于剪枝的极大极小树搜索技术为设计其它的计算机棋类博奕系统提供了良好的参照。但是不同的棋类博奕,其规则的千差万别赋予了每一种棋类博奕特殊的专业知识。这就必然要求设计一个具体的棋类博奕系统时应该深入研究它的基本原理和内在规律。 本文以计算机五子棋博奕系统做为研究课题,在对大量的相关文献进行分析研究的基础上,首先按照人工智能和计算机博奕的一般原理设计了一个五子棋博奕系统的基本模型,所做的工作包括三个方面: 第一研究了五子棋在计算机中的表示问题,讨论了计算机中存贮棋局和识别下棋次序,局势状态变化及局势特征、走法产生等方法。 第二研究了博弈树的极小极大搜索技术及在此基础上的Alpha-Beta剪枝过程和剪枝优化问题。实现将候选的后继节点按位置邻近顺序排序,使剪枝过程得到优化。此外还研究了Alpha-Beta剪枝的改进算法NegaScout算法,此算法首先采用一小的有限Alpha-Beta窗口,以确定实际估计值的范围,再在这个较小的范围中搜索实际的估计值。由于在较小的范围中搜索,效率能得以提高。 第三根据五子棋的特点,提取棋局局势的若干特征,对这些特征赋加权分,并对整个棋局进行特征统计,采用一个线性函数求得棋局的总估计分值。实践中,采用极小极大搜索加此静态估值技术的初版程序,达到了比初学者强的水平,一些比较熟练的业余人员时常也会负于此程序。 在上述工作的基础上,本文的创新性研究主要包括以下两个方面: 第一对五子棋博奕的专业知识进行了认真的整理,针对五子棋博奕规则简单、局势判断清楚的特点,对五子棋常见的开局、定式及其后的对局做了细致的统计分析,阐明了五子棋对奕中黑白双方优劣势并非均衡的规律,这一规律作为一个指导原则在设计五子棋博奕系统时起到重要作用。 第二针对初版程序中存在的缺点和不足,通过查找原因,实现了算法的优化和加强。初版程序在运行时其搜索速度和对奕表现不能让人满意。其主要原因有两个:使用常规的Alpha-Beta搜索和NegaScout算法不能避免相同局面的重复节点的搜索,从而影响搜索速度;采用固定的估值法,估值的不准确使其“智力”较低,而且固定的赋值方式使其不能在对奕过程中提高棋力。解决的方法有两个:在执行常 

 

 

【学位级别】：硕士

 

页数：59

 

中文摘要

Abstract (英文摘要)

第一章 绪论

    1.1 选题背景

    1.2 计算机博弈研究简史

    1.3 计算机博弈的研究意义

    1.4 计算机博奕的过程

    1.5 五子棋发展简史与基本知识介绍

    1.6 课题主要工作

第二章 五子棋博奕的理论研究

    2.1 五子棋博奕的不同形式

    2.2 五子棋博奕黑白双方优劣势的分析

    2.3 策略的选择

第三章棋盘状态空间表示与走法产生

    3.1 棋盘局势状态表示

    3.2 棋盘中下棋的顺序表示

    3.3 状态的变化

    3.4 特征的表示

    3.5 走法的产生

第四章 博弈树的搜索技术

    4.1 极大极小树搜索算法

    4.2 Alpha-Beta 剪枝过程

    4.3 Alpha-Beta 剪枝存在的问题及优化

    4.4 NegeScout 搜索

第五章 静态估值函数

    5.1 棋盘局势特征

    5.2 估值

    5.3 静态估值函数的不足及实践效果

第六章 搜索算法的优化与增强

    6.1 置换表的搜索

        6.1.1 哈希表

        6.1.2 应用置换表的其它问题

        6.1.3 Zobrist 技术

    6.2 威胁空间搜索

        6.2.1 专业术语和“威胁次序”

        6.2.2 人类专业棋手的分析

        6.2.3 计算机程序的策略

        6.2.4 人与计算机

        6.2.5 威胁空间搜索

        6.2.6 算法优化后效果的检验

参考文献

致谢

在读期间发表的论文和