博弈大賽賽前培訓(xùn)_六棋子程序的實現(xiàn)ppt課件

1、六子棋博弈程序唐志峰計算機博弈與人工智能協(xié)會icga.bitss/ 計算機博弈與人工智能icga.bitss/計算機博弈與人工智能 本次大賽通訊協(xié)議博弈程序整體設(shè)計思緒 博弈程序中心模塊 機器博弈交互平臺本次大賽的一些相關(guān)闡明講解要點.icga.bitss/計算機博弈與人工智能機器博弈交互平臺裁判系統(tǒng)棋盤黑方程序白方程序1112334556.icga.bitss/計算機博弈與人工智能本次大賽通訊協(xié)議接受裁判系統(tǒng)信息：scanf(%s,Msg);傳回裁判系統(tǒng)信息：printf(%s,Move);1.確定隊名：name?“ 傳回隊名： name BitStrongern“2.開局：new3.確定黑

2、白方： 黑方：black 白方：white4.發(fā)送、接納招法 /先橫向坐標(biāo)，后縱向坐標(biāo) 黑方第一步：move X0Y0 其他步數(shù)：move X0Y0X1Y1 .icga.bitss/計算機博弈與人工智能博弈程序整體設(shè)計思緒 實踐問題數(shù)學(xué)建模算法編程、調(diào)試得到結(jié)果.icga.bitss/計算機博弈與人工智能棋盤表示 六子棋棋盤由19條橫線和19條縱線組成。棋盤一共有19*19=361個交點。交點出現(xiàn)的能夠情況：無子、黑子、白子棋盤：char position1919;棋子： 黑棋BLACK：0 白棋WHITE：1 無子NOSTONE：0 xff.例如代碼宏定義：#define GRID_NUM

3、19 /棋盤行數(shù)#define GRID_COUNT 361 /可放棋子總數(shù)#define BLACK 0 /黑棋#define WHITE 1 /白棋#define NOSTONE 0 xff /無棋全局變量：BYTE position GRID_NUMGRID_NUM;/棋盤STONEMOVE m_cmBestMove; /記錄著法注: #include windows.h typedef unsigned char BYTE icga.bitss/計算機博弈與人工智能.例如代碼構(gòu)造定義：/棋子位置typedef struct _stonepositionBYTE x;BYTE y;STO

4、NEPOS;/走法typedef struct _stonemoveSTONEPOS StonePos2; /棋子位置int Score;/走法的分?jǐn)?shù)STONEMOVE;計算機博弈與人工智能icga.bitss/.例如代碼主函數(shù)，程序的入口void main()int ChessmanType; /記錄棋子顏色char Msg500; /保管接納到的音訊char name = “name 中國深度n; /隊伍信息char Move = move AABBn; /走法int x0,x1,y0,y1;/坐標(biāo) /初始化棋盤memset ( position, NOSTONE, GRID_COUNT)

5、; icga.bitss/計算機博弈與人工智能.例如代碼while (1)/循環(huán)接納裁判平臺發(fā)送的音訊，留意需求發(fā)送的字符串應(yīng)該/以n終了，裁判平臺才會以為是一次完好的輸入./發(fā)送完需求調(diào)用fflush(stdout)清空輸出緩沖區(qū)，使字符串/立刻輸出到裁判平臺memset(Msg,0,500);scanf(%s,Msg);if (strcmp(Msg,name?) = 0) printf(%s,name); fflush(stdout); continue;icga.bitss/計算機博弈與人工智能.例如代碼if (strcmp(Msg,“new) = 0) /新開局memset(posit

6、ion,NOSTONE,GRID_COUNT); /初始化棋盤scanf(%s,Msg);if (strcmp(Msg,“black) = 0) /確定我方棋子的顏色 Sleep(50); /延遲一段時間發(fā)送，經(jīng)測試，立刻發(fā)送可/能呵斥平臺無呼應(yīng) printf(move JJn); position99 = BLACK; fflush(stdout); ChessmanType = BLACK; continue;icga.bitss/計算機博弈與人工智能.例如代碼 else / if (strcmp(Msg,“white) = 0) ChessmanType = WHITE; continu

7、e; /確定棋型顏色終了if (strcmp(Msg,move) = 0) /接納對方的招法scanf(%s,Msg); icga.bitss/計算機博弈與人工智能.例如代碼 if (Msg2 = 0) /接納黑方的第一著/move XXny0 = (int)(Msg0) - (int)(A);x0 = (int)(S) - (int)(Msg1); positionx0y0 = !ChessmanType;icga.bitss/計算機博弈與人工智能.例如代碼else/接納對方的招法，普通招法都是一著下兩個子 /move XYXYny0 = (int)(Msg0) - (int)(A);x0

8、= (int)(S) - (int)(Msg1);y1 = (int)(Msg2) - (int)(A);x1 = (int)(S) - (int)(Msg3);positionx0y0 = !ChessmanType;positionx1y1 = !ChessmanType;icga.bitss/計算機博弈與人工智能.例如代碼if (SearchAGoodMove(position,ChessmanType) /獲得著法的坐標(biāo)x0 = m_cmBestMove.StonePos0.x;y0 = m_cmBestMove.StonePos0.y;x1 = m_cmBestMove.StoneP

9、os1.x;y1 = m_cmBestMove.StonePos1.y; /將著法記錄在棋盤中positionx0y0 = ChessmanType;positionx1y1 = ChessmanType;icga.bitss/計算機博弈與人工智能.例如代碼/將著法轉(zhuǎn)換成要發(fā)送的字符方式y(tǒng)0 = (char)(int)(A) + y0);x0 = (char)(int)(S) - x0);y1 = (char)(int)(A) + y1);x1 = (char)(int)(S) - x1);/Move = move AABBn/修正AABB 并發(fā)送Move5 = y0;Move6 = x0;M

10、ove7 = y1;Move8 = x1;printf(%s,Move);fflush(stdout);icga.bitss/計算機博弈與人工智能.icga.bitss/計算機博弈與人工智能機器博弈交互平臺裁判系統(tǒng)棋盤黑方程序白方程序1112334556.計算機博弈的設(shè)計思緒SearchAGoodMove(position,ChessmanType)如何根據(jù)已有的棋盤局面和我方子的顏色，來得到我方下一步將要走的招法。icga.bitss/計算機博弈與人工智能？.窮舉法窮舉出下一步一切能夠的招法，構(gòu)成不同的局面。比較一下這些局面，選取出其中最好的對我方最有利局面，那么構(gòu)成此局面對應(yīng)的招法就是我方

11、下一步“最正確的走法。一切能夠的招法：招法生成 比較：評價函數(shù) 選取、最好的：搜索函數(shù)極大極小值搜索最正確：此時對應(yīng)的招法真的是最好的招法嗎？icga.bitss/計算機博弈與人工智能.icga.bitss/計算機博弈與人工智能博弈程序中心模塊搜索函數(shù)招法生成評價函數(shù)AI引擎.招法生成招法生成：生成一個局面的一切能夠招法合法招法。例如：象棋中的，象走田，馬走日，兵可進(jìn)不可退。六子棋的合法招法：恣意空格點。思索：是不是一切招法都是我們需求思索的？可不可以舍棄一些招法？速度與準(zhǔn)確性的矛盾。icga.bitss/計算機博弈與人工智能.評價函數(shù)評價函數(shù)：用以評價一個局面的好壞。計算機如何知道一個局面的

12、好壞？局面的好壞 實數(shù)思緒：根據(jù)局面中的各方棋型，來詳細(xì)分析局面好壞，給出各局面的分值。難點：1.查找棋型，保證速度與準(zhǔn)確性。 2.如何根據(jù)棋型給分值，分值如何確定。icga.bitss/計算機博弈與人工智能.六子棋的棋型長連：在棋盤的縱向、橫向或斜向的恣意一條線上，形 成的7顆或7顆以上同色棋子不間隔地相連。六連：在棋盤的縱向、橫向或斜向的恣意一條線上，形 成的6顆同色棋子不間隔地相連。長連和六連是規(guī)定時間內(nèi)獲勝的必要條件。icga.bitss/計算機博弈與人工智能.六子棋的棋型活五：在同不斷線上的5顆同色棋子，符合“對方必需 用兩手棋才干擋住的條件?！皳踝∈侵覆蛔?另一方構(gòu)成六連或長連。i

13、cga.bitss/計算機博弈與人工智能.六子棋的棋型眠五：在同不斷線上的5顆同色棋子，符合“對方用 用一手棋才干擋住的條件。icga.bitss/計算機博弈與人工智能.六子棋的棋型活四：在同不斷線上的4顆同色棋子，符合“對方必需 用兩手棋才干擋住的條件。icga.bitss/計算機博弈與人工智能.六子棋的棋型眠四：在同不斷線上的4顆同色棋子，符合“對方用 用一手棋才干擋住的條件。icga.bitss/計算機博弈與人工智能.六子棋的棋型活三：在同不斷線上的3顆同色棋子，符合“再下一手 就能構(gòu)成活四的條件。icga.bitss/計算機博弈與人工智能.六子棋的棋型眠三：在同不斷線上的3顆同色棋子，

14、符合“再下兩手 棋也只能構(gòu)成眠四的條件。icga.bitss/計算機博弈與人工智能.六子棋的棋型活二：在同不斷線上的2顆同色棋子，符合“再下兩手 棋就能構(gòu)成活四的條件。icga.bitss/計算機博弈與人工智能.六子棋的棋型眠二：在同不斷線上的2顆同色棋子，符合“再下兩手 棋只能構(gòu)成眠四的條件。icga.bitss/計算機博弈與人工智能.搜索函數(shù)下一個最好的評價分值最高局面的對應(yīng)的招法就是最正確招法嗎？棋類高手都能看很多步！當(dāng)我方生成各種局面后，對方針對我方構(gòu)成的每一種局面又同樣會生成許多局面，我方再針對對方構(gòu)成的每一種局面同樣又會生成許多對應(yīng)局面，這樣循環(huán)往復(fù)，就構(gòu)成了一個顆博弈樹。icga

15、.bitss/計算機博弈與人工智能.博弈樹icga.bitss/計算機博弈與人工智能博弈樹一棵多叉樹。六子棋博弈樹的復(fù)雜度很高。每個局面對應(yīng)招法 開場： 360*359=129240 終了設(shè)50步之后：310*309=95790設(shè)平均取105 個節(jié)點。1層： 1052層： 105 * 105 = 10103層： 1010 * 1010 = 1020 節(jié)點數(shù)隨深度的添加以爆炸式方式增長.博弈樹提高時間效率普通一步能控制在半分鐘內(nèi)為宜。方法：減小博弈樹的規(guī)模： 1.降低搜索深度，但棋力提高有限。 2.每個局面對應(yīng)只生成少許有價值的節(jié)點， 能夠有漏選。運用高效的搜索算法，例如：-剪枝。提高各模塊的效

16、率，尤其是評價函數(shù)的效率。icga.bitss/計算機博弈與人工智能.極大極小值搜索建立了博弈樹，我們怎樣找到我們需求的招法？搜索與回溯方式：由于：局面分值越高，對我方越有利，對于對方越不利。局面分值越低，對我方越不利，也就是對于對方越有利。所以：輪到我方走時，我方會選擇使下一步局面分值最高的走法。此節(jié)點局面分值 = MAX一切子節(jié)點分值輪到對方走時，對方會選擇使下一步局面分值最低的走法。此節(jié)點局面分值 = MIN所以子節(jié)點分值icga.bitss/計算機博弈與人工智能.計算機博弈與人工智能極大極小值搜索局面取極大值局面取極小值RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3Depth = 3Depth = 2Depth =