Connect-K的良好啓發式AI

Question

我正在編寫Connect-K簡單AI（不修剪，僅限4層）。我想知道什麼是最好的啓發式這是快速計算。

東西比我有更好的：

def eval(board, player) 
    connections = 0 
    magnitude = 0 
    for x in range(0, self.boardW(board)): 
     for y in range(0, self.boardH(board)): 
      if(self.get_player(board, x, y) == player): #assuming x and y are in bounds 
       temp = 1 
       # keep checking in this direction to find the max temp can be 
       if (magnitude < temp): 
        magnitude = temp 
      if(self.get_player(board, x, y) == player): 
       connection += 1 
     ........ 
    return connection**2 + magnitude**2 

基本上，這應該與它相鄰的點返回的最大連接電路板上的任何點了，加上多少個連續的項目是在任何的8個方向的（上，下，左，右，上，左，下，左，...）

我ķ將大於4;因此我無法進行徹底的樹搜索。

Answer 1

A min-max搜索在這種情況下可能會有用，可能與簡化的MCTS相結合。基本上，更深的遞歸會讓你達到更多的遊戲結束狀態。通過分析哪個玩家在每種情況下獲勝，您可以更好地瞭解某個舉動的價值。

min-max方法對於兩個玩家之間的遊戲非常有用，並廣泛用於這類棋盤遊戲。 MCTS可能有點矯枉過正，但總體思路是交易廣泛的搜索，隨機更深入的搜索。例如，您可以隨機選擇10個分支，並使用相同的計算量具有6-7個遞歸步驟，而不是分支因子爲20，並且只有5個遞歸級別（20^5 = 320萬）。

在類似項目（檢查人員的AI）中取得了良好結果的東西是在遞歸中進一步降低了分支因子。通過定義最大分支（在遞歸步驟中要探索的分支的最大數量），讓這個數字大於頂層的典型分支，並且遞歸下降到更小的數目（5-10很快，底部1-3）。這樣，你就可以得到兩全其美的好處。你探索所有即將到來的舉動，但你也會得到很多關於它們如何影響遊戲後期部分的信息。

快速回顧：使用MCTS和min-max，您可以找到很多最終狀態。如果對手贏了，給它一個很大的負分。如果你贏了，給它一個很大的積極分數如果兩者都不是，你可以給它一個0，或使用你在問題中顯示的功能。通過利用min-max算法，讓父母遊戲狀態的分數取決於他們的孩子的分數。