桌游「步步為營」的演算法設計有沒有好的策略？

01-23

網路上常常能看到五子棋、中國象棋、國際象棋等等棋類的演算法。
我一直對這類演算法很有興趣，有一次看到一個桌游，加拿大的遊戲，叫Quoridor
資深桌遊玩家應該都知道這個棋類遊戲。
這個遊戲的演算法設計非常的有意思，複雜度高於五子棋，並不亞於象棋。
遊戲的規則我介紹一下。一個9X9或者7X7的棋盤（用7X7主要是降低演算法複雜度）

一方位於棋盤上方中間格子，一方位於棋盤下方的中間格子
遊戲的目的就是將己方的棋子，走到對方出發的那一行。
比如你是從底部出發，你就是走到最上一行（只要走到那一行即可，不管是這行的哪一格）
以下是規則：
1、行棋過程中，雙方各執10塊擋板，擋板用於阻攔對手前進。
擋板有橫有豎，阻擋時的唯一規則就是，你不能圍個圈把對方堵死。
2、每一個回合，玩家都可以控制棋子移動（可以向上下左右四個方向移動，每次移動一格，只要移動的方向上沒有擋板）或放置擋板（與行棋二者擇其一，擋板也只能一回合放置一塊）。擋板橫跨（或豎跨）兩個格子，放下後即無法收回。
3、如果你正在移動棋子，並且棋子下一步正好是對方棋子的位置，則可以再走一步（只能行棋不能放置擋板）
多說無益，上圖如下（這是我用這個遊戲寫的一個手機遊戲，叫貓狗大作戰，360就能你下，地址就不貼了，免得有廣告嫌疑）

仔細研究後，我嘗試寫了該遊戲的演算法。
這個遊戲演算法有兩個難處，也就是我的問題所在：
1、尋路。這個尋路和普通尋路問題不同，它的目標點位可能是一個或多個。整行都可以是目標點位，因此比普通的單點尋路計算時間要長。我現在用的是一個變形的A*演算法，但是效率並不太高。
2、棋盤局面的評估函數
這個棋局不能簡單的用雙方到達終點的距離作為評估函數。因為這裡有一個擋板數量的概念。也許你目前離目標更近，但由於你的擋板數量不如對方，也許在後續的局面里。你仍會陷入被動甚至失去比賽。
我目前的評估函數是稍微做了點判定，把到終點的距離和擋板數量分別乘以參數並相加，但是這個評估函數容易出錯。是否有比較好的評估函數？
3、局面深度
即使用了剪枝。這個遊戲的計算量仍然非常龐大，嚴格來說，很遠一個地方的擋板，有可能就是在未來能改變棋局，因此，該考慮的擋板一個都不能少。我自己測試，局面深度在5層的時候時間差不多能忍受，7層就有點太久了。但是7層對於電腦來說，它只不過才思考了3步而已。我自己目前用了一些辦法，讓電腦判定局面，有些局面會思考20層，大部分局面只思考3層來改善這個情況，但由於第二條評估函數設計問題，整個表現並不理想
研究這個純屬興趣，目前我有已經做好的遊戲，水平大概是這個棋的初級玩家的樣子。如果有研究興趣的，請PM我，我可以將遊戲發給您。
拍磚引玉，歡迎大家討論。

我覺得大致演算法框架應該差不多就是這樣了……A*尋路，設計一個估價函數，利用估價函數做mini-max。

判定局面來增減mini-max層數的方法不知道是出於什麼考慮？以我的理解，一定是在有限的時間內思考盡量多的層數更有利。如果需要優化時間，在減少思考層數之前，也可以考慮每一層內進行剪枝，效果應該也比單純減少層數更好。

對於估價函數的設計，考慮到對方會放擋板阻斷你的一些路徑，可以考慮使用當前點到終點的k短路長度。k的確定可以測試一個比較好的值，也可以根據雙方剩餘的擋板數調整。

沒有嘗試過，也沒什麼時間考慮細節，但是根據我的直覺，這應該是一個可行的估價函數。歡迎嘗試後告訴我結果:)

晚上睡不著，來答一發吧

不知道過了這麼久題主是否還有興趣，不過我先說一下我的看法。

相比較傳統的Minmax架構的搜索，我更推薦使用現在圍棋使用的MCTS架構的搜索。好處有這樣幾個：不需要評估函數；對於這樣分支大的遊戲擁有更好的效果；支持並行。

Wiki:MCTS

https://en.wikipedia.org/wiki/Monte_Carlo_tree_search

如果使用純粹的MCTS，效果並不一定會比較出彩。那麼這時候可以考慮代入剪枝，例如可以將題主你對於遊戲的一些理解代入，在每次生成所有可行的走法時直接進行剪枝，或者通過與評估函數結合進行剪枝。

從我個人的理解上來看，這個遊戲可能更適合使用MCTS框架來製作AI。效果應該會顯著高於Minmax

有些規則不大懂

1.能否橫向移動或後退？

2.每一回合的步驟如何？比如先走還是先放板，板是否會干擾自己移動。

3.板子的類型和長度？

4.放下板子後還可以取回嗎

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

思路寫在這裡

由於一塊板子可能大幅度改變當前局面，所以起碼要往前推算兩步，也就是考慮對手放板子的情況，才有一定程度的預測能力。

至於啟發函數：

己方優勢值=【棋子到對方底線的所有路徑的總長度】

無環指的是當前路徑中走過一次的格子不能再走，但允許繞路而不直走。當然，兩條路徑的話彼此之間可以有重合。
這裡的路徑不是指最短路，所以要考慮往回走一段然後繞一圈再走回正道的情況。
大概只能DFS。

這個思路的理由：

如果到目的地的路線像高速公路一樣一直都很寬闊，那麼路線會比較多；而如果像葫蘆一樣中間有一段羊腸小道，路線就比較少（很多路線都彙集到小道去了）。但羊腸小道意味著一塊板子就可以堵死。所以可行的路線越多，就說明對方越難堵死，你就越佔優勢。
對於「只有一條路所以對方堵死我就違反規則」的情況，對方雖然不能堵死那條小道，但由於知道你只能往那邊走，對方可以在你走到那個缺口之前用塔防遊戲的戰術盡量讓你繞遠路。

這裡沒考慮剩餘板子數，不過可以用優勢值 * 剩餘板子數的方式計算。

新買的，還不怎麼會玩，想上知乎看看有沒有更全的說明

帶的遊戲說明

維基百科

https://en.wikipedia.org/wiki/Quoridor

下面就有

Papers on implementing Quoridor-playing algorithms

我自己來回答下

我現在設計的這個步步為營的遊戲。

正常人完全沒法獲勝。

感覺沒有演算法更新的動力。