六子棋计算机博弈系统的研究与实现摘要：本文简述了目前计算机博弈技术的发展状况，通过将六子棋游戏作为计算机博弈技术的研究平台，提出了六子棋计算机博弈的概念。通过对国内外相关研究现状的综述，指出本课题研究的意义。通过借鉴国际象棋和中国象棋计算机博弈中的成熟技术，提出了建立六子棋计算机博弈系统的关键技术。关键词：人工智能；六子棋计算机博弈；状态表示；着法生成；棋局评估；博弈树搜索；开局库1引言人工智能诞生50周年以来，在知识工程、模式识别、机器学习、进化计算、专家系统、自然语言处理、数据挖掘、机器人、图象识别、人工生命、分布式人工智能等各个领域得到了蓬勃的发展[1]。计算机博弈作为人工智能领域的一个重要分支，也得到了极其快速的发展，并为人工智能带来了很多重要的方法和理论，同时也产生了广泛的社会影响和学术影响以及大量的研究成果。博弈就是对策[2]，是自然界中的普遍现象，它不仅存在于游戏、下棋之中，而且存在于政治、经济、军事和生物竞争中，博弈的参加者可以是个人、集体、某类生物或机器，他们都力图用自己的智力去击败对手。体现计算机博弈技术的各种棋类游戏在其博弈技术研究中已取得相当丰硕的成果，且各种棋类游戏的计算机博弈系统也日趋完善，基本上能达到大师级水平。六子棋作为最近两年才兴起的棋类游戏，其计算机博弈技术和算法的研究相对较少[3]。2六子棋计算机博弈的研究意义人们常常把计算机博弈描述为人工智能的果蝇，即人类在计算机博弈的研究中衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。通过博弈问题来研究人工智能典型问题，具有以下的优点[4]：（1）博弈问题局限在一个小的有典型意义的范围内，研究容易深入。（2）博弈问题非常集中的体现了人类的智能，已经足以为现实世界提供新的方法和新的模型。（3）专家经验容易获取。（4）进展可以精确的展示和表现出来，不同方法和模型的优缺点也容易比较。用一棵树来表示棋局发展的种种可能性，这种树叫做博弈树。根节点表示对局的开始状态，每一种可能的走法造成的结果作为其子节点，而对每一个这样的子节点，考虑另一方的各种可能应对，作为下一层的子节点，这样一直找下去就得到了博弈树。它是一棵与或树。这是一个典型的指数复杂性问题，如何在这棵树上有效的搜索，找出最佳或满意的目标，是研究的主要问题。由于机器速度和存储空间的限制，这种搜索只能进行到某一深度，得到一个层的子树。对于这一子树的叶节点进行某种评价，然后用搜索的方法找出最优解或满意解，这就是计算机博弈的主要方法。在博弈研究的早期阶段，人们使用这种方法研究博弈问题，主要的研究内容是[5][6]：（1）评价的效率更高，评价要花费时间和空间的代价，如何建立有效、快速的评价函数和评价方法。（2）找最佳解（在生成的子树上）的过程更为有效，由此发展了各种搜索法。在五、六十年代，博弈研究是人工智能研究的带头领域，Alpha-Beta剪枝、启发搜索[7]最初就是由博弈树的研究发展而来的。专家系统[8]的方法出现以后，研究者在产生树的过程中引入专家知识，使得不必要的节点不再产生，并以此来改进程序的效率。博弈研究的另一个成果是在六十年代就引入了机器学习[9]，使机器自己不断改进自己的博弈水平：（1）最简单的学习是改进评价函数的一些参数，使之更加精确和实用。（2）记忆自己和别人的错误，不再犯已犯过的错误。（3）记录一些常见的形状和模式，以便找出局部最好的应对。（4）自己学习规则。这些研究对于人工智能的发展起了很大的推动作用。不完备信息博弈的研究还推动了不精确信息、模糊信息推理和复杂环境决策的研究过程。由于博弈不能避免搜索，而搜索对时间的要求较高，所以博弈一直是研究并行算法、并行体系结构的工具。人们通过博弈的研究还提出了认知心理学上的很多新课题，对认知心理学产生了影响。有些博弈项目为一些新模型与新方法的研究提供了帮助。例如，Backgammon就对神经网络的发展做出了贡献。计算机博弈中指定决策和选择决策，与政治、军事、经济、日常生活中的决策有很多类似之处，是一种典型的决策系统，所以它的研究对于建立现实社...
