[VC]智能五子棋算法的设计与实现 | 毕业设计范例

【引言】

当电脑进入我们的生活中，许多与相关学科都欣欣的向上发展。典型的有电子商务、电子邮件等。当然也有人智能了。人们在惊叹机器人高效的工作时，也会想起自己聪明的一面。人工智能也这方面也就深受我们喜爱。

随着近几十年来人工智能的飞速发展，越来越多的具有智能的机器进入了人类的生活，人工智能的重要性如今显而易见。因此我想通过五子棋的电脑AI设计从而对人工智能中人机博弈方面有一个初步的认知并且也可以让我在简单的人机博弈全局设计以及具体到相关算法上有了深入的了解。      

五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”，英译为“Ren-ju”，英文称之为“Gobang”或“FIR”(Five in aRow的缩写)，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。五子棋不仅能增强思维能力，提高智力，而且变化多端，非常富有趣味性和消遣性，因此为人民群众所喜闻乐见。

1.绪论

1.1人机博弈初涉

人工智能是一门正在迅速发展的新兴的综合性很强的交叉科学，其属于计算机科学的领域，它以计算机技术为基础，近几十年它的应用领域也正在不断扩大。它的中心任务是研究如何使计算机去做那些过去只能靠人的智力才能做的工作，并运用计算机强大的计算能力快速解决问题。人工智能在机器人学习、模式识别、物景分析、数据库的智能检索、博弈论问题和家用电器智能化等领域都有广泛的应用。而本次设计就是和人工智能中的博弈论领域紧密相关的。博弈为人工智能提供了一个很好的试验场所，人工智能中许多概念和方法都是从博弈程序中提炼出来。人工智能中大多以下棋为例研究博弈规律。

在这里所抽象化后的博弈问题是，已知参与者集合(两方)，策略集合(所有棋着)，和盈利集合(赢子输子)，最终是想去找到一个理论上的解或平衡，也就是对参与双方来说都最合理、最优的具体策略。

应用传统决定论中的“最小最大” 准则，即博弈的每一方都假设对方的所有功略的根本目的是使自己最大程度地失利，并据此最优化自己的对策，冯·诺依曼从数学上证明，通过一定的线性运算，对于每一个二人零和博弈问题，都是能够找到一个“最小最大解”的 ，而这个简单的博弈思想，也即是人机博弈中最基础的组成部分，通过假设对手必定选取它所能选择的最优解来实现。

然而如何使计算机更智能更快速的反馈出最优解的方法仍然没有最好的解决办法，贝尔实验室的克劳迪·香农(Claude Shannon)是和图灵同时代的另一位伟大的数学家，他一直在探索教电脑下棋。他认识到问题在于棋步数量大得可怕，因此把搜索所有棋步的“A策略”和剔除某些变化路线的“B策略”区分开来。如今我们也区分“强行搜索”和“选择搜索”程序，尽管所有强大的程序或多或少属于前者。

第一个突破出现在1958年，匹兹堡大学的三位科学家奈维尔、肖恩和西蒙(Newell, Shaw and Simon)有重大发现：可以从搜索树中剔除相当大的部分而不影响最后结果，他们把这叫Alpha-beta算法。很重要指出的是，这是一个纯数学领域的技巧，独立于任何国际象棋知识而生效。

趁着这个机会，对人工智能中比较容易实现的人机博弈进行了解研究学习，也是很实用且很有必要的。而其中的博弈问题为搜索策略，机器学习等问题的研究课题提供了很好的实际背景，而且博弈问题自身也不断提出了一些新的研究课题，从而推动了人工智能的研究和发展。