请教大侠们关于围棋编程思路的问题：～

本人大四就要毕业了，过了高级程序员，现在做一个毕业设计，准备这学期做完后下学期直接出去找工作。用c＋＋builder做一个围棋的软件，界面等一些其他的小东西已经做出来了，现在遇到一个最难的地方，就是围棋提子的算法，我也想了一些算法，但都不是很完美，不是无敌的，不能针对所有可能的情况提子，已经想了两个星期了，感觉进度不是很大，所以上csdn上面来请教一下高手们。不知有没有做过围棋项目的，望给我提一下思路，只要思路就可以，包括提子用到数据结构里面到底那些东西（比如图里面最短路径等玩意），还有怎么去考虑提别人的子等。听我们老师说：曾经有一个大学的一个同学毕业设计就是做的围棋，算法很好，听说还得了国家优秀毕业设计的提名，我也想做一个围棋，现在不求算法最精，但求能正确提子，算目就行～～

望指教，特别是提子的思路，谢谢！！

13 个解决方案

#1

象棋软件水平还可以,围棋没有好的,原因就是算法.

#2

提子就是在没有眼的情况下遍历四周，要考虑边角的问题，所以判断提子你就要先判断眼位，遍历眼位我觉得要种子填充法改改就可以了，没有眼位就遍历边线，要不你考虑能不能一起来
数目不好做，除非你很熟悉围棋，简单点说一个无忧角在对方没有打击的情况下你要怎么算，这个可不是可以怎么遍历的，在围棋上无忧角是铁活的，除非对方打入你一直不理，那这样就无话说了
要分析出中盘胜不容易啊

#3

数目还要考虑双活的问题，这个比较特殊

#4

围棋算法是最难的.

#5

struct TWQPoint {char BW ; int x,y;}; 
//多個點構成一塊棋<穩定塊>
class TBaseBlock :public std::vector<TWQPoint>  
{
 int FSpace ;//存放氣的臨時變量
public :
TWQPoint *GetPoint(int x,int y);//返回指定點的信息，無則返回NULL
};
//虛連的塊<尖，跳，大小飛連等等>
class TVirtualBlock :public std::vector<TBaseBlock >  
{
int FSpace ;//存放氣的臨時變量
public :
int GetBlockSpace();//返回這塊棋的氣,考慮簡單的尖與跳等最壞情況下的氣數。
bool AddPoint(TWQPoint &Point); //加入一個點，如該點與塊不存在連的關系則失敗。
};
//遊戲者
class TBasePlayer
{
protected:
 static TWQPoint *QP ; //兩個player一定要共用一塊棋盤。
 static int QPLine  ; //默認為19*19的棋盤,這是用一維數組模擬的二維數組
 TBasePlayer *OtherPlayer ;  //(對戰方)
public:
 std::vector<TBaseBlock > oBlack; //穩定塊
 TVirtualBlock vBlock; //虛連塊
 int AllCount ; //下子數
 int WinCount ; //提子數
 std::vector<TWQPoint> Histroy ;

 int GetBlockSpace(TBaseBlock &Block);//返回一塊棋的氣,
 int GetBlockSpace(TVirtualBlock &Block);//返回一塊棋的氣,
 bool CanInsert(TWQPoint *Point);//該點是否可下，即非禁著點(劫及不可著點的判定)

bool IsLinkToMe(TWQPoint const &Point);//判定該點與自己有無連的關系

//下一步棋,MaxTime為給定考慮秒數
 virtual bool SetNextPoint(TWQPoint &Point,int MaxTime)
 {
  //先簡單實現為棋盤上的一個隨機點,以後由子類優化,MaxTime在這裡不用考慮
  std::vector<TWQPoint *> CanInserts ; 
  for(int i = 0 ; i < QPLine*QPLine ; ++i)
    if(QP[i].BW == ' ' && CanInsert(QP + i))
      CanInserts.push_back(QP + i); 
  if(CanInserts.empty()) //無點可下 
    return false ; 
  randomize();
  int Index = rand() % (CanInserts.size()); //一個隨機點
  Point.x = CanInserts [Index ]->x ; //這棋好臭。
  Point.y = CanInserts [Index ]->y ; 
  return true ;   
 }
};
//圍棋,可簡單算氣及判定死活及棋是否結束
class TBaseWQ
{
protected :
 TWQPoint QP[19][19]; //棋盤共19*19。  
public :
 TBasePlayer *Black , *White ; //用指針才可以操作從TBasePlayer繼承的有智能的Player
 std::vector<TWQPoint> Histroy ; //歷史記錄器，記錄每一步棋

 //入子,該點如為禁子則失敗。每一個入子都將重組Player當前數據,同時更新棋盤QP[19][19]; 
 bool AddPoint(char BW,int x,int y); 
 bool End(); //是否可判定結束.

//棋盤顯示接口,顯示交由另一個類實作，不會影響圍棋邏輯。
 static void (*UpdateQPView)(TWQPoint *QP,int count = 19*19 ); //重畫全部
 static void (*UpdateQPPoint)(TWQPoint const & QP);            //重畫一點
};

#6

圍棋算法很難寫，上面給的是一個圍棋模型原型，希望對你有幫助。

這是基於塊的思路。算法也是基於塊的。連起來的就是穩定的塊，尖飛等是不穩定塊，每下一個子都重算哪些塊是相連，虛連(立二拆三就是一個虛連)。

基本算法是：塊的氣，死活。塊已經被實際斷開

智能算法是：如何判斷一個塊已經被斷開(還沒下子),能否斷塊，如何有效地連自己的塊與不讓對方連塊等等。攻一個塊的策略及自己的塊可能受到怎樣的攻擊。開局中盤收官判斷。

定式原型匹配算法：該塊判定屬於某個定式。違反定式的常用懲罰方法。

這些邏輯都不好寫，能用的估值函數更是難做。

#7

一般我在中游下，中游說是俺業余五段，再過一兩個月可能會到業余六段。
可我感覺只有業余初段的樣子。如果能做好一個圍棋程序，我想棋力就會增加罷。
網上有源碼： http://www.lankogo.com 可看看。不過我不贊成lankogo那種程序寫法。

先有模型(原型)，才有算法，最後界面。用BCB做界面應該是容易的。
僅記在原型和算法中不要有界面代碼。這樣寫起來才容易。
網上有多資料，但均沒用對象封裝，所以我不看好。
要做圍棋程序，真的很難。用業余時間做，更難(除非上班不用做事了)。

#8

是不好做，广东有位教授写过一个，是不中大的就是华工的，写的就很不错，不过也不是绝对准确，但是大概不错，他的人机对弈也是我看过最好的，不过就算*也比较简单就可以下赢，这方面实在比较难，但是定式就很多，要处理好这些实在太难了

#9

首先谢谢各位大侠们百忙之中对我的指教，现在我把我现在的思路给大家说说，看能否，本人经验不是很足，望批评指正。谢谢！

首先我想把我写的那个围棋封装成一个class Vegos，设想这个class封装围棋的属性和方法（考虑的是19路的棋子，封装的方法有插入一颗棋子的method，这个method里面考虑提子，重构链等东西。。当然还有删除棋子的method，因为提子要删除子，删除子又要重构链的关系），这个class写好后再调用这个class去现在所有的围棋操作，包括后面没有写的数目等操作。

再说说我的提子的思路（首先说一下我现在正在学围棋，初懂规则，数目还不是很会，故下面有错的地方望指出），我想，提子首先要构成环，再判断环里是不是达到提子的要求，比如环里完全充满其他棋子；求环思路，先看一条直线上一种棋子的一条链上是不是大于两颗棋子，如果大于两颗棋子，那么这个可能位于环的正中，然后向这条直线的上下分别查找环的尽头，直到没有构成环跳出，或达到环的顶端。当然有各种各样的环，（因为环的可能型太多，所以我现在考虑的是构成上半环和下半环，半环比全环编程更好实现且对数目好，，，原因很多）。思路大致这样，没有完全说全，不过我感觉这个不好用文字说，图解更好，不过这个不支持图。

下面我把我部分代码放上，望指教。

#10

//Vegos.h头文件
#ifndef VegosH
#define VegosH
#include <Dialogs.hpp>
//---------------------------------------------------------------------
#define whiteChainMemoMax 1000
#define whiteChainMemoMin 501
#define blackChainMemoMax 500
#define blackChainMemoMin 1
#define aroundMax 8
#define blackChess 1
#define whiteChess 0
#define nullChess -1
//---------------------------------------------------------------------
class Vegos
{
    protected:
        int chess[20][20];     //存储棋子状态：1－500黑子501－1000白子
        int chessStatus;       //记录当前该下棋方：1－黑子0－白子
        int xp,yp;             //记录当前下子的位置
        int whiteChainMemo;    //记录白棋链的计数，从501－1000
        int blackChainMemo;    //记录黑棋链的计数，从1－500
        //创建一个能压入周围8颗子的栈。。
        int chessStack[aroundMax];
        void push8Chess(int x,int y)//压入8颗子进栈
        {//顺序分别是当前子的左上角到友下角
            chessStack[0]=chess[x-1][y-1];
            chessStack[1]=chess[x][y-1];
            chessStack[2]=chess[x+1][y-1];
            chessStack[3]=chess[x-1][y];
            chessStack[4]=chess[x+1][y];
            chessStack[5]=chess[x-1][y+1];
            chessStack[6]=chess[x][y+1];
            chessStack[7]=chess[x+1][y+1];
        }
        void emptyChessStack()//清空当前压入的8颗棋子
        {
            for(int i=1;i<aroundMax;i++)
                chessStack[i]=nullChess;
        }
        int judgeNullAround()//判断当前的棋子周围的8方位有棋子没有
        {
            for(int i=0;i<aroundMax;i++)
                if(chessStack[i]!=nullChess)
                    return 0;
            return 1;
        }
        void replaceChessChain(int end,int begin)
        {//把begin标识的链转换为end标识的链
            for(int i=1;i<20;i++)
                for(int j=1;j<20;j++)
                    if(chess[i][j]==begin)
                        chess[i][j]=end;
        }
        void rebuilderChain(int x,int y)
        {//重构链表结构
            for(int i=0;i<aroundMax;i++)
            {
                if(chessStack[i]<=blackChainMemoMax&&chessStack[i]>=blackChainMemoMin&&chessStatus==blackChess)
                {//如果当前是黑子且所在栈的子也是黑子
                    if(chess[x][y]==nullChess)
                        chess[x][y]=chessStack[i];
                    if(chess[x][y]!=nullChess&&chess[x][y]!=chessStack[i])
                        replaceChessChain(chess[x][y],chessStack[i]);//重构链
                }
                if(chessStack[i]<=whiteChainMemoMax&&chessStack[i]>=whiteChainMemoMin&&chessStatus==whiteChess)
                {//如果当前是白子且所在栈的子也是白子
                    if(chess[x][y]==nullChess)
                        chess[x][y]=chessStack[i];
                    if(chess[x][y]!=nullChess&&chess[x][y]!=chessStack[i])
                        replaceChessChain(chess[x][y],chessStack[i]);//重构链
                }
            }
        }
        void takeoffChess()//提子
        {
            
        }

        void showChessChain() //自己写的查看棋子数组变化的方法，用于辅助编程
        {
            String str="";
            for(int i=1;i<20;i++)
            {
                for(int j=1;j<20;j++)
                {
                    str+=IntToStr(chess[j][i]);
                    if(IntToStr(chess[j][i]).Length()==1)
                        str+="  ";
                    if(IntToStr(chess[j][i]).Length()==2)
                        str+=" ";
                }
                str+="\n";
            }
            ShowMessage(str);
        }

//下面一段注释起来的代码是以前写的
//打算用邻接表来存储连接构，后来感觉这个链遍历影响速度
//故改成上面的算法，用数组存储链，1-500黑子，相同标识的子构成一个链
/*        typedef struct point
        {                      //表示当前的棋子
            int x,y;
        }point;
        typedef struct chess_chain
        {                      //一条棋子的链表
            point chess_point;
            chess_chain *next;
        }chess_chain;
        typedef struct chess_chain_list
        {                      //用于以后定义链表数组分别指向不同链表
            chess_chain *head; //指向链表头
            chess_chain *leftBorder; //指向链表左边的棋子链 用于边界棋子算法
            chess_chain *rightBorder; //指向链表友边的棋子链
            chess_chain *topBorder; //指向链表上边的棋子链
            chess_chain *bottomBorder; //指向链表下边的棋子链
        }chess_chain_list_white[100],chess_chain_list_black[100];
        //上面定义白棋链表队列和黑棋链表队列
*/
    public:
        Vegos();
        ~Vegos();
        int getXPress() const{    return xp;  }
        int getYPress() const{    return yp;  }
        int getChessStatus() const{   return chessStatus; }
        int getChess(int i,int j) const{  return chess[i][j]; }
        void insertChess(int x,int y);    //插入一颗棋子

/*
        int getXPress() const{    return xp;  }
        int getYPress() const{    return yp;  }
        int getChessStatus() const{   return chessStatus; }
        int getChess(int i,int j) const{  return chess[i][j]; }
        void setXPress(int x){    xp=x; }
        void setYPress(int y){    yp=y; }
        void setChessStatus(int status){    chessStatus=status; }
        void setChess(int i,int j,int ches){   chess[i][j]=ches;    }
        //插入一颗棋子，参数x，y坐标和棋子颜色
        int insertChess(int x,int y,int chessColor);
*/
};
//---------------------------------------------------------------------
#endif

//Vegos.cpp
#include "Vegos.h"
//------------------------------------------------------------------
Vegos::Vegos()
{
    for(int i=1;i<20;i++)
        for(int j=1;j<20;j++)
            chess[i][j]=nullChess;
    xp=yp=21;
    for(int i=1;i<aroundMax;i++)
        chessStack[i]=nullChess;
    chessStatus=blackChess;
    blackChainMemo=blackChainMemoMin;
    whiteChainMemo=whiteChainMemoMin;
}
//------------------------------------------------------------------
Vegos::~Vegos(){}
//------------------------------------------------------------------
void Vegos::insertChess(int x,int y)
{   //还有一个判断，能否落子，根据后面的环判断。。。
    //这儿还有点代码没写，因为要判断构成环的链，而那个链现在还没有做
    //还有边界子现在还没有考虑，听老师说，边界子要另外考虑，故还没做
    if(x!=1&&x!=19&&y!=1&&y!=19)//非边界棋子
    {
        emptyChessStack();  //清空栈
        push8Chess(x,y);//压入x，y周围的8颗棋子；
        if(judgeNullAround()==1)//x，y周围没有任何棋子
        {
            if(chessStatus==whiteChess)
                chess[x][y]=whiteChainMemo++;//计数白链的标识自加
            else
                chess[x][y]=blackChainMemo++;//计数黑链的标识自加
        }else  //周围有棋子就判断加入链，重构链，提子等
        {
            rebuilderChain(x,y); //重构链表结构
            //还有提子等现在还没有做。。
        }

    }
    chessStatus=1-chessStatus; //改变下子方
    showChessChain();//用于我查看棋子数组的一个方法体
}
//------------------------------------------------------------------

希望大家提出宝贵意见。谢谢～～

#11

有一个地方有glgo源码的，在PandaNet，网址：http://www.pandanet.co.jp/English/glgo/download.html
试试下面这个地址
http://www.pandanet.co.jp/English/glgo/downloads/gnugo-3.6-win.zip

也有可执行程序，对弈水平还可以。

#12

上面的地址好像不对，是这个
http://panda-igs.joyjoy.net/English/glgo/downloads/src/

#13

或者搜索一下gnugo-3.4.tar.gz，vc的源码，我下载了，也可以发给你。