吴昊品游戏核心算法 Round 5 ——（转载）关于无禁手下先手必胜的证明
關于五子棋先手必勝的證明，用人工的方式過于復雜，其難度相當于證明四色定理的正確性或者是若兒當定理的正確性。但是，如果采用計算機來解決，則復雜程度 會降低許多。由于很難地毯式地枚舉到所有可能的情形，這一款五子棋終結者的算法（最新的應該是1.22版本，網絡上流傳的2.0和4.0版都是子虛烏有） 幾乎可以達到先手必勝了。作者甚至開出了懸賞92萬美元的獎勵，就是說如果你用他的程序戰勝了執黑的他，他就會給你這么多錢作為補償，但是，到目前為止該 算法還是幾乎可以實現先手必勝的！
?
?? 五子棋終結者算法 ???????
??
?? 任何一種棋類游戲其關鍵是對當前棋局是否有正確的評分,評分越準確則電腦的AI越高。五子棋游戲也是
?
如此，但在打分之前，我們先掃描整個棋盤，把每個空位從八個方向上的棋型填入數組gStyle(2, 15, 15,?
?
8, 2)，其中第一個下標為1時表示黑棋，為2時表示白棋，第二和第三個下標表示(x,y)，第四個下標表示8個
?
方向，最后一個下標為1時表示棋子數，為2時表示空格數，如：
?
gStyle(1,2,2,1,1)=3表示與坐標(2,2)在第1個方向上相鄰的黑棋棋子數為3?
gstyle(1,2,2,1,2)=4表示與坐標(2,2)在第1個方向上的最近的空格數為4?
在定義方向時，也應該注意一定的技巧，表示兩個相反的方向的數應該差4，在程序中我是這樣定義的：?
Const DIR_UP = 1?
Const DIR_UPRIGHT = 2?
Const DIR_RIGHT = 3?
Const DIR_RIGHTDOWN = 4?
Const DIR_DOWN = 5?
Const DIR_DOWNLEFT = 6?
Const DIR_LEFT = 7?
Const DIR_LEFTUP = 8?
這樣我們前四個方向可以通過加四得到另一個方向的值。請看下面的圖：?
---------?
---------?
---oo----?
-ox*xx---?
---------?
---------?
圖中的*點從標為(4,4),（打*的位置是空位）,則:?
gStyle(2,4,4,1,1)=1在(4,4)點相鄰的上方白棋數為1?
gStyle(2,4,4,1,2)=2在(4,4)點的上方距上方白棋最近的空格數為2?
gStyle(1,4,4,3,1)=2在(4,4)點相鄰的右方黑棋數為2?
gStyle(1,4,4,3,2)=1在(4,4)點的右方距右方黑棋最近的空格數為3?
...
?
一旦把所有空點的棋型值填完，我們很容易地得出黑棋水平方向上點(4,4)的價值，由一個沖1（我把有
?
界的棋稱為沖）和活2（兩邊無界的?
棋稱為活）組成的。對于而白棋在垂直方向上點(4,4)的價值是一個活1，而在/方向也是活1所以，只要我們
?
把該點的對于黑棋和白棋的價值算出?
來，然后我們就取棋盤上各個空點的這兩個值的和的最大一點作為下棋的點。然而，對各種棋型應該取什么
?
值呢？我們可以先作如下假設：?
Fn 表示先手n個棋子的活棋型，如：F4表示先手活四?
Fn'表示先手n個棋子的沖棋型，如：F4'表示先手沖四?
Ln 表示后手n個棋子的活棋型，如：L3表示后手活三?
Ln'表示后手n個棋子的沖棋型，如：L3'表示后手沖三?
.?
. .?
根據在一行中的棋型分析，得到如下關系：?
L1'<=F1'<L2'<=F2'<=L1<F1<L2<F2<L3'<=F3'<L4'<F4'=F4從這個關系包含了進攻和防守的關系（當然，這個
?
關系是由我定的，你可以自己定義這些關系）。對這些關系再進一步細化，如在一個可下棋的點，其四個方
?
向上都有活三，也比不上一個沖四，所以我們可以又得到4*F3<L4'這個關系，同樣，我們還可以得到其它的
?
關系，如：4*F2<L3、4*L3<F3...，這些的關系由于你的定法和我的定法制可能不一樣，這樣計算機的AI也就
?
不一樣，最后我們把分值最小的L1'值定為1，則我們就得到了下面各種棋型的分值，由C語言表示為：?
F[2][5]={{0,2,5,50,16000},{0,10,30,750,16000}};?
L[2][5]={{0,1,5,50,3750},{0,10,30,150,4000}};?
F數組表示先手，第一個下標為0時表示沖型，第二個下標表示棋子數，則F2'對應F[0][2]L數組表示后手
?
，第一個下標為0時表示沖型，第二個下標表示棋子數，則L2對應F[1][2]Ok，棋型的分值關系確定好了以后
?
，我們把每一個可下點的四個方向的棋型值相加（包括先手和后手的分值），最后選擇一個最大值，并把這
?
一點作為計算機要下的點就OK了:)。
?
后話：?
1、得到最大值也許不止一個點，但在我的程序中只選擇第一個最大點，當然你可以用于個隨機數來決定?
選擇那一個最大值點，也可以對這些最大值點再作進一步的分析。?
2、在這個算法中我只考慮了周圍有棋子的點，而其它點我沒有考慮。?
3、可以再更進一步，用這個算法來預測以后的幾步棋，再選擇預測值最好的一步，這樣電腦的AI就更高了?
4、這個算法沒有考慮黑棋的禁手（雙3、雙四和多于五子的連棋）。因為在平時我下的五子棋是沒有這些?
禁手的
?
五子棋終結者的算法求解過程2008-11-14 15:23
終 結五子棋不是一個很難的問題，和普通的遍歷求解問題沒多大區別。只是計算量稍微大點，設計的時候需要考慮系統性層次性逐步發展的觀點 ，不可能三兩天之內完成很精妙的算法。因此終結五子棋算不上卓有成效的工作，只是解了一個狀態空間稍微大點的遍歷題目而已，所需要的全部知識只是C語言、 二叉樹和對五子棋規則的了解，并不需要多么好的棋力才可以寫程序，只是將想法賦予機器。
五子棋終結者終結五子棋的計算引擎分為三層，上層調用下層，從上至下依次為
>>目標過程層。
受限于計算機能力，五子棋終結者是不可能一次搜索就被全面終結的，而是不斷地從主要干支到次要枝葉到全面終結的一個目標漸進過程。此層引擎只是一個for循環，逐步放大終結目標的寬度，從5到10到30到50到225，當到225時，五子棋就被完全地終結了。
>>策略引擎層。
最佳優先與或求解樹引擎。不要看到名字這么復雜，其實就是一個不斷擴展發展M叉樹。讓最優的棋子獲得CPU，棋子的優先度根據下層的結果動態計算調整，也稱作反饋，直到分支在當前的目標寬度下被終結。
>>VC攻擊引擎層。
VCF和VCT，簡稱VC，也就是連續攻擊取勝引擎。求解速度和求解嚴格精確至關重要。
如何在0.01S內進行深度為幾十步的攻擊？計算攻防時黑與白之間的無關性以及各自的相關性。
無關性的考慮可以化解對方的隨意反攻，相關性的考慮可以使自己的進攻關聯，保持節奏和組織性，不至盲目，二者結合使自己的進攻如行云流水，長驅直入，勢如破竹。
1.00 版本的vc設計是近似的，因為在VC中考慮了寬度估計，而不是全面地推理。因此終結也是近似的，很容易打敗。1.20版本vc設計是嚴格的，但是程序中 “相鄰三子形成的連活三只需防守與兩邊的兩個空白位置”是一條有漏洞的攻防邏輯，因此1.20版本也在出來一個月后被打敗。1.22版本改正了1.20版 本的上述漏洞，只改動了一個字符，也就是緊鄰活三的防守掩碼。以前我所認為的很嚴格的推理邏輯在后來仍然被發現了意外漏洞的存在，因此對于1.22的VC 引擎，我也不知道是否還有邏輯漏洞存在，暫時沒人打敗1.22并不能說明漏洞不存在。
以上算法實現后，執行終結命令，經過半個月的連續計算后，會生成一個完整的地毯必勝樹，包含大約百萬個棋子節點，樹的所有葉子都是可以VC求解的，如果VC求解引擎不存在漏洞，那么五子棋是必勝的。
終結者程序很小，算法部分的代碼只有一萬多行，編譯結果只有一百多K，而且運行只需要幾M的內存，必勝樹只有百來萬個節點。
下面是讀取必勝樹的代碼，你可以用下面的函數操作終結者資源里面的必勝樹：
?2?//int?key=1;//!!!!!!!
?3?//傳入當前key和指向子孫的指針root，將root指向的樹生長完整
?4?//上層調用此函數之時key已經指向[的下一個字符(，我的處理：
?5?//(－－添加root的孩子
?6?//)－－添加孩子完畢，可有可無
?7?//[－－為孩子添加子孫
?8?//]－－root樹生長完成
?9?//參數為長子的指針的指針和父親的指針
10?void?make(NODEOFTREE?**?root,NODEOFTREE?*parent)
11?{
12?/*?*root指向節點，我們要給*root賦值?*/
13?int?rootOK=0;
14?NODEOFTREE?*rightC=NULL;?/*?rightC總是指向剛剛加入的兄弟?*/
15?NODEOFTREE?*rightT=NULL;?/*?rightT指向新開辟兄弟?*/
16?
17?if(book[key]!='(')
18?{
19????F5_PRINT(1,"?make?book[key]!='('?");
20????return;
21?}
22?
23?do
24?{???
25?????switch(book[key])
26?????{
27?case?'['?:?//fprintf(outcourse,"?開始生孩子...?\n");
28????????????????key++;
29????????????????make(&(rightC->down),rightC);
30????????????????break;
31?case?']'?:?//fprintf(outcourse,"?孩子完成...?\n");
32????????????????key++;
33????????????????return?;
34?
35??????????case?'('?:?/*?加一個兄弟?*/
36?????????????????
37?????????????????rightT=(NODEOFTREE?*)malloc(sizeof(NODEDATA));
38?????????????????if(rightT==NULL)
39?????????????????F5_PRINT(1,"?make?rightT==NULL");
40?????node_mum++;
41?????????????????memset(rightT,0,sizeof(NODEDATA));
42?????????????????rightT->data[0]=cover(book[key+1],1);
43?????????????????rightT->data[1]=cover(book[key+2],2);
44?????????????????if(key==1)
45?????????????????rightT->data[2]=1;/*第一個子是黑子*/
46?????????????????else
47?????????????????{/*和父親的顏色相反*/
48?????????????????if(parent->data[2]==1)rightT->data[2]=2;
49?????????????????if(parent->data[2]==2)rightT->data[2]=1;
50?????????????????}
51?????????????????rightT->right=NULL;
52?????????????????rightT->down=NULL;
53?????????????????
54?????????????????if(rightC!=NULL)
55?????????????????{
56?????????????????rightC->right=rightT;
57?????????????????}????????????????
58?????????????????rightC=rightT;
59?????????????????
60?????????????????
61?????????????????if(rootOK!=1)/*兄弟的一個，即老大*/
62?????????????????{*root=rightT;?rootOK=1;
63?????????????????}
64?????????????????
65?????????????????key=key+3;
66?????????????????//?fprintf(outcourse,"加一個兄弟(%c-%c-%c)\n",rightC->data[0],rightC->data[1],rightC->data[2]);
67?????????????????
68?????????????????break;
69??????case?')'?:
70?????????????????key++;
71?????????????????break;
72?????????????????
73??????case?'\0':?//fprintf(outcourse,"不可能有此一字，在最后一個]的時候返回！\n");
74?????????????????break;??????
75?
76??????default?:?key++;
77?????????????????//fprintf(outcourse,"字符串中有錯誤的字符！\n");
78?????????????????break;
79?}
80?}?while(book[key]!='\0');
81?return;
82?}
?
轉載于:https://www.cnblogs.com/tuanzang/archive/2013/02/27/2935772.html
總結
以上是生活随笔為你收集整理的吴昊品游戏核心算法 Round 5 ——（转载）关于无禁手下先手必胜的证明的全部內容，希望文章能夠幫你解決所遇到的問題。
