跳棋算法：如何减少嵌套 for 循环

Question

我正在尝试构建一个播放 draughts/checkers 的程序。目前我正在尝试实现该功能，该功能允许计算机进行和评估动作。我的想法是让计算机查看它自己所有可能的着法，并针对其中的每一个着法，查看对手可能的着法，然后对于这些着法中的每一个，再次查看它自己可能的着法。

对于每一层，它都会评估移动对玩家来说是好是坏并分配分数，最后它会选择得分最高的移动。

到目前为止，我已经设法实现了这个版本的工作，但涉及很多嵌套的 for 循环。代码一团糟，目前可读性不强，但这是同一概念的简单模型。它不会评估和生成更多列表，而只是将新列表乘以二。

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

I thought recursion might be a way of doing this, but I can’t figure out how to stop the recursion after x levels of search depth.

您的直觉是正确的，一种简单的方法是将递增的数字传递给每个级别。当递归得到最大值时，递归完成。下面是一个简单的例子来演示。

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 的方式进行调整。 hueristicEvaluation 函数可以很简单，比如计算每个玩家在棋盘上的棋子数以及它们与另一边的距离。请记住，此函数需要 return [-1,1]

之间的数字

要考虑的边缘情况，我没有考虑到：

如果所有动作都赢and/or输
如果该位置没有棋子，比如你的棋子都被对手的棋子挡住了

像这样的简单搜索存在许多改进。如果您有兴趣，请阅读:)

对于跳棋，也许 Memoization would speed things up a lot. I'm not sure, but I'd think it would be especially in the beginning. See python's way of doing this.
Pruning
Alpha-beta pruning
Branch and bound

Answer 2

这是一个使用递归的等效函数。它使用跟踪当前深度和最大深度的两个参数控制递归。如果当前深度超过最大深度，它将立即 return 从而停止递归：

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 调用，它将产生相同的输出，除了打印当前深度而不是变量名。

跳棋算法：如何减少嵌套 for 循环

Checkers algorithm: how to reduce nested for loops

python

recursion

chess

nested-loops