五子棋算法研究

《五子棋算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、五子棋算法研究信息与计算科学2003级蔡杰指导教师汪建副教授摘要：人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学。博弈是人工智能的主要研究领域之一，他涉及人工智能中的推理技术、搜索方法和决策规划。本文将这些技术用于五子棋中。设计了一个智能五子棋系统，实现人和计算机两方进行博弈。关键词：五子棋，人工智能,搜索GobangalgorithmtoresearchCAIJieInformationandComputationalScience,Grade2003DirectedbyWANGJian(AssociateProfessor)Abstract:Artificialintellig

2、enceisanewly-developedandhighlycomprehensivefrontierscienceofrapiddevelopment.Gamblingandchessisoneofthemajorartificialintelligenceresearchareas・11involvesreasoning,decision一makingandplanning・Thesetechniquesareappliedtothegobang.Anintelligentgobangsystemisdesignedandrealizedinthegamebetweenhumanan

3、dcomputer.Keywords:Gobang,Artificialintelligence,Search1绪论在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。在人工智能领域内，博弈是很重要的一个研究分支，很多实际问题可以在博弈的研究中得到解决，并且使计算机智能更加靠近人类智能。电脑博弈是人工智能研究的一个方向，到了近50年前，随着电子计算机的诞生，科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战，香农(1950)与图灵(1953)提出了对棋类博弈程序的描述，随着电脑硕件和软件的高速发展，从1980开始,电脑博弈便开始逐渐大规模地向人的智能发起了挑战，到了1997年，IBM

4、超级电脑DeeperBlue击败了当时国际象棋世界冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要旅程碑。1.1电脑五子棋简介五子棋是起源于中国古代的传统黑门棋种之一。现代五子棋口文称之为“连珠”，英译为Ren-ju,英文称之为“Goban『或“FIR"(FiveinaRow的缩写)，亦有“连五子”、“五了连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。五了棋不仅能增强思维能力，提高智力，而且变化多端，菲常富有趣味性5和消逍性，因此为人民群众所喜闻乐见。本文在研究博弈机器人系统过程中，对五子棋博弈算法进行了一些有效的研究，设计和实现一个人机对弈的五子棋程序。五子棋属于黑

5、白棋的一种，它的博弈树复杂度为1O70,状态空间复杂度为101()5o因此盘面预测的计算量是非常大的，比如对于五了棋的中盘走法中，如果要预测四步的局面数的话可以达到一百万。1.2设计思路总介绍本文是对五子棋算法的设计原理和实现方法进行探讨和研究，主要包括数据结构、搜索算法和优劣评价函数组成，主要的特点包括快速的数据结构设计实现、以及高效率的搜索算法和尽叮能的模拟人类的智能。1.3本文架构第一章将会阐述计算机

6、•専弈发展以及对电脑五了棋的介绍、电脑五了棋的状态空间复杂度以及文章架构。第二章首先描述了电脑象棋表示的一些基本数据结构。第三章将重点讲述博弈树的搜索方法，包括博弈树构建、各算法介绍、

7、以及五子棋规则的实现，最后对整体搜索框架进行总结。最后，第四章是全文的总结及展望。2数据结构2.1棋局的表示我们知道五了棋的走法中有优先和禁手，如连四肯定是没有三四优先，而如果是黑方出现三三(包插“四、三、三”)、四四(包括“四、四、三”)，而黑方只能以四三取腔，如果黑方走出禁手则是输；五连与禁手同时形成，先五为胜，等等的规矩。但是电脑毕竟不是人类，可以类人但是却不可以自己思考，那么就需要给电脑一个它可以明门的评判标准。首先介绍一个五子棋中的常用术语：阳线：棋盘上可见的横纵直线。阴线：棋盘上无实线连接的隐形斜线。活3：由于一方走一着在无子交义点上形成一个“活三”的局面，也就是在放一子就可行

8、成4连了。活4：在棋盘某一条阳线或阴线上有同色4子不间隔地紧紧相连，且在此4子两端延长线上各有一个无子的交叉点与此4子紧密相连。冲四：除〃活四〃外的，再下一着棋便可形成五连，并且存在五连的可能性的局面。由于篇幅有限不能将所有的规则讲完，只是提出了对讲算法有用的儿点加以叙述。如何让电脑知道该落子在哪一点呢，在这方而。电脑要做得和人一•样，判断棋盘上每一点的重要度。比如冲四比冲强，冲三比造二强，遇到四三如果是对方的，堵死，如