AI五子棋程序设计

课程名称：人工智能项目名称：人工智能之五子棋程序设计专业班级：计算机科学与技术学号：2014510287学生姓名：冯婧指导教师：谢红薇2014年12月7日大数据的关键技术一、大数据环境下的数据处理需求大数据环境下数据来源非常丰富且数据类型多样，存储和分析挖掘的数据量庞大，对数据展现的要求较高，并且很看重数据处理的高效性和可用性。二、传统数据处理方法的不足传统的数据采集来源单一，且存储、管理和分析数据量也相对较小，大多采用关系型数据库和并行数据仓库即可处理。对依靠并行计算提升数据处理速度方面而言，传统的并行数据库技术追求高度一致性和容错性，根据CAP理论，难以保证其可用性和扩展性。传统的数据处理方法是以处理器为中心，而大数据环境下，需要采取以数据为中心的模式，减少数据移动带来的开销。因此，传统的数据处理方法，已经不能适应大数据的需求！三、大数据的处理流程包括哪些环节？每个环节有哪些主要工具？大数据的基本处理流程与传统数据处理流程并无太大差异，主要区别在于：由于大数据要处理大量、非结构化的数据，所以在各个处理环节中都可以采用MapReduce等方式进行并行处理。四、大数据技术为什么能提高数据的处理速度？大数据的并行处理利器——MapReduce。大数据可以通过MapReduce这一并行处理技术来提高数据的处理速度。MapReduce的设计初衷是通过大量廉价服务器实现大数据并行处理，对数据一致性要求不高，其突出优势是具有扩展性和可用性，特别适用于海量的结构化、半结构化及非结构化数据的混合处理。MapReduce将传统的查询、分解及数据分析进行分布式处理，将处理任务分配到不同的处理节点，因此具有更强的并行处理能力。作为一个简化的并行处理的编程模型，MapReduce还降低了开发并行应用的门槛。MapReduce是一套软件框架，包括Map（映射）和Reduce（化简）两个阶段，可以进行海量数据分割、任务分解与结果汇总，从而完成海量数据的并行处理。MapReduce的工作原理其实是先分后合的数据处理方式。Map即“分解”，把海量数据分割成了若干部分，分给多台处理器并行处理；Reduce即“合并”，把各台处理器处理后的结果进行汇总操作以得到最终结果。如右图所示，如果采用MapReduce来统计不同几何形状的数量，它会先把任务分配到两个节点，由两个节点分别并行统计，然后再把它们的结果汇总，得到最终的计算结果。MapReduce适合进行数据分析、日志分析、商业智能分析、客户营销、大规模索引等业务，并具有非常明显的效果。通过结合MapReduce技术进行实时分析，某家电公司的信用计算时间从33小时缩短到8秒，而MKI的基因分析时间从数天缩短到20分钟。说到这里，再看一看MapReduce与传统的分布式并行计算环境MPI到底有何不同？MapReduce在其设计目的、使用方式以及对文件系统的支持等方面与MPI都有很大的差异，使其能够更加适应大数据环境下的处理需求。五、大数据技术在数据采集方面采用了哪些新的方法1、系统日志采集方法很多互联网企业都有自己的海量数据采集工具，多用于系统日志采集，如Hadoop的Chukwa，Cloudera的Flume，Facebook的Scribe等，这些工具均采用分布式架构，能满足每秒数百MB的日志数据采集和传输需求。2、网络数据采集方法：对非结构化数据的采集网络数据采集是指通过网络爬虫或网站公开API等方式从网站上获取数据信息。该方法可以将非结构化数据从网页中抽取出来，将其存储为统一的本地数据文件，并以结构化的方式存储。它支持图片、音频、视频等文件或附件的采集，附件与正文可以自动关联。除了网络中包含的内容之外，对于网络流量的采集可以使用DPI或DFI等带宽管理技术进行处理。3、其他数据采集方法对于企业生产经营数据或学科研究数据等保密性要求较高的数据，可以通过与企业或研究机构合作，使用特定系统接口等相关方式采集数据。目录一、五子棋基本规则...........................................................................-1-二、五子棋常用术语...........................................................................-1-三、五子棋程序设计...........................................................................-4-1.程序设计思想.............................................................................-4-2.程序设计分析.............................................................................-4-四、五子棋算法分析...........................................................................-5-1.人机对弈算法概述.....................................................................-5-2.数据结构设计.............................................................................-5-3.获胜组合情况分析.....................................................................-5-4．棋型的估值分析.......................................................................-6-5.Alpha–Beta搜索函数...........................................................-7-6.五子棋算法之胜负判断...........................................................-8-五、java五子棋程序...........................................................................-9--1-人工智能之五子棋程序设计——算法详解一、五子棋基本规则(1)五子棋行棋时，黑棋先下第一子，后白棋在黑棋周围的交叉点落子，之后黑白双方相互顺序落子。(2)最先在棋盘线交点横向，纵向，斜向形成连续的五个棋子的一方为胜。二、五子棋常用术语(1)阳线：棋盘上可见的横线与直线的总称。(2)阴线：也称“斜线”，是棋盘上不可见的斜行线。(3)单子：一个棋子。(4)成五：同一色的五子连成一线，胜利。如图1所示。●●●●●图1五子棋“成五”图(5)活四：形成四子相连，并且两端是都没有子的。如图2所示。●●●●-2-图2五子棋“活四”图(6)冲四：形成四子相连，并且有一端是有对方棋子或者是边界，而另一端是没有子的。如图3所示。●●●●★●●●●图3五子棋“冲四”图(7)活三：形成三子相连，并且两端是都没有子的。如图4所示。●●●●●●图4五子棋“活三”图(8)死三：形成三子相连，并且有一端是有对方棋子或者是边界，而另一端是没有子的。如图5所示。-3-●●●★●●●图5五子棋“死三”图(9)双三：出现两次下面这种情况，同一色的三子连成一线，一端为空棋位或同一色的子，另一端为空棋位。如图6所示。●●●●★●●图6五子棋“双三”图(10)活二：形成两子相连，并且两端是都没有子的。如图7所示。●●●●-4-图7五子棋“活二”图(11)死二：形成两子相连，并且有一端是有对方棋子或者是边界，而另一端是没有子的。如图8所示。●●★●●图8五子棋死二”图三、五子棋程序设计1.程序设计思想(1)本程序要实现五子棋的游戏功能，必须先有一个棋盘。所以，通过继承JPanel，然后在JPanel上画出一个棋盘。另外还需要四个按钮：开局、棋盘、模式（人机对弈和人人对弈）、退出，提醒用户进行相应的操作。当然，JPanel必须放在JFrame中，所以，又通过继承JFrame得到一个实例。(2)对于下棋的操作，通过对JPanel增加鼠标事件监听器MouseListener，每次当用户点击鼠标时，先取得点击的坐标值，然后换算成对应棋盘上（即棋盘数组）的位置（数组的下标）。(3)判断此处是否已经有棋子，如果有则提示玩家重新下子，否则通过java里的画图函数在此处画上棋子，重新刷新输出棋盘。(4)判断该颜色棋子的上下左右是否满足连续五个，是的话提醒相应玩家获胜，不是的话，更换玩家下棋。(5)对于玩家的更换是程序自动的，每次用户点击鼠标后，若本局还未结束则会变换玩家，从而画出对应黑方白方的棋子，直到有一方获胜程序结束。2.程序设计分析(1)本款游戏有“游戏”、“视图”和“帮助”三个选项，其中“游戏”包括开局、棋盘、模式、退出四个选项；视图里边则包括Metal、Motif、Windows三个选项，玩家可以根据具体需要选择使用。(2)绘制棋盘，用户可根据需要自行选择棋盘大小。(3)首先程序会判断对弈模式是人机对弈还是人人对弈模式，若是人机对弈则是玩家先-5-下，玩家是黑方，电脑是白方。若是人人对弈，则是黑方先下，黑白交替下子。(4)棋盘处于鼠标监听状态，当鼠标在棋盘上有点击操作的时候，程序会获得鼠标点击的坐标然后换算成对应的棋盘的位置，再判断此处是否有棋子。假如没有，那么在此处画出对应颜色的实心棋子；假如已经有棋子了，则提示玩家此处已经有棋子请重新下棋。(5)当选择的是人机对弈模式的时候，轮到电脑下子时，电脑会通过算法来计算每个没有棋子的位置的分数，从而来选择最重要的位置下子。四、五子棋算法分析1.人机对弈算法概述人工智能五子棋游戏最核心的地方就是算法，因为这是整个程序最难的模块。算法的中心思想是：利用分数代表每个位置的重要程度，越重要的位置的分数值会越高，当电脑下棋时会先将电脑和玩家棋型的分数分别计算一遍，然后选择二者中分数最高的点下子。如果玩家的分数高，那么代表电脑应该防守，如果电脑的分数高，那么代表电脑应该进攻。2.数据结构设计以10×10大的棋盘为例：(1)两个获胜表（[10][10][192]）：也就是获胜组合，因为五个子一线则胜，不在一线上的五个子就不在一个组合中，对于10×10的棋盘获胜的组合有192种（下面将会详细说明），获胜表用来表示棋盘上的每个位置是否在玩家或计算机的获胜组合中。(2)一个二维数组（[2][192]）：记录玩家与计算机在各种获胜组合中填入了多少棋子。(3)两个10×10的数组：用来记录玩家与计算机在各个棋盘位置上的分数，分数高的将是计算机下一步的走法。3.获胜组合情况分析●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●图910×10棋盘获胜组合情况(1)垂直方向：垂直方向上获胜组合数为10×6=60种；(2)水平方向：水平方向上获胜组合数为10×6=60种；-6-(3)两个倾斜方向：倾斜方向上获胜组合数为(1+2+3+4+5)×2+6=36种。所以10×10的五子棋棋盘所有的获胜组合为：60*2+36*2=192种。4．棋型的估值分析不同的棋型，其优先级不同。例如，四个棋子连成一线且还能继续落子的棋型（活四）显然要比只有三个棋子连成一线（活三或死三）好。要使计算机正确地做出这种判断，就要把第一种棋型的估值设高。事实上，对于每一种特定的棋型，都需要相应的估值来反映其优劣情况。另外，由于搜索模块频繁地调用估