棋类游戏中的阿尔法-贝塔剪枝

Question

我想为跳棋游戏实现一个人工智能。但是我对“α-β剪枝”这个原理不太明白，所以一直没能成功！
我希望这个算法能在一定时间内（比如5秒或10秒）停止运行。但是，我觉得我的算法似乎从来不会停止。此外，这个算法也没有进行任何的剪枝操作。

编辑：
我遇到了这些错误：

    File "player.py", line 61, in min_value
    v = min(v, self.max_value(pBoard, single_move, pDue, alpha, beta))
    File "player.py", line 44, in max_value
    v = max(v, self.min_value(pBoard, single_move, pDue, alpha, beta))
    File "player.py", line 61, in min_value
    [...]  
    File "player.py", line 61, in min_value
    v = min(v, self.max_value(pBoard, single_move, pDue, alpha, beta))
    File "player.py", line 44, in max_value
    v = max(v, self.min_value(pBoard, single_move, pDue, alpha, beta))
    File "player.py", line 61, in min_value

    TypeError: unorderable types: NoneType() < float()

如果有人能清楚地解释一下该如何实现，我会非常感激。以下是我用Python写的代码：
“评估”函数会根据棋子在棋盘上的位置给出一个值。

    def calc_move(self, pBoard, pDue):
       score =0
       validMoves = pBoard.find_possible_moves(CELL_OWN)
       for move in validMoves:
          pBoard.do_move(move)
          score_move = self.max_value(pBoard, move, pDue, -float('inf'), float('inf'))
          if score_move > score:
             score = score_move
             best_move = move
       return best_move

    def max_value(self, pBoard, move, pDue, alpha, beta):
      if pDue - time.time() < 0.5 or move.is_EOG():
         return self.evaluation(move, CELL_OWN)
      v = -float('inf')
      validMoves = pBoard.find_possible_moves(CELL_OWN)
      for single_move in validMoves:
          pBoard.do_move(single_move)
          v = max(v, self.min_value(pBoard, single_move, pDue, alpha, beta))
          if v >= beta:
             return v
          alpha = max(alpha, v)
      return v

    def min_value(self, pBoard, move, pDue, alpha, beta):
      if pDue - time.time() < 0.5 or move.is_EOG():
         return self.evaluation(move, CELL_OTHER)
      v = float('inf')
      validMoves = pBoard.find_possible_moves(CELL_OTHER) 
      for single_move in validMoves:
         pBoard.do_move(single_move)
         v = min(v, self.max_value(pBoard, single_move, pDue, alpha, beta))
         if v <= alpha:
           return v
         beta = min(beta, v)
      return v

谢谢你的帮助。

Answer 1

在这段内容中，File "player.py", line 61, in min_value 和 TypeError: unorderable types: NoneType() < float() 是很重要的提示。你应该意识到，实际的错误信息比你说的其他问题更重要。

因为你没有仔细看错误信息，所以我们只能猜测第61行是哪一行。

在这个函数中，有一些比较操作（比如 min() 和 if v <= alpha）看起来和这个问题有关。

错误信息表明 v 的值是 None。

由于 v 的值可能来自于 return self.evaluation(move, CELL_OWN)，所以看起来 self.evaluation 返回了 None。这种情况通常是因为没有写 return，或者写了 return 但没有返回任何值。