五⼦棋算法
⼈机对战五⼦棋设计——算法设计⼀、五⼦棋基本规则
(1)五⼦棋⾏棋时，⿊棋先下第⼀⼦，后⽩棋在⿊棋周围的交叉点落⼦，之后⿊⽩双⽅相互顺序落⼦。(2)最先在棋盘线交点横向，纵向，斜向形成连续的五个棋⼦的⼀⽅为胜。⼆、五⼦棋程序设计1.程序设计思想
(1)本程序要实现五⼦棋的游戏功能，必须先有⼀个棋盘。所以，通过LinearLayout线性布局上画出⼀个棋盘。另外还需要四个按钮：开局、模式（⼈机对弈）、退出，提醒⽤户进⾏相应的操作。
(2)对于下棋的操作，通过增加⿏标事件MouseListener，每次当⽤户点击⿏标时，先取得点击的坐标值，然后换算成对应棋盘上（即棋盘数组）的位置（数组的下标）。
(3)判断此处是否已经有棋⼦，如果有则提⽰玩家重新下⼦，否则通过java⾥的画图函数在此处画上棋⼦，重新刷新输出棋盘。
(4)判断该颜⾊棋⼦的上下左右是否满⾜连续五个，是的话提醒相应玩家获胜，不是的话，更换玩家下棋。
(5)对于玩家的更换是程序⾃动的，每次⽤户点击⿏标后，若本局还未结束则会变换玩家，从⽽画出对应⿊⽅⽩⽅的棋⼦，直到有⼀⽅获胜程序结束。2.程序设计分析
(1)本款游戏有开始游戏、⼈机对战，关于我们、退出游戏四个选项；玩家可以根据具体需要选择使⽤。
(2)程序默认对弈模式是⼈机对弈模式，并且是玩家先⼿，玩家是⿊⽅，电脑是⽩⽅。。(3)棋盘处于⿏标监听状态，当⿏标在棋盘上有点击操作的时候，程序会获得⿏标点击的坐标然后换算成对应的棋盘的位置，再判断此处是否有棋⼦。假如没有，那么在此处画出对应颜⾊的实⼼棋⼦；假如已经有棋⼦了，则提⽰玩家此处已经有棋⼦请重新下棋。
(4)当选择的是⼈机对弈模式的时候，轮到电脑下⼦时，电脑会通过算法来计算每个没有棋⼦的位置的分数，从⽽来选择最重要的位置下⼦。三、五⼦棋算法分析1.⼈机对弈算法概述
⼈⼯智能五⼦棋游戏最核⼼的地⽅就是算法，因为这是整个程序最难的模块。算法的中⼼思想是：利⽤分数代表每个位置的重要程度，越重要的位置的分数值会越⾼，当电脑下棋时会先将电脑和玩家棋型的分数分别计算⼀遍，然后选择⼆者中分数最⾼的点下⼦。
如果玩家的分数⾼，那么代表电脑应该防守，如果电脑的分数⾼，那么代表电脑应该进
攻。
2.数据结构设计以10×10⼤的棋盘为例：
(1)两个获胜表（ptable[10][10][192],ctable[10][10][192]）：也就是获胜组合，因为五个⼦⼀线则胜，不在⼀线上的五个⼦就不在⼀个组合中，对于10×10的棋盘获胜的
组合有192种（下⾯将会详细说明），获胜表⽤来表⽰棋盘上的每个位置是否在玩家或计算机的获胜组合中。(2)⼀个⼆维数组（[2][192]）：记录玩家与计算机在各种获胜组合中填⼊了多少棋⼦。(3)两个10×10的数组：⽤来记录玩家与计算机在各个棋盘位置上的分数，分数⾼的将是计算机下⼀步的⾛法。3.获胜组合情况分析
图9 10×10棋盘获胜组合情况
(1)垂直⽅向：垂直⽅向上获胜组合数为10×6=60种；(2)⽔平⽅向：⽔平⽅向上获胜组合数为10×6=60种；
(3)两个对⾓⽅向：倾斜⽅向上获胜组合数为(1+2+3+4+5)×2+6=36种。所以10×10的五⼦棋棋盘所有的获胜组合为：60*2+36*2=192种。4．棋型的估值分析
不同的棋型，其优先级不同。例如，四个棋⼦连成⼀线且还能继续落⼦的棋型（活四）显然要⽐只有三个棋⼦连成⼀线（活三或死三）好。要使计算机正确地做出这种判断，就要把第⼀种棋型的估值设⾼。事实上，对于每⼀种特定的棋型，都需要相应的估值来反映其优劣情况。另外，由于搜索模块频繁地调⽤估值函数，为了尽可能地加快搜索速度，估值函数应设计的越仔细越好。
估值时，需要从四个⽅向上来考虑所下棋⼦对当前盘⾯的影响。这⼋个⽅向分别是以该棋⼦为出发点，⽔平、竖直和两条为45度⾓和135度⾓的线。
为⽅便分析棋盘上的格局，约定以“A”代表⿊⼦，“B”代表⽩⼦，“？”代表棋盘上空位。算法中关于棋⼦死活的规定如下：⼀⽅落⼦后，它的落⼦连成的⼀条线有两条不损伤的出路，则称该棋型是活的。否则称该棋型是死的。⽐如关于活三的定义：不论对⼿如何落⼦，仍然⾄少有⼀种⽅法可以冲四。因此，B?AAA? B中的三个A，不能算是活三；B?AAA??B中的三个A，也不是活三，尽管它有可能成为活四。这样，棋型的估值设计才能⽐较细致。本⽂算法对特定棋型的估值如图10所⽰。
图10 特定棋型的估值
之所以要给出如此⼤的分值差距，主要是考虑以后的全局判断的时候不会因为分数的累加使得电脑判断错误。⽽电脑在判断双⽅的分值的时候，就是在落⼦时对⾃⼰的落⼦点涉及分值和对⽅的分值进⾏对⽐来进⾏之后落⼦的判断。
⽤两个⼆维数组（pgrades[,cgrades）存储每个棋位的分数，⼀个是计算机的，另⼀个是玩家的，表⽰该位置对于各⽅是最佳着法的肯定程度，对⼀个位置的评分就是：遍历该位置所在的每⼀种获胜组合，根据这个组合中已经拥有的⼰⽅棋⼦数1到4分别加不同分数，最后将这些所有的获胜组合所得出的分数相加就是该位置的分数，下图是对于五⼦棋⿊⽅各棋位的评分（其中的1，2，3，4这⼏个值要根据实际需要来确定）。如图11所⽰。
图11⿊⽅棋位的评分5.五⼦棋算法之胜负判断
棋局的胜负是根据最后⼀个落⼦的情况来判断的。此时需要查看四个⽅向，即以该棋⼦为出发点的⽔平，竖直和两条分别为45度⾓和135 度⾓的线，看在这四个⽅向上的其它棋⼦是否能和最后落⼦构成连续五个棋⼦，如果能的话，则表⽰这盘棋局已经分出胜负。
实际上，我们可以提前若⼲步预判当前棋局的胜负情况。可以提⾼算法的智能
