資源簡介
?Alpha-Beta剪枝(Alpha-Beta pruning)
對于一般的最大最小搜索,即使每一步只有很少的下法,搜索的位置也會增長非常快;在大多數的中局棋形中,每步平均有十個位置可以下棋,于是假設搜索九步(程序術語稱為搜索深度為九),就要搜索十億個位置(十的九次方),極大地限制了電腦的棋力。于是采用了一個方法,叫“alpha-beta剪枝”,它大為減少了檢測的數目,提高電腦搜索的速度。各種各樣的這種算法用于所有的強力Othello程序。(同樣用于其他棋類游戲,如國際象棋和跳棋)。為了搜索九步,一個好的程序只用搜索十萬到一百萬個位置,而不是沒用前的十億次。
?估值
這是一個程序中最重要的部分,如果這個模塊太弱,則就算算法再好也沒有用。我將要敘述三種不同的估值函數范例。我相信,大多數的Othello程序都可以歸結于此。
棋格表:這種算法的意思是,不同的棋格有不同的值,角的值大而角旁邊的格子值要小。忽視對稱的話,棋盤上有10個不同的位置,每個格子根據三種可能性賦值:黑棋、白棋和空。更有經驗的逼近是在游戲的不同階段對格子賦予不同的值。例如,角在開局階段和中局開始階段比終局階段更重要。采用這種算法的程序總是很弱(我這樣認為),但另一方面,它很容易實現,于是許多程序開始采用這種逼近。
基于行動力的估值:這種更久遠的接近有很強的全局觀,而不像棋格表那樣局部化。觀察表明,許多人類玩者努力獲得最大的行動力(可下棋的數目)和潛在行動力(臨近對手棋子的空格,見技巧篇)。如果代碼有效率的話,可以很快發現,它們提高棋力很多。
基于模版的估值 :正如上面提及的,許多中等力量的程序經常合并一些邊角判斷的知識,最大行動力和潛在行動力是全局特性,但是他們可以被切割成局部配置,再加在一起。棋子最少化也是如此。這導致了以下的概括:在估值函數中僅用局部配置(模版),這通常用單獨計算每一行、一列、斜邊和角落判斷,再加在一起來實現。
估值合并:一般程序的估值基于許多的參數,如行動力、潛在行動力、余裕手、邊角判斷、穩定子。但是怎么樣將他們合并起來得到一個估值呢?一般采用線性合并。設a1,a2,a3,a4為參數,則估值s:=n1*a1+n2*a2+n3*a3+n4*a4。其中n1,n2,n3,n4為常數,術語叫“權重”(weight),它決定了參數的重要性,它們取決于統計值。

代碼片段和文件信息
/**********************************************/
/*???????????????黑白棋源代碼?????????????????*/
/*??????????????TC2.0下運行通過???????????????*/
/*?????????采用深度搜索邊角權值算法???????????*/
/**********************************************/
#?include?
#?include?
#?include?
#?include?
#?include?
#?include?
#?define?BGCOLOR ??1????/*?背景顏色*/
#?define?COLOR_WHITECHESS?0????/*白棋棋子的顏色*/
#?define?COLOR_BLACKCHESS?15???/*黑棋棋子的顏色*/
#?define?COLOR_LINE? ??15???/*棋盤線的顏色*/
#?define?MINBOXSIZE???????30???/*棋盤每一格邊長*/
#?define?MAXSIZE??????????300??/*棋盤的大小?(1+8+1)*25?*/
#?define?SCCOL????????????50???/*棋盤左上角的坐標*/
#?define?SCROW????????????60
#?define?VK_LEFT???0x4b00 /*?按鍵碼*/
#?define?VK_RIGHT??0x4d00
#?define?VK_DOWN???0x5000
#?define?VK_UP?????0x4800
#?define?VK_SPACE??0x3920
#?define?VK_ESC????0x011b
#?define?MAX_TREE_SIZE?15
#?define?INF ???1000
int?TREE_LEVEL=7;
int?empty_num=0;
int?num_user=2;??????????????/*得分統計*/
int?num_computer=2;
int?gbwzc=5gbwzr=5;?????????/*光標的初始位置*/
int?present_p_v[10][10];?????/*當前格的位置及其權值*/
char?again=‘0‘;??????????????/*用來判斷游戲是否需要重新開始*/
int?l=0k=0;
/*初始棋盤布局*/
int?gril[10][10]=
????{{0000000000}
?????{0000000000}
?????{0000000000}
?????{0000000000}
?????{0000120000}
?????{0000210000}
?????{0000000000}
?????{0000000000}
?????{0000000000}
?????{0000000000}
????};
/*初始棋盤權值*/
int?gril_value[10][10]=
????{{0000000000}
?????{076-49159915-49760}
?????{0-49-494444-49-490}
?????{015484484150}
?????{0944444490}
?????{0944444490}
?????{015484484150}
?????{0-49-494444-49-490}
?????{076-49159915-49760}
?????{0000000000}
????};
/*************************************************************/
/****************用到的漢字***********************************/
char?zuo16S[]={
/*?以下是?‘左‘?的?16點陣宋體?字模,32?byte?*/
??0x020x000x030x000x020x000xFF0xFE
??0x020x000x020x000x040x000x040x00
??0x0F0xF80x080x800x100x800x100x80
??0x200x800x400x800xBF0xFE0x000x00
};
char?you16S[]={
/*?以下是?‘右‘?的?16點陣宋體?字模,32?byte?*/
??0x020x000x020x000x020x000xFF0xFE
??0x040x000x040x000x080x000x180x00
??0x2F0xF80x480x080x880x080x080x08
??0x080x080x0F0xF80x080x080x000x00
};
char?shang16S[]={
/*?以下是?‘上‘?的?16點陣宋體?字模,32?byte?*/
??0x000x000x010x000x010x000x010x00
??0x010x000x010x000x010xF80x010x00
??0x010x000x010x000x010x000x010x00
??0x010x000x010x040x7F0xFE0x000x00
};
char?xia16S[]={
/*?以下是?‘下‘?的?16點陣宋體?字模,32?byte?*/
??0x000x040x7F0xFE0x010x000x010x00
??0x010x000x010xC00x010x600x010x30
??0x010x200x010x000x010x000x010x00
??0x010x000x010x000x010x000x000x00
};
char?yi16S[]={
/*?以下是?‘移‘?的?16點陣宋體?字模,32?byte?*/
??0x0C0x400x7
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件??????90112??2005-06-16?09:58??中英文翻譯.doc
?????文件???????5363??1988-08-29?10:00??EGAVGA.BGI
?????文件??????30517??2005-06-15?14:25??final.c
?????文件??????45909??2005-06-15?14:25??FINAL.EXE
?????文件??????24685??2005-06-01?09:34??Test15.c
?????文件?????561664??2005-06-14?07:27??回溯算法及其基本應用.ppt
?????文件??????24064??2005-06-16?09:59??回溯算法及其基本應用的文獻綜述.doc
?????文件????3307520??2005-06-16?11:42??論文正文.doc
-----------?---------??----------?-----??----
??????????????4089834????????????????????8
- 上一篇:FFT并行MPI實現
- 下一篇:可以詳細查詢IP地址的小程序
評論
共有 條評論