益智遊戲「斜方棋」之電腦解法及分析

劉哲志、林順喜

國立臺灣師範大學

資訊教育系

 

摘要

    斜方棋是一個兩人對奕的有趣遊戲,本文嘗試利用電腦來分析這個遊戲是否存在必贏的策略?先下手的一方是否有占便宜?是否有達到和棋的走法?經過我們的分析,發現此遊戲與大部份遊戲不同的是,只要依照正確的策略下棋,則後手必勝。最後我們將研究的成果設計成程式,放在網頁上供大家下載與我們的程式下棋。

緒論

1. 四子棋介紹:

    這是在民國八十一年七月三十一日的中國時報上看到的一個小遊戲,當天的報紙一共介紹了直棋、梅花棋、蛇梯棋、斜方棋、四子棋、孔明棋、江山變色棋、洋棋、西洋雙陸棋、雙井棋等十棋遊戲。其中「四子棋」可以說是比較複雜的圈叉遊戲,玩法如下:

<圖一> 斜方棋的棋盤,共有十三個下子到處

   準備一個棋盤,棋盤如圖一所示,每個線與線的交點即為下子處,共十三個,由甲乙兩方分持黑白各五子,由原來空的棋盤,輪流下子在空的點上,各下完五子之後,再輪流移動,移動的方式為選擇我方棋子一顆,再移至相鄰的空點上,目標是用我方棋子擋住對方棋子,使其無法移動,便算獲勝,如圖二所示,若現在輪到黑棋移動,則每個棋子旁邊皆有其它棋子,無路可走,因此白棋獲勝。

<圖二>輪到黑棋移動,但相鄰的點都被擋住,因此輸了

2.人腦玩此遊戲和電腦玩有何不同之處?

以人腦來玩這樣的對奕遊戲,除了要考慮自己的攻守策略外,還要考慮對方的可能採取的攻守策略,但是人常常會考慮得不夠周延,對於重複的盤面也不能有效的記錄,所以在心裡推算幾個盤面後,自己也搞不清之前考慮過哪些況狀,很難歸納出有效的下棋策略,常常都是從不斷的練習的經驗,來減少自己犯錯的機會,但是也不能保證自己一定不會再出錯。

以人腦玩這個遊戲,必須先輪流下五步,再開始正式對奕,第一次下棋由於推算的困難,常是隨便下子,有了幾盤棋的經驗後,便會採取所謂的「經驗法則」,從不斷的下棋經驗中去找自己最佳的下棋策略,但是經驗未必代表就是最佳解,可能只是還沒失敗過而已。

如果我們要讓電腦來解這樣的對奕遊戲,和人腦最大的不同,就是電腦能有效地記錄所走過的盤面,並且能從展開Game-tree的過程中窮舉所有的盤面,及尋找最佳的對應盤面,這樣便可以在可能贏的時候一定得到勝利,不過這樣的假設前提是要有一個好的方法去記錄盤面及分析盤面,否則只是浪費大量的記憶體及時間。

電腦解題之演算法

    這個遊戲用電腦解題可能有許多種方法,一種方法是將各個點給定一個weight,weight最高的為下子的目標,不同的狀況可能有不同的weight,再從不斷的試驗修正,找出最佳的weight,但這不能保證必勝;一個比較可能的方法是從開始就展開Game-tree,用遞迴的方法一直展開到最底層,即由第一步到各下五子,到分出勝負,再由最後的勝負,一層層往回填,如果最底層是負,則它的上一層(parent node)應該走到這個盤面,因此這個上一層應該是必勝,而上上一層就應該避免走到上一層的盤面,而選擇其它的盤面,但若上上一層發現它的下一層都是必勝,那麼上上一層為必負(參考圖三),如此一直往上一層就可以知道最好的解法是如何。

<圖三>左側的上層盤面雖然其下層盤面有各種結果,但可選擇必負的那個使對方輸,所以應為必勝;中間則下一步無法使對方輸,所以選擇和棋;右方則為必負(除非對方走錯)

在這裡我們使用和上述第二種很類似的解法。首先我們先解決棋盤上有十顆棋子的情況,知道十顆棋子時每種盤面的勝負後,就可以依照上述方法,很快的知道已有九顆棋子時各盤面的勝負,然後依序往前可知道已有8∼1顆棋的的勝負況狀。

由於必須知道哪些盤面是我們已經走過的盤面,還有到了某一個盤面它最好的下一步,因此必須有一個方法去記錄,我們首先將盤面的十三個點編號(順序無所謂),將盤面上空的點、我方棋子和對方棋子分別編號成0、1和2,因此在盤面上有十顆子時,依照字典順序的第一種情況是{0001111122222},最後一種情況是{2222211111000},不考慮對稱的情況時,一共有13!/(3! 5! 5!)=72072種不同的盤面,每一點都要記錄是否走過和勝負情況,這需要3bits,因此至少需要72072*3 bits,每一個盤面的下一步需要知道從哪一個點走到哪一個,個點都要能表示1∼13,要4 bits,因此至少還需要72072*(4+4) bits=72072bytes來記錄下一步;而有九顆棋時,盤面一共有13!/(4! 4! 5!)=90090種,需要90090*3 bits,記錄下一步只要知道下在哪一個點,需要90090*4 bits=45045bytes,至於8到1顆棋子的情況則依照9顆棋子的情況類推。

         在展開已有十顆棋子時的Game-tree,會遇到一個盤面的下一個盤面有「已經走過但還不知道勝負」的情形,這是因為雙方在對奕時可能在分出勝負前又走到重複的盤面,這時如果它的下一個盤面有一個是負的情況,那麼這一個盤面還是勝,其它況狀則暫時當做「未知勝負」來處理(圖四),因此在走過已經有十顆子的所有盤面後,還有許多這種未知勝負的情況,我們必須將這些盤面都不斷重新展開,直到已經沒有盤面能夠再分出勝負,剩下的盤面為「和」的盤面,因為有這樣重新判斷的工作,所以我們要在已有十顆棋子時就開始展開Game-tree,而不從下第一顆子就展開Game-tree。

<圖四>下一個盤面只有「勝」「和」和「未知」三種情況時,將無法判斷勝負。

三.程式執行結與分析

         我們程式的執行環境,是在Pentium 120的主機,64MB RAM,Windows95為作業系統下,程式語言使用Borland C++ Builder,依照上述的演算法寫成程式,執行的時間接近一分鐘,以下是執行的結果:

已有棋子數

盤面數

10

72072

38608

32436

1028

9

90090

86620

3138

332

8

90090

10922

79038

130

7

60060

59334

694

32

6

34320

1704

32616

0

5

12870

12870

0

0

4

4290

0

4290

0

3

858

858

0

0

2

156

0

156

0

1

13

13

0

0

0

13

0

13

0

由結果我們可以現,在盤面上已有10 顆棋時,勝負情況是差不多的,而盤面上有九顆棋時,由於會考慮下一步必須走到「負」的情況,因此勝的情況明顯多了很多,一直往回推到剩下五顆棋時,可以發現下一步一定可以走到使對方負的情況,所以只要是後手,前面不管如何下,只要在第六子及後面都下在正確的地方,就可以保證一定是必勝。

我們將結果做成遊戲,程式可以到http://alg.ice.ntnu.edu.tw下載,可以和電腦進行對奕,

四.結論

        後手如果在第三次下子及之後都能使用適當的策略,那麼不論先前兩子如何下,都能必勝。

        這次我們雖然證明了後手必勝及找出必勝的走法,對於先手的每一個盤面也都有適當的建議,但並未歸納出人和人在下棋時是否應該依照什麼樣的策略才能增加勝的機會,這是以後可以努力的目標。

 

本網站是由國立高雄應用科技大學(K.U.A.S)機械工程系邱錦華老師
及其智慧幾何專題製作小組所共製而成.維護人員Golden