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