围棋编程思路

来源:转载

首先我想把我写的那个围棋封装成一个class Vegos,设想这个class封装围棋的属性和方法(考
虑的是19路的棋子,封装的方法有插入一颗棋子的method,这个method里面考虑提子,重构链等
东西。。当然还有删除棋子的method,因为提子要删除子,删除子又要重构链的关系),这个
class写好后再调用这个class去现在所有的围棋操作,包括后面没有写的数目等操作。 
再说说我的提子的思路(首先说一下我现在正在学围棋,初懂规则,数目还不是很会,故下面有
错的地方望指出),我想,提子首先要构成环,再判断环里是不是达到提子的要求,比如环里完
全充满其他棋子;求环思路,先看一条直线上一种棋子的一条链上是不是大于两颗棋子,如果大
于两颗棋子,那么这个可能位于环的正中,然后向这条直线的上下分别查找环的尽头,直到没有
构成环跳出,或达到环的顶端。当然有各种各样的环,(因为环的可能型太多,所以我现在考虑
的是构成上半环和下半环,半环比全环编程更好实现且对数目好,,,原因很多)。思路大致这
样,没有完全说全,不过我感觉这个不好用文字说,图解更好,不过这个不支持图。 
下面我把我部分代码放上,望指教。  

//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();//用于我查看棋子数组的一个方法体
}
//------------------------------------------------------------------
 希望大家提出宝贵意见。谢谢~~ 
围棋编程源码-delphi2008-10-26 23:00我用的是PASCAL,因为数据结构清晰明了,排错极易且
IDE简单!   这段代码是玩cgo的最基本的内容,任何时候调用play函数,它总能在一个19×19的棋盘上正
确计算下子,包括解决最基本的提子,打劫等等问题,最简单不过,现放出来供爱好CGo的朋友参
考。如有问题,请QQ:385550324或计算机围棋群(2445708)中反映。
围棋吧http://weiqi8.5d6d.com
UNIT _XGoAI;
interface
uses Classes,SysUtils,Math;
//==============================================================================
//定义棋盘智能
//fHistory的格式是(B/W)(##);
//此部分符合GTP规范
//==============================================================================
//棋盘智能对象,这一部分应当与GTP协议吻合
TYPE TXGoAI=CLASS(Tobject)
private
fVertex:array[0..18,0..18]of char; //盘所有位只有'B','W'和#0三种情况
fHistory:TstringList; //着棋历史,格式为[B/W+AA+AAAAAAAA]
public
Constructor Create;
Destructor Destroy;override;
//读取
function GetColor(Const Row,Col:integer):char; //取得棋子颜色
function GetSequence(Const Row,Col:integer):integer; //取得次序
function GetTurn:char; //取得该下子
function GetLast:string; //最得最后子
//GTP命令
procedure clear_board; //清除
function Play(Const GoVertex:string):Boolean; //下子
function Genmove(Const GoType:char):string; //生成一子
function Undo:Boolean; //回退
END;

implementation
//=============================================================================
//围棋智能
//=============================================================================
//以下过程均为置棋过程式函数,函数依赖GoHistory和fGoVertex两变量;
//-----------------------------------------------------------------------------
CONSTRUCTOR TXGoAI.Create;
BEGIN
fHistory:=TstringList.Create;
clear_board;
END;
DESTRUCTOR TXGoAI.Destroy;
BEGIN
fHistory.Free;
END;
//查询次序
FUNCTION TXGoAI.GetTurn:char;
var c:char;
BEGIN
result:='B';//默认为黑,当首步时
if fHistory.Count>0 then
begin
c:=upcase(fHistory[fHistory.Count-1][1]);//检查最后一个子颜色
if c='B' then result:='W';
if c='W' then result:='B';
end;
END;
//查询末子
FUNCTION TXGoAI.GetLast:string;
VAR i:integer;
BEGIN
i:=fHistory.Count;
if i>0 then result:=copy(fHistory[i-1],2,2)
else result:='';
END;
//查询棋子
FUNCTION TXGoAI.GetColor(Const Row,Col:integer):char;
BEGIN
Result:=fVertex[Row,Col];
END;
//查询次序,某子的最后下子次序
FUNCTION TXGoAI.GetSequence(Const Row,Col:integer):integer;
VAR s:string;
i:integer;
BEGIN
result:=0;
s:=char(Row+byte('A'))+char(Col+byte('A'));
for i:=fHistory.Count-1 downto 0 do
if s=copy(fHistory,2,2) then
begin
result:=i+1;
exit;
end;
END;
//GTP兼容格式函数
//清理盘
PROCEDURE TXGoAI.clear_board;
VAR x,y:integer;
BEGIN
fHistory.Clear;
for x:=0 to 18 do for y:=0 to 18 do
fVertex[x,y]:=#0;
END;
//基本功能:下一子
FUNCTION TXGoAI.Play(Const GoVertex:string):Boolean;//命令格式为/[W]##
//基本功能:是否可下子!
function GetCapable(Const Row,Col:integer;Turn:char;var

Dstr:string):Boolean;//返回相邻子
var bs,es,os,ss:string;
//检查某点棋块气的个数
function GeTXGoEmpty(Const Row,Col:integer;Var

Bstr,Estr,Ostr:string):Boolean;
var i,j:integer;
C:array[0..18,0..18] of Boolean; //存储是否被访问的信


// 递归的找寻程序,返回相同子,周围气,别外子
function check(const m,n:integer):integer;
begin
Result:=0;
if (m<0)or(n<0)or(m>18)or(n>18) then exit;//一定要有
if C[m,n] then exit;
C[m,n]:=True; //设置已访问过
if fVertex[m,n]=fVertex[Row,Col] then
begin //如果是相同子及空


Bstr:=BStr+char(m+byte('A'))+char(n+byte('A'));
Result:=Check(m,n-1)+Check(m,n+1)+Check(m-1,n)

+Check(m+1,n);
end else
begin
if fVertex[m,n]=#0 then
begin //是个空
EStr:=EStr+char(m+byte('A'))+char(n+byte

('A'));
result:=1;
end else
OStr:=OStr+char(m+byte('A'))+char(n+byte

('A'));
end;
end;//end of function check
begin
result:=false;
if (fVertex[Row,Col]=#0)then exit;
Result:=true;
BStr:='';OStr:='';EStr:='';
for i:=0 to 18 do for j:=0 to 18 do C[i,j]:=false;
check(Row,Col);//递归查询
end;//end of function GeTXGoEmpty
//得到死子
function Getdeathgo(const cg:string):string;
var i,r,c:integer;
b,e,o,s:string;
begin
s:='';
for i:=0 to length(cg)p 2 -1 do//此处可能增大了时间
begin
r:=byte(cg[i*2+1])-byte('A');
c:=byte(cg[i*2+2])-byte('A');
if GeTXGoEmpty(R,C,b,e,o) then
if e='' then s:=s+b;
end;
result:=s;
end;
begin
Result:=False;
if (fVertex[Row,Col]<>#0) then exit;//放在前一句之后
fVertex[Row,Col]:=Turn;//预设定值
if GeTXGoEmpty(Row,Col,bs,es,os) then//正常检查气数
begin
Dstr:=Getdeathgo(os);//得到相邻其它的死子
if es<>'' then Result:=true else//有空
if length(Dstr)>2 then Result:=true else//有死子
if length(Dstr)=2 then//是不是打劫
begin//判断打劫
ss:=fHistory[fHistory.count-1];
if not ((Dstr=copy(ss,2,2))and
(bs=copy(ss,4,length(ss)-2))) then Result:=True;
end;
end;
fVertex[Row,Col]:=#0;//恢复点值
end;
//清除死子
procedure Cleargo(const gs:string);//清子串
var i:integer;
r,c:integer;
begin
for i:=0 to length(gs)p 2 -1 do
begin
r:=byte(gs[i*2+1])-byte('A');
c:=byte(gs[i*2+2])-byte('A');
fVertex[r,c]:=#0;
end;
end;
// main procedure
VAR DeadGo:string;
Row,Col:integer;
Goturn:char;
BEGIN
result:=false;
Row:=Byte(GoVertex[2])-Byte('A');
Col:=Byte(GoVertex[3])-Byte('A');
if not((Row in [0..18])and(Col in [0..18]))then exit;
case GoVertex[1] of
'B':Goturn:='B';
'W':Goturn:='W';
else exit;
end;//end of case
if GetCapable(Row,Col,Goturn,DeadGo) then//返回气s
begin
if DeadGo<>'' then Cleargo(DeadGo);//去掉死子
fHistory.Add(GoVertex+DeadGo);//加入历史后面是被提的字
fVertex[Row,Col]:=Goturn;//设定颜色
result:=true;
end;
END;
//基本功能:悔一步
FUNCTION TXGoAI.Undo:Boolean;
VAR x,y,n:integer;
s:string;
//补上被提子
procedure Restorego(const gs:string);
var i:integer;
r,c:integer;
begin
for i:=0 to length(gs)p 2 -1 do
begin
r:=byte(gs[i*2+1])-byte('A');
c:=byte(gs[i*2+2])-byte('A');
fVertex[r,c]:=GetTurn;
end;
end;
BEGIN
n:=fHistory.Count;
if n>0 then
begin
s:=copy(fHistory[n-1],2,length(fHistory[n-1])-1);
Restorego(copy(s,3,length(s)-2));
x:=byte(s[1])-byte('A');
y:=byte(s[2])-byte('A');
fVertex[x,y]:=#0;
fHistory.Delete(n-1);
Result:=true;
end else Result:=false;//i=0
END;
//智能的关键,产生走法
FUNCTION TXGoAI.Genmove(Const GoType:char):string; //生成一子
BEGIN
//N/A
END;
 end


分享给朋友:
您可能感兴趣的文章:
随机阅读: