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

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

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

3、e In A Row ） 起源于中國起源于中國 發(fā)展在日本（連珠棋）發(fā)展在日本（連珠棋） Renju / Go-Moku 棋盤棋盤 1515 已被證明先手勝已被證明先手勝 禁手禁手 換手換手 金球制改進(jìn)球制金球制改進(jìn)球制6六子棋（六子棋（Connect 6） 吳毅成教授發(fā)明吳毅成教授發(fā)明 棋盤棋盤 1919 6子連珠為勝子連珠為勝 先手下一子，然后每手先手下一子，然后每手下兩子，削減先手優(yōu)勢下兩子，削減先手優(yōu)勢 復(fù)雜度顯著提高復(fù)雜度顯著提高 臺灣已經(jīng)盛行臺灣已經(jīng)盛行 歐洲也很關(guān)注歐洲也很關(guān)注7點(diǎn)格棋（點(diǎn)格棋（3，3）8Dots and Boxes(點(diǎn)格棋)9點(diǎn)格棋（點(diǎn)格棋（6，6）10“點(diǎn)點(diǎn)連

4、格棋”規(guī)則棋盤由66個點(diǎn)構(gòu)成方陣，可以連成55個小方格子。玩法 1）雙方輪流將鄰近兩點(diǎn)連成邊，不可越點(diǎn)，不可重邊，不連對角線； 2）邊不歸屬于任一方，只對格子判斷歸屬； 3）每個格子的四條邊被占滿四條邊被占滿時，該格子便被最后一個占邊者所俘獲； 4）俘獲格子后可以并必須再連一條邊； 5）格子全部圍成后，博弈結(jié)束。勝負(fù)占領(lǐng)格子較多的一方為獲勝方。11蘇拉卡爾塔（ Surakarta）12“蘇拉卡爾塔”規(guī)則棋盤棋子1）橫豎各6條邊構(gòu)成正方形棋盤，36個交叉點(diǎn)為棋位，各邊由8段圓弧連接，通常用2種不同顏色表示。2）紅黑雙方各12枚棋子。初始狀態(tài)棋子各方底線排成2排。玩法 1）雙方輪流走棋，每次走動一

5、枚棋子； 2）除了吃子之外，每枚棋子只能沿著垂直或?qū)欠较蜃邉右桓?，只能走向空位?3）吃對方子時必須經(jīng)過至少一個完整的弧線。勝負(fù)吃掉所有對方棋子一方獲勝。13亞馬遜亞馬遜 棋盤表示：棋盤表示：1010方陣方陣 棋子：黑白各四個皇后棋子：黑白各四個皇后 占格棋子（可用圍棋黑占格棋子（可用圍棋黑棋子）棋子）80個，表示路障個，表示路障14“亞馬遜亞馬遜”規(guī)則規(guī)則1. 棋盤棋子棋盤棋子1）棋盤是由深淺兩色間隔排列的）棋盤是由深淺兩色間隔排列的100個小方格組成的正方形。個小方格組成的正方形。2）雙方各有）雙方各有4個（國際象棋）個（國際象棋）“皇后皇后” 棋子，初始棋位如圖所示。棋子，初始棋位如圖

6、所示。2. 棋子走法棋子走法 1）雙方著法均由兩部分構(gòu)成：先走棋，再）雙方著法均由兩部分構(gòu)成：先走棋，再 “放箭放箭”。雙方輪流走棋并。雙方輪流走棋并放箭（設(shè)障），但不吃子。放箭（設(shè)障），但不吃子。 2）走棋：按照國際象棋）走棋：按照國際象棋 “皇后皇后”的走法，即可以走到橫向、豎向和斜的走法，即可以走到橫向、豎向和斜向的任何空棋位。此棋位稱之為向的任何空棋位。此棋位稱之為“到達(dá)棋位到達(dá)棋位”； 3）放箭（設(shè)障）：從）放箭（設(shè)障）：從“到達(dá)棋位到達(dá)棋位”向向“皇后皇后”可行的路徑上的任一棋可行的路徑上的任一棋位放置一個永久性障礙物?？梢栽谠擖c(diǎn)放置一枚黑色的圍棋子，任何棋位放置一個永久性障礙物。

7、可以在該點(diǎn)放置一枚黑色的圍棋子，任何棋子都不可以越過。子都不可以越過。3. 勝負(fù)勝負(fù)結(jié)束標(biāo)志為一方?jīng)]有棋子可以移動。最后可以走動棋子的一方獲勝。結(jié)束標(biāo)志為一方?jīng)]有棋子可以移動。最后可以走動棋子的一方獲勝。 考慮到白方的先手優(yōu)勢，一般允許黑方有考慮到白方的先手優(yōu)勢，一般允許黑方有n次次pass（不走棋）（不走棋）15走棋與放箭走棋與放箭16幻影圍棋幻影圍棋 幻影圍棋是一項(xiàng)歐洲的棋類游戲，因?yàn)橄缕逡?guī)則是基于幻影圍棋是一項(xiàng)歐洲的棋類游戲，因?yàn)橄缕逡?guī)則是基于圍棋，但又是圍棋，但又是在圍棋的基礎(chǔ)上加入了信息不完全的限在圍棋的基礎(chǔ)上加入了信息不完全的限制制看不到對方的落子，看不到對方的落子，故名幻影圍棋。

8、故名幻影圍棋。 棋盤：棋盤：99圍棋的棋盤。圍棋的棋盤。 棋子：黑白兩種圍棋棋子。棋子：黑白兩種圍棋棋子。 實(shí)際上有實(shí)際上有3個棋盤，黑方棋盤，白方棋盤，裁判棋盤。個棋盤，黑方棋盤，白方棋盤，裁判棋盤。 本方只清楚自己的落子情況，對于對方落子情況只能判本方只清楚自己的落子情況，對于對方落子情況只能判斷和猜測。裁判的棋盤才給出真正的棋局。斷和猜測。裁判的棋盤才給出真正的棋局。1718幻影圍棋棋規(guī)幻影圍棋棋規(guī)黑白雙方輪流落子，黑白雙方輪流落子，落子的基本規(guī)則與圍棋一致，其中氣、禁招等落子的基本規(guī)則與圍棋一致，其中氣、禁招等概念都相同；概念都相同；幻影圍棋中加入了信息隱藏的概念幻影圍棋中加入了信息隱

9、藏的概念在下棋時，雙方都無法看到在下棋時，雙方都無法看到對手棋盤上的落子，形成兩個不完備信息的棋盤，完備信息的對弈對手棋盤上的落子，形成兩個不完備信息的棋盤，完備信息的對弈棋盤是由雙方的棋盤取并集而成；棋盤是由雙方的棋盤取并集而成；由于信息隱藏，就需要一個中間裁判。裁判可以看到雙方棋盤，也由于信息隱藏，就需要一個中間裁判。裁判可以看到雙方棋盤，也就是說，就是說，從裁判角度所看到的是一個完備信息的從裁判角度所看到的是一個完備信息的99圍棋棋盤，并圍棋棋盤，并且根據(jù)圍棋規(guī)則判斷雙方落子是否合法，如果合法的話返回且根據(jù)圍棋規(guī)則判斷雙方落子是否合法，如果合法的話返回legal，若不合法則返回若不合法則

10、返回illegal；當(dāng)有一方落子后出現(xiàn)當(dāng)有一方落子后出現(xiàn)提子提子情況時，裁判會向雙方返回提子數(shù)目與位情況時，裁判會向雙方返回提子數(shù)目與位置信息，雙方同時更改棋面；置信息，雙方同時更改棋面；當(dāng)一方所有落子都返回當(dāng)一方所有落子都返回illegal時即可判斷該方時即可判斷該方PASS；直至雙方都無法再落子，即雙方都返回直至雙方都無法再落子，即雙方都返回PASS，此時由裁判根據(jù)所占，此時由裁判根據(jù)所占地域多少判定勝負(fù)。地域多少判定勝負(fù)。 19一盤人機(jī)對弈的棋譜一盤人機(jī)對弈的棋譜摘自：摘自：Tristan Cazenave A Phantom Go Program黑方（黑方（B）：計(jì)算機(jī)程序，白方（）：

11、計(jì)算機(jī)程序，白方（W）：幻影圍棋選手）：幻影圍棋選手2030手后的裁判棋盤手后的裁判棋盤30手后的黑棋棋盤手后的黑棋棋盤摘自：摘自：Tristan Cazenave A Phantom Go Program21最終棋局最終棋局 領(lǐng)地已經(jīng)分明，沒有繼續(xù)落領(lǐng)地已經(jīng)分明，沒有繼續(xù)落子的必要了，雙方子的必要了，雙方pass 黑先手，落黑先手，落32子；白后手，子；白后手，落落30子，其中子，其中2子被提出子被提出（H8, J7） 白棋獲勝，白棋獲勝，49:32 白棋策略：先將棋盤分為左白棋策略：先將棋盤分為左右兩部分，做活左半部分，右兩部分，做活左半部分，確保優(yōu)勢到最后。確保優(yōu)勢到最后。22在游戲軟件的編