計算機博弈引擎協(xié)議和博弈程序比賽.ppt

1、2020/10/7,1,計算機博弈引擎協(xié)議和博弈程序比賽 黃晨 mailto: ,計算機博弈引擎協(xié)議和博弈程序比賽,2020/10/7,2,報告內(nèi)容 1. 國際象棋引擎協(xié)議歷史 2. 博弈引擎協(xié)議 3. 博弈程序自動比賽 4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,1. 國際象棋引擎協(xié)議歷史,2020/10/7,3,國際象棋引擎協(xié)議歷史 1.1 從 MANIAC 到“深藍”,1. 國際象棋引擎協(xié)議歷史,c. Ken Tompson 和他設(shè)計的 Belle,a. 最早機器下棋的構(gòu)想(1769年),b. 第一臺會下棋MANIAC(1950年),2020/10/7,4,1. 國際象棋引擎協(xié)議歷史,d.

2、 “深藍”的兩位設(shè)計師 Hans Berliner 和許峰雄,e. Ken Thompson 和 Gary Kasparov,1.1 從 MANIAC 到“深藍”,2020/10/7,5,1.2 GNU Chess 和 XBoard,1. 國際象棋引擎協(xié)議歷史,f. WinBoard,g. WinBoard 的作者 Tim Mann,h. Crafty 的作者 Robert Hyatt Crafty 是國際象棋程序的教科書,2020/10/7,6,1. 國際象棋引擎協(xié)議歷史,1.3 WinBoard、ChessBase 和 UCI并存的格局 XBoard/WinBoard協(xié)議 - 最早、用得最

3、多的開放引擎協(xié)議 1986年，GNU Chess誕生，有了文本界面的概念； 1991年，XBoard誕生，支持Xboard的文本界面； 1993年，Xboard在Windows下的版本W(wǎng)inBoard誕生，WinBoard協(xié)議形成體系。 截止至2006年7月，支持WinBoard的程序共有312個(WBEC Ridderkerk)。 ChessBase協(xié)議 - ChessBase系列國際象棋程序的專用引擎協(xié)議 1998年，由Fritz首創(chuàng)，支持Junior、Hiarcs、Shredder、NIMZO等程序； 2002年，由于Shredder創(chuàng)立UCI的原因，ChessBase開始全面支持UCI

4、。 目前支持5個商業(yè)引擎(Fritz、Junior、Hiarcs、NIMZO和Zap!Chess)和 9個免費引擎(大都改自開放源程序的WinBoard引擎) UCI/Chess960協(xié)議 - 新興的開放引擎協(xié)議，與WinBoard相抗衡 2000年，Shredder創(chuàng)立UCI協(xié)議； 2002年，ChessBase開始全面支持UCI； 截止至2006年7月，支持UCI的程序共有89個(其中65個也支持WinBoard)。,(WBEC Ridderkerk的統(tǒng)計數(shù)據(jù)，不包括克隆程序，如Toga II。),2020/10/7,7,1.4 WBEC Ridderkerk 和 PolyGlot WBE

5、C Ridderkerk - 規(guī)模最大的國際象棋引擎聯(lián)賽組織 2001年，WBEC Ridderkerk開始對WinBoard引擎進行測試； 冠軍引擎：Gandalf(第1期)、Ruffian(第2、3期)、DeepSjeng(第4、6期)、 (第5期沒有舉行頂級組聯(lián)賽)、The King(第7期)。 PolyGlot - 使 UCI 引擎和 WinBoard 引擎同臺競技 2004年，UCI到WinBoard的適配器PolyGlot誕生； 同年UCI引擎都加入了WBEC Ridderkerk聯(lián)賽的行列； 冠軍引擎：Shredder(第8、9、10期)、Fruit(第11期)、Rybka(第1

6、2期)； 最近幾期的冠軍全部被UCI引擎包攬。,1. 國際象棋引擎協(xié)議歷史,2020/10/7,8,報告內(nèi)容 1. 國際象棋引擎協(xié)議歷史 2. 博弈引擎協(xié)議 3. 博弈程序自動比賽 4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,2. 博弈引擎協(xié)議,2020/10/7,9,博弈引擎協(xié)議 2.1 界面、引擎和“界面-引擎協(xié)議” 界面(GUI) -可視化操作模塊 引擎 - 智能核心模塊 界面-引擎協(xié)議(簡稱引擎協(xié)議) - 界面和引擎耦合方式(通訊方式) 針對一個界面(符合某一協(xié)議的)，可以設(shè)計出水平更高的引擎 針對一個引擎(符合某一協(xié)議的)，可以設(shè)計出功能更強大的界面 引擎協(xié)議的意義在于：使博弈軟件的設(shè)

7、計者更專著于某一模塊(要么是界面， 要么是引擎)的設(shè)計。,2. 博弈引擎協(xié)議,2020/10/7,10,2. 博弈引擎協(xié)議,2.2 博弈引擎協(xié)議的技術(shù)特點 A. 通訊方式 B. 工作方式同步和異步 C. 語法指令和反饋 D. 后臺思考 E. 認輸和提和 F. 禁止著法 G. 歷史著法,2020/10/7,11,標準輸入/輸出通道的通訊方式,A. 通訊方式 ChessBase等非開放的引擎協(xié)議：類似DLL的API函數(shù)程序庫； WinBoard、UCI等開放的引擎協(xié)議：通過標準輸入/輸出通道實現(xiàn)通訊； 標準輸入/輸出通道的優(yōu)點： a. 有利于引擎和界面的跨平臺發(fā)展； b. 單一的引擎或單一的界面有

8、實現(xiàn)商業(yè)化的可能。 界面程序向引擎程序傳送的信息稱為“指令”； 引擎程序向界面程序傳誦的信息稱為“反饋”。,2. 博弈引擎協(xié)議,2020/10/7,12,同步方式,異步方式,B. 工作方式同步和異步 同步方式：界面和引擎采用同樣的棋局進程。 優(yōu)點：通訊簡單； 缺點：a. 引擎重復(fù)了界面的棋局進程處理，b. 要應(yīng)對“不同步”的情況。 異步方式：引擎沒有棋局進程，而只是針對一系列局面進行思考，給出著法。 優(yōu)點：a. 無需處理棋局進程，b. 不存在“不同步”的情況； 缺點：a. 通訊量大，協(xié)議內(nèi)容繁多，b. 要解決歷史著法引起的重復(fù)局面問題。,2. 博弈引擎協(xié)議,2020/10/7,13,C. 語法

9、指令和反饋 指令和反饋的要求：i. 文本方式和行方式，ii. 界面和引擎都隨時待命， iii. 語法規(guī)范(類似于DOS/UNIX的控制臺命令)； 引擎的狀態(tài)：i. 等待狀態(tài)，ii. 思考狀態(tài)； 語法說明書和示例：指令用紅色表示，反饋用藍色表示。,ucci id name ElephantEye Demo option usemillisec type check default false option usebook type check default true ucciok setoption usemillisec true setoption usebook false positi

10、on fen rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w - - 0 1 go time 300000 increment 0 info depth 6 score 4 pv b0c2 b9c7 c3c4 h9i7 c2d4 h7e7 info nodes 5000000 time 5000 stop bestmove b0c2 ponder b9c7 quit bye,引導狀態(tài),空閑狀態(tài),思考狀態(tài),空閑狀態(tài),2. 博弈引擎協(xié)議,2020/10/7,14,D. 后臺思考 同步方式：引擎自動控制，有“是否啟用后臺思考

11、”的開關(guān)(easy/hard)； 異步方式：由界面控制，有專門的處理后臺思考的指令和反饋。 后臺思考的工作原理：猜測著法！ i. 引擎提供猜測著法：bestmove ponder 和是主要變例的前兩個著法。 ii. 界面要求進行后臺：go ponder iii. 對方著法與猜測著法一致后臺思考命中：ponderhit iv. 后臺思考沒有命中：stop / go ,2. 博弈引擎協(xié)議,2020/10/7,15,E. 認輸和提和 人類棋手采用的提和規(guī)則：走棋的一方提和，不走棋的一方?jīng)Q定是否接受提和； 電腦的問題：是否“接受提和”是需要計算的，這樣會打斷“后臺思考”！ 適應(yīng)電腦的提和規(guī)則： i.

12、走棋的一方可在走棋的同時提和； ii. 輪到對方走棋時，對方可以選擇提和，也可以繼續(xù)走棋； 異步方式引擎協(xié)議對認輸和提和的規(guī)定： i.引擎認輸：bestmove ponder resign ii.界面不需要向引擎發(fā)出認輸指令； iii.引擎提和： bestmove ponder draw iv.界面向引擎提和：go draw v.界面向引擎提和(后臺思考命中)：ponderhit draw vi.引擎拒絕提和： bestmove ponder vii.引擎接受提和： bestmove ponder draw viii.界面不需要向引擎發(fā)出接受提和的指令。,2. 博弈引擎協(xié)議,2020/10/7

13、,16,F. 禁止著法 長打中國象棋規(guī)則問題的疑難雜癥！ 人類棋手采用的做法：遇到爭議，由裁判作出仲裁； 電腦可以采用的做法：如果不能正確判斷，可由人類作出仲裁； 界面向引擎發(fā)出禁止著法的指令：banmoves ,2. 博弈引擎協(xié)議,6回合后,紅方?jīng)]有禁著,車二進一是禁著 界面要向引擎發(fā)送：banmoves h8h9,2020/10/7,17,G. 歷史著法 問題引擎如何自動避免走出禁止著法？,2回合后?,紅方?jīng)]有禁著,2回合后：車二進一不是禁著 6回合后：車二進一是禁著,6回合后?, 解決界面向引擎?zhèn)鬟_歷史著法：position moves 例：position fen 4k4/9/5a3/

14、4r4/9/9/9/9/9/5K1R1 w - - 0 1 moves h0h9 e9e8 ,2. 博弈引擎協(xié)議,2020/10/7,18,2.3 引擎協(xié)議適配器 實現(xiàn)兩種不同的引擎協(xié)議之間的轉(zhuǎn)換和通用 適配器的方向性從“引擎端協(xié)議”到“界面端協(xié)議” 例如：WinBoard(引擎)到ChessBase(界面)的適配器 WinBoard(引擎)到UCI(界面)的適配器WB2UCI UCI(引擎)到WinBoard(界面)的適配器PolyGlot 淺紅象棋(引擎)到UCCI(界面)的適配器QH2UCCI UCCI(引擎)到淺紅象棋(界面)的適配器UCCI2QH,2. 博弈引擎協(xié)議,2020/10/

15、7,19,報告內(nèi)容 1. 國際象棋引擎協(xié)議歷史 2. 博弈引擎協(xié)議 3. 博弈程序自動比賽 4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,3. 博弈程序自動比賽,2020/10/7,20,3. 博弈程序自動比賽,博弈程序自動比賽 3.1 國際大賽普遍采用的方式手動比賽 ICGA 11th Computer Olympiad 14th World Computer-Chess Championship (WCCC) 2004年世界電腦象棋爭霸賽/2005年世界電腦圍棋爭霸賽 全國首屆計算機博弈錦標賽 3.2 手動比賽帶來的問題 比機器還是比程序? 電腦之間的比賽為什么要人來操作? 能否延長賽程?,2

16、020/10/7,21,3. 博弈程序自動比賽,3.3 民間賽事自動比賽 WinBoard Engine Competition (WBEC) - Ridderkerk, Netherlands Gomocup 電腦象棋(UCCI引擎)聯(lián)賽 3.4 自動比賽的優(yōu)勢和技術(shù)問題 硬件環(huán)境公平 實現(xiàn)全天候工作，不需要人工操作，不需要參賽者到場 建立程序間的通訊方式引擎協(xié)議是現(xiàn)成的通訊方式 賽程控制程序 WinBoard Tournament Manager (WBTM) UCCI引擎聯(lián)賽模擬器 對比賽環(huán)境、程序、賽制等都要有詳細嚴格的要求(WBEC有詳細的規(guī)定),2020/10/7,22,3.5 W

17、BEC 的環(huán)境和程序要求 硬件環(huán)境：每個級別聯(lián)賽在一臺機器上進行，雙處理器，1024MB存儲器； 從超級到末級，處理器依次為：Opteron 244(超級和甲級)、Athlon MP2600、 Athlon MP2400、Athlon MP2200、P3-1266Mhz； 操作系統(tǒng)：Windows XP Pro 64(超級和甲級)，Windows 2000 Pro(其他級別) 比賽軟件：WBTM(聯(lián)賽控制程序)，WinBoard-X(自動對弈程序)， PolyGlot(UCI到WinBoard適配器)，3、4、5子Nalimov殘局庫； 報名要求：在報名截止日期前將程序發(fā)給賽事組織者提供； 程

18、序要求：單線程的WinBoard或UCI引擎； 程序設(shè)置：參賽者可提供最適合本程序的配置文件和開局庫； 穩(wěn)定性要求：正式比賽前，進行1次3分鐘走40步的測試賽， 測試賽中程序崩潰超過2局，或者超時局數(shù)超過10%，則取消正式比賽資格， 但發(fā)現(xiàn)問題的程序有機會修正錯誤，或者用舊版穩(wěn)定的程序代替； 存儲器限制：最多使用128MB置換表和32MB殘局庫緩沖區(qū)； 程序版權(quán)：注名所有程序參與者(包括)； 作者限制：一位作者(程序的主要參與者)只能有一個程序參賽； 參賽者權(quán)利：賽前可讓賽事組織者測試其程序是否符合聯(lián)賽規(guī)則；,3. 博弈程序自動比賽,2020/10/7,23,3.6 WBEC 的賽制和規(guī)則 時

19、限：時段制，40分鐘走40步，啟用后臺思考(因此需要使用雙處理器)； 判和規(guī)則： (1) 逼和， (2) 50回合沒有吃子或進兵， (3) 3次重復(fù)局面， (4) 雙方明顯沒有足夠子力獲勝(例如王馬對王，或王象對王)； 判負規(guī)則： (1) 被將死(例外情況，對方明顯沒有足夠子力獲勝，則判和)， (2) 超時(例外同上)， (3) 錯判“將死”或“和棋” (例外同上)， (4) 不合法著法(例外同上)， (5) 程序崩潰(例外同上)； 平分的名次判定依據(jù)： (1) 相互勝負， (2) 總勝局多者在前， (3) 執(zhí)黑得分高者在前。,3. 博弈程序自動比賽,2020/10/7,24,3.7 WBEC

20、 的升降級制度 超級、甲級、乙級、丙級，各24個程序，進行4次循環(huán)賽(先后手各兩局)； 丁級32個程序，進行2次循環(huán)賽(先后手各一局)； 其余程序都編入末級，進行若干次循環(huán)賽(取決于參賽程序的數(shù)量)； 各級(除超級外)的第1名直接升入上一級別； 甲級到丁級第2至5名和末級第2至7名要參加上一級別的資格賽； 超級到乙級的最后5名、丙級和丁級的最后7名要參加同一級別的資格賽； 超級到丙級資格賽的前4名和丁級資格賽的前6名留將參加本級別聯(lián)賽， 其余程序降入下一級別； 超級、甲級、乙級、丙級資格賽進行4次循環(huán)賽，丁級進行2次循環(huán)賽； 某個程序的等級分比任何一級的第10名還高，就有資格跟該級別的第10、

21、11和 12名各進行4局比賽，達到6.5分即可參該級別的聯(lián)賽，這會給程序跳級的機會； 如果某一級別的跳級沒有成功，那么該程序可以嘗試低一級別的跳級測試； 新的程序加入時，首先跟丁級的第10、11和12名各進行4局比賽，達到6分即可 參加該級別，并且用同樣的過程測試是否參加更高級別的比賽。,3. 博弈程序自動比賽,2020/10/7,25,4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,報告內(nèi)容 1. 國際象棋引擎協(xié)議歷史 2. 博弈引擎協(xié)議 3. 博弈程序自動比賽 4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,2020/10/7,26,UCCI引擎協(xié)議和UCCI引擎聯(lián)賽 4.1 UCCI引擎協(xié)議的初衷

22、2004年開設(shè)象棋百科全書網(wǎng)站() 借鑒國際象棋的方法和理念，在中國象棋中引進ECCO、PGN、FEN等概念 “中國象棋程序設(shè)計”這一課題成為試金石，UCI協(xié)議成為借鑒的首選 4.2 UCCI引擎協(xié)議的發(fā)展 UCCI引擎協(xié)議并非最早的中國象棋引擎協(xié)議 2000年，夢入神蛋(Kill Egg)是首個公開源代碼的中國象棋程序 2003年，淺紅象棋(V2.8)支持引擎，并把夢入神蛋制成淺紅象棋引擎 2005年，第一個UCCI界面象堡和第一個UCCI引擎象眼誕生 2006年，第一期UCCI引擎聯(lián)賽舉行，參賽程序有8個 截止到2006年7月，在象棋百科全書網(wǎng)站上登記的UCCI引擎共有16個,4. UCC

23、I引擎協(xié)議和UCCI引擎聯(lián)賽,2020/10/7,27,4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,2006年3月，UCCI界面象堡更名為象棋巫師,2020/10/7,28,4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,4.3 UCCI引擎聯(lián)賽 2006年1月，UCCI引擎聯(lián)賽模擬器研制成功，支持加時制時限和循環(huán)賽制 2006年2月，第一期UCCI引擎聯(lián)賽舉行，參賽程序有8個 2006年7月，夢入神蛋制成UCCI引擎參加第6期聯(lián)賽，在聯(lián)賽中排名墊底 2006年2月至7月，UCCI引擎聯(lián)賽共舉行了6期 第1期(上海站)，2.202.26，8隊28輪快棋，象眼奪冠 第2期(北京站)，3.243.27，8

24、隊28輪快棋，象棋旋風奪冠 第3期(南寧站)，4.214.24，9隊36輪慢棋，象棋旋風奪冠 第4期(南寧站)，4.214.24，9隊36輪快棋，EndEgg奪冠 第5期(南京站)，6.26.9，12隊44輪快棋，象棋旋風奪冠 第6期(杭州站)，7.137.19，9隊36輪慢棋，象棋旋風奪冠 聯(lián)賽的環(huán)境和程序要求： i. 32位Windows平臺， 單線程的UCCI引擎，不啟用后臺思考； ii. 用時和存儲器限制視東道主提供的比賽用機器而定。 聯(lián)賽采用的規(guī)則： i. 將死、不合法著法、單方面長將、超時判負； ii. 50回合不吃子、除單方面長將外的循環(huán)著法判和。,2020/10/7,29,4. UCCI引擎協(xié)議和UCCI引擎聯(lián)賽,4.4 中國象棋自動對弈的難題用程序描述規(guī)則 亞洲規(guī)則的實現(xiàn)比中國規(guī)則簡單，所以電腦象棋程序大都只支持亞洲規(guī)則 亞洲規(guī)則的“打”只包括“將”和“捉”，不包括“殺”和“要抽吃” 目前還沒有一個程序聲稱完全支持亞洲規(guī)則 “捉”的定義：自己的一個子可以攻擊到對方的一個子 “捉”的補充規(guī)定： i. 走子之前已經(jīng)構(gòu)成攻擊的不算捉； ii. 兵(卒)和帥(將)