最新版本地址：/Files/saha/CCS0.5.rar
參考資料：http://www.sluijten.com/winglet/ http://www.frayn.net/beowulf/theory.html
Monday, April 16, 2012 總體框架設(shè)計(jì)
分離UI和AI算法，以利于以后不同平臺(tái)的移植。其中AI算法部分做到平臺(tái)無關(guān)性。
基本框架如下：
Thursday, April 19, 2012簡(jiǎn)單的UI及棋子移動(dòng)實(shí)現(xiàn)
設(shè)置棋盤為16*16的數(shù)組。冗余部分便于棋子出界判斷。
紅棋值從8-14，黑棋值從16-22.其余部分全部為0
點(diǎn)擊流程.jpg)
基本UI實(shí)現(xiàn)，基本象棋類實(shí)現(xiàn)。
Tuesday, April 24, 2012實(shí)現(xiàn)棋子規(guī)則
1. 實(shí)現(xiàn)各個(gè)棋子的走法規(guī)則，將照面規(guī)則暫時(shí)未實(shí)現(xiàn)。
2. 實(shí)現(xiàn)了將軍判斷函數(shù)
3. 支持了翻轉(zhuǎn)功能
4. 實(shí)現(xiàn)一些細(xì)節(jié)。結(jié)束后不允許再走棋，重新初始化棋盤等。
Thursday, April 26, 2012
重新實(shí)現(xiàn)棋子走法規(guī)則判斷邏輯如下：
則.jpg)
Friday, May 11, 2012
1.基本的人工智能算法 Alpha-Beta搜索.
其中
Alpha為搜索到的最好值，beta為對(duì)方的最壞值。一般起始時(shí)設(shè)置Alpha為負(fù)無窮，beta為正無窮。
之所以在遞歸內(nèi)部要傳入-beta和-alpha是為了反應(yīng)對(duì)方走棋，及簡(jiǎn)化代碼。即表示我方的最好值與對(duì)方的最壞值的對(duì)應(yīng)關(guān)系。
int AlphaBeta(int depth, int alpha, int beta)
{
if (depth == 0)
{
return Evaluate(); //如果是第一層返回局面估計(jì)
}
GenerateLegalMoves(); //產(chǎn)生當(dāng)前的所有下一步走法
while (MovesLeft()) //排序并遍歷每一步走法
{
MakeNextMove(); //走一步
//遞歸搜索
val = -AlphaBeta(depth - 1, -beta, -alpha);
UnmakeMove(); //回退該步
//如果比最壞情況還壞，則返回最壞情況
if (val >= beta)
{
return beta;
}
//如果比最好情況差，則保持它為目前探索到的最好情況
if (val > alpha)
{
alpha = val;
}
}
return alpha; //返回目前找到的最好情況，其對(duì)應(yīng)的走法即是搜索到的最好著法
}
從根局面開始，默認(rèn)的Alpha和Beta值分別為己方被殺和對(duì)方被殺的分值，遞歸搜索己方所有走法。
當(dāng)一個(gè)走法返回的估計(jì)值A(chǔ)1>=Beta時(shí)，認(rèn)為該節(jié)點(diǎn)是殺棋,則己方必選擇該走法，因此其余節(jié)點(diǎn)不用再搜索，只要保存該走法并返回，稱為beta截?cái)唷?br />當(dāng)一個(gè)走法A1<=Alpha時(shí)，認(rèn)為該節(jié)點(diǎn)比己方所能接受的最差結(jié)果更差，因此不保留該走法(這里無法做截?cái)?。
當(dāng)一個(gè)走法A1>Alpha && A1<Beta時(shí)，認(rèn)為該節(jié)點(diǎn)是主變例節(jié)點(diǎn)(PV Principal Variation)，需要保留該走法，并將Alpha設(shè)為A1，并繼續(xù)探索剩余節(jié)點(diǎn)。
對(duì)于對(duì)方走棋時(shí)，只要將上下限取反調(diào)用同一alpha-beta函數(shù)即可。
2.增加自動(dòng)測(cè)試功能，能電腦vs電腦測(cè)試
3.增加不同的電腦級(jí)別，以搜索層數(shù)劃分
Wednesday, May 12, 2012
1.增加聲音開關(guān)功能
2.悔棋功能，最多支持悔512步
V0.2版本完成
Wednesday, May 30, 2012
1.空著向前裁剪
空著裁剪的含義就是如果當(dāng)前的局勢(shì)優(yōu)勢(shì)巨大，即使不走這一步棋讓對(duì)方走還是能產(chǎn)生beta截?cái)啵喈?dāng)于少搜索了一層，能大大縮短搜索的時(shí)間。
存在的一個(gè)問題是在殘局階段，當(dāng)存在無棋可走的情況下，使用空著恰恰避開了這種問題，從而導(dǎo)致估計(jì)不準(zhǔn)確，因此在殘局時(shí)需要進(jìn)行判斷來決定是否使用空著裁剪，一種流行的簡(jiǎn)單做法是到了殘局就不進(jìn)行空著裁剪。
2.靜態(tài)搜索
相對(duì)穩(wěn)定的局面稱為“安靜”(Quiet)或“寂靜”(Quiescent)的局面，它們需要通過“靜態(tài)搜索”(Quiescence Search)來達(dá)到。
目前采用簡(jiǎn)單的策略即只考慮所有的吃子走法來進(jìn)行搜索。
3.局面檢驗(yàn)Zobrist鍵值
Zobrist用一個(gè)整型數(shù)值來代表一個(gè)棋的局面，目前采用的做法是對(duì)于每一個(gè)棋盤位置的14種情況(7種紅棋，7種黑棋)產(chǎn)生14*256個(gè)隨機(jī)數(shù)，每一個(gè)棋局是所有存在棋子的棋盤位置的隨機(jī)數(shù)異或而得到的一個(gè)整型值(稱為Zobrist鍵值)，據(jù)前人經(jīng)驗(yàn)這種表示方法出現(xiàn)沖突的概率非常小。這種表示方法的另一個(gè)好處是去除一個(gè)棋子和添加一個(gè)棋子都是異或操作(由于異或的異或得到原來的值)，利用Zobrist鍵值可以做重復(fù)局面判斷，長(zhǎng)將判斷。
V0.3版本完成
Thursday, June 14, 2012
1.修改Zobrist鍵值從原來的32位無符號(hào)變?yōu)閕nt64（據(jù)前人經(jīng)驗(yàn)32位存在沖突有很多爭(zhēng)論，而64位雖然仍存在沖突的局面，但是實(shí)戰(zhàn)中這種情況非常罕見）。
2.修改重復(fù)局面檢查函數(shù)，從以前的把所有歷史局面全部檢查到現(xiàn)在的只檢查最近6步，以減少不必要的檢查。
3.增加主變例搜索優(yōu)化。即對(duì)當(dāng)前搜索存在PV走法時(shí)，對(duì)以后的每一個(gè)節(jié)點(diǎn)搜索的搜索上下限先設(shè)為[-Alpha-1, -Alpha],如果當(dāng)前節(jié)點(diǎn)的值比pv值要大則重新對(duì)該節(jié)點(diǎn)進(jìn)行正常搜索，否則丟棄該節(jié)點(diǎn)進(jìn)行下一個(gè)節(jié)點(diǎn)的搜索。據(jù)統(tǒng)計(jì)可以提供10%的搜索效率，在程序中直接使用沒有明顯的變化。。。
4.增加置換表。
基本思想：每一個(gè)搜索過的局面都記錄他的平均值，以避免以后搜索到同一局面時(shí)的重復(fù)計(jì)算工作。
使用zobrist-hash值記錄每個(gè)搜索過的局面。一個(gè)置換表的元素包括以下結(jié)構(gòu)：
CCSINT64 ulZobristKey; //hash-key
CCSUINT32 depth : 8; //搜索深度
CCSUINT32 flags : 2; //標(biāo)志，分為PV,BETA,ALPHA3種
CCSUINT32 mvBest : 22; //該局面下的最佳走法
CCSINT32 nValue; //該局面下的估計(jì)值
其中flags3種標(biāo)志代表不同含義。
pv表示主變例搜索的結(jié)果，即這時(shí)的nValue是個(gè)精確值，可以直接使用
BETA表示該局面的估計(jì)值至少為nValue。
ALPHA表示該局面的估計(jì)值最多為nValue。
在alpha-beta搜索中的使用如下：
if (HASH_PV == pItem->flags)
{
return nValue;
}
if (HASH_BETA == pItem->flags && nValue >= nBeta)
{
return nBeta;
}
else if (HASH_ALPHA == pItem->flags && nValue <= nAlpha)
{
return nAlpha;
}
return VALUEUNKNOWN;
是否正確還有待測(cè)試。
使用置換表時(shí)除了判斷zobrist-hash值是否相同外,還要判斷當(dāng)前走棋方是否與記錄中的走棋方一致,不一致不能替換.
Friday, July 27, 2012
修改置換表的使用方式
去除輸棋后的不文明用語
在騰訊游戲中進(jìn)行測(cè)試，使用中等水平在1000分以下玩家中勝率95%+
posted on 2012-04-16 17:44
saha 閱讀(828)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
棋類AI