Take the 2-minute tour ×

I have what I think can be only a synchronizing problem in this Python code. The code is intended to apply a minimax algorithm to a Tic Tac Toe game, implemented with parallel processes instead of a single process exploring all the possible moves one by one. Before labeling it as a really bad idea, I've been required to do so.

Assume that unknown methods do exaclty what they suggest with their name, and assume that they work properly (they have been manually tested). The only method I'm not 100% sure of is this one, here's the code:

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

Game board is represented with a simple Board class (extends list class). SimpleQueue and Process classes are imported from the multiprocessing Python module. H function is the heuristic function I implemented: it returns positive values for boards good for player MAX, negative for MIN and 0 for a tie. Here's the algorithm code:

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

     if is_winning(board) or is_tie(board) or depth == 0:

     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


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

     # turn was MAX
     if turn == TURN_MAX:
     # turn was MIN

Main method is simply:

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

I often meet this kind of errors:

Traceback (most recent call last):
  File "game.py", line 202, in <module>
  File "game.py", line 182, in minimax
ValueError: max() arg is an empty sequence

but not always. Is there a mistake in the recursive method? I really can't figure it out.

My idea was to build a local queue for every turn, and then extract the max/min value from that queue to bring it to the "upper" queue, the queue from the preceding turn.

share|improve this question

2 Answers 2

So, from that message, it's sounding like q_elems(local_queue) is returning [], which means there's nothing in the local_queue.

Could possible_moves() be returning an empty list (say, after all moves have been taken on the board)? If possible_moves doesn't spawn anything then your local queue won't have anything in it.

share|improve this answer
If the board is a terminal board (no further possible moves - a tie or a winning board), the for loop shouldn't be executed: the return statement in the first if should exit the function. –  whatyouhide Jan 26 '13 at 11:38

I doubt that anyone of you is asking himself where is the problem here, but for future possible readers: the q_elems method performs a get method on the queue passed to it, and that method actually pops out elements from the queue, returning them but also removing them from the queue.

Problem solved.

share|improve this answer

Your Answer


