《點點連格棋機器博弈系統(tǒng)關(guān)鍵技術(shù)分析》由會員分享，可在線閱讀，更多相關(guān)《點點連格棋機器博弈系統(tǒng)關(guān)鍵技術(shù)分析（37頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,東北大學(xué)機器博弈研究室,*,第,12,章,點點連格棋機器博弈系統(tǒng)關(guān)鍵技術(shù)分析,連 蓮 徐心和,東北大學(xué)機器博弈研究室,2010.01,東北大學(xué)機器博弈研究室,東北大學(xué)機器博弈研究室,12.1.1,點點連格棋簡介,點格棋（,3,，,3,）,東北大學(xué)機器博弈研究室,Dots and Boxes(,點格棋,),東北大學(xué)機器博弈研究室,點格棋（,6,，,6,）,東北大學(xué)機器博弈研究室,“點點連格棋”規(guī)則,棋盤,由,66,個點構(gòu)成方陣，可以連成,55,個小方格子。,玩法,1,）雙方輪流將鄰近兩點連成邊，不可越點，不可重邊，不連對角線；,2,）邊
2、不歸屬于任一方，只對格子判斷歸屬；,3,）每個格子的,四條邊被占滿,時，該格子便被最后一個占邊者所俘獲；,4,）俘獲格子后可以并必須再連一條邊；,5,）格子全部圍成后，博弈結(jié)束。,勝負(fù),占領(lǐng)格子較多的一方為獲勝方。,東北大學(xué)機器博弈研究室,棋盤：,3,3,，,5,5,，,6,6,東北大學(xué)機器博弈研究室,點數(shù),3,3 5,5 6,6,n,n,點數(shù),9 25 36,格數(shù),2,2 4,4 5,5 (n-1),(,n-1),格數(shù),4 16 25,邊數(shù),2,2,3 2,4,5 2,5,6 2,(,n-1),n,邊數(shù),12 40 60,一般比賽采用,6,6,，不會產(chǎn)生平局,東北大學(xué)機器博弈研究室,點格棋棋
3、局示意,東北大學(xué)機器博弈研究室,點點連格棋終止局面,E,和,D,分別代表對弈雙方。,雙方均在自己捕獲的格子內(nèi)做己方的標(biāo)記。,標(biāo)記,E,的一方占格,10,個，標(biāo)記,D,的一方占格,15,個，獲勝方為標(biāo)記,D,的一方。,東北大學(xué)機器博弈研究室,點點連格棋殘局,假定游戲,G,是一個點點連格游戲，,b,是游戲,G,中的一個格子,。,參加對弈的一方開始走棋到走棋結(jié)束而換做另一方開始，我們稱之為,一輪（,Turn,），,一輪中，每走一次棋，稱之為,一步（,Move,）,。,東北大學(xué)機器博弈研究室,圖形要素與圖屬性,點格棋的,棋局是由各種各樣的圖形組成,，于是可以定義各種棋局元素。,棋局元素包括：死格、,C
4、,型格、長鏈、短鏈、環(huán)、雙交等。,格的屬性包括：自由度、鄰居、開闊度等。,東北大學(xué)機器博弈研究室,死格，,C,型格,死格,(,dead box),：自由度為,1,的格子,C,型格,(C box),：由三個邊構(gòu)成的格子。,大,C,型格,C,型格是特殊的死格,東北大學(xué)機器博弈研究室,自由度，鄰居，開闊度,自由度,(,liberties),：構(gòu)成格子尚缺的邊數(shù),鄰居,(neighbor),：公用邊未被,占領(lǐng)的相鄰,(adjacent),的格子,開闊度,(,openess,),=,自由度,-,鄰居個數(shù),東北大學(xué)機器博弈研究室,長鏈，短鏈,鏈,(chain),：彼此相鄰的多個自由度為,2,的一串格子,短
5、鏈,(short chain),：,2,個格子構(gòu)成的鏈,長鏈,(long chain),：,3,個及,3,個以上格子構(gòu)成的鏈,東北大學(xué)機器博弈研究室,子格，子樹,子格,(,subbox,),：接續(xù)捕獲的格子。,子樹,(,subtree,),：接續(xù)捕獲格子的集合。,東北大學(xué)機器博弈研究室,環(huán),環(huán),(circle),：首尾相接的長鏈。多由,4,格構(gòu)成。,東北大學(xué)機器博弈研究室,雙交,雙交,(,doublecross,),：兩個交互連接的,C,型格,東北大學(xué)機器博弈研究室,相關(guān)定義,定義,1,格子,b,的,自由度,（,Liberties,）等于,b,未被占領(lǐng)的邊的個數(shù)。,定義,2,格子,b,被稱為,
6、C,型,，當(dāng)且僅當(dāng),b,的自由度為,1,。,定義,3,格子,b,被稱為,死格,（,Dead Box,），當(dāng)且僅當(dāng),b,可由當(dāng)前對弈方捕獲。,也就是說當(dāng)且僅當(dāng)參加對弈的某一方當(dāng)前存在一系列著法（,Moves),，其中每個著法都捕獲一個格子，這一系列格子都被稱為死格。,如果畫個圖，每個死格作為一個節(jié)點，相鄰的死格用一條邊連接，則所有可貫通的節(jié)點構(gòu)成了一個,死樹,（,Dead Tree,）。,特殊的，一個沒有,死鄰居,的,C,型格也是一個死樹。,所有的死樹構(gòu)成了一個,死森林,（,Dead Forest,）。,東北大學(xué)機器博弈研究室,C,型格、死格與死樹,1,號和,16,號格子為,C,型格,，它們的自
7、由度為,1,；,1,、,5,、,10,、,9,、,8,、,7,、,12,、,17,、,16,號格子均是,死格,，,1,號格為一個,死樹,，,5,、,10,、,9,、,8,、,7,、,12,、,17,、,16,號格子構(gòu)成了另一個,死樹,。,東北大學(xué)機器博弈研究室,貪婪算法（,Greedy Algorithm,）,定義,4,一組著法被稱為貪婪算法（,Greedy Algorithm,），當(dāng)其中的每個著法都捕獲一個,C,型格，進而該組著法最終捕獲所有的死格。,所以，如前圖所示的局面，如果當(dāng)前走棋方選擇一次性占領(lǐng)全部死格子，即,1,號和,16,、,17,、,12,、,7,、,8,、,9,、,10,、,
8、5,號格子，那么這個策略就是貪婪算法。,定義,5,坐標(biāo)分別為（,i,，,j,）和（,k,，,l,）的兩個格子稱為是,相鄰的,（,Adjacent,），當(dāng)且僅當(dāng)，并且二者的公共邊（,Common Edge,）未被占領(lǐng)。,相鄰的兩個格子互稱為鄰居，當(dāng)一個格子的鄰居是死格時，該鄰居稱為,死鄰居,。,前例中，,19,和,25,號格子都是,24,號格子的鄰居。而,7,和,9,號格子都是,8,號格子的死鄰居。,東北大學(xué)機器博弈研究室,相關(guān)定義,定義,6,死格,b,的,開闊度,（,Openness,）大小等于,b,的自由度減去,b,的死鄰居的個數(shù)，即：,O(,b,)=,Lib(,b,)-DN(,b,),其中
9、，,O(,b,),代表開闊度，,Lib,代表自由度，,DN,代表死鄰居的個數(shù)，易知,O(,b,),的值只為,0,或者,1,。開闊度僅僅針對死格而言。,定義,7,死格,b,被稱作是是,開闊格,，當(dāng)且僅當(dāng),O(,b,)=1,，否則稱,b,是閉合格。開闊格不與死鄰居共用的一條邊稱為,開闊邊,。,東北大學(xué)機器博弈研究室,可見,C,型格是閉合格的一個特例。根據(jù)定義,6,和定義,7,，可以得到如下結(jié)論：,結(jié)論,每條死樹只能含有一個或者兩個,C,型格，當(dāng)一條死樹只含有一個,C,型格時，可以把它看做死樹的起點，占格操作由起點開始，并且這條死樹有且僅有一個開闊格，可以看做其終點。當(dāng)一條死樹含有,2,個,C,型格
10、時，死樹中不含有開闊格。,含有開闊格的死樹叫做,開闊死樹,（,Open Dead Tree,，,OT,），不含有開闊格的死樹叫做,閉合死樹,（,Closed Dead Tree,，,CT,）。,東北大學(xué)機器博弈研究室,相關(guān)定義,東北大學(xué)機器博弈研究室,長鏈、短鏈與環(huán),21,，,22,，,23,，,18,，,13,，,14,，,15,號格子構(gòu)成一條,長鏈,，,6,，,11,號格子構(gòu)成一條,短鏈,，,19,，,20,，,24,，,25,號格子構(gòu)成一個,環(huán),。,6,和,11,號格子的兩條非公共邊占據(jù)后，就構(gòu)成了一個,2C,型,。,東北大學(xué)機器博弈研究室,12.2,點點連格棋機器博弈系統(tǒng)策略分析,一般
11、點點連格棋的對弈過程中，長鏈和環(huán)是高頻率出現(xiàn)的兩種形狀，而,對于長鏈和環(huán)的處理也是取勝的關(guān)鍵之一,。而通常，這兩種形狀的處理出現(xiàn)在殘局（,Final Phase,）階段。,開局是生成長鏈、短鏈和環(huán)的預(yù)備期，中局是著手生成這三種形狀，,而開局和中局一般不會在鏈或者環(huán)里動作，偶爾會出現(xiàn)捕獲,C,型格的情況。,長鏈的個數(shù)的奇偶性通常是決定勝負(fù)的關(guān)鍵,，如果條件足夠?qū)捤煽梢钥刂崎L鏈的條數(shù)的時候，我們必須掌握長鏈定理。,東北大學(xué)機器博弈研究室,重要定理,定理,1,：,Dots+doublecrosses,=Turns,通常情況下，最后捕獲格子的一方獲勝。,于是，對于先手而言，總換手次數(shù)為奇數(shù)時獲勝；,對
12、于后手而言，總換手次數(shù)為偶數(shù)時獲勝。,開局記一次換手。,定理,1,用以計算結(jié)束前的換手次數(shù)。,東北大學(xué)機器博弈研究室,重要定理,定理,2,（長鏈法則）：,1.,換手?jǐn)?shù)為偶數(shù)時，先手方應(yīng)力圖形成偶數(shù)條長鏈，而后手方應(yīng)力圖形成奇數(shù)條長鏈；,2.,換手?jǐn)?shù)為奇數(shù)時，先手方應(yīng)力圖形成奇數(shù)條長鏈，而后手方應(yīng)力圖形成偶數(shù)條長鏈。,東北大學(xué)機器博弈研究室,重要公式,可能形成,雙交,數(shù)目的計算公式,doublecrosses,=longchain-1+2*circle,東北大學(xué)機器博弈研究室,長鏈定理,定理,1,無論初始棋盤的尺寸如何，總有以下式子成立：,Dots+Doublecrosses,=Turns,（,
13、1,）,其中，,Dots,指的是初始棋盤點的個數(shù)，,Doublecrosses,指的是棋局結(jié)束時，共形成的,2C,型的個數(shù)，,Turns,指的是棋局結(jié)束時，共經(jīng)歷了多少輪的走棋。,定理,2,被稱為長鏈定理，它是,Berlekamp,對定理,1,的一個推論,。,定理,2,如果棋盤共有奇數(shù)個點，則先手方應(yīng)當(dāng)形成奇數(shù)條長鏈以取勝，后手方應(yīng)形成偶數(shù)條長鏈以取勝；,若棋盤共有偶數(shù)個點，則先手方應(yīng)當(dāng)形成偶數(shù)條長鏈，后手方應(yīng)形成奇數(shù)條長鏈以取勝。,東北大學(xué)機器博弈研究室,引理,1,在點點連格對弈過程中，最后一輪的走棋方是強迫對手率先進入長鏈或者環(huán)中走棋的一方。,對于,66,的點點連格棋，共有,36,個點，即
14、點的個數(shù)為偶數(shù)，所以先手方應(yīng)當(dāng)極力形成偶數(shù)條長鏈，后手方應(yīng)致力于形成奇數(shù)條長鏈。,通常一條長鏈或者過多的長鏈在實際博弈中是不易形成的，故開局時，,先手方一般考慮,2,條或者,4,條長鏈的情況，而后手方可以搜索利于形成,3,條或者,5,條長鏈的著法,。,東北大學(xué)機器博弈研究室,12.3,點點連格棋機器博弈系統(tǒng)數(shù)字表示,東北大學(xué)機器博弈研究室,東北大學(xué)機器博弈研究室,著法的表示,著法是填入,水平或豎直相鄰兩點尚未連接的邊，故應(yīng)該以相鄰兩點坐標(biāo)來描述。,點陣坐標(biāo)矩陣,著法表示,需要實現(xiàn)從點陣矩陣到棋局矩陣的映射（變換）。,東北大學(xué)機器博弈研究室,棋局各階段的博弈策略,開局：棋盤劃分，板塊規(guī)劃，目標(biāo)是保證板塊的奇偶性，符合長鏈定理。,注意：每個長鏈需要兩個開口的邊界,中局：以長鏈定理為核心，讓格、短鏈及環(huán)配合,殘局：貪婪還是讓格走法的考慮。,出發(fā)點：比分差距小的葉子？,東北大學(xué)機器博弈研究室,重要著法,1,：貪婪,(greedy),走法,不放過每一個可以形成格子的著法。,只考慮眼前利益。,2,：讓格走法,(loony):,構(gòu)成,doublecross,爭取最后“收秋”，故意作成雙交，保證最后捕獲的格子多。,東北大學(xué)機器博弈研究室,在游戲軟件的編寫中,提高素質(zhì)！,讓創(chuàng)新的火花,在機器博弈中迸發(fā)！,聯(lián)系：,,http:/,,/,東北大學(xué)機器博弈研究室,
點點連格棋機器博弈系統(tǒng)關(guān)鍵技術(shù)分析
