孔明棋

◎peaceful

摘要

孔明棋是屬於一個人就可以玩的遊戲，它是由三十三個棋子排成井字型盤面，一般流傳的玩法是先取去中央的那個棋子，便可以展開遊戲。遊戲時，是將棋子跳過鄰近的棋子，到達一個旁邊空著的位置，被跳過的棋子則從棋盤上取開；跳的路徑可以前、後、左、右，但不可對角跳，直到剩下最後的一顆棋子，遊戲便結束了。這是一種流傳很廣的益智遊戲，也有很多種變形的棋盤擺法，本文主要是在應用電腦，來求出各種盤面的解，用以驗證，這個自古流傳自今的遊戲，是不是有解，如果有又有多少解，除此之外，推廣這個問題，並試驗看看，各種可能的盤面是否有解，希望藉由解孔明棋的演算方法發展，能對演算法的發展有所貢獻。

◎peaceful

序論

孔明棋的介紹


孔明棋，也有人叫它跳彈珠，或者叫它「Pegged」。關於孔明棋的流傳，有許多的傳說，有人說是三國時代孔明所發明的益智棋，失傳後輾轉流傳至日本、歐美，成為外國普及的益智遊戲。另外也有一種說法，說它真正的名字叫作十字棋，據傳是發明於法國，是一個被囚的法國貴族，在獄中為了打發時光，而想出來的。後來在十八世紀末期傳至英國，才漸漸流行至世界各地。

不論它的流傳經過是如何，這種遊戲它的魅力在於，雖然玩法簡單，但是卻是變化無窮。大致上就是有三十三個格子，以及三十二顆棋子，擺法如下：（「●」：表示棋子，「．」：表示空格）



最普遍的玩法就是棋子得跳過一顆旁邊的棋子到一個空格上，被跳過的那顆棋子就必須從棋盤上取開，跳的路徑可以往左、右、前、後，但是不能夠對角跳，最後讓它剩下一顆棋子（如果能夠讓這顆棋子回到最中央，那當然是更加的厲害囉！），若是最後留下許多動彈不得的棋子，那當然是還得再加油囉！



左邊盤面這顆棋子往下跳過一顆棋子到中央，被跳過的棋子則取走 ，變成右邊盤面的情形。因此每走一步，則會減少一顆棋子。



如果出現了這種情形，因為棋盤中的二顆棋子，因為不能互相跳越，所以至此遊戲就結束了，已經不能再玩下去了。

除了這種最常見的起始盤面擺法之外，還有其它種流傳的擺法，例如：



還有一種玩法也是一樣的遊戲，但是棋盤型狀是呈三角型的，而拿起來的第一顆棋子位置也可以隨意變化的，如下：



以上這些都是廣為流傳的遊戲，這種遊戲的魅力在於，玩法非常的簡單，但是其中變化卻是數不盡的，解法更是不只一種，所以不論其形式如何變化，總是能帶給人們無窮的樂趣。
由於其它種排法都是孔明棋的變形，所以我們在研究的時候，就專注於孔明棋上面，並推廣孔明棋的問題，想找出是否任意空一格，而不只是研究空在中央的時候，因為若只是空在中央那一格，用暴力法也可以很快找到答案，但是當我們把問題推廣之後，便需要應用一些演算方法，才能夠解決，也希望藉由問題的推廣，讓這個演算法能夠適用更多任何類似棋類問題的解決。

◎peaceful

人類下孔明棋和電腦下棋的差別

        基本上人類在玩這類遊戲的時候，多半是依據直覺，或者依據著經驗法則，會有一些策略來決定如何下棋，例如有人會決定要把棋子都儘量的往中間跳、也有人會依照著自己的喜好順序來跳，不論如何，大多是以隨機的方式來決定如何走下一步的。

         但是當用電腦來處理這種問題是，就不會用這種隨機的方式來作，而是會以更有系統的方法找出可能的下一步，然後嚐試著走過這些可能的路徑，去找到最後的解答，由於電腦可以準確並大量記憶的特性，所以我們可以讓電腦記憶走過的路徑，所以，當電腦走到無法再走下去的情況時，可以退回到之前的盤面，改下另一種可能的走法，而繼續嚐試找出解答來。當然，電腦在選擇可能的下一步時，也可以有一些策略來判斷，要嚐試哪一步才可以比較快找到解答。

電腦解題所遇到的困難

          由於孔明棋的盤面有33格，每一格可分為有棋子和沒有棋子二種可能，因此，所有可能的盤面組合，高達233，相當於有80億種以上的盤面組合，由此可以想見其盤面變化之多。所以，要是只用暴力法去展開這整個樹來求解，而每走一步會少一顆棋子，總共32顆棋子需要31步才能求得解答，也就是說，這棵樹最深會到31層，每一層又可能會有很多條分枝，由此可以想見這棵樹的龐大。當然，這樹中間是有很多重覆的節點，是表示同樣的盤面，所以，我們努力的方向就是在於要如何減少經過這些重覆的節點，來減少搜尋的空間與時間。

         假設每一種盤面用一個bit來表示，那233種盤面組合就得用233 bits，相當於1GB的空間來紀錄。因此在應用上我們使用了硬碟來記錄走過並且確定展開下去會無解的盤面，而利用Hashing的方法，把每個盤面對應到一個bit，但是，因為硬碟大量的讀寫動作，所以造成在執行時的速度變慢。為了解決這個問題我們應用了一些策略。


         同時，因為它有對稱關係，所以我們每一種盤面，經過旋轉和翻轉的組合，相當於有八種盤面，因此，我們每經過一個盤面，相當於經過了八個盤面。同樣的道理，在解各種盤面的時候，也可以應用這種對稱的關係，來減少需要解的盤面。


左邊這個盤面，經過順時鐘方向90度旋轉之後，變成右邊這種盤面，在本研究中，我們可以把這二種盤面視為相同的盤面。



左邊的盤面經過翻轉（以Y軸對稱翻轉）之後，變成右邊的盤面，在本研究中，我們也把這二種盤面視為相同的盤面。

         而在另外一方面，因為在每次找到一個盤面確定是無解時要把這個盤面經過Hashing的動作紀錄起來，而在每次展開到一個新的盤面的時候，我們要從這個Hash Table裡面找出相對應的bit，以確定這個盤面是否為無解的盤面，以決定要不要繼續就這個盤面再展開下去，用這種方法我們可以減少搜尋的空間。但是相對的我們就會因為這些大量的硬碟存取動作，而增加了許多搜尋時間，為了要減少硬碟在Hashing時的讀寫動作，所以我們用了一些演算方法，判斷盤面是不是曾經走過，而不用實際展開。（實際展開的時候，就會去讀寫硬碟裡面的紀錄看看是否曾經展開過這個節點。



          當有這種情形的時候，雖然第二步的走法不一樣，但是到了第三步，仍然會變成相同旳盤面，所以我們認為第二步的二種走法為互相獨立的，哪一顆棋子先走，並不影響之後的結果，因此我們在展開樹的時候，要把這種走法去除，只留下一種，以減少搜尋時間。

         以此推廣，可能中間有很多步走法不一樣，但是最後到了某一步的盤面會一樣，我們也可以把這種相關的走法去除。

◎peaceful

電腦解題之演算方法

         我們解決這個孔明棋這個問題的時候，並不特別限定起始盤面，而是希望不論任何盤面，都可以在最短時間之內求得。

         主要的演算法是用深入優先搜尋（DFS，Depth First Search）的方法，將一個盤面有可能的下一步走法全部找出來，然後用深入優先搜尋法，去展開棋盤的樹，一直展開到找到剩下一顆棋子的時候（表示找到解了），便停止繼續搜尋。除此之外，利用電腦的記憶優勢，我們配合應用去除互相獨立的走法（如前文所介紹的），以及使用Hashing的方式，把走過無解的盤面，紀錄下來，如此每次應用這個檔案，就可以不用再費時展開那些會展開到無解的盤面，並且隨著每次的紀錄，到後來我們便不會再犯相同的錯誤，也就是說我們不會再第二次試著展開那些將會展開至無解盤面的棋盤組合，也就會讓我們每次求解的速度愈來愈快。這就是說，我們可以讓電腦在解孔明棋時，愈來愈「聰明」，並且我們可以預期的是，在將所有的盤面走過的情況之下，電腦要解孔明棋的任意盤面，那都可以在一眨眼的時間之內就解出來。我們的演算法如下：

1.    先選定好起始盤面。從無解盤面紀錄中判斷這個盤面是不是將會展到無解的盤面。如果是無解的盤面，則由堆疊中找出上一個盤面當作起始盤面。如果是可能有解的盤面，則繼續下一步。
2.    找出這個盤面所有可能的下一步走法，並紀錄起來，繼續第3步驟。如果找不到可能的下一步走法，而且這個盤面剩下的棋子數目多於一顆的話，則由堆疊中找出上一個盤面當作起始盤面，並再回到第1步驟。若是這個盤面只剩下一顆棋子的話，則表示找到解了，可以跳出程式。
3.    選定其中一種走法往下展開，並把現在這個盤面以及其它可能的走法都推入堆疊，把現在這個盤面當作起始盤面，回到第1步驟。若是所有的走法都已經走過了，則由堆疊中找出上一個盤面當作起始盤面。回到第1步驟。

◎peaceful

資料來源


http://www2.kuas.edu.tw/prof/cjh/2003puzzle/subject/index11.htm


==========================

心得感想：

　　孔明棋其實分成了很多種，大家還記得嗎？改版前鐵傲遊戲裡有個藉由將子
碰上對方的子好變成自己的子的遊戲，最後再看子數目的多寡而決定勝負，那就
是其中的一種。

　　這裡介紹的，是傳統的孔明棋，形式上變花多端，玩不膩可能（？）