跳棋算法：如何減少嵌套for循環

Question

我試圖建立一個播放草稿/跳棋的程序。目前我正在嘗試製作這個功能，它允許電腦製作和評估動作。我的想法是讓電腦看看它自己可能發生的所有動作，並且對於每一個動作，看看可能的對手動作，然後對每一個動作再次看看它自己可能的動作。

每一層都會評估這個移動對於玩家來說是好還是不好，並且分配點，最後它會選擇最高點的移動。

到目前爲止，我已經設法得到這個工作的一個版本，但涉及很多嵌套for循環。代碼是一團糟，並且目前不太可讀，但這是一個相同概念的簡單模型。而不是評估和生產更多的清單，它只是爲新清單乘以2。

counter = 0 
    for x in list: 
     counter += 1 
     list_2 = [x * 2 for x in list] 
     print 'list_2', list_2, counter 
     for x in list_2: 
      counter += 1 
      list_3 = [x * 2 for x in list_2] 
      print 'list_3',list_3, counter 
      for x in list_3: 
       counter += 1 
       list_4 = [x * 2 for x in list_3] 
       print 'list_4', list_4, counter 

如果我運行此代碼，我得到我想要的東西，但我不能輕鬆地控制搜索的深度沒有更多的複製for循環。我認爲遞歸可能是這樣做的一種方式，但我無法弄清楚如何在x級搜索深度後停止遞歸。

有沒有更好的方式獲得相同的輸出形式上面的代碼，同時擺脫所有for循環？如果我能做到這一點，我想我可以自己完成剩下的工作。

Answer 1

下面是一個使用遞歸的等價功能。它通過跟蹤當前深度和最大深度的兩個參數來控制遞歸。如果當前深度超過最大深度它會返回立即從而停止遞歸：

def evaluate(l, max_depth, cur_depth=0, counter=0): 
    if cur_depth > max_depth: 
     return counter 

    for x in l: 
     counter += 1 
     l2 = [x * 2 for x in l] 
     print cur_depth, l2, counter 
     counter = evaluate(l2, max_depth, cur_depth + 1, counter) 

    return counter 

如果具有max_depth=2調用時，它將產生相同的輸出，除了代替變量名被印刷當前深度。

Answer 2

我認爲遞歸可能是這樣做的一種方式，但我無法弄清楚如何停止x級搜索深度後的遞歸。

你的直覺是正確的，一個簡單的方法是將一個遞增的數字傳遞給每個級別。當遞歸獲得最大值時，遞歸完成。下面將演示一個簡單的例子。

def countup(i=0): 
    print(i) 
    if i==MAX_COUNT: return 
    countup(i+1) 

對於您的算法，您需要一個值來表示評估板。例如在範圍[-1,1]。例如，如果評價是-1而玩家A可以說是贏得獎勵，如果評價是1則玩家B贏得獎勵。遞歸算法可以如下。

def evaulate(board, player, depth=0): 
    if depth==MAX_DEPTH: return hueristicEvaluation(board) 
    bestMove = None 
    if player==PLAYER_A: 
    val=999 # some large value 
    for move in get_moves(): 
     newboard = board.makeMove(move) 
     eval, _ = evaluate(newboard, PLAYER_B, depth+1) 
     if eval < val: 
     bestMove = move 
     val = eval 
    elif player==PLAYER_B: 
    val=-999 # some large negative value 
    for move in get_moves(): 
     newboard = board.makeMove(move) 
     eval, _ = evaluate(newboard, PLAYER_A, depth+1) 
     if eval > val: 
     bestMove = move 
     val = eval 
    return val, bestMove 

這是抽象的，但想法是存在的。根據您代表board或player s的方式進行調整。功能hueristicEvaluation可能很簡單，就像爲每個玩家計算棋盤上的棋子一樣，以及他們距離另一邊有多近。請記住，這個功能需要返回[-1,1]

邊緣情形之間的一個數來考慮，這是我沒有考慮到：

• 如果所有的動作是勝利和/或失去
• 如果是例如，如果你的棋子全部被對手的棋子阻擋，那麼NO移動。

像這樣的簡單搜索存在許多改進。閱讀你是否感興趣:)

• 對於跳棋，或許Memoization會加速很多東西。我不確定，但我認爲這會特別在一開始。 See python's way of doing this.
• Pruning
• Alpha-beta pruning
• Branch and bound