基于博弈树的五子棋算法研究论文

1.五子棋基础知识 五子连珠棋基本知识和棋扑研究1、先手：对方必须应答的着法。 2、绝对先手：相对先手而言，特指冲四、嵌五。3、四三：指同时具备两个先手，其中一个四，另一个是活三。 4、活三（包括连三和跳三）：①连三：紧紧相连的同色三子②跳三：中间间隔一子的活三5、嵌五：亦叫跳冲四。6、迫下取胜：指白棋利用黑棋禁手取胜的战术。 7、自由取胜：追下取胜以外的取胜方法都叫自由取胜。8、长连：相同颜色的连续六子或六子以上。9、禁手：对局中禁止使用的战术或被判为负的行棋手段。10、阳线：棋盘上可见的横线与直线的总称。 11、阴线：亦称斜线，为棋盘上不可见的斜行线。12、开局：也称“布局”，对局的第一阶段，过程大体为七至十几着之间，种类繁多，日本的职业连珠五子棋有二十四种开局。 13、局面：亦称“局势”，为对局中某一段时间内双方子力的配置情况。14、优势：对局中某一阶段内，一方棋子布置上优于对方，称为“优势”。 15、胜势：指足力取胜的局面优势。拥有这类优势的一方，如不出现错着，可以获胜。 当一方拥有胜势时，其对方即为败势。16、妙着：也称“高招”。 为对局中走出的一步精妙着法。此着既合乎逻辑，又出人意料、引人入胜，有使局面顿时改观的效果，对局势的发展及对局的质量都有重大影响。 17、好着：也称“佳着”。对局中成功的某一步着法。 18、正着：对局的某一局面中的正确着法。19、劣着：对局中，导致严重不利后果的一步错误着法。 20、败着：也称“失着”、“漏着”。对局的某一局面的一步严重错误着法。 往往造成局面恶化而导致输棋。21、等着：对局的某一局面中具有等待性的一步着法，主要意图是等待有利时机。 22、废着：也称“空着”。对局中不起作用的一步着法。 实际上为一种浪费时间的错着，有可能丧失均势或优势；如已居劣势，则可能导致败局。23、抢先：对局中利用反活三或反冲四等强制手段夺取主动权的着法。 24、打谱：按照棋谱演练着法，是提高棋艺水平的重要方法之一25、复局：也称“复盘”。对局结束以后重演对局的过程。 一般用以研究、比较双方的成败得失和着法优劣。可由一方或双方进行，也可在高手指导下进行。 是提高棋艺水平的重要方法之一。对于比赛中有争议的对局，则由裁判员根据双方的记录复局。 26、着：也称“步”。对局中，把一个棋子按照规则放到某一交叉点上去，称之为一着棋。 一着是否完成有两种规定：1在执行落子无悔规则时，以走棋者的手离开棋子作为一着已完成。2在执行超过时限算输棋的规则时，以走棋者己按棋钟作为一着已完成。 27、胜局：对局的一方获胜，称为“胜局”。包括：①一方首先在棋盘的直线或横线或斜线上形成连续的五子或五子以上（特指白方）。 ②对方表示认输。③对方超过比赛规定的时限。 ④当黑方禁手形成未能同时形成五连，白方立即指出禁手后，判定为白方胜局。⑤对方迟到超过容许时间。 ⑥对方严重犯规而被判负。28、和局：也称和棋。 为结局不分胜负的对局或双方同意作和。29、Pass：五子棋中引入的英文名称，即让对方通过，再行棋一次之意。 为该行棋的一方主动放弃一次行棋的机会的行为。30、串珠战术：五子棋的基本技巧之一。 即持白方预先给黑棋留下一个禁手点（多为长连禁手），次后，白方只需防手对方的进攻并刻意留下次禁手点。由于五子棋共有225个交叉点，最后一个为单数，轮到黑方行棋时，黑方只得将盘面最后一个交叉点占领。 但是，只要黑方一落子，即为长连禁手，盘终黑负白胜。31、VCT:(Victory of Continuous Three的缩写)为五子棋引入的英文名称，即利用连续不断地活三，直至取德胜利之意。 32、VCF:(Victory of Continuous Four的缩写) 亦五子棋中引入的英文名称，即利用连续冲四取胜之意。为五子棋残局排局解题的一种取胜技巧。 利用连续不断冲四或嵌五的绝对先手，直至形成四三后变活四而取得胜利的一种方法。33、百局满珠：五子棋的一种赛制。 即在规定的时间内，盘面以满100珠棋子，仍不能连五或追下取胜，则算和棋。34、黑方定局：五子棋专业比赛的一种规则。 即用猜先执黑的一方先在盘中放置三枚棋子，形成一种开局之后，再由执白选择是否交换。由于，白方有交换的权利，因此，黑方只能选择不占优的开局。 35、四四：一子落下同时形成两个“四”的棋形36、三三：一子落下形成了两个活三的棋形37、定式：拥有最佳的手顺，能够取胜或者占优，这种棋形称之为定式 38、眠三：一端有对方棋子阻拦的三叫眠三，眠三是冲四的基础39、假活三：在活三两端相隔一点的位置上有对方的棋子（或边线）阻拦时，这个看起来是活三的棋形实际上是个假活三40、禁点：黑棋一子形成三三、四四、长连、四三三、四四三的那一点称为禁点41、禁手：黑方因走了禁点而被判负的一手棋叫禁手，有三三、四四、长连等禁手打谱：按照棋谱演练着法，是提高棋艺水平的重要方法之一。 2.五子棋的基本知识 1. 五子棋算法探讨 朱磊 文献来自： 电脑知识与技术 2003年 第29期 CAJ下载 PDF下载 （假设您在阅读本文之前已经掌握五子棋的基本规则）我们知道，五子棋水平的高低主要在于能够计算后步路数的多少，也就是我们常说的算了几步，如果电脑具有这种能力，就不会掉入玩家设下的陷阱，这也是初学者常犯的错误，目光短浅，只看到眼前一步。 而这样的运 。 被引用次数： 1 文献引用-相似文献-同类文献 2. 五子棋中的博弈问题 曾小宁 文献来自： 广东教育学院学报 2003年 第02期 CAJ下载 PDF下载 五子棋及博弈问题博弈问题一向被认为是一种具有智能行为的游戏，因而很早就受到人工智能界的重视 。 以五子棋问题为例，综合数据库可用15*15的2维数组表示棋盘内各点状态（空、白子、黑子） 。 对于五子棋可分为禁手和无禁手两类，以下为一规则：if棋盘（i,j）处为空then令（i,j）处为白子，诸如此类规则还有很多 。 被引用次数： 1 文献引用-相似文献-同类文献 3. 五子棋中的博弈智能设计 张海峰，白振兴，张登福 文献来自： 现代电子技术 2004年 第07期 CAJ下载 PDF下载 以五子棋为入口进行研究 ，设计了一个智能五子棋系统 ，讨论博弈中人工智能的设计方法。1 人机博弈的要点人机对弈的程序 ，至少应具备以下 5个部分 ：（ 1 ）某种在机器中表示棋局的方法 ，能够让程序知道博弈的状态 。 五子棋特点及规则五子棋的娱乐性强、规则简单、易学、流行性广。普通人不需长时间专门训练即可自如行棋 。 被引用次数： 1 文献引用-相似文献-同类文献 4. 智能五子棋博弈程序的核心算法 董红安，蒋秀英 文献来自： 枣庄学院学报 2005年 第02期 CAJ下载 PDF下载 人工智能中大多以下棋（如象棋、围棋、五子棋等）为例来研究计算机博奕规律.五子棋是一种深受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性 。 这里设计和实现了一个人机博奕的五子棋程序，采用了博弈树的方法，应用了剪枝和极大极小树原理进行搜索发现最好的下子位置 。 被引用次数： 1 文献引用-相似文献-同类文献 5. 概说五子棋 那威 文献来自： 新体育 1998年 第11期 CAJ下载 PDF下载 五子棋县DW方羹手形成时，自方应立即指出门有“短、平、快”的现代游戏特征，匐D 着自方来发现，不能判累方负。I单另学而又囱有趣味，为大众容闪D 职业五子棋最高为九段，以下D乐见。 振而，五子棋又包含深臭的哲l 为 。 得g曰对团棋和五子棋有们妙的比喻。 D”到有段位棋手的承认即可。如果戳他说：国 罩团作战，槽大们深 。 被引用次数： 0 文献引用-相似文献-同类文献 6. 五子棋擂台赛 顾曙 文献来自： 早期教育 2003年 第06期 CAJ下载 PDF下载 在一群下五子棋的小朋友中传出了阵阵掌声，我走过去一看，原来是枫枫连赢了云云三盘棋。云云是我们班的下棋高手，而枫枫平时能力一般，文文弱弱，不善表现，没想到却有那么好的棋艺。 看到这情景，我也跃跃欲试，想和枫枫比个高低。别看 。 被引用次数： 0 文献引用-相似文献-同类文献 7. 五子棋大战 二乔 源自： 软件报/2003/02/17 CAJ下载 PDF下载 “五子棋大 战”虽然十分小 巧，但能支持双 人对战和人机 对战模式；可以 通过“操作者设 备锁定”功能来 使键盘和鼠标 各执一方棋子 操作， 。 被引用次数： 0 文献引用-相似文献-同类文献 8. 人工智能五子棋游戏 蒲应文 源自： 软件报/2006/11/27 CAJ下载 PDF下载 $T五子棋是由两个人在棋盘上进行对抗的益智游戏，在棋局开始时，先由执黑棋一方将一枚棋子落在棋盘上，然后由执白棋的一方落棋，如此轮流落子 。 被引用次数： 0 文献引用-相似文献-同类文献 9. 五子棋的基本知识 源自： 河北商报/2000-10-11 CAJ下载 PDF下载 是 一种五子棋最常用、最主要的获胜方法。下面 为您提供一些中盘布局，及时应的连续冲四取 胜方法，供您参考，并欢迎您提供更佳方案？。 被引用次数： 0 文献引用-相似文献-同类文献 10. 五子棋与坐标教学 郭建平 文献来自： 师道 2002年 第01期 CAJ下载 PDF下载 进行一次“五子棋与坐标教学”的尝试。 上课 *** 响过，我走上讲台，提出了这样的问题：“大家会下五子棋吗 。 进行一次“五子棋与坐标。 3.五子棋有什么技巧 ----先手要攻，后手要守。 这句话的表面意思应该很容易理解，先手当然应该进攻，不要贻误时机。但有些时候局面并不是一边倒的形势，这就需要认真判断自己到底是不是真正的先手，如果前途暗淡，而对方也有些手段，就要小心了，冒然进攻，用完了自己的力量，再去防守对手，就成了彻底的后手。 ----以攻为守，以守待攻。 攻不忘守，守不忘攻。 有句话叫“最强的防守就是进攻”，防守别人棋的时候仔细看清局势，是不是有既能防守住对方又可以进攻的点。以守待攻，在对方狂攻一阵却无胜棋后，你防守的棋是否形成了外围的攻势？在安全的前提下，防守对方的棋最好不要太消极，等他攻完，就可以利用防守时形成的攻势轻松收拾对方。 ---攻守转换，慎思变化。 发现进攻没有胜棋，而对方防守的子力形成了一定的威胁，一般就会转攻为守了。 或者守住了对方的进攻，得到先手而转守为攻。攻守转换的时候，要分析局面，有些冲四、活三是不是该先下了再去防守更好？还是冲后以后再防守会变得更困难？以守转攻的时候，要看清是不是真的已经完全守住了对方？他还有哪些力量，能不能够成威胁？ ----先行争夺，地破天惊。 用妙手强行夺得先手，这样的气势连天地都会惊动。 ----守取外势，攻聚内力。 防守的时候，尽可能防在外围，限制对方的空间，让他的棋没有发展前途。进攻则不能太分散子力，下得太*外，被对方占据要点，阻断子力联系，不能形成有效的进攻。 但攻聚内力并不等于放弃外围，使自己没有足够的空间进攻，守取外势也不能一味地在外围防守，而放弃内部必须占据的要点。 ----八卦易守，成角易攻。 八卦就是由象棋四个马步形成的一种棋形，如果摆满全盘，则对方没有取胜的可能。还有一种说法叫“马步是强防”，既使不能摆满全盘，很多时候自己的棋子形成马步的点就是强防点。 成角易攻，角就是三个紧紧*在一起的棋子构成的直角三角形，成角的形状后子力可互相多次利用，进攻源源不断。 ----阻断分隔，稳如泰山。 这句话说的就是防守时的一种思想，阻断对方子力的联系，逐个击破。 ----不思争先，胜比登天。 仅仅*消极的防御是赢不了棋的，防御的时候时刻要考虑夺回先手。两个棋力相当的棋手，一盘五子棋比赛过程，就是互相争先手的过程。 ----初盘争二，局终抢三。 开局的时候双方都没有连续进攻取胜的手段，就需要在限制对方形成活二的基础上自己形成更多的活二，时机成熟，一举攻胜。 到了局终双方各有些活二、眠三，这时有些三就要先活，有些眠三就要先冲，占据空间要点，切断对方子力联系。 ----留三不冲，变化万千。 有很多初学五子棋的朋友是有三必冲的，殊不知在鞘中的剑才是最强的剑，冲四犹如宝剑出鞘，如果不能一击致命，出鞘之后的剑就没有威力了。留三不冲，你的这个冲就有两个点（一个连冲，一个跳冲）可以利用，相应对方防守的子也会少一个。 有时把冲了以后活三改为直接叫四三，可以收到更好的效果。 ----多个先手，细算次先。 ----五子要点，次序在前。 这里说的是顺序问题。 同样的棋，顺序对了可以取胜，顺序错了没有胜棋，在实战中可以遇到这类情况。不要被自己很多可以活三冲四的棋看花了眼，认真计算正确的进攻顺序以及对方防守后会不会形成反三、反四。 ----斜线为阴，直线为阳。 ----阴阳结合，防不胜防。 新手的朋友很容易忽视斜线的子力，斜线成五子同样取胜，可不能大意。善于进攻的棋手，能够做到直线和斜线相互配合，多角度的攻击能够大大增加进攻的杀伤力。 之所以说斜线是阴因为不同颜色的两条斜线可以交*互不影响，相反的不用颜色的两条直线就不可能交*，因为无法穿越对方。 ----连三连四，易见为明。 ----跳三跳四，暗剑深藏。 连三连四很容易看出，很多朋友却老是忽视跳活三、跳冲四的下法，不晓得跳出去又是另一片天空，跳出去进攻更具有隐蔽性。 这两句放在一起是告诉棋手，连和跳并没有一定之规，关键看临场的形势，但是千万不能忽略可任何一种可能性，否则就会错失良机。 ----己落一子，敌增一兵。 这句话主要是说在进攻的时候不要忘记对方防守的子力，五子棋是你下一子，对方下一子，不比你少。你进攻一手棋，敌人防守一子，防守的棋子是不是会给你造成反三、反四？会不会阻碍了你的后续进攻？所以下棋的时候一定要惜子如金，每一子都要发挥出最大的效力，千万不可随便将变化走完。 ----攻其要点，守其必争。 进攻的时候占据重要位置，下在可持续进攻的点。 防守就要守在对方进攻过程中非常想占据的连接点，你想下的点，我来下。 ----势已形成，败即降临。 高手对弈很多时候是我们看不懂的，因为他们所追求的是“势”，一种压制住对方而取得压倒性优势的情况，这个时候可能不能简单的杀，但是通过精准的计算可以立即将这种“势”转化为杀。 ----五子精华，一子输赢。 有些朋友输了以后说“你成五子了，我也活四了，我只比你差一颗子嘛”。其实五子棋争的就是这一步棋，谁争得了先手下成五子，谁就获胜，这也是五子棋的魅力所在。 不要以一子之差原谅自己，一子就已经可以使你输棋了。 其实我也很想诠释。 4.五子棋基础知识 五子棋开局口诀《彭氏口诀》 寒星溪月疏星首，花残二月并白莲， 雨月金星追黑玉，松丘新宵瑞山腥。 星月长峡恒水流，白莲垂俏云浦岚， 黑玉银月倚明星，斜月名月堪称朋。 二十六局先弃二，直指游星斜慧星。 五子棋26开局简图 ┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼●┨┠┼┼┼┼┼┨ ┠┼┼┼○┼┨┠┼┼┼○┼┨┠┼┼┼○┼┨┠┼┼┼○●┨ ┠┼┼●┼┼┨┠┼┼●┼●┨┠┼┼●┼┼┨┠┼┼●┼┼┨ ┠┼┼┼●┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚ 蒲月 恒星 长星 峡月 ┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼┼○┼┨┠┼┼┼○┼┨┠┼┼┼○┼┨┠┼┼┼○┼┨ ┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●●┼┨┠┼┼●┼┼┨ ┠┼┼┼┼●┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨┠┼┼┼┼●┨┠┼┼┼┼┼┨┠┼┼┼●┼┨ ┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚ 水月 流星 云月 岚月 -------------------------------------------------------- ┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼┼○┼┨┠┼┼┼○┼┨┠┼┼┼○┼┨┠┼┼┼○┼┨ ┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●┼┼┨ ┠┼┼●┼┼┨┠┼┼┼┼┼┨┠┼●┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨┠┼┼●┼┼┨┠┼┼┼┼┼┨┠┼●┼┼┼┨ ┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚ 银月 明星 斜月 名月 ┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒ ┠┼┼●┼┼┨┠┼┼┼┼●┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼○┼┼┨┠┼┼○┼┼┨┠┼┼○●┼┨┠┼┼○┼●┨ ┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●┼┼┨ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚ 寒星 疏星 花月 残月 -------------------------------------------------------- ┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼○┼┼┨┠┼┼○┼┼┨┠┼┼○┼┼┨┠┼┼○┼┼┨ ┠┼┼●┼●┨┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●┼┼┨ ┠┼┼┼┼┼┨┠┼┼●┼┼┨┠┼┼┼●┼┨┠┼┼┼┼●┨ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚ 金星 松月 丘月 新月 -------------------------------------------------------- ┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒┎┬┬┬┬┬┒ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼●┼┨ ┠┼┼○┼┼┨┠┼┼○┼┼┨┠┼┼○┼┼┨┠┼┼○┼┼┨ ┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●┼┼┨┠┼┼●┼┼┨ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼●┼┼┨┠┼┼┼●┼┨┠┼┼┼┼●┨┠┼┼┼┼┼┨ ┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚┖┷┷┷┷┷┚ 瑞星 山月 游星 溪月 -------------------------------------------------------- ┎┬┬┬┬┬┒┎┬┬┬┬┬┒ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼○┼┼┨┠┼○┼┼┼┨ ┠┼┼●●┼┨┠┼┼●┼┼┨ ┠┼┼┼┼┼┨┠┼┼┼┼┼┨ ┠┼┼┼┼┼┨┠┼┼┼┼●┨ ┖┷┷┷┷┷┚┖┷┷┷┷┷┚ 雨月 彗星 花月及蒲月是必胜开局 游星及慧星是必败开局 26种开局以外的开局为妖刀------。 5.五子棋常识 黑棋禁手判负（Lose），白棋无禁手。 黑棋禁手包括“三、三”（Double Three）（包括“四、三、三”）、“四、四”（Double Four）（包括“四、四、三”）、“长连”（Overline）。黑棋只能以“四、三”取胜。 五连与禁手同时形成，先五为胜。 黑方禁手形成时，白方应立即指出。 若白方未发现或发现后未指明而继续应子，则不能判黑方负。 黑方走出长连禁手则不同，只要是在终局前，无论白方何时发现此长连禁手点，指出此点而宣布胜利，判白方胜。 长连：在棋盘的任意一条线上，形成的5个以上同色棋子不间隔地相连 活三：本方再走一着可以形成活四的三。 活四：有两个点可以成五的四。 冲四：只有一个点可以成五的四。 禁手：对局中如果使用将被判负的行棋手段。 三三禁手：黑棋一子落下同时形成两个或两个以上的活三. 四四禁手：黑棋一子落下同时形成两个或两个以上的冲四或活四。 长连禁手：黑棋一子落下形成一个或一个以上的长连。

你百度，极大极小数alpha-beta剪枝树算法这是最基础的算法，如果你想做得好，这个东西绝对够你研究个三年五年的。我写过五子棋人工智能，如果你需要，我有源码发给你。

其实这个不是难点的，那个分数是当前落子后所形成的以这个棋子为中心的9x9矩阵中所形成的棋型，计算其他地方的棋型显然没有什么意义，再有就是不是C语言才可以写算法的，对于极大极小原理，博弈树和alpha-beta剪枝算法都是基于这个原理的，如果你是刚学编程不久，而且没有数据结构的基础是写不出来运用博弈树算法的五子棋的，先把基础打好再说。。

机器博弈是人工智能领域的重要分支，它的研究对象多以复杂的棋牌类智力游戏为主，已经得到解决的棋类游戏，几乎全部都应归功于机器博弈近半个世纪的发展。计算机解决问题的优势在于能把不易解析的问题，借助于现代计算机的运算速度优势枚举出所有的合理情形而得解;然而，博弈问题的复杂程度决定了它不能过度依赖机器的计算能力。许多待解决的或已经解决的棋类，其状态空间复杂度或博弈树复杂度量级都太过庞大，所以我们需要添加约束，并且采用合理的算法进行优化。

五子棋问题是人工智能中的一个经典问题。当今世界，AlphaGo已经执围棋之牛耳，五子棋领域却鲜少有人问津。本文根据课堂所学知识结合文献、博客，基于两种开发语言实现了一个智能对战的AI五子棋游戏平台。

本文所做工作如下：

（1） 五子棋界面实现；

（2） 智能判定棋盘走势；

（3） 改进了棋盘扫描方式；

（4） 改良了系统评分表评估方式；

（5） 实现了基于点评分表估值找出最佳落子方式。

五子棋AI问题的最大问题是如何实现智能对弈，即当人落子之后，算法如何解读当前的棋盘并且对其进行分析解读，得到电脑方的最佳落子点。其次还有一个问题是如何判断胜利，这可以作为前面棋盘局势判定的一个子问题，也可以看做是一个单独的问题，不过这个问题总体来说较为简单，所以不做详细说明。

五子棋的整体知识构建包含以下部分：

（1） 棋盘局面表示法

（2） 棋局胜利判定

（3） 棋型知识库

（4） 智能博弈流程

对于问题（1），采用数组表示法。棋盘中的各交叉点有三种状态，不妨令 0表示空(未放置棋子) ，-1 表示有黑子 ，1 表示有白子，数组表示法的基本思想是:以交叉点对应的数组索引值来表达物理位置 ，以交叉点对应的元素值表达状态(空、 黑子、 白子)。令 V = {0 ，1 ，-1} ，棋盘 的第 i 个交叉点的状态 Si ∈V ，任何棋局都可以表示成一个 n ×n 的二元组。

对于问题（2）， 采用数组表示法时，想知道任意两个元素 Si 和Sj 是否共线，要通过 i 和 j 之间的数值规律来判断。从这方面看，数组表示法是一种原始、低效的表示方法，但是对于评分表算法来说其性能损失是可以接受的。要判断是否有一方已经胜利，只需要对整个棋盘判定当前落子点的纵、横、正斜、反斜四个方向的最长延伸出四个位置看是否能连成一条同色直线即可。具体的操作可以视为：从落子点出发，向两个方向延伸，如果遇到同色，那么计数器加一，遇到非同色（空白或者异色）则停止在该方向的延伸，一个计数器记下该方向上的两头的连续同色棋子数。等到四个方向都探索完毕，如果四个计数器中有一个计数器达到了5，那么即可判断出已经有五子连珠了，此局结束。

问题（3）棋型知识库主要包括各种既定的棋盘形式，有如下几种：

² 活四 ：有两个连五点（即有两个点可以形成五），图中白点即为连五点。当活四出现的时候，整个局势已经无法阻止连五了，活四的归属方一定能取得胜利；

² 冲四 ：有一个连五点，如下面三图，均为冲四棋型。图中白点为连五点。 相对比活四来说，冲四的威胁性就小了很多，因为这个时候，只要跟着防守在那个唯一的连五点上，冲四就没法形成连五。

² 活三 ：可以形成活四的三，如下图，代表两种最基本的活三棋型。图中白点为活四点。活三棋型是进攻中最常见的一种，因为活三之后，如果对方不以理会，将可以下一手将活三变成活四，而活四是无法防守的。所以，面对活三的时候，需要非常谨慎对待。在没有更好的进攻手段的情况下，必须对其进行防守，以防止其形成可怕的活四棋型。

² 眠三： 只能够形成冲四的三，如下各图，分别代表最基础的六种眠三形状。图中白点代表冲四点。眠三的棋型与活三的棋型相比，危险系数下降不少，因为眠三棋型即使不去防守，下一手它也只能形成冲四，而对于单纯的冲四棋型，是可以很简单的防守住的。

² 活二 ：能够形成活三的二，如下图，是三种基本的活二棋型。图中白点为活三点。

² 眠二 ：能够形成眠三的二。图中四个为最基本的眠二棋型，细心且喜欢思考的同学会根据眠三介绍中的图2-13找到与下列四个基本眠二棋型都不一样的眠二。图中白点为眠三点。

对于上述的棋型，我们主要考虑的是活四、冲四、活三、眠三这几种主要的进攻棋型的防守与构成，整体棋型遵从以下原则：优先考虑数目，同等数目的情况下考虑是活是眠。评分表算法的设计整体偏向于防守。

对于问题（4），当下棋型的评估分析，算法严格遵从以下流程：

当人类方落下一子，算法启动，扫描全局，得到人类棋子的集合和电脑棋子的集合。全局扫描之后，对当前局势进行排序、计算。对每个集合的每个空白点位置打分，打分依据是根据这个点周围四个方向上的同色连续棋子的数量。按照这些最后得到的评分，得出最大值。得到人类方和电脑方的两个最大值之后，进行比较，如果人类方局势较好（分数较高），则算法将下一次落子位置设置为人类方得分最高的点，尽力降低人类方的下一步得分；如果电脑方的分数较高，那么则直接在使得分数最高的点落子即可。

本次课程设计，一共设计了两个版本，一个Java版本，为19X19的棋盘，配备简单的消息提示，基于AWT实现GUI，开发工具IntelliJ IDEA 2018.1

另一个版本是使用Python设计，核心算法相同，但是受限于图片源文件，为15X15棋盘，基于pygame实现GUI，开发工具是：JetBrains PyCharm 2018.2.4 x64

因为近期时间较为紧迫，所以《人工智能》这门课我选择了较为简单的五子棋问题进行课程设计。在本次课程设计中，我的编码能力、调试能力、算法解读实现能力、函数优化能力等各方面有了长足的进步。在本次的设计过程中也出现了几个问题，下面对这些问题进行一个简单的描述：

（1） 对棋盘局势的判断力不够，因为只是简单的对当前的棋盘局势进行判断，基本等同于一个粗通规则而且天赋不高的五子棋选手。如果对手很细心，而且熟练经营各种布局策略，那么基本这个算法就会被钻研出习惯，从而被轻易针对，而且针对方案百试不爽；

（2） 判断棋局形式的时候对边界的评分算法跟中心区域的评分算法一致，无法有效提前识别边界，降低边界空白点的权重；

（3） 用户图形界面需要改进，另外可以增设PK模式以及选色、选择棋盘大小功能等；

后续可以尝试用博弈树算法尝试与当前算法进行比较。评分表算法牺牲了更高的精度，以求迅速的得出最佳落子点；而博弈树可以通过提前落子进行全局预判进行更全方位的对人类方的围追堵截。

另外，可以通过在课堂上学到的知识，比如BFS、DFS、A*算法、决策树算法 等应用于五子棋的智能决策中。

《人工智能》这门课让我对于图、知识表示、智能决策等各个方面有了更好地认识与体验，课堂设计内容充实有趣，让我受益匪浅，希望今后可以更加深入这个方面，并且将课堂上学到的知识应用于实践之中。