文档介绍：五子棋算法研究信息与计算科学2003级蔡杰指导教师汪建副教授摘要:人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学。博弈是人工智能的主要研究领域之一,他涉及人工智能中的推理技术、搜索方法和决策规划。本文将这些技术用于五子棋中。设计了一个智能五子棋系统,实现人和计算机两方进行博弈。关键词:五子棋,人工智能,putationalScience,Grade2003DirectedbyWANGJian(AssociateProfessor)Abstract:Artificialintelligenceisanewly-,decision一makingandplanning・:Gobang,Artificialintelligence,Search1绪论在人类文明发展的初期,人们便开始进行棋类傅弈的游戏了。在人工智能领域内,傅弈是很重要的一个研究分支,很多实际问题可以在博弈的研究屮得到解决,并且使计算机智能更加靠近人类智能。电脑博弈是人工智能研究的一个方向,到了近50年前,随着电子计算机的诞生,科学家们开始通过屯脑模拟人的智能逐步向人类智能发起挑战,香农(1950)与图灵(1953)提出了对棋类博弈程序的描述,随着电脑硬件和软件的高速发展,从1980开始,电脑博弈便开始逐渐大规模地向人的智能发起了挑战,到了1997年,IBM超级电脑DeeperBlue击败了当时国际象棋世界冠军卡斯帕罗夫,成为了人工智能挑战人类智能发展的一个重要旅程碑。。现代五子棋口文称之为“连珠”,英译为“Ren・jiT,英文称之为"Gobang”或"FIR^FiveinaRow的缩写),亦有"连五子"、"五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。五子棋不仅能增强思维能力,捉高智力,而且变化多端,非常富冇趣味性和消逍性,因此为人民群众所喜闻乐见。本文在研究博弈机器人系统过程中,对五了棋博弈算法进行了一些有效的研究,设计和实现一个人机对弈的五子棋程序。五子棋属于黑口棋的一种,它的I専弈树复杂度为1O70,状态空间复杂度为10心。因此盘面预测的计算量是非常大的,比如对于五子棋的中盘走法中,如果要预测四步的局面数的话可以达到一百万。,主耍包括数据结构、搜索算法和优劣评价函数组成,主耍的特点包括快速的数据结构设计实现、以及高效率的搜索算法和尽口J能的模拟人类的智能。、电脑五子棋的状态空间复杂度以及文章架构。第二章首先描述了电脑象棋表示的一些基本数据结构。第三章将重点讲述博弈树的搜索方法,包括博弈树构建、各算法介绍、以及五子棋规则的实现,最后对整体搜索框架进行总结。最后,第四章是全文的总结及展望。,如连四肯定是没有三四优先,而如果是黑方岀现三三(包捋四、三、三”)、四四(包括“四、四、三”),I何黑方只能以四三取胜,如果黑方走出禁手则是输;五连与禁手同时形成,先五为胜,等等的规矩。但是电脑毕竞不是人类,可以类人但是却不可以自己思考,那么就需要给电脑一个它可以明白的评判标准。首先介绍一个五子棋中的常用术语:阳线:棋盘上可见的横纵直线。阴线:棋盘上无实线连接的隐形斜线。活3:由于一方走一着在无子交叉点上形成一个“活三”的局而,也就是在放一子就可行成4连了。活4:在棋盘某一条阳线或阴线上有同色4子不间隔地紧紧相连,11在此4子两端延长线上各有一个无子的交叉点与此4子紧密相连。冲四:除〃活四〃外的,再下一着棋便可形成五连,并且存在五连的可能性的局面。由于篇幅有限不能将所有的规则讲完,只是捉岀了对讲算法有用的几点加以叙述。如何让电脑知道该落了在哪一点呢,在这方面。电脑要做得和人一样,判断棋盘上每一点的重要度。比如冲四比冲强,冲三比造二强,遇到四三如果是对方的,堵死,如果是自己的,优先落子。遇到双三,如果是黑棋,黑方输,如果是白棋,优先等级仅次于四三。我们看到电脑在运算的时候,同种棋型在敌我双方的优先等级并不相同,由于禁手的缘故黑棋和白棋的处理也不相同。同样是四三,如果是玩家的,则电脑不会冲自己的,而是先堵玩家的。禁手的处理比较复杂,我们稍候讨论。下面,我