中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽新增比賽項(xiàng)目課件

1、東北大學(xué)機(jī)器博弈研究室2010中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽比賽項(xiàng)目簡(jiǎn)介比賽項(xiàng)目簡(jiǎn)介徐徐 心心 和和2010.01東北大學(xué)機(jī)器博弈研究室2010中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽中國(guó)計(jì)算機(jī)博弈錦標(biāo)賽比賽項(xiàng)目比賽項(xiàng)目 傳統(tǒng)項(xiàng)目傳統(tǒng)項(xiàng)目 中國(guó)象棋中國(guó)象棋 圍棋圍棋 九路圍棋九路圍棋 六子棋六子棋 新增項(xiàng)目新增項(xiàng)目點(diǎn)格棋（點(diǎn)格棋（Dots and Boxes）蘇拉卡爾塔（蘇拉卡爾塔（Surakarta）亞馬遜（亞馬遜（Amazons）幻影圍棋（幻影圍棋（ Phantom Go ） 國(guó)際機(jī)器博弈協(xié)會(huì)（國(guó)際機(jī)器博弈協(xié)會(huì)（ICGA）計(jì)算機(jī)奧林匹克大賽）計(jì)算機(jī)奧林匹克大賽 （Computer Olympiad）

2、項(xiàng)目）項(xiàng)目東北大學(xué)機(jī)器博弈研究室中國(guó)象棋（中國(guó)象棋（Chinese Chess） 棋盤(pán)棋盤(pán) 910 棋子：紅黑各棋子：紅黑各7個(gè)兵種，個(gè)兵種，16子子 各兵種的行棋規(guī)各兵種的行棋規(guī)則和活動(dòng)范圍則和活動(dòng)范圍 勝負(fù)判定準(zhǔn)則勝負(fù)判定準(zhǔn)則 長(zhǎng)將、長(zhǎng)拖長(zhǎng)將、長(zhǎng)拖 時(shí)間約束時(shí)間約束 60步不吃子判和步不吃子判和東北大學(xué)機(jī)器博弈研究室圍棋（圍棋（Go / I-Go） 棋盤(pán)棋盤(pán) 1919 輪流下子，誰(shuí)占輪流下子，誰(shuí)占的地盤(pán)多誰(shuí)勝。的地盤(pán)多誰(shuí)勝。 先下手為強(qiáng)，貼先下手為強(qiáng)，貼目（目（5-7）。）。 規(guī)則最簡(jiǎn)單，計(jì)規(guī)則最簡(jiǎn)單，計(jì)算機(jī)博弈難度最算機(jī)博弈難度最大。大。 當(dāng)前側(cè)重解決當(dāng)前側(cè)重解決1/4棋盤(pán)棋盤(pán) Go 9

3、9東北大學(xué)機(jī)器博弈研究室五子棋（五子棋（ FIR-Five In A Row ） 起源于中國(guó)起源于中國(guó) 發(fā)展在日本（連珠棋）發(fā)展在日本（連珠棋） Renju / Go-Moku 棋盤(pán)棋盤(pán) 1515 已被證明先手勝已被證明先手勝 禁手禁手 換手換手 金球制改進(jìn)球制金球制改進(jìn)球制東北大學(xué)機(jī)器博弈研究室六子棋（六子棋（Connect 6） 吳毅成教授發(fā)明吳毅成教授發(fā)明 棋盤(pán)棋盤(pán) 1919 6子連珠為勝子連珠為勝 先手下一子，然后每手先手下一子，然后每手下兩子，削減先手優(yōu)勢(shì)下兩子，削減先手優(yōu)勢(shì) 復(fù)雜度顯著提高復(fù)雜度顯著提高 臺(tái)灣已經(jīng)盛行臺(tái)灣已經(jīng)盛行 歐洲也很關(guān)注歐洲也很關(guān)注東北大學(xué)機(jī)器博弈研究室點(diǎn)格棋

4、（點(diǎn)格棋（3，3）東北大學(xué)機(jī)器博弈研究室Dots and Boxes(點(diǎn)格棋)東北大學(xué)機(jī)器博弈研究室點(diǎn)格棋（點(diǎn)格棋（6，6）東北大學(xué)機(jī)器博弈研究室“點(diǎn)點(diǎn)連格棋”規(guī)則棋盤(pán)由66個(gè)點(diǎn)構(gòu)成方陣，可以連成55個(gè)小方格子。玩法 1）雙方輪流將鄰近兩點(diǎn)連成邊，不可越點(diǎn)，不可重邊，不連對(duì)角線； 2）邊不歸屬于任一方，只對(duì)格子判斷歸屬； 3）每個(gè)格子的四條邊被占滿四條邊被占滿時(shí)，該格子便被最后一個(gè)占邊者所俘獲； 4）俘獲格子后可以并必須再連一條邊； 5）格子全部圍成后，博弈結(jié)束。勝負(fù)占領(lǐng)格子較多的一方為獲勝方。東北大學(xué)機(jī)器博弈研究室蘇拉卡爾塔（ Surakarta）東北大學(xué)機(jī)器博弈研究室“蘇拉卡爾塔”規(guī)則棋盤(pán)

5、棋子1）橫豎各6條邊構(gòu)成正方形棋盤(pán)，36個(gè)交叉點(diǎn)為棋位，各邊由8段圓弧連接，通常用2種不同顏色表示。2）紅黑雙方各12枚棋子。初始狀態(tài)棋子各方底線排成2排。玩法 1）雙方輪流走棋，每次走動(dòng)一枚棋子； 2）除了吃子之外，每枚棋子只能沿著垂直或?qū)欠较蜃邉?dòng)一格，只能走向空位； 3）吃對(duì)方子時(shí)必須經(jīng)過(guò)至少一個(gè)完整的弧線。勝負(fù)吃掉所有對(duì)方棋子一方獲勝。東北大學(xué)機(jī)器博弈研究室亞馬遜亞馬遜 棋盤(pán)表示：棋盤(pán)表示：1010方陣方陣 棋子：黑白各四個(gè)皇后棋子：黑白各四個(gè)皇后 占格棋子（可用圍棋黑占格棋子（可用圍棋黑棋子）棋子）80個(gè)，表示路障個(gè)，表示路障東北大學(xué)機(jī)器博弈研究室“亞馬遜亞馬遜”規(guī)則規(guī)則1. 棋盤(pán)棋

6、子棋盤(pán)棋子1）棋盤(pán)是由深淺兩色間隔排列的）棋盤(pán)是由深淺兩色間隔排列的100個(gè)小方格組成的正方形。個(gè)小方格組成的正方形。2）雙方各有）雙方各有4個(gè)（國(guó)際象棋）個(gè)（國(guó)際象棋）“皇后皇后” 棋子，初始棋位如圖所示。棋子，初始棋位如圖所示。2. 棋子走法棋子走法 1）雙方著法均由兩部分構(gòu)成：先走棋，再）雙方著法均由兩部分構(gòu)成：先走棋，再 “放箭放箭”。雙方輪流走棋并。雙方輪流走棋并放箭（設(shè)障），但不吃子。放箭（設(shè)障），但不吃子。 2）走棋：按照國(guó)際象棋）走棋：按照國(guó)際象棋 “皇后皇后”的走法，即可以走到橫向、豎向和斜的走法，即可以走到橫向、豎向和斜向的任何空棋位。此棋位稱(chēng)之為向的任何空棋位。此棋位稱(chēng)之

7、為“到達(dá)棋位到達(dá)棋位”； 3）放箭（設(shè)障）：從）放箭（設(shè)障）：從“到達(dá)棋位到達(dá)棋位”向向“皇后皇后”可行的路徑上的任一棋可行的路徑上的任一棋位放置一個(gè)永久性障礙物。可以在該點(diǎn)放置一枚黑色的圍棋子，任何棋位放置一個(gè)永久性障礙物?？梢栽谠擖c(diǎn)放置一枚黑色的圍棋子，任何棋子都不可以越過(guò)。子都不可以越過(guò)。3. 勝負(fù)勝負(fù)結(jié)束標(biāo)志為一方?jīng)]有棋子可以移動(dòng)。最后可以走動(dòng)棋子的一方獲勝。結(jié)束標(biāo)志為一方?jīng)]有棋子可以移動(dòng)。最后可以走動(dòng)棋子的一方獲勝。 考慮到白方的先手優(yōu)勢(shì)，一般允許黑方有考慮到白方的先手優(yōu)勢(shì)，一般允許黑方有n次次pass（不走棋）（不走棋）東北大學(xué)機(jī)器博弈研究室走棋與放箭走棋與放箭東北大學(xué)機(jī)器博弈研究

8、室幻影圍棋幻影圍棋 幻影圍棋是一項(xiàng)歐洲的棋類(lèi)游戲，因?yàn)橄缕逡?guī)則是基于幻影圍棋是一項(xiàng)歐洲的棋類(lèi)游戲，因?yàn)橄缕逡?guī)則是基于圍棋，但又是圍棋，但又是在圍棋的基礎(chǔ)上加入了信息不完全的限在圍棋的基礎(chǔ)上加入了信息不完全的限制制看不到對(duì)方的落子，看不到對(duì)方的落子，故名幻影圍棋。故名幻影圍棋。 棋盤(pán)：棋盤(pán)：99圍棋的棋盤(pán)。圍棋的棋盤(pán)。 棋子：黑白兩種圍棋棋子。棋子：黑白兩種圍棋棋子。 實(shí)際上有實(shí)際上有3個(gè)棋盤(pán)，黑方棋盤(pán)，白方棋盤(pán)，裁判棋盤(pán)。個(gè)棋盤(pán)，黑方棋盤(pán)，白方棋盤(pán)，裁判棋盤(pán)。 本方只清楚自己的落子情況，對(duì)于對(duì)方落子情況只能判本方只清楚自己的落子情況，對(duì)于對(duì)方落子情況只能判斷和猜測(cè)。裁判的棋盤(pán)才給出真正的棋局。

9、斷和猜測(cè)。裁判的棋盤(pán)才給出真正的棋局。東北大學(xué)機(jī)器博弈研究室東北大學(xué)機(jī)器博弈研究室幻影圍棋棋規(guī)幻影圍棋棋規(guī)黑白雙方輪流落子，黑白雙方輪流落子，落子的基本規(guī)則與圍棋一致，其中氣、禁招等落子的基本規(guī)則與圍棋一致，其中氣、禁招等概念都相同；概念都相同；幻影圍棋中加入了信息隱藏的概念幻影圍棋中加入了信息隱藏的概念在下棋時(shí)，雙方都無(wú)法看到在下棋時(shí)，雙方都無(wú)法看到對(duì)手棋盤(pán)上的落子，形成兩個(gè)不完備信息的棋盤(pán)，完備信息的對(duì)弈對(duì)手棋盤(pán)上的落子，形成兩個(gè)不完備信息的棋盤(pán)，完備信息的對(duì)弈棋盤(pán)是由雙方的棋盤(pán)取并集而成；棋盤(pán)是由雙方的棋盤(pán)取并集而成；由于信息隱藏，就需要一個(gè)中間裁判。裁判可以看到雙方棋盤(pán)，也由于信息隱藏

10、，就需要一個(gè)中間裁判。裁判可以看到雙方棋盤(pán)，也就是說(shuō)，就是說(shuō)，從裁判角度所看到的是一個(gè)完備信息的從裁判角度所看到的是一個(gè)完備信息的99圍棋棋盤(pán)，并圍棋棋盤(pán)，并且根據(jù)圍棋規(guī)則判斷雙方落子是否合法，如果合法的話返回且根據(jù)圍棋規(guī)則判斷雙方落子是否合法，如果合法的話返回legal，若不合法則返回若不合法則返回illegal；當(dāng)有一方落子后出現(xiàn)當(dāng)有一方落子后出現(xiàn)提子提子情況時(shí)，裁判會(huì)向雙方返回提子數(shù)目與位情況時(shí)，裁判會(huì)向雙方返回提子數(shù)目與位置信息，雙方同時(shí)更改棋面；置信息，雙方同時(shí)更改棋面；當(dāng)一方所有落子都返回當(dāng)一方所有落子都返回illegal時(shí)即可判斷該方時(shí)即可判斷該方PASS；直至雙方都無(wú)法再落子，

11、即雙方都返回直至雙方都無(wú)法再落子，即雙方都返回PASS，此時(shí)由裁判根據(jù)所占，此時(shí)由裁判根據(jù)所占地域多少判定勝負(fù)。地域多少判定勝負(fù)。 東北大學(xué)機(jī)器博弈研究室一盤(pán)人機(jī)對(duì)弈的棋譜一盤(pán)人機(jī)對(duì)弈的棋譜摘自：摘自：Tristan Cazenave A Phantom Go Program黑方（黑方（B）：計(jì)算機(jī)程序，白方（）：計(jì)算機(jī)程序，白方（W）：幻影圍棋選手）：幻影圍棋選手東北大學(xué)機(jī)器博弈研究室30手后的裁判棋盤(pán)手后的裁判棋盤(pán)30手后的黑棋棋盤(pán)手后的黑棋棋盤(pán)摘自：摘自：Tristan Cazenave A Phantom Go Program東北大學(xué)機(jī)器博弈研究室最終棋局最終棋局 領(lǐng)地已經(jīng)分明，沒(méi)有繼續(xù)落領(lǐng)地已經(jīng)分明，沒(méi)有繼續(xù)落子的必要了，雙方子的必要了，雙方pass 黑先手，落黑先手，落32子；白后手，子；白后手，落落30子，其中子，其中2子被