博弈大賽賽前培訓(xùn)六棋子程序的實(shí)現(xiàn)

1、六子棋博弈程序計(jì)算機(jī)博弈與人工智能協(xié)會(huì) 計(jì)算機(jī)博弈與人工智能1 本次大賽通信協(xié)議博弈程序整體設(shè)計(jì)思路 博弈程序核心模塊 機(jī)器博弈交互平臺(tái)本次大賽的一些相關(guān)說(shuō)明講解要點(diǎn)2機(jī)器博弈交互平臺(tái)裁判系統(tǒng)棋盤黑方程序白方程序11123345563本次大賽通信協(xié)議接受裁判系統(tǒng)信息：scanf(%s,Msg);傳回裁判系統(tǒng)信息：printf(%s,Move);1.確定隊(duì)名：name?“ 傳回隊(duì)名： name BitStrongern“2.開(kāi)局：new3.確定黑白方： 黑方：black 白方：white4.發(fā)送、接收招法 /先橫向坐標(biāo)，后縱向坐標(biāo) 黑方第一步：move X0Y0 其他步數(shù)：move X0Y0X1

2、Y1 4博弈程序整體設(shè)計(jì)思路 實(shí)際問(wèn)題數(shù)學(xué)建模算法編程、調(diào)試得到結(jié)果5棋盤表示 六子棋棋盤由19條橫線和19條縱線組成。棋盤一共有19*19=361個(gè)交點(diǎn)。交點(diǎn)出現(xiàn)的可能情況：無(wú)子、黑子、白子棋盤：char position1919;棋子： 黑棋（BLACK）：0 白棋（WHITE）：1 無(wú)子（NOSTONE）：0 xff6示例代碼宏定義：#define GRID_NUM 19 /棋盤行數(shù)#define GRID_COUNT 361 /可放棋子總數(shù)#define BLACK 0 /黑棋#define WHITE 1 /白棋#define NOSTONE 0 xff /無(wú)棋全局變量：BYTE p

3、osition GRID_NUMGRID_NUM;/棋盤STONEMOVE m_cmBestMove; /記錄著法注: #include windows.h typedef unsigned char BYTE 7示例代碼結(jié)構(gòu)定義：/棋子位置typedef struct _stonepositionBYTE x;BYTE y;STONEPOS;/走法typedef struct _stonemoveSTONEPOS StonePos2; /棋子位置int Score;/走法的分?jǐn)?shù)STONEMOVE;8示例代碼主函數(shù)，程序的入口void main()int ChessmanType; /記錄棋子

4、顏色char Msg500; /保存接收到的消息char name = “name 中國(guó)深度n; /隊(duì)伍信息char Move = move AABBn; /走法int x0,x1,y0,y1;/坐標(biāo) /初始化棋盤memset ( position, NOSTONE, GRID_COUNT); 9示例代碼while (1)/循環(huán)接收裁判平臺(tái)發(fā)送的消息，注意需要發(fā)送的字符串應(yīng)該/以n結(jié)束，裁判平臺(tái)才會(huì)認(rèn)為是一次完整的輸入./發(fā)送完需要調(diào)用fflush(stdout)清空輸出緩沖區(qū)，使字符串/立刻輸出到裁判平臺(tái)memset(Msg,0,500);scanf(%s,Msg);if (strcmp(M

5、sg,name?) = 0) printf(%s,name); fflush(stdout); continue;10示例代碼if (strcmp(Msg,“new”) = 0) /新開(kāi)局memset(position,NOSTONE,GRID_COUNT); /初始化棋盤scanf(%s,Msg);if (strcmp(Msg,“black”) = 0) /確定我方棋子的顏色 Sleep(50); /延遲一段時(shí)間發(fā)送，經(jīng)測(cè)試，立即發(fā)送可/能造成平臺(tái)無(wú)響應(yīng) printf(move JJn); position99 = BLACK; fflush(stdout); ChessmanType =

6、BLACK; continue;11示例代碼 else / if (strcmp(Msg,“white”) = 0) ChessmanType = WHITE; continue; /確定棋型顏色結(jié)束if (strcmp(Msg,move) = 0) /接收對(duì)方的招法scanf(%s,Msg); 12示例代碼 if (Msg2 = 0) /接收黑方的第一著/move XXny0 = (int)(Msg0) - (int)(A);x0 = (int)(S) - (int)(Msg1); positionx0y0 = !ChessmanType;13示例代碼else/接收對(duì)方的招法，一般招法都是一

7、著下兩個(gè)子 /move XYXYny0 = (int)(Msg0) - (int)(A);x0 = (int)(S) - (int)(Msg1);y1 = (int)(Msg2) - (int)(A);x1 = (int)(S) - (int)(Msg3);positionx0y0 = !ChessmanType;positionx1y1 = !ChessmanType;14示例代碼if (SearchAGoodMove(position,ChessmanType) /獲得著法的坐標(biāo)x0 = m_cmBestMove.StonePos0.x;y0 = m_cmBestMove.StonePos

8、0.y;x1 = m_cmBestMove.StonePos1.x;y1 = m_cmBestMove.StonePos1.y; /將著法記錄在棋盤中positionx0y0 = ChessmanType;positionx1y1 = ChessmanType;15示例代碼/將著法轉(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;Move

9、6 = x0;Move7 = y1;Move8 = x1;printf(%s,Move);fflush(stdout);16機(jī)器博弈交互平臺(tái)裁判系統(tǒng)棋盤黑方程序白方程序111233455617計(jì)算機(jī)博弈的設(shè)計(jì)思路SearchAGoodMove(position,ChessmanType)如何根據(jù)已有的棋盤局面和我方子的顏色，來(lái)得到我方下一步將要走的招法。？18窮舉法窮舉出下一步所有可能的招法，形成不同的局面。比較一下這些局面，選取出其中最好的（對(duì)我方最有利）局面，則形成此局面對(duì)應(yīng)的招法就是我方下一步“最佳”的走法。所有可能的招法：招法生成 比較：評(píng)估函數(shù) 選取、最好的：搜索函數(shù)（極大極小值搜索

10、）最佳：此時(shí)對(duì)應(yīng)的招法真的是最好的招法嗎？19博弈程序核心模塊搜索函數(shù)招法生成評(píng)估函數(shù)AI引擎20招法生成招法生成：生成一個(gè)局面的所有可能招法（合法招法）。例如：象棋中的，象走田，馬走日，兵可進(jìn)不可退。六子棋的合法招法：任意空格點(diǎn)。思考：是不是所有招法都是我們需要考慮的？可不可以舍棄一些招法？速度與準(zhǔn)確性的矛盾。21評(píng)估函數(shù)評(píng)估函數(shù)：用以評(píng)價(jià)一個(gè)局面的好壞。計(jì)算機(jī)如何知道一個(gè)局面的好壞？局面的好壞 實(shí)數(shù)思路：根據(jù)局面中的各方棋型，來(lái)具體分析局面好壞，給出各局面的分值。難點(diǎn)：1.查找棋型，保證速度與準(zhǔn)確性。 2.如何根據(jù)棋型給分值，分值如何確定。22六子棋的棋型長(zhǎng)連：在棋盤的縱向、橫向或斜向的任

11、意一條線上，形 成的7顆或7顆以上同色棋子不間隔地相連。六連：在棋盤的縱向、橫向或斜向的任意一條線上，形 成的6顆同色棋子不間隔地相連。長(zhǎng)連和六連是規(guī)定時(shí)間內(nèi)獲勝的必要條件。23六子棋的棋型活五：在同一直線上的5顆同色棋子，符合“對(duì)方必須 用兩手棋才能擋住”的條件?！皳踝　笔侵覆蛔?另一方形成六連或長(zhǎng)連。24六子棋的棋型眠五：在同一直線上的5顆同色棋子，符合“對(duì)方用 用一手棋才能擋住”的條件。25六子棋的棋型活四：在同一直線上的4顆同色棋子，符合“對(duì)方必須 用兩手棋才能擋住”的條件。26六子棋的棋型眠四：在同一直線上的4顆同色棋子，符合“對(duì)方用 用一手棋才能擋住”的條件。27六子棋的棋型活三：

12、在同一直線上的3顆同色棋子，符合“再下一手 就能形成活四”的條件。28六子棋的棋型眠三：在同一直線上的3顆同色棋子，符合“再下兩手 棋也只能形成眠四”的條件。29六子棋的棋型活二：在同一直線上的2顆同色棋子，符合“再下兩手 棋就能形成活四”的條件。30六子棋的棋型眠二：在同一直線上的2顆同色棋子，符合“再下兩手 棋只能形成眠四”的條件。31搜索函數(shù)下一個(gè)最好的（評(píng)估分值最高）局面的對(duì)應(yīng)的招法就是最佳招法嗎？棋類高手都能看很多步！當(dāng)我方生成各種局面后，對(duì)方針對(duì)我方形成的每一種局面又同樣會(huì)生成許多局面，我方再針對(duì)對(duì)方形成的每一種局面同樣又會(huì)生成許多對(duì)應(yīng)局面，這樣循環(huán)往復(fù)，就形成了一個(gè)顆博弈樹。32

13、博弈樹博弈樹一棵多叉樹。六子棋博弈樹的復(fù)雜度很高。每個(gè)局面對(duì)應(yīng)招法 開(kāi)始： 360*359=129240 結(jié)束（設(shè)50步之后）：310*309=95790設(shè)平均取105 個(gè)節(jié)點(diǎn)。1層： 1052層： 105 * 105 = 10103層： 1010 * 1010 = 1020 節(jié)點(diǎn)數(shù)隨深度的增加以爆炸式方式增長(zhǎng)33博弈樹提高時(shí)間效率一般一步能控制在半分鐘內(nèi)為宜。方法：減小博弈樹的規(guī)模： 1.降低搜索深度，但棋力提高有限。 2.每個(gè)局面對(duì)應(yīng)只生成少許有價(jià)值的節(jié)點(diǎn)， 可能有漏選。運(yùn)用高效的搜索算法，例如：-剪枝。提高各模塊的效率，尤其是評(píng)估函數(shù)的效率。34極大極小值搜索建立了博弈樹，我們?cè)鯓诱业轿覀冃枰恼蟹ǎ克阉髋c回溯方式：因?yàn)椋壕置娣种翟礁?，?duì)我方越有利，對(duì)于對(duì)方越不利。局面分值越低，對(duì)我方越不利，也就是對(duì)于對(duì)方越有利。所以：輪到我方走時(shí)，我方會(huì)選擇使下一步局面分值最高的走法。此節(jié)點(diǎn)（局面）分值 = MAX所有子節(jié)點(diǎn)分值輪到對(duì)方走時(shí)，對(duì)方會(huì)選擇使下一步局面分值最低的走法。此節(jié)點(diǎn)（局面）分值 = MIN所以子節(jié)點(diǎn)分值35極大極小值搜索局面（取極大值）局面（取極小值）RootRoot MovesLeavesPly = 0Ply = 1Ply = 2Ply = 3De