带有多进程问题的极小极大算法

Question

我觉得我在这段Python代码中遇到了一个同步问题。这个代码是用来在井字棋游戏中应用一个叫做“极小极大算法”的，特别的是，它是用并行处理的方式来实现的，而不是一个一个地检查所有可能的走法。在有人说这主意不太好之前，我是被要求这样做的。

假设那些未知的方法都是按照它们名字的意思来工作的，并且假设它们运行得很好（已经手动测试过了）。我唯一不太确定的方法是这个，代码如下：

def q_elems(queue):
    li = []
    while not queue.empty(): li.append(queue.get())
    return li

游戏棋盘用一个简单的Board类表示（它是list类的扩展）。SimpleQueue和Process类是从Python的multiprocessing模块导入的。H函数是我实现的启发式函数：它对对玩家MAX有利的棋盘返回正值，对MIN有利的棋盘返回负值，平局时返回0。算法的代码如下：

def minimax(board: Board, depth: int, turn: int, queue: SimpleQueue) -> int:
     queue.put(10000)

     if is_winning(board) or is_tie(board) or depth == 0:
         queue.put(H(board))
         return

     local_queue = SimpleQueue()

     prcs_list = []
     for child_brd in possible_moves(board, MAX if turn == TURN_MAX else MIN):
         p = Process(target=minimax, args=(
             Board(child_brd),                               # board
             depth - 1,                                      # depth
             TURN_MIN if turn == TURN_MAX else TURN_MAX,     # turn
             local_queue)                                    # queue
             )

         prcs_list.append(p)

     [p.start() for p in prcs_list]
     [p.join() for p in prcs_list]

     # turn was MAX
     if turn == TURN_MAX:
         queue.put(max(q_elems(local_queue)))
         return
     # turn was MIN
     else:
         queue.put(min(q_elems(local_queue)))
         return

主方法非常简单：

k = SimpleQueue()
minimax(b, MINIMAX_DEPTH, turn=TURN_MAX, queue=k)

我经常遇到这种错误：

Traceback (most recent call last):
  File "game.py", line 202, in <module>
    minimax(b, MINIMAX_DEPTH, turn=TURN_MAX, queue=k)
  File "game.py", line 182, in minimax
    queue.put(max(q_elems(local_queue)))
ValueError: max() arg is an empty sequence

但并不是每次都会出现。我在递归方法中是不是犯了什么错误？我真的搞不清楚。

我的想法是为每一步建立一个本地队列，然后从这个队列中提取最大或最小值，带到“上层”队列，也就是前一步的队列。

Answer 1

从这条信息来看，q_elems(local_queue) 返回的是一个空列表 []，这就意味着 local_queue 里没有任何东西。

那么，possible_moves() 可能会返回一个空列表吗？比如说，当棋盘上的所有移动都已经完成后？如果 possible_moves 没有生成任何内容，那么你的 local_queue 就会是空的。

Answer 2

我想大家可能不会问这个问题，但为了将来可能会看到这段内容的人来说：这个 q_elems 方法其实是在对传入的队列执行一个 get 方法，而这个方法实际上是弹出队列里的元素，也就是说它会把元素取出来并返回给你，同时也把这些元素从队列里删除。

问题就这样解决了。