點點連格棋機器博弈系統(tǒng)關鍵技術分析

《點點連格棋機器博弈系統(tǒng)關鍵技術分析》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第12章點點連格棋機器博弈系統(tǒng)關鍵技術分析連蓮徐心和東北大學機器博弈研究室2010.01東北大學機器博弈研究室東北大學機器博弈研究室12.1.1點點連格棋簡介點格棋（3，3）東北大學機器博弈研究室DotsandBoxes(點格棋)東北大學機器博弈研究室點格棋（6，6）東北大學機器博弈研究室“點點連格棋”規(guī)則棋盤由6×6個點構成方陣，可以連成5×5個小方格子。玩法1）雙方輪流將鄰近兩點連成邊，不可越點，不可重邊，不連對角線；2）邊不歸屬于任一方，只對格子判斷歸屬；3）每個格子的四條邊被占滿時，該格子便被最后一個占邊者所俘獲；4）俘獲格子后可以并必須再連一條邊；5）格子全部圍成后，博弈結束。勝負

2、占領格子較多的一方為獲勝方。東北大學機器博弈研究室棋盤：3×3，5×5，6×6東北大學機器博弈研究室點數(shù)3×35×56×6n×n點數(shù)92536格數(shù)2×24×45×5(n-1)×(n-1)格數(shù)41625邊數(shù)2×2×32×4×52×5×62×(n-1)×n邊數(shù)124060一般比賽采用6×6，不會產生平局東北大學機器博弈研究室點格棋棋局示意東北大學機器博弈研究室點點連格棋終止局面E和D分別代表對弈雙方。雙方均在自己捕獲的格子內做己方的標記。標記E的一方占格10個，標記D的一方占格15個，獲勝方為標記D的一方。東北大學機器博弈研究室點點連格棋殘局假定游戲G是一個點點連格游戲，b是游戲G中的一個格子。參

3、加對弈的一方開始走棋到走棋結束而換做另一方開始，我們稱之為一輪（Turn），一輪中，每走一次棋，稱之為一步（Move）。東北大學機器博弈研究室圖形要素與圖屬性點格棋的棋局是由各種各樣的圖形組成，于是可以定義各種棋局元素。棋局元素包括：死格、C型格、長鏈、短鏈、環(huán)、雙交等。格的屬性包括：自由度、鄰居、開闊度等。東北大學機器博弈研究室死格，C型格死格(deadbox)：自由度為1的格子C型格(Cbox)：由三個邊構成的格子。大C型格C型格是特殊的死格東北大學機器博弈研究室自由度，鄰居，開闊度自由度(liberties)：構成格子尚缺的邊數(shù)鄰居(neighbor)：公用邊未被占領的相鄰(adjace

4、nt)的格子開闊度(openess)=自由度-鄰居個數(shù)東北大學機器博弈研究室長鏈，短鏈鏈(chain)：彼此相鄰的多個自由度為2的一串格子短鏈(shortchain)：2個格子構成的鏈長鏈(longchain)：3個及3個以上格子構成的鏈東北大學機器博弈研究室子格，子樹子格(subbox)：接續(xù)捕獲的格子。子樹(subtree)：接續(xù)捕獲格子的集合。東北大學機器博弈研究室環(huán)環(huán)(circle)：首尾相接的長鏈。多由4格構成。東北大學機器博弈研究室雙交雙交(doublecross)：兩個交互連接的C型格東北大學機器博弈研究室相關定義定義1格子b的自由度（Liberties）等于b未被占領的邊的個數(shù)

5、。定義2格子b被稱為C型，當且僅當b的自由度為1。定義3格子b被稱為死格（DeadBox），當且僅當b可由當前對弈方捕獲。也就是說當且僅當參加對弈的某一方當前存在一系列著法（Moves)，其中每個著法都捕獲一個格子，這一系列格子都被稱為死格。如果畫個圖，每個死格作為一個節(jié)點，相鄰的死格用一條邊連接，則所有可貫通的節(jié)點構成了一個死樹（DeadTree）。特殊的，一個沒有死鄰居的C型格也是一個死樹。所有的死樹構成了一個死森林（DeadForest）。東北大學機器博弈研究室C型格、死格與死樹1號和16號格子為C型格，它們的自由度為1；1、5、10、9、8、7、12、17、16號格子均是死格，1號格為

6、一個死樹，5、10、9、8、7、12、17、16號格子構成了另一個死樹。東北大學機器博弈研究室貪婪算法（GreedyAlgorithm）定義4一組著法被稱為貪婪算法（GreedyAlgorithm），當其中的每個著法都捕獲一個C型格，進而該組著法最終捕獲所有的死格。所以，如前圖所示的局面，如果當前走棋方選擇一次性占領全部死格子，即1號和16、17、12、7、8、9、10、5號格子，那么這個策略就是貪婪算法。定義5坐標分別為（i，j）和（k，l）的兩個格子稱為是相鄰的（Adjacent），當且僅當，并且二者的公共邊（CommonEdge）未被占領。相鄰的兩個格子互稱為鄰居，當一個格子的鄰居是死格

7、時，該鄰居稱為死鄰居。前例中，19和25號格子都是24號格子的鄰居。而7和9號格子都是8號格子的死鄰居。東北大學機器博弈研究室相關定義定義6死格b的開闊度（Openness）大小等于b的自由度減去b的死鄰居的個數(shù)，即：O(b)=Lib(b)-DN(b)其中，O(b)代表開闊度，Lib代表自由度，DN代表死鄰居的個數(shù)，易知O(b)的值只為0或者1。開闊度僅僅針對死格而言。定義7死格b被稱作是是開闊格