《毕业设计（论文）五子棋人机对弈程序设计.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）五子棋人机对弈程序设计.doc（49页珍藏版）》请在三一办公上搜索。
1、五子棋人机对弈程序摘要：五子棋程序由两个主要部分组成：一个估值函数和一个树状搜索算法。而程序依靠估值函数来判断对于一方来说什么局面是好而什么局面是坏，后者是用来搜索几乎全部可能的棋步次序，目的是为了找出对于程序来说是最佳的一条路线。人工智能电脑下棋模拟的是人类的智能，它的启发式搜索是边走边试探，即极大极小法。关键词：五子棋 人工智能 估值函数 树状搜索算法 极大极小法The program for Renju in man vs computerAbstract:The program for Renju is composed of two parts: a evaluation funct
2、ion and a hashtable tree-searching algorithm. The evaluation function is used to judge the advantage or disadvantage situation for each part, the hashtable tree-searching algorithm is used to search almost all the possible steps and find out the best pathway for the program. The computer of Artifici
3、al Intelligence (AI) imitate the intelligence of human, its inspiring search way is Go and Explore, namely, Minimax.Key words: Renju Artificial Intelligence (AI) evaluation function hashtable tree-searching algorithm Minimax五子棋人机对弈程序目录中文摘要英文摘要第一章 引言51.1本课题的研究意义51.2本论文的目的、内容及作者的任务5第二章 研究现状及设计目标72.1相近
4、研究课题的特点及优缺点分析72.2现行研究存在的问题及解决办法72.3本课题要达到的设计目标8第三章 要解决的几个关键问题93.1研究设计中要使用的知识93.1.1五子棋棋盘介绍93.1.2五子棋规则和术语的解释93.2研究设计中要解决的问题 133.2.1估值函数 133.2.2启发式搜索 133.3具体实现中采用的关键技术及复杂性分析 14第四章 系统结构与模型 164.1五子棋人机对弈程序流程图 164.2设计实现的策略和算法描述 164.2.1博弈树 164.2.2极大极小值算法（Minimax Algorithm）184.2.3 Alpha-Beta剪枝(Alpha-Beta Pur
5、ning) 194.3编程模型及数据结构 214.3.1棋盘及棋子表示 214.3.2编程模型及数据结构 22第五章 系统实现技术 255.1分模块详述系统各部分的实现方法 255.1.1初始化 255.1.2主循环控制模块 285.1.3玩家下子 295.1.4盘面分析填写棋型表 315.1.5电脑下子 315.1.6胜负判断 335.2关键技术的实现 37第六章 性能测试与分析 416.1系统运行所需的软件、硬件环境 416.2性能测试 416.2.1计算机与计算机对弈 416.2.2人与计算机对弈 426.3性能分析 42第七章 结束语 47参考文献48附录：程序清单（附光盘）第一章 引
6、 言1.1本课题的研究意义五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“連珠”，英译为“Renju”，英文称之为“Gobang”或“FIR”(Five in a Row的缩写)，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”，又有古典哲学的高深学问“阴阳易理”；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化渊远流长，具有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。它是中西文化的
7、交流点，是古今哲理的结晶近来随着计算机的快速发展，各种棋类游戏被纷纷请进了电脑，使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。而且这类软件个个水平颇高，大有与人脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力的代表；其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜爱。由于五子棋相对围棋、象棋而言简单一些，所以结合自己所学的人工智能课程和Visual C+ 编制了五子棋人机对弈程序。1.2本论文的目的、内容及作者的任务人工智能是一门广泛的交叉和前沿科学，从1956年正式提出人工智能学科算起，已有40多年历史。目前人工智能在发展过程中
8、既有突破但也面临很大的困难。人脑可以通过自学习、自组织、自适应来不断提高信息处理能力；而存储程序式计算机的所有能力都是人们通过编制程序赋予它的，与人脑相比是机械的、死板的和无法自我提高的。所以通过该程序设计也探讨一下该领域的问题。第二章 研究现状及设计目标2.1相近研究课题的特点及优缺点分析博弈，历来是人工智能（AI）的一个重要的研究领域 。早期人工智能的研究实践，正是从电脑下棋发端；人工智能的第一大应用成就，就是发展了能够求解难题的下棋程序。自从早期欺骗性的下棋机展出后，人们已被制造一台真正能下象棋机器的幻想深深迷住，直到电脑和人工智能时代拉开了帷幕，这一幻想才有了变成现实的可能性。人工智能
9、的先驱者们曾认真地表明过他们的信念：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。博弈是研究使自己取胜、战胜对手的策略。在决策过程中要对形势做出恰当的估计，搜寻各种可能的策略组合，通过对比分析确定对自己最有利的策略。其中运用到问题求解、启发式搜索等方法。2.2现行研究存在的问题及解决办法长期以来，人们对电脑下棋的原理普遍存在着误解，通常以为在电脑高速计算的威力下，可以毫不费力地算出双方所有可能的棋步，从中选择最优的方案。当时电脑下象棋之所以难突破，大概是计算机速度太慢的缘故。仔细思考一下，就会发现这种想法实
10、在太幼稚。假如有台机器正在与人对弈，那么它首先必须考虑下一步棋有哪几种可能的走法，对方又可能应哪几着棋。比如，机器可以出“兵”，也可以出“车”；人的应棋可能是跳“马”，也可能是让“后”斜着走5格，如此等等。然后，对应着每一种可能的回合，都必须分别一步步推算下去，一直算到能把人类棋手的“王”杀死的那一步为止。也就是说，电脑若想找到当前最优的走法，需要全广度全深度地搜索双方棋子所有的可能走法。即使能按图灵“估值函数”的方法计算优势，也必须算完可能走法的所有组合状态。搜索计算所有组合状态的后果是引出天文数字。有人曾作过这样的估算：国际象棋大师之间对弈的平均总棋步约为84步，任一种棋局状态下又有38种
11、合乎规则的可能走法。因此，穷举搜索所有的可能走法，面对的组合数将达到38的84次方之巨，它大于10的132次方，即1后面有132个0，与整个世界中原子的总数相近。我们知道，迄今为止宇宙大约才存在了10的18次方秒钟，估算出的组合数字表明，哪怕启用目前最高速的Pentium 4微电脑计算，恐怕算到宇宙毁灭的那一刻，还是算不出如何走第一步！2.3本课题要达到的设计目标要使程序达到6、7段棋力、且落子速度在2、3秒以内，是有一定难度，原因是五子棋的博弈树过于庞大，不剪枝的话，结点总数为225的阶乘，要让电脑考虑所有的结点，显然受限于空间和时间上。如果采用棋谱库，当然可以让电脑落子如飞，但同时也失去了
12、“电脑思考”的意义。本程序不采用棋谱库，用启发式搜索，做到前瞻5、6步棋，尽力击败对手。第三章 要解决的几个关键问题3.1研究设计中要使用的知识3.1.1五子棋棋盘介绍五子棋棋盘：棋盘正中一点为“天元”。棋盘两端的横线称端线。棋盘左右最外边的两条纵线称边线。从两条端线和两条边线向正中发展而纵横交叉在第四条线形成的四个点称为“星”。天元和星应在棋盘上用直径约为0.5厘米的实心小圆点标出。 以持黑方为准，棋盘上的纵轴线从左到右用英文字母AO标记。横行线从近到远用阿拉伯数字115标记。纵横轴上的横纵线交叉点分别用横纵线标记的名称合写成。如“天元”H8，四个“星”分别为D4、D12、L12、L4等。3
13、.1.2规则和术语的解释1、一着：在对局过程中，行棋方把棋子落在棋盘无子的交叉点上，不论落子的手是否脱离棋子，均被视为一着。 2、回合：双方各走一着，称为一个回合。 3、连：在棋阳线和阴线的任意一条线上形成的有5个或5个以上的同色棋子不间隔地紧紧相连。 五连：在棋盘上形成的5个同色棋子的“连”。 长连：在棋盘上形成的6个或6个以上同色棋子的“连”。 4、“四”包括“活四”和“冲四”。 A、活四：在棋盘某一条阳线或阴线上有同色4子不间隔地紧紧相连，且在此4子两端延长线上各有一个无子的交叉点与此4子紧密相连。（如下图）B、冲四：除“活四”外的，再下一着棋便可形成五连，并且存在五连的可能性的局面。
14、C、白棋再下一着可形成长连的局面也视为“四”。5、“三”指活三，包括“连三”和“跳三”。A、连三：在棋盘某一条阳线或阴线上有同色三子相连，且在此三子两端延长线上有一端至少有一个，另一端至少有两个无子的交叉点与此三子紧密相连。B、跳三：中间仅间隔一个无子交叉点的连三，但两端延长线均至少有一个无子的交叉点与此三子相连。6、禁手：对局中禁止使用的着法（白棋无禁手）。黑棋禁手包括“三三”、“四四”和“长连”。 三三：由于黑方走一着在无子交叉点上同时形成二个或二个以上黑方“活三”的局面。四四：由于黑方走一着在无子交叉点上同时形成二个或二个以上黑方“四”的局面。7、四三：指某一方同时具备两个先手，其中一个
15、是四，一个是活三。先手：对方必须应答的着法，其中冲四称为绝对先手。8、三手可交换：是指黑棋下盘面第3着棋后，白方在应白之前，如感觉黑方棋形不利于己方，可提出交换，即执白棋一方变为执黑棋一方，而黑方不可以不换。9、五手两打：是指黑棋在下盘面上关键的第5手棋时，必须下两步棋，让白棋在这两步棋中任选一步，然后再继续对弈。一般说来，白棋肯定拿掉对白方不利的一点，而保留对黑方较为不利的那点让黑方行棋。10、关于禁手 三三禁手 三三禁手 四四禁手 四四禁手 四四禁手 四四禁手(扁担阵) 四三三禁手 长连禁手11、关于非禁手A、“a”这一点不是三三，因为横向不是活三，而是一个长连禁手的骨架(日本称为“六腐”
16、)。B、“a”这一点也不是三三，因为横向也不是活三，而是一个假活三(此形状日本称之为“下止”)。C、“a”这一点有可能被看作是三三。但是，由于竖跳三的下一手在x点将成四四禁手而不能走，这种竖三属于死三，所以a点不算三三。 3.2研究设计中要解决的问题3.2.1估值函数估值是一个通过既有的棋类知识来评估一个局面优势的过程。这一过程对具体的棋类知识依赖程度很深，但是仍有一般性的规律可循。棋子的价值评估棋子的价值评估，简单的说就是评估双方都有哪些棋子在棋盘上。与搜索算法相结合3.2.2启发式搜索所谓启发式搜索，就是利用一个估价函数评估每次的决策的价值，决定先尝试哪一种方案。这样可以极大的优化普通的广
17、度优先搜索。以下以A*搜索为例进行说明。在各种搜索算法中，有一个A*搜索算法，也叫做最佳搜索算法，实际是一种启发式搜索，它是对于问题的各种情况设定一个估值函数，假设我们选择的是值最小的道路，在搜索的时候，A*算法根据估值函数判断下一步应选择的道路，并不停地用走过的实际路线的价值加上下一点的估值函数作为新的估值。当新的估值小于以前所做的另一条路线的估值的时候，改换到另一路线中重新进行估值和搜索，这倒有点像人下棋时的判断：看看这样走行不行，看到大概不行时，就换个办法再看看。理论上，如果估值函数永远小于实际路线的价值，那么，A*算法总可以找到最优解。但这样太困难。我们还可以有这样的想法：如果A*算法
18、的估值函数可以做到差不离的话，也许我们就可以找到一个比较好的走法。比如，如果A*算法能够把下一手的选择点降到平均 6步，计算一路变化所需的步数降到平均20步，那么总的计算量就变成了620=3.66*1015，这就已经接近于计算机可接受的计算量了。曾经设想过一个五子棋AI模型：把所有的棋子以连在一起的一块为基本单位，而后再根据棋子的形状，位置情况，赋予它强度、影响力等属性，用力学模型来分析全局势力范围，并据此选择下一手的大致位置。实际上这就是对A*算法估值函数的一种设想。3.3具体实现中采用的关键技术及复杂性分析1、估值函数问题求解空间中每一个节点对应于一个子目标。当解决每个子目标时可应用的知识
19、一般有多种选择（即有多条可用规则），为了比较优劣，通常需要定义一种反映其优劣程度的数值函数，称为估值函数。然后根据函数的大小来选择合适的知识，以提高问题求解的效率，这种策略称为估值函数策略。在五子棋程序中，需要计算双方的棋局优势，在哪些地方布防哪类棋子具有更大的威慑力。然后，把兵力优势和棋局优势用加权求和的数学式联系起来，构成某种形式的“估值函数”。余下的任务就是用“估值函数”来计算每一可能的合法棋步，寻找函数值最大即对自己最有利的那一步着法，当然，也要把诸如机动性、安全性等五子棋知识方面的内容包括在“估值函数”里。2、启发式搜索基于估值函数的搜索控制策略实际上是一种启发式搜索。这是因为确定估
20、价函数所依据的知识往往是经验的和直观判断的知识，这类知识通常称为启发式知识。启发式搜索也是边走边试探，每走一步，都设法计算当前棋局的各种可能走法及对手各种反应的得分，然后立足于对方应棋以后自己面临的最坏局势，寻找那种能够争取到的最好的结果，然后倒推回去选择满意的棋步，因而也叫做“极大极小分析法”。当然，搜索时需要向前思考若干步棋以后的状况，但由于受到电脑存储空间和速度限制，只能根据实际情况决定向前搜索的深度。启发式搜索不是一种程序算法，它也是人工智能一般性“问题求解”的主要技术。顺便提一句，在下棋策略中放弃“寻求最优”而代之“寻求满意”的思想，后来又被西蒙教授发扬光大，使之成为现代经济决策理论
21、的重要基石。第四章 系统结构与模型4.1五子棋人机对弈程序流程图开始（a）初始化（b）主循环控制模块（c）玩家下子（d）盘面分析填写棋型表（e）电脑下子（f）胜负判断结束轮到电脑轮到玩家否则五子棋人机对弈程序流程图4.2设计实现的策略和算法描述用来实现计算机下棋的方法是:将棋盘看成一条条的线,然后就开始试着在各个点上放上棋子,看看有没有五连,长连,四三,四四等情况出现。当然了,对方的棋和自己方的棋都要看,基本原理用的还是博弈树。判断部分用到链表和递归,计算量很大。4.2.1博弈树博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等。博弈分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈，
22、就是两人对垒，轮流走步，每一方不知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。这类博弈我主要谈五子棋人机对弈程序。所谓机遇性博弈，是指存在不可测性的博弈，如掷币。对机遇性博弈，由于不具备完备信息，我们不作讨论。在双人完备信息博弈过程中，双方都希望自己能够获胜。因此，当任何一方走步时，都选择自己最为有利，而对另一方最为不利的行动方案。假设博弈的一方为MAX，另一方为MIN。在博弈过程的每一步，可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看，可供自己选择的那些行动方案的主动权都掌握在自己手里，任何一个方案都有可能被MAX选中，M
23、AX必须防止那种对自己最为不利的情况的发生。反之MIN也是如此。我们可以依此构建一个博弈树，将所有的走法罗列出来。在这棵树的根部是棋局的初始局面。根的若干子结点则是由甲的每一种可能走法所生成的局面，而这些节点的子节点则是由与乙相对的乙的每一种可能走法所生成的局面在这棵树的末梢，是结束的棋局，人胜或者计算机胜或是双方都无法取胜的平局。博弈树具有如下特点：1、博弈的初始状态是初始节点。2、博弈树中的节点是逐层交替出现的。3、整个博弈过程始终站在某一方的立场上，所有能使自己获胜的终局都是本原问题。4.2.2极大极小值算法（Minimax Algorithm）对于简单的博弈问题，可以生成整个博弈树，找
24、到必胜的策略。但对于复杂的博弈，如国际象棋，大约有10120个节点，可见要生成整个搜索树是不可能的。一种可行的方法是用当前正在考虑的节点生成一棵部分博弈树，由于该博弈树的叶节点一般不是哪一方面的获胜点，因此需要利用估价函数对叶节点进行静态估值。一般来说，那些对MAX有利的节点，其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。为了计算非叶节点的值，必须从叶节点向上倒退。对于MAX节点，由于MAX方总是选择估值最大的走步，因此，MAX节点的倒退值应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选择使估值最小的走步，因此MIN
25、节点的倒退值应取其后继节点的最小值。这样一步一步的计算倒退值，直至求出初始节点的倒退值为止。由于我们站在MAX的立场上，因此应该选择具有最大倒退值的走步。这一过程称为极大极小过程。在上面的博弈树中，如果我们令甲胜的局面的为1，乙胜的局面值为-1，而各局的值为0。当轮到甲走时，甲定会选择子节点值最大的走法；而轮到乙时，乙则会选择子节点值最小的走法。所以，对于中间节点的值可以有如下计算方法：如果该节点所对应的局面轮到甲走棋，则该节点的值是所有子节点中值最大的一个值。而如果该节点所对应的局面轮到乙走棋，则该节点的值是其所有子节点中值最小的一个的值。4.2.3 Alpha-Beta剪枝(Alpha-B
26、eta Purning)对于一般的最大最小搜索，即使每一步只有很少的下法，搜索的位置也会增长非常快；在大多数的中局棋形中，每步平均有十个位置可以下棋，于是假设搜索九步(程序术语称为搜索深度为九)，就要搜索十亿个位置(十的九次方)，极大地限制了电脑的棋力。幸运的是，可以算术的证明，程序不需要考虑所有的位置而找到最佳点，于是采用了一个方法，叫“alpha-beta剪枝”，它大为减少了检测的数目，提高电脑搜索的速度。各种各样的这种算法用于同样用于其他棋类游戏，如国际象棋和跳棋。为了搜索九步，一个好的程序只用搜索十万到一百万个位置，而不是没用前的十亿次。-剪枝的方法如下：（1） MAX节点的值为当前子
27、节点的最大倒推值；（2） MIN节点的值为当前子节点的最小倒推值；（3） -剪枝的规则如下：任何MIN节点n的值大于或等于它先辈节点的值，则n以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。任何MAX节点n的值大于或等于它先辈节点的值，则n以下的分枝可停止搜索，并令节点n的倒推值为。这种剪枝称为剪枝。将上述这个情形推广一下，设想有如下图左部所示的一棵极大极小树的片断，节点数字为该节点的值，节点B的值为18，节点D的值为16，由此我们可以判断节点C的值将小于等于16（取极小值）；而节点A的值为节点MAX（B，C），为18，也就是说不再需要估节点C的其他子节点如E，F的值就可以得出父
28、节点A的值。这样将节点D的后继兄弟节点减去称为Alpha剪枝（alpha cutoff）。右半部分所示的一棵极大极小树的片断，节点B的估值为8，节点D的估值为18，由此我们可以判断节点C的值其他子节点如E、F的值就可以得出父节点A的值了。这样将节点D的后继兄弟节点减去称为（beta cutoff）。ABCDEFBACDEF 18 16 16 18 alpha剪枝示例beta剪枝示例取极大值的节点取极小值的节点裁减在考虑轮到棋手下棋的一个亲节点及轮到对手下棋的一个子节点时，如果该子节点的数值已经小于或等于其亲节点的回溯值，那么就不需要对该节点或者其后续节点做更多的处理了。计算的过程可以直接返回到
29、亲节点上。裁减在考虑轮到对手下棋的一个亲节点及轮到棋手下棋的一个子节点时，如果该子节点的部分回溯值已经大于或等于其亲节点的部分回溯值，那么就不需要对该子节点或者其后裔节点做更多的处理了。计算过程可以直接返回到亲节点上。 4.3编程模型及数据结构4.3.1棋盘及棋子表示 首先得为整个棋盘建立一张表格用以记录棋子信息，我们使用一个1515的二维数组 chessboard_map1515 (1515是五子棋棋盘的大小)，数组的每一个元素对应棋盘上的一个交叉点，用1表示没有棋子、2代表黑棋子、3代表白棋子；这张表也是今后分析的基础。BOOL draw_black_chessman; 表示是下黑棋还是下
30、白棋 true:黑棋; false:白棋struct POINT_IN_CHESSBOARD 保存棋子信息的结构int * line_heng;/横int position_heng;int * line_shu;/竖int position_shu;int * line_pie;/撇int position_pie;int * line_na;/捺int position_na;int chessman_type;/1.没棋子;2.黑棋子;3.白棋子;4.3.2编程模型及数据结构定义一个用来保存棋盘上所有位置信息的数组,从左上角开始,横向排列,至左下角结束,编号从0至224。 POINT_I
31、N_CHESSBOARD chessman225;棋盘单位坐标到棋子编号的映射表,共15行15列,例如chessboard_map00=0;int chessboard_map1515;定义一个数组,用来保存每一局双方所走的棋struct ACTUAL_STEP_INFOint chessman_no;bool is_black_chessman;/true.黑棋子;false.白棋子;struct ACTUAL_STEP_INFO actual_step_saved225;int min_empty_index; /actual_step_saved 数组中保存的最小可用下标,在数组为空时此
32、变量的值为0下面是横竖撇捺四个方向的72条有效线的定义。每条线的头两个元素是:标志位(标志位表示此线是否被改变过,例如添加了一个棋子)，和数组(线)长度;数组中剩下的元素是此线上的点的编号。int h_line0017;/横向第 1条线。 int h_line1417;/横向第15条线int s_line0017;/纵向(竖)第 1条线 int s_line1417;/纵向(竖)第15条线int p_line00 7;/左斜(撇)第 1条线 int p_line20 7;/左斜(撇)第21条线int n_line00 7;/右斜(捺)第 1条线 int n_line01 8;/右斜(捺)第 2
33、1条线int Empty_Array1;/定义一个空数组,用来填充那些不属于有效线的点下面定义一个用来访问所有72条线的数组int * visit_all_line72=h_line00,h_line01,h_line02,h_line03,h_line04,h_line05,h_line06,h_line07,h_line08,h_line09,h_line10,h_line11,h_line12,h_line13,h_line14,s_line00,s_line01,s_line02,s_line03,s_line04,s_line05,s_line06,s_line07,s_line08
34、,s_line09,s_line10,s_line11,s_line12,s_line13,s_line14,p_line00,p_line01,p_line02,p_line03,p_line04,p_line05,p_line06,p_line07,p_line08,p_line09,p_line10,p_line11,p_line12,p_line13,p_line14,p_line15,p_line16,p_line17,p_line18,p_line19,p_line20,n_line00,n_line01,n_line02,n_line03,n_line04,n_line05,n_
35、line06,n_line07,n_line08,n_line09,n_line10,n_line11,n_line12,n_line13,n_line14,n_line15,n_line16,n_line17,n_line18,n_line19,n_line20 ;int Chessman_No;/用来保存当前棋子的编号,这个变量的值始终跟棋盘上最后下的那个棋子的编号相同CPoint Chessman_Position;/用来保存当前棋子的精确坐标CPoint previous_Chessman_Position;/用来保存上一个当前棋子的精确坐标int previous_Chessman_
36、type;/用来保存上一个当前棋子的颜色 1.空白 2.黑棋 3.白棋BOOL Game_Over;BOOL ComputerVsMan;BOOL ComputerFirst;BOOL PutTwoChessmanInFifthStep;/用来决定在黑方下第五个棋子的时候是否采用“五手两打”的国际比赛规则。false表示：不采用“五手两打”，true表示：采用“五手两打”用来存储搜索得到的有用点(四呀、三呀什么的)的数组struct MyNode/双向链表的结点int Chessman_No;struct MyNode *previous;struct MyNode *next;定义一些用来保
37、存黑棋的有用点的链表五连点的链表MyNode *five_head; MyNode *five_end; MyNode *five_current; 还有长连点的链表，活四点的链表，四三点的链表，双四点的链表，双三点的链表，双叫四三点的链表，单叫四三点的链表，连三点的链表，跳三点的链表，死四点的链表，死三点的链表，活二点的链表。定义一些用来保存白棋的有用点的链表，均以3结尾，因为3是白棋的代号五连点的链表MyNode *five_head3;MyNode *five_end3;MyNode *five_current3;还有长连点的链表，活四点的链表，四三点的链表，双四点的链表，双三点的链表，
38、连三点的链表，跳三点的链表，死四点的链表，死三点的链表，活二点的链表。下面定义一个供链表使用的结构，用来实现树(其实是个栈)，这个树是动态生成的，是用来实现对VCF或连续的活三冲四或下一个棋子后就可以形成连续进攻直至取胜的点的检验。struct Crunode /链表中的每一个结点的类型int chessman_no;/棋子在棋盘上的位置的编号bool is_black_chessman;/true.黑棋子;false.白棋子;struct MyNode *dynamic_created8;/应该用8才完美，不过估计实际上连5也很难出现int dynamic_created_index;str
39、uct Crunode tree_stack225;/为了能省掉动态分配内存的时间，决定用数组，理论上应该用225，不过用100都是足够大了int tree_stack_index;/上面的数组的索引，初值为0上面定义的结构体数组要初始化的，尤其是数组的索引，在使用后一定要恢复为0。必须在InitMyData()函数中对上述数组进行初始化!还有链表的指针，也要初始化。如果在树栈中发现了能必胜的走法，就应该将这个必胜的步骤保存到另一个链表中。这样，下次就不用再计算了，直接按照保存的步骤走棋就行了。用来为黑棋保存必胜下法的链表MyNode *SavedVictoryStepHead;MyNode
40、*SavedVictoryStepEnd;用来为白棋保存必胜下法的链表MyNode *SavedVictoryStepHead3;MyNode *SavedVictoryStepEnd3;第五章 系统实现技术5.1分模块详述系统各部分的实现方法五子棋人机对弈程序流程图开始（a）初始化（b）主循环控制模块（c）玩家下子（d）盘面分析填写棋型表（e）电脑下子（f）胜负判断结束轮到电脑轮到玩家否则由五子棋人机对弈程序流程图可知，程序共由六个基本功能模块构成，各模块的详细分析如下：5.1.1初始化1）初始化：首先，建立盘面数组、对战双方的棋型表并将它们清零以备使用；然后初始化显示器、键盘、鼠等输入输出
41、设备并在屏幕上画出棋盘。1）初始化函数void InitMyData()int i,j; garbage=111; min_empty_index=0; Game_Over=true; Chessman_Position.x=-20; Chessman_Position.y=-20; previous_Chessman_Position.x=-20; previous_Chessman_Position.y=-20; previous_Chessman_type=1;/1.空白 2.黑棋 3.白棋 int ddd=0; for(j=0;j15;j+)/y坐标从0到14 for(i=0;i15;
42、i+)/x坐标从0到14chessboard_mapij=ddd;ddd+=1; /给用来保存棋盘上所有位置信息的数组赋初值 CPoint xy; for (i=0;i225;i+) chessmani.line_heng=Empty_Array;chessmani.line_shu=Empty_Array;chessmani.line_pie=Empty_Array;chessmani.line_na=Empty_Array;chessmani.position_heng=0;chessmani.position_shu=0;chessmani.position_pie=0;chessmani.position_na=0;chessmani.chessman_type=1;/初始化棋盘上的所有点都为没有棋子2）初始化用来保存黑棋的有用点的链表 初始化五连点链表,三个指针都指向同一个结点,产生一个头结点。 five_head=new MyNode; five_end=five_head; five_current=five_head;初始化长连点链表初始化活四点链表初始化四三点链表初始化双四点链表初始化双三点链表初始化双叫四三点链表初始化单叫四三点链表初始化连三点链
