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

六子棋博弈程序 唐志峰計(jì)算機(jī)博弈與人工智能協(xié)會(huì) 計(jì)算機(jī)博弈與人工智能 計(jì)算機(jī)博弈與人工智能 本次大賽通信協(xié)議 博弈程序整體設(shè)計(jì)思路 博弈程序核心模塊 機(jī)器博弈交互平臺(tái) 本次大賽的一些相關(guān)說明 講解要點(diǎn) 計(jì)算機(jī)博弈與人工智能 機(jī)器博弈交互平臺(tái) 棋盤 黑方程序 白方程序 1 1 1 2 3 3 4 5 5 6 計(jì)算機(jī)博弈與人工智能 本次大賽通信協(xié)議 接受裁判系統(tǒng)信息 scanf s Msg 傳回裁判系統(tǒng)信息 printf s Move 1 確定隊(duì)名 name 傳回隊(duì)名 nameBitStronger n 2 開局 new 3 確定黑白方 黑方 black 白方 white 4 發(fā)送 接收招法 先橫向坐標(biāo) 后縱向坐標(biāo)黑方第一步 moveX0Y0其他步數(shù) moveX0Y0X1Y1 計(jì)算機(jī)博弈與人工智能 博弈程序整體設(shè)計(jì)思路 實(shí)際問題 數(shù)學(xué)建模 算法 編程 調(diào)試 得到結(jié)果 計(jì)算機(jī)博弈與人工智能 棋盤表示 六子棋棋盤由19條橫線和19條縱線組成 棋盤一共有19 19 361個(gè)交點(diǎn) 交點(diǎn)出現(xiàn)的可能情況 無子 黑子 白子棋盤 charposition 19 19 棋子 黑棋 BLACK 0白棋 WHITE 1無子 NOSTONE 0 xff 示例代碼 宏定義 defineGRID NUM19 棋盤行數(shù) defineGRID COUNT361 可放棋子總數(shù) defineBLACK0 黑棋 defineWHITE1 白棋 defineNOSTONE0 xff 無棋全局變量 BYTEposition GRID NUM GRID NUM 棋盤STONEMOVEm cmBestMove 記錄著法注 include windows h typedefunsignedcharBYTE 計(jì)算機(jī)博弈與人工智能 示例代碼 結(jié)構(gòu)定義 棋子位置typedefstruct stoneposition BYTEx BYTEy STONEPOS 走法typedefstruct stonemove STONEPOSStonePos 2 棋子位置intScore 走法的分?jǐn)?shù) STONEMOVE 計(jì)算機(jī)博弈與人工智能 示例代碼 主函數(shù) 程序的入口voidmain intChessmanType 記錄棋子顏色charMsg 500 保存接收到的消息charname name中國深度 n 隊(duì)伍信息charMove moveAABB n 走法intx0 x1 y0 y1 坐標(biāo) 初始化棋盤memset position NOSTONE GRID COUNT 計(jì)算機(jī)博弈與人工智能 示例代碼 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 Msg name 0 printf s name fflush stdout continue 計(jì)算機(jī)博弈與人工智能 示例代碼 if strcmp Msg new 0 新開局 memset position NOSTONE GRID COUNT 初始化棋盤scanf s Msg if strcmp Msg black 0 確定我方棋子的顏色 Sleep 50 延遲一段時(shí)間發(fā)送 經(jīng)測試 立即發(fā)送可 能造成平臺(tái)無響應(yīng)printf moveJJ n position 9 9 BLACK fflush stdout ChessmanType BLACK continue 計(jì)算機(jī)博弈與人工智能 示例代碼 else if strcmp Msg white 0 ChessmanType WHITE continue 確定棋型顏色結(jié)束if strcmp Msg move 0 接收對方的招法scanf s Msg 計(jì)算機(jī)博弈與人工智能 示例代碼 if Msg 2 0 接收黑方的第一著 moveXX ny0 int Msg 0 int A x0 int S int Msg 1 position x0 y0 ChessmanType 計(jì)算機(jī)博弈與人工智能 示例代碼 else 接收對方的招法 一般招法都是一著下兩個(gè)子 moveXYXY ny0 int Msg 0 int A x0 int S int Msg 1 y1 int Msg 2 int A x1 int S int Msg 3 position x0 y0 ChessmanType position x1 y1 ChessmanType 計(jì)算機(jī)博弈與人工智能 示例代碼 if SearchAGoodMove position ChessmanType 獲得著法的坐標(biāo)x0 m cmBestMove StonePos 0 x y0 m cmBestMove StonePos 0 y x1 m cmBestMove StonePos 1 x y1 m cmBestMove StonePos 1 y 將著法記錄在棋盤中position x0 y0 ChessmanType position x1 y1 ChessmanType 計(jì)算機(jī)博弈與人工智能 示例代碼 將著法轉(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 moveAABB n 修改 AABB 并發(fā)送Move 5 y0 Move 6 x0 Move 7 y1 Move 8 x1 printf s Move fflush stdout 計(jì)算機(jī)博弈與人工智能 計(jì)算機(jī)博弈與人工智能 機(jī)器博弈交互平臺(tái) 棋盤 黑方程序 白方程序 1 1 1 2 3 3 4 5 5 6 計(jì)算機(jī)博弈的設(shè)計(jì)思路 SearchAGoodMove position ChessmanType 如何根據(jù)已有的棋盤局面和我方子的顏色 來得到我方下一步將要走的招法 計(jì)算機(jī)博弈與人工智能 窮舉法 窮舉出下一步所有可能的招法 形成不同的局面 比較一下這些局面 選取出其中最好的 對我方最有利 局面 則形成此局面對應(yīng)的招法就是我方下一步 最佳 的走法 所有可能的招法 招法生成比較 評估函數(shù)選取 最好的 搜索函數(shù) 極大極小值搜索 最佳 此時(shí)對應(yīng)的招法真的是最好的招法嗎 計(jì)算機(jī)博弈與人工智能 計(jì)算機(jī)博弈與人工智能 博弈程序核心模塊 AI引擎 招法生成 招法生成 生成一個(gè)局面的所有可能招法 合法招法 例如 象棋中的 象走田 馬走日 兵可進(jìn)不可退 六子棋的合法招法 任意空格點(diǎn) 思考 是不是所有招法都是我們需要考慮的 可不可以舍棄一些招法 速度與準(zhǔn)確性的矛盾 計(jì)算機(jī)博弈與人工智能 評估函數(shù) 評估函數(shù) 用以評價(jià)一個(gè)局面的好壞 計(jì)算機(jī)如何知道一個(gè)局面的好壞 局面的好壞實(shí)數(shù)思路 根據(jù)局面中的各方棋型 來具體分析局面好壞 給出各局面的分值 難點(diǎn) 1 查找棋型 保證速度與準(zhǔn)確性 2 如何根據(jù)棋型給分值 分值如何確定 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 長連 在棋盤的縱向 橫向或斜向的任意一條線上 形成的7顆或7顆以上同色棋子不間隔地相連 六連 在棋盤的縱向 橫向或斜向的任意一條線上 形成的6顆同色棋子不間隔地相連 長連和六連是規(guī)定時(shí)間內(nèi)獲勝的必要條件 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 活五 在同一直線上的5顆同色棋子 符合 對方必須用兩手棋才能擋住 的條件 擋住 是指不讓另一方形成六連或長連 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 眠五 在同一直線上的5顆同色棋子 符合 對方用用一手棋才能擋住 的條件 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 活四 在同一直線上的4顆同色棋子 符合 對方必須用兩手棋才能擋住 的條件 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 眠四 在同一直線上的4顆同色棋子 符合 對方用用一手棋才能擋住 的條件 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 活三 在同一直線上的3顆同色棋子 符合 再下一手就能形成活四 的條件 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 眠三 在同一直線上的3顆同色棋子 符合 再下兩手棋也只能形成眠四 的條件 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 活二 在同一直線上的2顆同色棋子 符合 再下兩手棋就能形成活四 的條件 計(jì)算機(jī)博弈與人工智能 六子棋的棋型 眠二 在同一直線上的2顆同色棋子 符合 再下兩手棋只能形成眠四 的條件 計(jì)算機(jī)博弈與人工智能 搜索函數(shù) 下一個(gè)最好的 評估分值最高 局面的對應(yīng)的招法就是最佳招法嗎 棋類高手都能看很多步 當(dāng)我方生成各種局面后 對方針對我方形成的每一種局面又同樣會(huì)生成許多局面 我方再針對對方形成的每一種局面同樣又會(huì)生成許多對應(yīng)局面 這樣循環(huán)往復(fù) 就形成了一個(gè)顆博弈樹 計(jì)算機(jī)博弈與人工智能 博弈樹 計(jì)算機(jī)博弈與人工智能 博弈樹一棵多叉樹 六子棋博弈樹的復(fù)雜度很高 每個(gè)局面對應(yīng)招法開始 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ù)隨深度的增加以爆炸式方式增長 博弈樹 提高時(shí)間效率一般一步能控制在半分鐘內(nèi)為宜 方法 減小博弈樹的規(guī)模 1 降低搜索深度 但棋力提高有限 2 每個(gè)局面對應(yīng)只生成少許有價(jià)值的節(jié)點(diǎn) 可能有漏選 運(yùn)用高效的搜索算法 例如 剪枝 提高各模塊的效率 尤其是評估函數(shù)的效率 計(jì)算機(jī)博弈與人工智能 極大極小值搜索 建立了博弈樹 我們怎樣找到我們需要的招法 搜索與回溯方式 因?yàn)?局面分值越高 對我方越有利 對于對方越不利 局面分值越低 對我方越不利 也就是對于對方越有利 所以 輪到我方走時(shí) 我方會(huì)選擇使下一步局面分值最高的走法 此節(jié)點(diǎn) 局面 分值 MAX 所有子節(jié)點(diǎn)分值 輪到對方走時(shí) 對方會(huì)選擇使下一步局面分值最低的走法 此節(jié)點(diǎn) 局面 分值 MIN 所以子節(jié)點(diǎn)分值 計(jì)算機(jī)博弈與人工智能 計(jì)算機(jī)博弈與人工智能 極大極小值搜索