象棋開源演算法

㈠ pascal 中國象棋 Alpha-Beta演算法源程序及解釋

Alpha值代表的是發起走棋一方(期望極大值)做能接受的最小值,搜索極大值一方必須要找到一個比Alpha值更大的，否則這步棋就沒有任何意義
Beta值代表的是對手(期望極小值)所能接受的最壞值，搜索極小值的一方必須找到一個比Beta值更小的一步棋，否則也是沒意義的（因為有更好的一步棋已經生成了)

先看函數調用方式
int AlphaBeta(int depth, int alpha, int beta);

AlphaBeta(5, -INFINITE INFINITE);
這是發起走棋一方（搜索極大值的一方）調用的，因此設定為alpha為
-INFINITE；

這里假設是採用負極大值演算法的

int AlphaBeta(int depth, int alpha, int beta)
{
if(depth == 0 || IsGameOver()) return Evaluate(); //如果層數為0或者已達最終狀態則返回本步棋的估值
for(each possible move)
{
MakeMove();

int val = -AlphaBeta(depth - 1, -beta, -alpha);
UnMakeMove();

if(val >= beta)
{
return val;
//注意，這里需要返回val，因為上一層應該知道具體搜索到的值，以配合各種Alpha-Beta演算法的變種
}
if(val > alpha)
{
alpha = val;
...
//當然 這里還需要記錄這步最佳的走法
}

}
return alpha;//返回最好的值
}

首先假設是負極大演算法，
Alpha值是父節點（非root)能搜索到的最大值，任何比他小的值都沒意義。
Beta值是你所能找到的最壞的一種情況，任何比它大的都沒意義。
{
int val = -AlphaBeta(depth - 1, -beta, -alpha);
}
注意這個所謂的負極大的估值函數是估算本方的最優值，所以你的對手（子節點）估算出來的最優值如果大於你的-Beta
例如-beta == 3 子節點估值== 4，那麼他實際上返回後（取負得-4)是小於你的Beta,所以它是有意義的。再看這個-alpha,
實際上是本層的beta是上一層節點（對手)的最大值的負值，如果任何本層節點取值,例如-alpha == 3,子節點估值為4,
4 >= 3，那麼返回的是-4,-4< -3(alpha那個地方），所以無意義，因為在本層所有節點又都是越取越大（負極大），
所以本層也就沒必要找了，直接剪枝了

㈡ 象棋軟體如何開發的

先弄明白數據的結構：
MantisChessDef.h里的東西一定要先看一下， 否則會摸不到頭腦的。
還有棋盤坐標：
象棋棋盤大小9x10,為了便於編程，規定棋盤每條邊留有一個元素的邊界。
這樣棋盤大小（包括邊界）變成11x12。棋盤x坐標軸向右，y軸向下。
黑棋永遠在上方，在標准開局時左上角的黑車坐標是（1，1）。

局面用這三個變數表示:

static POINT g_pointChessman[32]; //棋子坐標
static int g_iChessmanMap[11][12]; //棋位狀態
static int g_iSide; //輪到哪方走

智能部分有幾個函數的前三個參數就是這個東西, 應該不難理解吧?

---------------------------------------------------------------------------------------
search函數:

先說明一下， 經常有朋友問我要原理, 但我公開源代碼是給大家一個參考， 而不是什麼教程，所以我不想說那些理論的東西。
基本原理是α-β搜索， 很多人工智慧的教科書上都有講到， 沒看過的的趕快去找一本來啃一啃；
雖然這些書上的文字大多晦澀難懂，但畢竟講得明明白白。
沒有書的朋友請發揮一下主觀能動性， 去找一找，不要來問我要， 因為我也沒有。

我在這里只分析一下search函數:

弄懂α-β搜索後來看看這個博弈樹， 看怎麼編程實現它。

先規定一下， 我們用一個整數表示局面的好壞.
這個數越大說明局面對 "走棋方" 越有利，0表示雙方實力相等。

1a( 1) ┬ 2a(-1) ┬ 3a(-1)
│ └ 3b( 1)
└ 2b(-5) ┬ 3c( 2)
├ 3d(-4)
└ 3e( 5)

分析一下這棵樹，有這么個特點: 父結點的值 = -MAX(子結點的值)

我們還知道1、每個結點對應一個局面。2、底層的結點的值是"估"出來的。

於是我們可以寫出偽代碼了:

偽代碼: 搜索一個結點下的分支， 得到這個結點的值。

參數: 局面，搜索深度

返回值:結點的值

int search(局面，int depth)
{
if(depth!=0)//不是底層結點
{

枚舉出所有子結點(列出所有走法);

int count=子結點數；
int maxvalue= -∞;
for(int i=0;i<count;i++)//遍歷所有結點
{
算出子結點局面;

maxvalue=max(maxvalue，search(子結點局面,depth-1));
}
return -maxvalue;
}
else //是底層結點
{
return 估計值;
}
}

這就是搜索演算法的框架， 用到了遞歸。
MantisChess的智能部分函數都在MantisChessThink.cpp里， 其中search是搜索， 跟上面的這個search差不多，我把它出來注釋一下：

int Search(int tmap[11][12],POINT tmanposition[32],int &tside,int man, POINT point,int upmax,int depth)
{

//前面的三個參數就是局面。
//man 和point 是走法，用來計算本結點的局面。 這里是把計算局面放在函數的開頭，跟上面的偽代碼不太一樣。
//upmax: up - 上一層， max - 最大值， 這是α-β的剪枝用到的東西， 後面再講。
//depth: 搜索深度

int ate,cur,maxvalue,curvalue,xs,ys;
int count;

//#####################這一段是計算本結點的局面#########################################
ate=32;
//移動棋子:
xs=tmanposition[man].x;ys=tmanposition[man].y; //原坐標
if (SideOfMan[tmap[point.x][point.y]]==!tside) //目標點有對方的棋子
{
ate=tmap[point.x][point.y]; //記錄下被吃掉的棋子
if(ate==0 || ate==16)
{
return 9999;
}
tmanposition[ate].x=0; //目標點的棋子被吃掉
}

tmap[point.x][point.y]=man; //這兩行是:
tmap[xs][ys]=32; //在map上的移動
tmanposition[man]=point;
tside=!tside;
//####################################################################################

depth--;

if(depth>0) //不是底層結點
{
int chessman[125];
POINT targetpoint[125];
if(EnumList(tmap,tmanposition,tside,chessman,targetpoint,count)) //枚舉出所有子結點(列出所有走法)
{
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
//這里是剪枝(不是α-β剪枝), 原理是在正式搜索之前先用較淺的搜索來得到誤差較大的值
//然後根據這些值來對子結點排序， 只保留最好的S_WIDTH個結點進行正式搜索。
//顯然，這個剪枝有一定的風險

if(depth>=2 && count>S_WIDTH+2)
{
int value[125];
cur=0;
maxvalue=-10000;
while(cur< count)
{
curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],-10000,depth-2);
value[cur]=curvalue;
if(curvalue>maxvalue)maxvalue=curvalue;
cur ++;
}
::Mantis_QuickSort(value,chessman,targetpoint,0,count-1); //排序
count=S_WIDTH;//剪枝
}
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

maxvalue=-10000;
cur=0;
while(cur< count)
{
curvalue=Search(tmap,tmanposition,tside,chessman[cur],targetpoint[cur],maxvalue,depth);
if(curvalue>maxvalue)maxvalue=curvalue;
if(curvalue>=-upmax)goto _ENDSUB; //α-β剪枝, 符合剪枝條件的就Cut掉。 這里用了goto語句了， 千萬別學我。
cur ++;
}
}
else maxvalue=9800;
}
else //是底層結點
{
maxvalue=Value(tmap,tmanposition,tside); //估值
}

_ENDSUB:

//返回之前要恢復父結點的局面
//####################################################################################
tmanposition[man].x=xs; //這兩行是:
tmanposition[man].y=ys; //在face上的恢復
tmap[xs][ys]=man; //在map上的恢復
if(ate!=32)
{
tmanposition[ate]=point;
tmap[point.x][point.y]=ate;
}
else tmap[point.x][point.y]=32;

tside=!tside;
//####################################################################################

return -maxvalue;
}

上面的代碼用到了α-β剪枝, 舉個例子就明白了:

還是這個博弈樹，從上往下遍歷。

1a( 1) ┳ 2a(-1) ┳ 3a(-1)
┃ ┗ 3b( 1)
┗ 2b(-5) ┯ 3c( 2)
├ 3d(-4)
└ 3e( 5)

2a遍歷完後 upmax=-1, 繼續遍歷完3c後返回2b， 發現3c=2>-upmax, 這時就不用管3d和3e了, 因為無論他們的值是多少 2b=-max(3c,3d,3e)<2a 一定成立,
也就是說2b可以安全地剪掉。這就是α-β剪枝。

從上面的代碼來看我的MantisChess演算法與標準的α-β剪枝搜索並沒有什麼不同， 只不過加了排序和剪枝而已。

㈢ 天機象棋是否抄襲或者說是引用國際象棋開源代碼

目前國內象棋軟體幾乎均引用或抄襲國際象棋的開源代碼，天機也不例外。以往只為演算法的不公開，也沒有開源代碼，所以中國象棋軟體的發展很慢，自主研發的也多來自寶島台灣。近幾年來，隨著國際象棋軟體代碼的開源，所以大陸在此領域才得以發展。
綜上所述，天機「借鑒」國際象棋的代碼，幾乎是肯定的。

㈣ 中國象棋演算法

對於中國象棋，每一個字都有自己的規則，正所謂無規矩不成方圓。

棋盤先設定好，a:array[1..10][1..9] of MapStruct;
是個二維數組，每個單元符全自定義的棋盤結構
不要定義一個棋字結構

int StepJudge(int oldx,int oldy,int nowx,int nowy)

/* oldx,oldy 棋字原來位置 */
/* oldx,oldy 棋字新位置 */
/* 判斷從原位置到新位置的合法性 */
{
int index,count=0;
int nox,noy;
int x,y,x1,x2,y1,y2;
BYTE ChessId; /* 棋字是哪一方的，有RED，BLUE，NONE三種值 */
ChessId=map[oldx][oldy].Id;
if(ChessId==NONE) return 0;
if(oldx==nowx&&oldy==nowy) return 0;
if(nowx>8||nowx<0||nowy<0||nowy>9) return 0;
nox=nowx-oldx;noy=nowy-oldy;
switch(map[oldx][oldy].num)
{
case 0:/*HeaderCapital*/將或帥
{
if(map[nowx][nowy].num==0&&map[nowx][nowy].Id!=NONE&&oldx==nowx)
{
/*Face to Face*/
y1=oldy;y2=nowy;
if(nowy<oldy) Swap(&y1,&y2);
for(y=y1+1;y<y2;y++) if(map[nowx][y].Id!=NONE) count++;
if(count==0) return 1;
}
if(abs(nox)>1||abs(noy)>1||abs(nox)==1&&abs(noy)==1) return 0;
if(nowy>2&&nowy<7||nowx<3||nowx>5) return 0;
break;
}
case 14: case 15:/*Genaral*/車
{
if(abs(nox)!=0&&abs(noy)!=0) return 0;
if(abs(nox)>1&&noy==0)
{
x1=oldx;x2=nowx;
if(nowx<oldx) Swap(&x1,&x2);
for(x=x1+1;x<x2;x++) if(map[x][nowy].Id!=NONE) return 0;
}
if(nox==0&&abs(noy)>1)
{
y1=oldy;y2=nowy;
if(nowy<oldy) Swap(&y1,&y2);
for(y=y1+1;y<y2;y++) if(map[nowx][y].Id!=NONE) return 0;
}
break;
}
case 10: case 11:/*Horse*/馬
{
if(abs(nox)==2&&abs(noy)==1||abs(nox)==1&&abs(noy)==2)
{
if(abs(nox)==1&&map[oldx][oldy+noy/2].Id!=NONE) return 0;
if(abs(nox)==2&&map[oldx+nox/2][oldy].Id!=NONE) return 0;
break;
}
else return 0;
}
case 12: case 13:/*Gun*/炮
{
if(abs(nox)>0&&abs(noy)>0) return 0;
if(abs(nox)>0&&noy==0)
{
x1=oldx;x2=nowx;
if(nowx<oldx) Swap(&x1,&x2);
for(x=x1+1;x<x2;x++) if(map[x][nowy].Id!=NONE) count++;
}
else if(nox==0&&abs(noy)>0)
{
y1=oldy;y2=nowy;
if(nowy<oldy) Swap(&y1,&y2);
for(y=y1+1;y<y2;y++) if(map[nowx][y].Id!=NONE) count++;
}
if(count==0&&map[nowx][nowy].Id!=NONE) return 0;
if(count==1&&map[nowx][nowy].Id==NONE) return 0;
if(count>1) return 0;
break;
}
case 3: case 4:/*Minister*/象或相
{
if(abs(nox)!=2||abs(noy)!=2) return 0;
else if(map[oldx+nox/2][oldy+noy/2].Id!=NONE) return 0;
if(nowy==0||nowy==4||nowy==5||nowy==9)
if(nowx==2||nowx==6) break;
if(nowy==2||nowy==7)
if(nowx==0||nowx==4||nowx==8) break;
}
case 1: case 2:/*Shi*/士或仕
{
if(abs(nox)!=1||abs(noy)!=1) return 0;
if(nowy>2&&nowy<7||nowx<3||nowx>5) return 0;
break;
}
case 5: case 6: case 7: case 8: case 9: /*Soldier*/兵或卒
{
if(abs(nox)>0&&abs(noy)>0) return 0;
if(ChessId==GREEN&&GreenChess[0].y<3||ChessId==RED&&RedChess[0].y<3)
{
if(oldy>4)
{
if(nox==0&&noy!=1) return 0;
if(abs(nox)!=1&&noy==0) return 0;
}
if(oldy<5) if(nox!=0||noy!=1) return 0;
}
if(ChessId==GREEN&&GreenChess[0].y>6||ChessId==RED&&RedChess[0].y>6)
{
if(oldy<5)
{
if(nox==0&&noy!=-1) return 0;
if(abs(nox)!=1&&noy==0) return 0;
}
if(oldy>4) if(nox!=0||noy!=-1) return 0;
}
index=map[oldx][oldy].num;
if(ChessId==GREEN)
if(GreenChess[0].y<3&&GreenChess[index].y>4||GreenChess[0].y>6&&GreenChess[index].y<5)
GreenChess[index].FixLevel=ADVANCED_SOLDIER_LEVEL;
if(ChessId==RED)
if(RedChess[0].y<3&&RedChess[index].y>4||RedChess[0].y>6&&RedChess[index].y<5)
RedChess[index].FixLevel=ADVANCED_SOLDIER_LEVEL;//兵過河後等級值加1
break;
}
}
if(ChessId==map[nowx][nowy].Id) return 2;
else return 1;
}

用c語言寫的

㈤ 中國象棋AI實現

喜歡下象棋的朋友都知道，象棋的博弈更像是一場堅持到最後才是勝利的游戲。阿爾法狗和柯潔的國際象棋的博弈在當時可以是引起了一場轟動的，人工智慧的出現更是改變了很多東西。這應該算是一個重大突破，在一個以人為智力博弈的游戲中，AI的出現的對決是一場突破人的游戲，機械人自然人的智商，其實也在說明了時代的大潮流發展，未來的世界的正朝著新領域去發展。

我們知道如果從計算機統計的步數的復雜和空間的復雜上來講，相對來說搜索比較容易實現了，只要模擬一下博弈樹，再進行極大值和極小值的搜索 + 剪枝，難么一個DFS就完成了。 舉個例子，我們都知道，每一步有很多多子可以走，每一個子有那麼多步可以走。如果要思考很多層，那博弈樹就太大了。

這兩塊演算法寫出能跑的不難，寫出能PK過自己的AI也不難，但要真的要寫好是個巨大的坑，要量化自己演算法的好壞就是和開源演算法進行對弈，在相同開銷下比勝率，或者勝率相同比開銷。

㈥ 象棋軟體引擎分析，詳細信息，引擎是怎麼搜索招式的

作者:nicepeople10

中象棋軟搜索引擎揭密(一) fenon
北京大賽終於過去了, 在這場盛事前後這段時間, 靜下心來回顧了走過的象棋研究的路子,心得感觸良多.為了紀念這段時間的美好, 我決定把這段時間積累的對象棋引擎的心得, 總結分享出來
我個人希望通過這篇文章,把一些頂尖棋軟的知識普及開來,提高開源象棋軟體的水平.

1. 搜索引擎和審局之間的關系, 如何建立

閱讀下面的內容時, 首先需要了解幾個背景知識
a. 人工智慧的博弈搜索樹和PVS搜索之間的關系
b. PVS搜索是無損搜索
c. PVS的搜索效率和搜索次序的關系

首先明確幾點:

a. 做一個全PVS的搜索, 在限定了層數的情況下, 如果基於不正確的知識(比如子力表),並不能保證一定能把殺棋找出來(可能會跑去吃子)
b. 為了提高棋力, 無損搜索PVS是不足夠的, 還是需要剪枝的
c. 搜索樹和審局之間的關系, 首先知識必須能夠引導搜索到正確盤面(這個地球人應該都知道), 第二是避免搜索把正確的分支剪除掉(這個談論得少一些,我以前曾經有很長一段時間不知道)
我認為, 審局和搜索之間的關系的建立, 在於
a. 知識是帶有正確的傾向性的(只能說是傾向性,因為知識很難做到全面准確)
b. 搜索是根據知識而採取剪枝方式的(這個下面詳細分析)

下面我舉一個簡單的例子, 來說明知識和搜索之間的關系

帥
_____
| | |
馬 _| 將_|_兵
| _ |_ |_ |_象

在這個盤面, 兵只要靠近王一步, 就可以將死了對方, 但是基於子力表做depth=1的PVS搜索,只會選擇: 兵吃象, 有利, 而且評估子力分數很高, 所以吃象

那麼, 有什麼辦法避免這種情況呢?

a. depth=1的時候不做剪枝
b. 給予引擎審局的知識, 告訴引擎保持"馬非底線兵"這種組合對將才具有殺傷力

這樣就給出了兩種選擇, 哪種更好?

實際上, b這種選擇有兩種局限
a. 局限於現在對審局模型建立的水平, b這種情況需要花費大量的人力功夫來維護完整的知識, 而且很難做到准確
b. 目前的引擎的搜索棋步排序, 大都是基於最近訪問->殺棋步->吃子步這樣的棋步排序方法, 我們可以很容易想像到, 使用全面復雜的知識, 會引起搜索結果沖突(湊著一個吃子或者殺棋的步子去走, 但是最後發現達不到預期的效果), 大大降低了搜索的效率

正是因為上面的原因, 現在我所了解到的高端引擎, 大都是通過控制剪枝的危險程度, 來彌補知識的不足, 比如, 在nullmove中限制depth>=2, 或者, 在lmr(late move rection)--如變種:fruit的history pruning, 控制depth>=3, 都是利用控制剪枝來彌補知識的缺陷.

我們很清楚知道, depth<=2的時候, 都限制了不能剪枝的話, 那麼剛才的盤面, 並不需要任何知識,就可以找出殺棋步, 但是, 這個是不是我們需要的呢? 我想不是的, 如果限制了depth<=2不能剪枝的話, 我們會發現我們的搜索, 產生了大量的節點, 啊, 天啊, 可怕的搜索浪費

當然, 最理想的方法是, 搜索排序的次序是基於知識的, 而且盤面評估是基於知識的, 如果我們能夠達到這樣的效果, 嗯, 我想depth<=1不剪枝的限制也可以去掉了, 這樣的引擎肯定效率更高吧

現在, 讓我們想想, 哪些分支我們是不想被錯誤剪掉的? 當然是殺棋步, 殺棋>吃子, 基於子力表的搜索PVS, 很可能漏掉的棋步是殺棋步, 而這個恰恰是我們不想見到的
對於攻殺激烈的中國象棋,可以說兩個引擎的差別在於,誰能更快更准確找到殺棋步.

口語化一點來說,給你多搜索兩層的能耐,你能保證絕對能通過蠶食我的大子把我變成光棍司令? 尤其是隨著高層效應的出現(引擎和硬體的發展,搜索的層數越來越大), 這種可能更是趨向於零, 所以, 我們應該盡量避免漏掉殺棋步

我知道有很多引擎的做法是, 對有潛在攻勢的局面做出模糊判斷, 並且賦予高分, 如越容易發生殺棋的棋步, 給予越高的分數, 例如三子歸邊的分數>馬炮的分數, 這樣就可避免因為吃馬炮而漏掉殺棋, 但是這種模糊判斷有些致命的缺點
a. 模糊知識,會造成大量的搜索浪費(條件越不準確, 越容易造成搜索浪費)
b. 模糊知識會造成錯誤的判斷, 導致亂棄子
c. 引擎發展需要更長的發展周期, 需要大量的對局來積累知識

一種比較適中的解決方案是, 採取depth<=1不剪枝的搜索方法, 並且給予depth=1時候, 可以形成殺棋的棋型知識的判斷
這種方法的原理是, depth=1的搜索,可以達到depth==2的效果, 並且可以避免模糊知識判斷帶來的誤搜索的缺陷

這種解決方案的優點在於
a. depth=1可以生成殺棋的知識可以窮舉
b. 知識准確度高,可以大幅度減少搜索浪費

缺點在於, depth=1可以形成的殺型, 覆蓋面有限, 剩下的知識, 還是需要通過一些模糊判斷來補充, 當然, 這種補充少很多了, 而且完善起來也難度降低很多

上面的介紹可以說是知識模型的缺陷造成的對搜索的依賴, 下面我再來說說, 知識對搜索產生的影響

我們假設有一個盤面, depth=11的PVS全搜索才能發現殺棋, 那麼下面的知識, 做depth=10搜索時,哪種才能走出正確的棋步呢?

a. 對depth=1情況可殺棋的知識評估
b. 對depth>=2情況可殺棋的知識評估
c. 子力組合(如單車單王勝單王)和子力優勢
d. 位置分(不是子力表,只是位置的分數,如靈活度等)

實際上我們很容易就可以判斷出來, depth=1的知識評估,能走出正確的棋步,情況b也可能走出正確的棋步, 但是會有一定的誤判, c, d大都情況下, 走不出正確的棋步

我們現在對所有的知識打分, 這個分數依賴的因素應該是(depth, 准確度, 搜索浪費), 即score=形勢*(准確度/(depth*搜索浪費))

因為用評估盤面希望得到的分數等於depth>3的棋步, 准確度是相當低甚至會引起大量錯誤的, 所以我們對盤面評估會有一定的限度,同理,評估depth=1變化內的盤面,我們可以做到非常精確,這個時候可以給一個准確的分數

上面提到的a,b,c,d四種知識,對中國象棋軟體的知識覆蓋面是相當廣了, 我們可以很簡單看出, a可以獎勵>馬炮的分數, 而b因為可能走入誤區, 常常只是獎勵>士相的分數, 子力組合不會產生誤區,但是需要搜索很深才能得出正解,所以分數也是不會太高,位置分則更小了

但是, 給予引擎全面而准確的知識是否恰當呢? 即, 知識是不是越全面, 棋力越強呢? 很多朋友都問過這個問題, 並且認為恰當的知識會減少搜索量, 而且這也是很多朋友追求的方向. 我實踐的答案是否. 搜索其實是追求一種性價比, 單位搜索量內, 能得到最好的搜索結果, 才是好的搜索. 簡單說說原理, 當盤面有兩三個知識傾向都可以產生PV路徑的時候, 只會帶來引擎的左右徘徊, 尤其在殺棋的盤面, 會大大降低搜索的效率, 這部分的實踐結果, 我會在"6. 建立以kingsafety為核心的審局, 以及審局模型的詳細分析"再進一步詳細分析

這里我想糾正一個錯誤的想法,常常有一些不了解搜索引擎原理的朋友,拿一些盤面,讓棋軟去判斷,看誰能更快更准找到正解,要盡快解出這種盤面,往往需要大量的模糊知識,或者足夠的深度,前者無疑是把棋軟送上絕路的一種做法.這種評估只是有一定的意義,但絕對不是衡量棋軟水平的標准.

2. fruit引擎分析, fruit引擎能達到2600的高度的原因 (對比crafty進行闡述)

fruit引擎並不追求速度,實際上,fruit並沒有使用流行的bitfile,bitrank技術或者bitboard,所以fruit的nps在國際象棋引擎中並不算高(我想比起crafty應該比不上),如果說兩者的差異在於評估的話,嗯,那不在我所了解的范圍,我只談談兩者引擎上面的差別

a. fruit的pv節點的意義以及基於pv節點搜索剪枝的效率
能夠在搜索中, 把PV節點區分出來, 並且根據節點類型進行剪枝, fruit可以說對PVS理解是非常深刻的.

PV節點的定義大家可以查查相關資料, 既然PV節點表示正確的搜索結果, 那麼就肯定不應該剪掉. 同樣,對於不是PV節點的, 就不會找出正確的搜索路徑, 這就應該剪掉.這個也是fruit剪枝的理論依據。

道理是這樣說, 但是我們一開始並不知道每一個節點的類型, 所以在搜索的時候, 會假設某個節點不是PV節點, 然後看它是否會fail, 如果fail,再做PV節點的搜索.

假如這種假設是成立的, 那麼就成功完成了對該非PV節點路徑的剪枝,否則,需要重新搜索,因為對PV節點假設判斷的搜索是做windows=1的搜索,所以耗費的代價是很低的.

下面來看看fruit的實現方法,我認為fruit對PV節點理解的實現方法非常優雅.

int search_root()
{
本節點做PV搜索

if (樹根節點並且首節點)
下一層節點為PV節點 // 這個時候還沒有找出PV路徑,所以必須做PV節點搜索
else
{
下一層節點做假設不是PV節點的搜索
if (fail)
下一層節點做PV節點的搜索
}
}
int search_full()
{
根據上一層對該節點的判斷, 進行節點搜索

if (首節點 || 假設不是PV節點的搜索) // 當假設不是PV節點時, windows=1這個時候不應該假設,應該直接計算了,否則就是重復計算浪費時間
下一節點的節點類型跟本節點類型一致
else
{
下一層節點做假設不是PV節點的搜索
if (fail)
下一層節點做PV節點的搜索
}
}

中象棋軟搜索引擎揭密(二) fenon
crafty中,對PV節點的區分方法,是PV節點是否落在[-vMate,+vMate]中,實際上,這種判斷方法,對子樹的PV節點並不能做出有效的判斷,這也直接導致了搜索效率的下降

正是因為PV節點的特殊意義,所以凡是PV節點,fruit都不做剪枝,不從HASH取步,甚至PV節點還需要加強搜索的強度(參考TogaII)

b. fruit的nullmove剖析

我們先來看看fruit的nullmove的實現
if (UseNull && depth >= NullDepth && node_type != NodePV) { // 不對PV節點進行剪枝, 而且depth==1時不剪枝(原因參考上文)

if (!in_check // 不是將軍盤面
&& !value_is_mate(beta) // 當落入一個不知道上限的窗口時,不剪枝,這種情況發生在height==2時
&& do_null(board) // 國象規矩限定子>=2
&& (!UseNullEval || depth <= NullRection+1 || eval(board) >= beta)) { // 根據距離葉子或者alpha,beta搜索中,棋形的評估進行控制

我想, 對上面的控制條件,大家都是很好理解的, fruit中NullRedcution==3, 這個可以理解為fruit審局做得比較完善,depth<=4進入審局搜索盤面評估的結果, 逼近搜索的結果, 而eval則是對depth>4時候剪枝的控制條件,這種控制條件往往是根據棋形進行控制, crafty是控制大子的個數, fruit是控制評估的結果, 考慮到這個結果因引擎而異, 我就不在這里討論哪種條件才是更好的了

new_depth = depth - NullRection - 1;

move_do_null(board,undo);
value = -full_search(board,-beta,-beta+1,new_depth,height+1,new_pv,NODE_OPP(node_type));
move_undo_null(board,undo);

fruit的nullmove會導致一種和以外不同的搜索情況產生,crafty的做法是,上一層做了NULLMOVE,現在輪到我了,我應該移動棋步,但是fruit的做法,會引起雙方的等待,這是否正確?

答案是,很正確.首先,考慮演算法上面的等價性,連續做NULLMOVE,其實等價於我不知道你是否做了NULLMOVE,不過我也嘗試做一個NULLMOVE,看你是否能對我造成威脅,這個並不違背NULLMOVE的思想,而且一個不會產生PV路徑的節點,做搜索有意義嗎?沒有意義.既然如此,那麼就剪掉吧.

對nullmove的結果,fruit有兩種特別的處理手段

第一,不保存結果,因為fruit的演算法的剪枝,會讓實際的值和nullmove產生的值差別很大
第二,對某些特殊情況,fruit會做一個nullmove verify的search, fruit嘗試全面利用nullmove, 但是某些情況, nullmove成功的概率有限, 需要做一定的驗證

fruit對nullmove的實現方法,可以說得上是歷史性的(開源的引擎來說),這個演算法的優異,是fruit搜索效率特高的一個根本原因

c. fruit的qs加強

在上文中, 我已經提過, fruit是嘗試通過控制depth<=1使用全搜索的方法, 盡可能發現殺棋, 那麼, 對nullmove來說, 如果depth<=4,發生了一個剪枝, 立刻進入了qs, 馬上就把殺棋步剪掉了

為了防止這種情況, fruit對剛進入qs的棋步,不單單生成吃子步,還生成將軍步,這可以有效防止把殺棋步漏掉的情況.

qs裡面,fruit對吃子步產生的將軍步,會解將,讓對方保持繼續進攻的機會,這也是為了防止qs漏掉殺棋步的一種有效措施

雖然qs的論述很少,而且很簡單,但是,對qs中,將軍的檢查,卻有著消耗20%性能,提高50%功能的性價比,這個也是crafty所缺少的

d. fruit的history pruning

要了解history pruning, 首先建議參考國象中成熟的演算法lmr (late move rection)的論述
fruit對lmr引入了history value,並且對搜索結果做了verify,有效避免了lmr曾經的fail high的問題
這里就不對history pruning的限制條件做詳細的闡述了,實際上這種防止危險的檢查方法和nullmove的限制是類似的,而且會根據不同引擎知識和搜索結合的特點而存在差異
history pruning經實踐證明, 是一種非常有效的剪枝方法, 並且絕對不會對棋力有降低的影響(其實根本原因是不會漏掉殺棋步)

history pruning根據國外的測試,能夠提高elo 100,舊版的crafty並沒有history pruning

e. fruit的hash實現方法

fruit的hash實現方法,經實踐,大概比crafty的方法提高了5%~10%的性能

fruit對每個盤面,保存了一個上界和一個下界,如果對一個盤面搜索時,發現該盤面的搜索范圍上界比過往的下界都要小, 則返回保存的下界, 如果發現搜索范圍的下界比保存的上界要大, 則返回保存的上界, 如果發現盤面落入保存的窗口中, 則當保存的上界和下界重合而且搜索深度比當前搜索深度更深時, 返回保存的結果

這種hash的處理方法,修正了crafty中,只能對單邊情況保存的不足, 有效提高了效率

需要注意的地方是, 在iterative search中, 每次fruit都會把搜索出來的PV路徑都保存到hash中,這是用於取步(不是取值), 還有,在處理hash沖突時候, fruit使用了多個cluster的方法...需要細究的細節很多, 大家有興趣可以仔細看看fruit的實現

f. fruit的search root move list

fruit對每次搜索後對root節點記錄分值,並根據分值重新排序,以便下一次使用,當棋步產生振盪的時候(在兩個棋步之間徘徊)會有效提高引擎的搜索效率

g. fruit的FAIL SOFT

嗯, 關於FAIL SOFT以及實踐的方法, 可以參考縱馬奔流的****和fruit的代碼, 我就不再無聊多說一次了..

3. fruit 2.1和TogaII1.2.1的差異,elo 100的差距原因

首先需要說明的是,我是用diff的方法,比較兩者在搜索實現上的差別的, 應該是沒有遺漏的

兩者的差別列舉如下
a. 延伸的差異, 根據特定棋形做了depth+1的搜索, 也就是越搜反而越深(當然TogaII有手段防止過深)
b. 剪枝的差異, 包括打開futility, delta, 並且對底層也做了history pruning
c. 對棋步穩定的盤面(只產生一個PV路徑), 用渴望窗口搜索, 減少搜索量
d. 對危險情況的搜索的加強

兩者差異原理分析
簡單概括TogaII的改進,那就是利用國際象棋的知識調整了fruit的搜索樹,對危險的盤面進行了更深的搜索,否則就剪掉.

首先，TogaII最有效的改進，是在葉子附近，利用history value把證明曾經無效的葉子節點丟棄掉，這是一個非常有效的演算法，這裡面的道理值得我們深思？為什麼我們不能夠發現一個這樣的演算法呢？

如果光是觀察futility和delta剪枝法, 我想肯定會有人對我提出疑問? 不是說這些根據子力情況剪掉的分支會漏掉殺棋步嗎? 為什麼還打開剪枝, OK, 我來一個簡單的回答, 假如已經是用了知識判斷過這類分支並不危險, 那就可以剪掉了.

TogaII能改進fruit的原因基於對國際象棋的深刻理解(也許是大量的測試的證明), 它的剪枝和延伸, 是相輔相成的, 如果有人想嘗試這個方向, 千萬不要只開剪枝或者只加延伸

這個方向, 是在搜索樹中, 加入對棋類知識的判斷. 調整搜索樹更適合某種棋規.

4. fruit演算法應用於中象引擎的分析及中象引擎演算法改進分析

下面的內容，是基於上述闡述的一些具體應用的例子，可對引擎做出一定的修正

a. nullmove改進

nullmove限制條件中, 當depth<=4時, 進入nullmove. 這種情況會忽略了depth=1可能產生的殺棋步, 當審局的知識缺乏該方面的內容時, 會漏掉殺棋步

這個時候, 可以根據自己引擎的審局知識的特點, 做depth=1的search_verify

代碼如下

if (depth<=4)
do_nullmove;

if (nullscore>=beta)
do_search_verify(depth=1);

這種方法可以避免一些殺棋情況的漏算, 這個也可以算是搜索和知識結合的一個典型例子吧

b. history pruning改進

考慮下面的情況

[炮]吃車1, 車2吃[炮], 車2移動, 和車1移動, 這兩個棋步, 會引起同樣的history value的減少, 雖然限制了history pruning發生在不吃子的情況, 但是, 中象的交換頻率遠>國象, 這種情況對fruit中historyvalue<9830就剪枝(60%)顯然不適合, 因為中象發生上面的情況要高多了, 而historyvalue<9834(60%)只要該棋步有一次被檢索的情況就會發生, 這個時候, 修正historyvalue<16384*45%, 可以有效減少誤判

c. futility剪枝及delta剪枝的意義分析

嗯, 這個, 首先參考TogaII和fruit對比的文章

futility和delta, 如果不會漏掉殺棋步, 或者, 在不會被對方殺死的情況, 非常有助於擴大自己的子力優勢, 這是這兩個剪枝法的機制決定的(注意，這兩個剪枝法的依據是擴大子力優勢，所以適用的范圍是有限的，對雙方對殺的盤面是會削弱攻擊能力的)

我建議使用這兩個剪枝法, 當然是建立在調整過搜索樹以後(避免在容易引發殺棋的盤面使用，常見的手段是判斷kingsafety，是否處於被攻擊狀態中)

中象棋軟搜索引擎揭密(三) fenon
d. 棋步排序的改進

從PVS搜索的原理出發, 搜索效率取決於搜索次序

常見的棋步排序是歷史步->吃子步->killer->etc, 這是基於最大化子力優勢的搜索, 當對殺時, 這種搜索排序效率是非常低的.

考慮killer棋步,如果能夠發生一個killer步的分數是殺棋步,那麼調整棋步排序為歷史步->killer->吃子步->etc,這樣就很好地把殺棋和吃子都結合起來了

5. fruit演算法和象眼的差異, 如何提高象眼的棋力
通過本篇的介紹, 希望能夠把開源的象眼程序, 改進到一個全新的高度, 假如有人希望一起完成象眼的改進, 請站內和我聯系

下面是我認為可以有效提高象眼棋力的幾個地方
a. 基於PV節點的nullmove pruning
b. qs加強
c. History pruning及TogaII剪枝法
d. 棋步排序
e. hash的改進
f. IID演算法修正
g.search root move list

6. 建立以kingsafety為核心的審局, 以及審局模型的詳細介紹

a. 對盤面區分階段, 不同階段採取的策略是不同的, 開中殘差異是很大的

實際上, 開局通過開局庫和子力位置分+若干簡單知識, 是很容易走出正確的棋步盤面的, 這個研究不深, 我更多是依賴開局庫解決這個問題

殘局時候, 調整位置分表, 判斷子力組合, 這個時候因為子力很少, 基本上難以進取, 更多是應該考慮防守, 控制搜索的危險程度和給予適當的分數, 很容易做到這點

中局是比較復雜的, 下面詳細說說我所理解的地方

b. 對某個階段的知識, 不要給引擎太多的選擇, 避免引擎找出多個PV路徑, 引起棋步的來回選擇, 如中局, 應該集中思考殺棋或者擴大子力的優勢

c. 上面1.講述了搜索和知識之間的關系, 其中也提及了depth=1時候的殺棋知識評估的重要性, 但是, 只是局限於depth=1的殺棋知識, 我們的盤面判斷力還是很有限的, 這個時候怎麼辦? 我們能不能對depth>=2的情況進行評估

我提供一個實踐的方法, 那就是分層次打分.

比如: 三子歸邊的判斷, 我們通過以下三種層次評分
(a) 有沉底炮, +分 (depth=3)
(b) 有沉底炮和車可做炮架, +分 (depth=2)
(c) 有沉底炮和車並且馬進入了可以助攻的區域, +分 (depth=1)

剛才在上面的審局和搜索的關系中，我列舉了4種知識，並且強調了知識只應該選擇有效的，下面分別說說哪些知識是必須的，不在下面列表內的知識，我都不做判斷了
a. 准確的殺型
利用位置分值提示車馬兵攻擊王周圍，依賴搜索完成
b. 模糊的殺型
(a) 當頭炮 (空頭炮,鎮中)
(b) 底炮 (三子歸邊)
(c) 雙車殺
c. 子力組合，只做會引起問題的子力組合判斷，如兌子後雙馬不佳
d. 某些特別容易出問題的知識的補充

7. 國際象棋Rybka的勝利以及將來棋軟發展的一些展望

一些未來的研究方向, 所以個人的意見應該是一些胡言亂語,僅作笑料

上面所說的一切, 都是基於知識會有一個確定的分數, 但是, 這明顯是錯誤的, 誰能說三子歸邊是400分,而不是395分呢? 有沒有一種方法, 可以動態評估這個分數, 從而達到知識的最優化呢?

第二,傳說中的根據知識排序棋步的方法

在國外流行的認為Rybka超越其他軟體的原因是因為更聰明的搜索和知識, 從作者言論和Rybka反映的信息做一個猜測(nps超低, 搜索准確度超高), 一致認為Rybka在搜索和評估中, 都採取了全新的方法

其中一個流派3moves現在被認為是Rybka最有可能採取的方法(包含了我的理解補充)

什麼是3moves? 首先, 當前盤面移動一步, 對可以攻擊的子,計算3步內可以攻擊的點集,這個點集每個點都有權重.那麼,多個攻擊子做交集的時候, 密度最高權重最高的區域, 就是當前盤面最容易攻擊的位置, 這表明了這一個棋步的攻擊能力
當這個棋步能攻擊到王或者其他子時, 這自然就是一個好的棋步,這時候根據點集的情況進行算分,自然是非常准確的.

這種方法超越了子力表和知識分數的局限, 而且更好理解了棋規, 也難怪被認為是最有可能的

以上轉載，不知是否你想要的？

㈦ C語言 象棋的代碼(主要是走棋子的部分)

你好！！沒有c語言的，只有窗體的象棋，還是網路版的執行文件，你試試看吧

㈧ c++程序設計 中國象棋源代碼

我提供兩個功能完善，而且最重要的，我認為演算法設計比較好的中國象棋源代碼，因為是源碼網的，所以可以學習參考下：
http://www.codefans.net/soft/1466.shtml
http://www.codefans.net/soft/1289.shtml

㈨ 象棋的演算法

多下慢棋，最快也要50+20的慢棋。長期慢棋且復盤能提升棋感，很多棋你可以一眼看去就知道不是好棋，從而思考的時候能把這些奇怪的方向排除掉，專注於幾個看似不錯的選擇，再分別計算。下的慢棋越多，每一步的方向就越少，這樣計算深度就有了。

長期下去，盡管這樣深度足夠，但往往復盤的時候會發現思維盲點，有時候類似的情況下某種手段往往不成立，但特定的局面恰好成立。記住這樣的手段組合，並且在類似的局面下計算該手段是否成立。

舉個栗子：

黑的少倆卒子，如果出車紅的炮八平七，黑方底象被紅方瞄著，多少有點難受，如果黑方再補象，紅方從容的走到車六進三的話，戰線漫長，紅方維持先手。以上是一般的行棋思路。

但如果你的思維擴展開來，黑方雙炮位置相當不錯，這時候就要有動刀子的覺悟了。

………… 車1平2
炮八平七 馬4進5
車六進三 車2進9
仕五退六 炮4進7！
這一步代表的就是思維的廣度：洞察對方的弱點，在看似不可能的地方果斷出擊一搏。此時紅方如果選擇交換，無論何種交換方式，紅方都會落入下風殘局。私以為此時車六平五吃馬交換，紅方雖然缺雙士，但位置尚佳，仍可一戰。但如果退車吃炮，紅方簡單落入下風殘棋，顯然不滿。在他把網上的步時限制用完後，他果然選擇了最強硬的招法：

5. 炮七退二 炮7進7！

這也在我計算之內，所以我毫不猶豫砸了出去。立時紅方陣型千瘡百孔。我和他比賽上只下過一盤，那盤我是靠循序漸進然後靠殘局一點點贏下來的，他可能沒感受過我進攻時的力量，難免不大適應。這幾手他都把步時用完，也沒想出好辦法。

6. 相五退三 炮4平6

7. 相三進五 炮6平3

8. 相五退七 車2平3

9. 帥五進一 馬5退6

至此黑方以一大子的代價，換取紅方全部士相，且紅方的2路弱馬難以處理。最終在一系列頓挫下，二路馬被抓死，紅方被絕殺。

如果說打士這種棋靠的是思考廣度，那麼保證這個計劃能實行則靠的是強大的計算能力。如果黑無法保證打士成立，那麼恐怕出車就是一步很糟糕的棋了，例如黑出車後紅炮八平七，黑如果走個車2進7，紅方有馬七退六的招法，輕而易舉就能立於不敗，黑方只能苦苦求和了。又比如說黑方沒有計算清楚，打相時紅方補士黑方的應手，黑方也仍然會血本無歸。

慢棋的作用就是讓你習慣於長考，練得多了自然計算深度就有了。而行棋的時候則要洞察對方的弱點，然後大膽出手。有時對方的弱點並不好找，這也是需要多下多練才能找到的。

這真的沒有捷徑，我所能提供的，只是在你盤數上去之後，有這樣的思考方式能提升計算深度和廣度。至於速度和精度，這完全是靠盤數堆疊才能得到的。

㈩ 象棋游戲通過什麼演算法實現

你是問人工智慧吧。
一般是通過錄入常規棋局的走法，然後機器會根據棋局去匹配尋找最佳走法。呵呵，說白了，還是讓電腦找一段相似值，然後做選擇題。真正的人工學習思考的方法，目前還不成熟。