五子棋AI（12）
作者同类文章X
& & & & 在五子棋中，招法的生成其实“很容易”凡是没有子的点都是招法点，但这样做无疑是“低效”的，有很多文章（包括我前期的代码）都采用了“临近点”搜索的策略，例如下子H8之后，搜索周围5格以内的空点，但这也存在问题：随着棋子量的增多尤其是冲4然后对方堵死的情况，这种“棋盘剪裁”将迅速扩大搜索范围。经过观察我们可以发现，下五子棋的时候无非是要连得更长（无禁手），当长度超过4就胜利了。所以下子时所挑选的点无疑在同一线上，基于这种考虑我们完全可以只生成“冲棋点”作为走法。当然，这种做法也不是没有异议，尤其是开局阶段很多招法并不是这样的，于是有一些文章将“威胁空间搜索”视为一文不值，其实这个问题很简单，在后面讨论“启发算法”的时候，我会给出解决方法，并且寥寥几行代码，不仅很好的解决了这个问题而且有非常好的启发作用。
& & & & 接下来我们貌似可以讨论招法如何产生的问题了，但在这之前，必须要明确的问题是模板。很多五子棋程序定义模板并给出评分，开始我也是这么做的，并且做得比较彻底：手工制作模板从5长度一直到11长度（下一子之后受影响的大约都在5格之内，但实际上这不准确），但后来我测试VCF代码时发现我的模板存在不一致性，并且存在一些评分不正确的情况。于是用了一些时间把模板改为自动生成，这些自动生成的函数的工作非常快并且准确，至少现在我没有发现任何问题。而且我不再使用直接给出评分的方式，而是简单的归类。例如在PosInsHelper.vb中用这样一段代码生成从1到15长度的所有模板（模板当中只有有子、无子之分）：
& & & & For len = 1 To 15 & & & & & & &&
& & & & & & For bitkey = 0 To 2 ^ len - 1 & &
& & & & & & & & idxkey = bitkey Or ((17 - len) && (len + 1))
& & & & & & & & If dm(idxkey) IsNot Nothing Then Throw New Exception(&位置冲突避免算法错误，或重复调用填充函数&)
& & & & & & & & Dim cline(len - 1) As Byte
& & & & & & & & For i = 0 To len - 1
& & & & & & & & & & If ((bitkey && i) And 1) = 1 Then
& & & & & & & & & & & & cline(i) = LinkType.lnll
& & & & & & & & & & End If
& & & & & & & & Next
& & & & & & & & dm(idxkey) = cline
& & & & & & & & If idxkey & keySpaceMax(len) OrElse idxkey & keySpaceMin(len) Then Throw New Exception(&key空间算法错误&)
& & & & & & Next
& & & & Next
这段代码当中唯一的亮点可能就是利用了二进制的特点用循环代替了递归调用，当得到全部模板后，用一个双层循环来得出胜利情况：
& & & & For len = 5 To 15 & & & & & & & & & & & & & & & & &&
& & & & & & For idxkey = keySpaceMin(len) To keySpaceMax(len) & &&
& & & & & & & & Dim linkcount As Integer
& & & & & & & & For i = 0 To len - 1
& & & & & & & & & & linkcount = 1
& & & & & & & & & & If ((idxkey && i) And 1) = 1 Then &
& & & & & & & & & & & & For j = i + 1 To len - 1 & & & &'向低位检测连接长度
& & & & & & & & & & & & & & If ((idxkey && j) And 1) = 1 Then
& & & & & & & & & & & & & & & & linkcount += 1
& & & & & & & & & & & & & & Else
& & & & & & & & & & & & & & & & Exit For
& & & & & & & & & & & & & & End If
& & & & & & & & & & & & Next
& & & & & & & & & & & & For j = i - 1 To 0 Step -1 & & & '向高位检测连接长度
& & & & & & & & & & & & & & If ((idxkey && j) And 1) = 1 Then
& & & & & & & & & & & & & & & & linkcount += 1
& & & & & & & & & & & & & & Else
& & & & & & & & & & & & & & & & Exit For
& & & & & & & & & & & & & & End If
& & & & & & & & & & & & Next
& & & & & & & & & & & & If linkcount = 5 Then
& & & & & & & & & & & & & & dm(idxkey)(i) = LinkType.lwin
& & & & & & & & & & & & ElseIf linkcount & 5 Then
& & & & & & & & & & & & & & dm(idxkey)(i) = LinkType.llng
& & & & & & & & & & & & End If
& & & & & & & & & & End If
& & & & & & & & Next
& & & & & & Next
& & & & Next
当这个循环运行完成之后，dm当中对应的byte就会被设置为lwin或llng，即胜利或长连。当然，长连在后续处理中与胜利合并了。以此类推（注意顺序，要从“高”棋型向“低”棋型生成），直到得到最小的棋型（在我的代码中是冲1或活1）。
& & & & & &好了，接下来我们可以讨论招法生成器是如何运行的。其实在这之前，额…………我们确实要考虑这样一些问题：
1、快速得到冲棋点
2、快速分辨冲棋点类型，如43肯定要比41来的重要……
3、按冲棋点类型排序冲棋点
& & & & & 在我的代码中，定义了两个表：
& & '各点的冲棋值表 & & & & & & & &&
& & dim cpTable(1)(239) As Integer
& & '冲棋点排序表
& & Private cpSort(1)(239) As Integer & & &&
当然这种定义方式是不允许的，只是为了更明确，这里这么写了。当添（提）一子时，根据坐标和走棋者，确定verkey更新的4个元素，进行更新后查找模板dm，确定需要更新的点坐标并将cpsort按冲棋点类型（2所述）进行分段排序（事实上cpsort是一个链表）。这样做更新的量就非常少、很准确、省去排序（为何排序在“剪裁函数”会解释）过程。
& & & & & &接下来生成招法就简单了，按顺序逐个生成就可以了。当然，如果需要足够优化的话，不要一次性生成全部走法，原因也在于剪裁过程，但我的代码一直都是全部生成（其实没有啥好处的，只是我懒得改）。当然，招法生成不仅仅是这一点生成和“排序”，启发算法有很多是基于招法生成的。
& & & & & &好了，至此招法生成就介绍完毕了。貌似只介绍了一段，其他的都是铺垫……
全部文章和源码整理完成，以后更新也会在下面地址：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3731041次
积分：8984
积分：8984
排名：第1008名
原创：76篇
转载：21篇
评论：72条
(13)(1)(1)(1)(1)(2)(2)(1)(1)(1)(3)(3)(21)(5)(4)(2)(11)(1)(8)(1)(3)(5)(6)1010人阅读
五子棋AI（12）
作者同类文章X
& & & & &开局库不是我自己制作的，是在网上下载的“十四地毯普”，然后我把它解析出来，去掉无用信息，进行压缩作为资源放在软件中。因为是执黑必胜的地毯，所以软件执白时很少用到开局库，除非开局库中的局面被证明是好局面（其实无禁手来讲，黑棋控盘稍强白棋就没有好局面——即使在地毯普中）。
& & & & 下面说一下解析LIB类型的地毯普，其实解析LIB根本没有什么难度，RENLIB是开源的，除了它使用的第三方bestmove.dll之外。只需要在它的主页上下载源码看一下就知道了，它是按位记录信息类型的，我用VB.NET复原了一部分解析代码，然后去掉对软件无用的部分。
& & & & 开局库的重点除了获取之外（五子棋的比较容易，因为有地毯普，不要介意禁手问题）就是保存，这里的保存不是指文件（保存为文件只需要用先序遍历保存，读取时设置一个后进先出记录就很容易复原树），而是指在内存中保存的形式——这种形式要便于根据局面取得招法，而且还有就是局面的对称、旋转局面都要易于查找。开始时我写了一系列的函数来完成这些工作，而且至今这些对称、旋转局面的方法依然存在在代码中。其主要原因就是把对称、旋转局面合并需要的解析时间太长了…………简直就是久远……但旋转走法非常简单。
& & & & 不要尝试用树的形式保存，然后去遍历，你会发现当局面上的棋子达到一定数目之后（例如十个），要搜索每种排列将是耗时非常长的。所以我们使用一个key/value集合来记录走法。而其中的key就取自局面key，这并不意味着搜索开局库还需要addpipe，我们只需要直接计算key就可以了。这样一来，就避免了全排列——key与顺序无关。value是一个走法数组，我的代码中用了一个list(of integer)，因为4字节记录坐标之外，我还记录了其他一些信息——例如走法的好坏。
& & & & 于是，搜索开局库时，传入当前走法路线mvs()，然后把他们用转换函数转换得到用于搜索的8个key，依次搜索，在最好的一组结果中随机取一个并逆转换即可。
& & & & 对于五子棋来讲，执黑必胜地毯普我们可以更深入的利用：树上的叶节点即VCF/VCT的起点。当然也可以这样理解：无论下一步白棋走哪里，黑棋也有VCF或VCT。之所以这样说，是因为在编码时即使知道当前走了叶节点，也不能马上搜索，当然如果你非要这么做将面临搜索对方所有可能走法或者提前一步进行VCF/VCT搜索，这样做无疑效率低太多。所以我的做法是识别上一步的上一步是叶节点走法，亦即上一步的上一步的上一步在开局库中得到了叶节点走法——也许你会考虑到，这不严格，但实际上如果考虑到走法有好坏记录以及白棋脱谱的情况，可以说这是严格的——这个严格是指一定存在VCT或VCF。
& & & & 具体实现来说，就是把走法路线的后几步去掉，然后在开局库中搜索，看看是否达到叶节点，如果是，则进行VCF/VCT搜索找到路径。
全部文章和源码整理完成，以后更新也会在下面地址：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3731043次
积分：8984
积分：8984
排名：第1008名
原创：76篇
转载：21篇
评论：72条
(13)(1)(1)(1)(1)(2)(2)(1)(1)(1)(3)(3)(21)(5)(4)(2)(11)(1)(8)(1)(3)(5)(6)阅读排行榜
评论排行榜6648人阅读
Java（26）
作者同类文章X
五子棋AI算法 也算是一个典型的游戏AI算法，一些棋类的AI算法都可以参考实现，下面是Java实现代码
棋盘抽象接口
import java.util.L
public interface IChessboard {
//取得棋盘最大横坐标
public int getMaxX();
//最大纵坐标
public int getMaxY();
//取得当前所有空白点，这些点才可以下棋
public List&Point& getFreePoints();
棋子类实现
public class Point {
// 这了性能，设成公有
public int getX() {
public Point setX(int x) {
public int getY() {
public Point setY(int y) {
public Point(int x, int y) {
public int hashCode() {
return x +
public boolean equals(Object obj) {
if (this == obj)
Point other = (Point)
if (x != other.x)
if (y != other.y)
}玩家抽象接口import java.util.L
public interface IPlayer {
//下一步棋子，传入对手已经下的棋子集合
public void run(List&Point& enemyPoints, Point point);
public boolean hasWin();
public void setChessboard(IChessboard chessboard);
public List&Point& getMyPoints();
}玩家基础抽象类
import java.util.ArrayL
import java.util.L
public abstract class BasePlayer implements IPlayer {
//我已下的棋子
protected List&Point& myPoints = new ArrayList&Point&(200);
protected IC
//棋盘最大横坐标和纵标，
protected int maxX;
protected int maxY;
//所有空白棋子
protected List&Point& allFreeP
public final List&Point& getMyPoints() {
return myP
public void setChessboard(IChessboard chessboard) {
this.chessboard =
allFreePoints = chessboard.getFreePoints();
maxX = chessboard.getMaxX();
maxY = chessboard.getMaxY();
myPoints.clear();
private final Point temp = new Point(0, 0);
//我是否是否赢了
public final boolean hasWin(){
if(myPoints.size()&5){
Point point = myPoints.get(myPoints.size()-1);
int count = 1;
int x=point.getX(),y=point.getY();
temp.setX(x).setY(y);
while (myPoints.contains(temp.setX(temp.getX()-1)) && temp.getX()&=0 && count&5) {
if(count&=5){
temp.setX(x).setY(y);
while (myPoints.contains(temp.setX(temp.getX()+1)) && temp.getX()&maxX && count&5) {
if(count&=5){
count = 1;
temp.setX(x).setY(y);
while (myPoints.contains(temp.setY(temp.getY()-1)) && temp.getY()&=0) {
if(count&=5){
temp.setX(x).setY(y);
while (myPoints.contains(temp.setY(temp.getY()+1)) && temp.getY()&maxY && count&5) {
if(count&=5){
//正斜向 /
temp.setX(x).setY(y);
while (myPoints.contains(temp.setX(temp.getX()-1).setY(temp.getY()+1)) && temp.getX()&=0 && temp.getY()&maxY) {
if(count&=5){
temp.setX(x).setY(y);
while (myPoints.contains(temp.setX(temp.getX()+1).setY(temp.getY()-1)) && temp.getX()&maxX && temp.getY()&=0 && count&6) {
if(count&=5){
count = 1;
temp.setX(x).setY(y);
while (myPoints.contains(temp.setX(temp.getX()-1).setY(temp.getY()-1)) && temp.getX()&=0 && temp.getY()&=0) {
if(count&=5){
temp.setX(x).setY(y);
while (myPoints.contains(temp.setX(temp.getX()+1).setY(temp.getY()+1)) && temp.getX()&maxX && temp.getY()&maxY && count&5) {
if(count&=5){
电脑AI类实现
import java.util.ArrayL
import java.util.C
import java.util.HashM
import java.util.L
import java.util.M
//算法核心类，算法的主体思想分三个步骤，
//第一步：根据双方的当前的形势循环地假设性的分别给自己和对方下一子（在某个范围内下子），并判断此棋子能带来的形势上的变化，如能不能冲4，能不能形成我方或敌方双3等，
//第二步：根据上一步结果，组合每一步棋子所带来的所有结果（如某一步棋子可能形成我方1个活3，1个冲4（我叫它半活4）等），包括敌方和我方的。
//第三步：根据用户给的规则对上一步结果进行排序，并选子（有进攻形、防守形规则）
public class BaseComputerAi extends BasePlayer {
// 四个方向，横- 、纵| 、正斜/ 、反斜\
private static final int HENG = 0;
private static final int ZHONG = 1;
private static final int ZHENG_XIE = 2;
private static final int FAN_XIE = 3;
//往前往后
private static final boolean FORWARD =
private static final boolean BACKWARD =
//标示分析结果当前点位是两头通（ALIVE）还是只有一头通（HALF_ALIVE），封死的棋子分析过程自动屏蔽，不作为待选棋子
private static final int ALIVE = 1;
private static final int HALF_ALIVE = 0;
//private static final int DEAD = -1;
//计算范围，太大的范围会有性能问题
private class CalcuteRange{
int xStart,yStart,xStop,yS
private CalcuteRange(int xStart, int yStart, int xStop, int yStop) {
this.xStart = xS
this.yStart = yS
this.xStop = xS
this.yStop = yS
//限定电脑计算范围，如果整个棋盘计算，性能太差，目前是根据所有已下的棋子的边界值加RANGE_STEP值形成，目前为1
private static final int RANGE_STEP = 1;
CalcuteRange currentRange = new CalcuteRange(0, 0, 0, 0);
private void initRange(List&Point& comuters, List&Point& humans){
currentRange.xStart = humans.get(0).getX()-RANGE_STEP;
currentRange.yStart = humans.get(0).getY()-RANGE_STEP;
currentRange.xStop = humans.get(0).getX()+RANGE_STEP;
currentRange.yStop = humans.get(0).getY()+RANGE_STEP;
for (Point point : humans) {
if(point.getX()-RANGE_STEP&currentRange.xStart){
currentRange.xStart = point.getX()-RANGE_STEP;
}else if(point.getX()+RANGE_STEP&currentRange.xStop){
currentRange.xStop = point.getX()+RANGE_STEP;
if(point.getY()-RANGE_STEP&currentRange.yStart){
currentRange.yStart = point.getY()-RANGE_STEP;
}else if(point.getY()+RANGE_STEP&currentRange.yStop){
currentRange.yStop = point.getY()+RANGE_STEP;
for (Point point : comuters) {
if(point.getX()-RANGE_STEP&currentRange.xStart){
currentRange.xStart = point.getX()-RANGE_STEP;
}else if(point.getX()+RANGE_STEP&currentRange.xStop){
currentRange.xStop = point.getX()+RANGE_STEP;
if(point.getY()-RANGE_STEP&currentRange.yStart){
currentRange.yStart = point.getY()-RANGE_STEP;
}else if(point.getY()+RANGE_STEP&currentRange.yStop){
currentRange.yStop = point.getY()+RANGE_STEP;
//如果范围扩大后超过了棋盘，则等于棋盘
currentRange.xStart=currentRange.xStart&0?0:currentRange.xS
currentRange.yStart=currentRange.yStart&0?0:currentRange.yS
currentRange.xStop=currentRange.xStop&=maxX?maxX-1:currentRange.xS
currentRange.yStop=currentRange.yStop&=maxY?maxY-1:currentRange.yS
// 分析当前形式的入口方法，分析总共分三个步骤，第三步骤可由子类干预以作难度控制
private Point doAnalysis(List&Point& comuters, List&Point& humans) {
if(humans.size()==1){//第一步
return getFirstPoint(humans);
//初始化计算范围
initRange(comuters, humans);
//清除以前的结果
initAnalysisResults();
// 开始分析，扫描所有空白点，形成第一次分析结果
Point bestPoint = doFirstAnalysis(comuters, humans);
if(bestPoint!=null){
//System.out.println(&这个棋子最重要，只能下这个棋子&);
return bestP
// 分析第一次结果，找到自己的最佳点位
bestPoint = doComputerSencondAnalysis(computerFirstResults,computerSencodResults);
if(bestPoint!=null){
//System.out.println(&快要赢了，就下这个棋子&);
return bestP
computerFirstResults.clear();
System.gc();
// 分析第一次结果，找到敌人的最佳点位
bestPoint = doHumanSencondAnalysis(humanFirstResults,humanSencodResults);
if(bestPoint!=null){
//System.out.println(&再不下这个棋子就输了&);
return bestP
humanFirstResults.clear();
System.gc();
//没找到绝杀点，第三次结果分析
return doThirdAnalysis();
//下第一步棋子，不需要复杂的计算，根据人类第一步棋子X值减1完成
private Point getFirstPoint(List&Point& humans) {
Point point = humans.get(0);
if(point.getX()==0 || point.getY()==0 || point.getX()==maxX && point.getY()==maxY)
return new Point(maxX/2, maxY/2);
return new Point(point.getX()-1,point.getY());
// private int debugx,//用于DEBUG
// 开始分析，扫描所有空白点，形成第一次分析结果
private Point doFirstAnalysis(List&Point& comuters, List&Point& humans){
int size = allFreePoints.size();
Point computerPoint =
Point humanPoint =
FirstAnalysisResult firstAnalysisR
for (int i = 0; i & i++) {
computerPoint = allFreePoints.get(i);
//先把X、Y坐标记下来，因为在分析过程中会改变原来的对象
x = computerPoint.getX();
y = computerPoint.getY();
if(x&currentRange.xStart || x&currentRange.xStop || y&currentRange.yStart || y&currentRange.yStop){
if(x==debugx && y==debugy){
System.out.println(&sssssssssssss&);
//尝试在此位置上下一个棋子，并分析在“横向”这个方向上我方可形成的状态，如活4，活3，半活4，活2等所有状态
firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, HENG);
computerPoint.setX(x).setY(y);//回复点位的原值，以供下次分析
if(firstAnalysisResult!=null){//无返回结果此方向上不可能达到五个棋子，
if(firstAnalysisResult.count==5)//等于5表示在此点上下棋子即可连成5个，胜利了，不再往下进行分析
return computerP
//记录第一次分析结果
addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);
//在“纵向”这个方向上重复上面的步骤
firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, ZHONG);
computerPoint.setX(x).setY(y);
if(firstAnalysisResult!=null){//死棋，不下
if(firstAnalysisResult.count==5)
return computerP
addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);
firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, ZHENG_XIE);
computerPoint.setX(x).setY(y);
if(firstAnalysisResult!=null){//死棋，不下
if(firstAnalysisResult.count==5)
return computerP
addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);
firstAnalysisResult = tryAndCountResult(comuters,humans, computerPoint, FAN_XIE);
computerPoint.setX(x).setY(y);
if(firstAnalysisResult!=null){//死棋，不下
if(firstAnalysisResult.count==5)
return computerP
addToFirstAnalysisResult(firstAnalysisResult,computerFirstResults);
//在“横向”上分析此棋子可在敌方形成如何状态，如敌方的活3、半活4等
firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, HENG);
computerPoint.setX(x).setY(y);
if(firstAnalysisResult!=null){//死棋，不下
if(firstAnalysisResult.count==5)
humanPoint = computerP
addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);
//“纵向”
firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, ZHONG);
computerPoint.setX(x).setY(y);
if(firstAnalysisResult!=null){//死棋，不下
if(firstAnalysisResult.count==5)
humanPoint = computerP
addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);
//“正斜”
firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, ZHENG_XIE);
computerPoint.setX(x).setY(y);
if(firstAnalysisResult!=null){//死棋，不下
if(firstAnalysisResult.count==5)
humanPoint = computerP
addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);
//“反斜”
firstAnalysisResult = tryAndCountResult(humans,comuters, computerPoint, FAN_XIE);
computerPoint.setX(x).setY(y);
if(firstAnalysisResult!=null){//死棋，不下
if(firstAnalysisResult.count==5)
humanPoint = computerP
addToFirstAnalysisResult(firstAnalysisResult,humanFirstResults);
//如果没有绝杀棋子，第一次分析不需要返回结果
return humanP
//第二次分析，分析第一次形成的结果，第一次分析结果会把一步棋在四个方向上可形成的结果生成最多四个FirstAnalysisResult对象（敌我各四）
//这里要把这四个对象组合成一个SencondAnalysisResult对象，
private Point doComputerSencondAnalysis(Map&Point,List&FirstAnalysisResult&& firstResults,List&SencondAnalysisResult& sencodResults) {
List&FirstAnalysisResult& list =
SencondAnalysisResult sr =
for (Point p : firstResults.keySet()) {
sr = new SencondAnalysisResult(p);
list = firstResults.get(p);
for (FirstAnalysisResult result : list) {
if(result.count==4){
if(result.aliveState==ALIVE){//经过前面的过滤，双方都排除了绝杀棋，有活4就下这一步了，再下一步就赢了
return result.//如果有绝杀，第一轮已返回，在此轮活4已经是好的棋子，直接返回，不再往下分析
sr.halfAlive4 ++;
computer4HalfAlives.add(sr);
}else if(result.count==3){
if(result.aliveState==ALIVE){
sr.alive3++;
if(sr.alive3==1){
computer3Alives.add(sr);
computerDouble3Alives.add(sr);
sr.halfAlive3++;
computer3HalfAlives.add(sr);
}else{//半活2在第一阶段已被排除，不再处理
sr.alive2++;
if(sr.alive2==1){
computer2Alives.add(sr);
computerDouble2Alives.add(sr);
sencodResults.add(sr);
//没有找到活4
//这个方法和上面的基本一样，但为了性能，少作几次判断，将人类和电脑的分开了
private Point doHumanSencondAnalysis(Map&Point,List&FirstAnalysisResult&& firstResults,List&SencondAnalysisResult& sencodResults) {
List&FirstAnalysisResult& list =
SencondAnalysisResult sr =
for (Point p : firstResults.keySet()) {
sr = new SencondAnalysisResult(p);
list = firstResults.get(p);
for (FirstAnalysisResult result : list) {
if(result.count==4){
if(result.aliveState==ALIVE){
human4Alives.add(sr);
sr.halfAlive4 ++;
human4HalfAlives.add(sr);
}else if(result.count==3){
if(result.aliveState==ALIVE){
sr.alive3++;
if(sr.alive3==1){
human3Alives.add(sr);
humanDouble3Alives.add(sr);
sr.halfAlive3++;
human3HalfAlives.add(sr);
sr.alive2++;
if(sr.alive2==1){
human2Alives.add(sr);
humanDouble2Alives.add(sr);
sencodResults.add(sr);
//没有找到活4
private void sleep(int miniSecond){
Thread.sleep(miniSecond);
} catch (InterruptedException e) {
//第三次分析，双方都不可以制造活4，找双活3棋子，不行就找半活4，再不行就找单活3，双活2
private Point doThirdAnalysis() {
if(!computer4HalfAlives.isEmpty()){
return computer4HalfAlives.get(0).
System.gc();
sleep(300);
Collections.sort(computerSencodResults);
System.gc();
//即将单活4，且我没有半活4以上的，只能堵
Point mostBest = getBestPoint(human4Alives, computerSencodResults);
if(mostBest!=null)
return mostB
Collections.sort(humanSencodResults);
System.gc();
mostBest = getBestPoint();
if(mostBest!=null)
return mostB
//拿出各自排第一的，谁好就下谁
return computerSencodResults.get(0).
//子类实现这个方法，并改变其顺序可以实现防守为主还是猛攻
protected Point getBestPoint(){
//即将单活4，且我没有半活4以上的，只能堵
Point mostBest = getBestPoint(computerDouble3Alives, humanSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(computer3Alives, humanSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(humanDouble3Alives, computerSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(human3Alives, computerSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(computerDouble2Alives, humanSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(computer2Alives, humanSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(computer3HalfAlives, humanSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(human4HalfAlives, computerSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(humanDouble2Alives, computerSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(human2Alives, computerSencodResults);
if(mostBest!=null)
return mostB
mostBest = getBestPoint(human3HalfAlives, computerSencodResults);
return mostB
//第三次分析的最后一步，第二次结果已经过排序，在此可以从前面选出最好的棋子
protected Point getBestPoint(List&SencondAnalysisResult& myBest,List&SencondAnalysisResult& yourSencodResults){
if(!myBest.isEmpty()){
if(myBest.size()&1){
for (SencondAnalysisResult your : yourSencodResults) {
if(myBest.contains(your)){
return your.
return myBest.get(0).
return myBest.get(0).
//第一次分析结果
private final Map&Point,List&FirstAnalysisResult&& computerFirstResults = new HashMap&Point,List&FirstAnalysisResult&&();
private final Map&Point,List&FirstAnalysisResult&& humanFirstResults = new HashMap&Point,List&FirstAnalysisResult&&();
//第二次总结果
protected final List&SencondAnalysisResult& computerSencodResults = new ArrayList&SencondAnalysisResult&();
protected final List&SencondAnalysisResult& humanSencodResults = new ArrayList&SencondAnalysisResult&();
//第二次分结果，电脑
protected final List&SencondAnalysisResult& computer4HalfAlives = new ArrayList&SencondAnalysisResult&(2);
protected final List&SencondAnalysisResult& computerDouble3Alives = new ArrayList&SencondAnalysisResult&(4);
protected final List&SencondAnalysisResult& computer3Alives = new ArrayList&SencondAnalysisResult&(5);
protected final List&SencondAnalysisResult& computerDouble2Alives = new ArrayList&SencondAnalysisResult&();
protected final List&SencondAnalysisResult& computer2Alives = new ArrayList&SencondAnalysisResult&();
protected final List&SencondAnalysisResult& computer3HalfAlives = new ArrayList&SencondAnalysisResult&();
//第二次分结果，人类
protected final List&SencondAnalysisResult& human4Alives = new ArrayList&SencondAnalysisResult&(2);
protected final List&SencondAnalysisResult& human4HalfAlives = new ArrayList&SencondAnalysisResult&(5);
protected final List&SencondAnalysisResult& humanDouble3Alives = new ArrayList&SencondAnalysisResult&(2);
protected final List&SencondAnalysisResult& human3Alives = new ArrayList&SencondAnalysisResult&(10);
protected final List&SencondAnalysisResult& humanDouble2Alives = new ArrayList&SencondAnalysisResult&(3);
protected final List&SencondAnalysisResult& human2Alives = new ArrayList&SencondAnalysisResult&();
protected final List&SencondAnalysisResult& human3HalfAlives = new ArrayList&SencondAnalysisResult&();
//第一次分析前清空上一步棋子的分析结果
private void initAnalysisResults(){
computerFirstResults.clear();
humanFirstResults.clear();
//第二次总结果
computerSencodResults.clear();
humanSencodResults.clear();
//第二次分结果
computer4HalfAlives.clear();
computerDouble3Alives.clear();
computer3Alives.clear();
computerDouble2Alives.clear();
computer2Alives.clear();
computer3HalfAlives.clear();
//第二次分结果，人类
human4Alives.clear();
human4HalfAlives.clear();
humanDouble3Alives.clear();
human3Alives.clear();
humanDouble2Alives.clear();
human2Alives.clear();
human3HalfAlives.clear();
System.gc();
//加入到第一次分析结果中
private void addToFirstAnalysisResult(FirstAnalysisResult result,Map&Point,List&FirstAnalysisResult&& dest){
if(dest.containsKey(result.point)){
dest.get(result.point).add(result);
List&FirstAnalysisResult& list = new ArrayList&FirstAnalysisResult&(1);
list.add(result);
dest.put(result.point, list);
//第一次分析结果类
private class FirstAnalysisResult{
int aliveS
private FirstAnalysisResult(int count, Point point, int direction) {
this(count, point, direction, ALIVE);
private FirstAnalysisResult(int count, Point point, int direction,int aliveState) {
this.count =
this.point =
this.direction =
this.aliveState = aliveS
private FirstAnalysisResult init(Point point,int direction,int aliveState){
this.count = 1;
this.point =
this.direction =
this.aliveState = aliveS
private FirstAnalysisResult cloneMe(){
return new FirstAnalysisResult(count, point, direction,aliveState);
//第二次分析结果类
class SencondAnalysisResult implements Comparable&SencondAnalysisResult&{
int alive4 = 0;
int alive3 = 0;
//半活4，一头封的
int halfAlive4 = 0;
//半活3，一头封的
int halfAlive3 = 0;
int alive2 = 0;
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((point == null) ? 0 : point.hashCode());
public boolean equals(Object obj) {
SencondAnalysisResult other = (SencondAnalysisResult)
if (point == null) {
if (other.point != null)
} else if (!point.equals(other.point))
private SencondAnalysisResult(Point point) {
this.point =
//第三次分析时，对第二次分析结果进行排序，此为排序回调函数
public int compareTo(SencondAnalysisResult another) {
return compareTowResult(this, another);
//返加-1则第一个参数优先，1则第二个参数优先，0则按原来顺序
private int compareTowResult(SencondAnalysisResult oneResult,SencondAnalysisResult another){
if(oneResult.alive4&another.alive4){
return -1;
if(oneResult.alive4&another.alive4){
if(oneResult.halfAlive4&another.halfAlive4){
return -1;
if(oneResult.halfAlive4&another.halfAlive4){
if(oneResult.alive3&another.alive3){
return -1;
if(oneResult.alive3&another.alive3){
if(oneResult.alive2&another.alive2){
return -1;
if(oneResult.alive2&another.alive2){
if(oneResult.halfAlive3&another.halfAlive3){
return -1;
if(oneResult.halfAlive3&another.halfAlive3){
//一个临时对象，供第一次分析时临时存放分析结果使用，如果分析出有活1以上（不含）的结果，则调用其cloneMe方法获得结果，否则抛弃此结果
private final FirstAnalysisResult far = new FirstAnalysisResult(1, null, HENG);
// 分析如果在当前位下一子，会形成某个方向上多少个子，参数：当前己方已下的所有点，当前要假设的点，需要判断的方向
private FirstAnalysisResult tryAndCountResult(List&Point& myPoints,List&Point& enemyPoints, Point point,int direction) {
int x = point.getX();
int y = point.getY();
FirstAnalysisResult fr =
int maxCountOnThisDirection = maxCountOnThisDirection(point, enemyPoints, direction, 1);
if(maxCountOnThisDirection&5){
//无意义的棋子
//此方向不足五个空位，已排除己方已下的棋子
}else if(maxCountOnThisDirection==5){
//半死状态，当是一头通
fr = far.init(point, direction,HALF_ALIVE);
//两头皆通
fr = far.init(point, direction,ALIVE);
//在前和后的方向上计算一次
countPoint(myPoints,enemyPoints,point.setX(x).setY(y),fr,direction,FORWARD);
countPoint(myPoints,enemyPoints,point.setX(x).setY(y),fr,direction,BACKWARD);
if(fr.count&=1 || (fr.count==2 && fr.aliveState==HALF_ALIVE)){//活1，半活2及其以下结果，抛弃
//返回复制的结果
return fr.cloneMe();
//棋子出了墙
private boolean isOutSideOfWall(Point point,int direction){
if(direction==HENG){
return point.getX()&0 || point.getX()&=maxX;//最大的X和Y值均在墙外所以用等号
}else if(direction==ZHONG){
return point.getY()&0 || point.getY()&=maxY;
}else{//这里可能有问题
return point.getX()&0 || point.getY()&0 || point.getX()&=maxX || point.getY()&=maxY;
private Point pointToNext(Point point,int direction,boolean forward){
switch (direction) {
case HENG:
if(forward)
point.x++;
point.x--;
case ZHONG:
if(forward)
point.y++;
point.y--;
case ZHENG_XIE:
if(forward){
point.x++;
point.y--;
point.x--;
point.y++;
case FAN_XIE:
if(forward){
point.x++;
point.y++;
point.x--;
point.y--;
//在某个方向（八个中的一个）可下多少棋子，这个方法是第一分析中的核心方法
private void countPoint(List&Point& myPoints, List&Point& enemyPoints, Point point, FirstAnalysisResult fr,int direction,boolean forward) {
if(myPoints.contains(pointToNext(point,direction,forward))){
fr.count ++;
if(myPoints.contains(pointToNext(point,direction,forward))){
fr.count ++;
if(myPoints.contains(pointToNext(point,direction,forward))){
fr.count ++;
if(myPoints.contains(pointToNext(point,direction,forward))){
fr.count ++;
}else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){
fr.aliveState=HALF_ALIVE;
}else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){
fr.aliveState=HALF_ALIVE;
}else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){
fr.aliveState=HALF_ALIVE;
}else if(enemyPoints.contains(point) || isOutSideOfWall(point,direction)){
fr.aliveState=HALF_ALIVE;
//在某个方向上是否还能下到满五个棋子
private int maxCountOnThisDirection(Point point,List&Point& enemyPoints,int direction,int count){
int x=point.getX(),y=point.getY();
switch (direction) {
case HENG:
while (!enemyPoints.contains(point.setX(point.getX()-1)) && point.getX()&=0 && count&6) {
point.setX(x);
while (!enemyPoints.contains(point.setX(point.getX()+1)) && point.getX()&maxX && count&6) {
case ZHONG:
while (!enemyPoints.contains(point.setY(point.getY()-1)) && point.getY()&=0) {
point.setY(y);
while (!enemyPoints.contains(point.setY(point.getY()+1)) && point.getY()&maxY && count&6) {
//正斜向 /
case ZHENG_XIE:
while (!enemyPoints.contains(point.setX(point.getX()-1).setY(point.getY()+1)) && point.getX()&=0 && point.getY()&maxY) {
point.setX(x).setY(y);
while (!enemyPoints.contains(point.setX(point.getX()+1).setY(point.getY()-1)) && point.getX()&maxX && point.getY()&=0 && count&6) {
case FAN_XIE:
while (!enemyPoints.contains(point.setX(point.getX()-1).setY(point.getY()-1)) && point.getX()&=0 && point.getY()&=0) {
point.setX(x).setY(y);
while (!enemyPoints.contains(point.setX(point.getX()+1).setY(point.getY()+1)) && point.getX()&maxX && point.getY()&maxY && count&6) {
//下棋子，对外接口
public void run(List&Point& humans,Point p) {
//把人类下的最后一步棋子去除
allFreePoints.remove(humans.get(humans.size()-1));
//电脑可以下的一步棋子
Point result = doAnalysis(myPoints, humans);
//去除电脑下的棋子
allFreePoints.remove(result);
//加入到电脑棋子中，下棋了
myPoints.add(result);
人类玩家实现起来就非常简单
import java.util.L
public class HumanPlayer extends BasePlayer {
public void run(List&Point& enemyPoints,Point p) {
getMyPoints().add(p);
allFreePoints.remove(p);
总结：虽然是Java写的但算法已被抽象可以方便的修改成各种平台的实现。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：173163次
积分：2427
积分：2427
排名：第8556名
原创：61篇
评论：64条
(2)(1)(1)(4)(4)(8)(6)(5)(4)(5)(1)(4)(6)(1)(1)(6)(7)