Parallelizing a Python for-loop that plays two players against each other (game theory simulation)

Question

I'm writing a game theory simulation in Python. As part of the simulation, each generation, two players are paired and played against each other (each player is an instance of the Player1 or Player2 classes). Simplified a bit, the code looks like this:

pool1 = [Player1() for _ in range(50)]
pool2 = [Player2() for _ in range(50)]

assignments = range(50)
random.shuffle(assignments)

pairs = []
for i, assignment in enumerate(assignments):
    pairs.append((pool1[i], pool2[assignment]))

for player1, player2 in pairs:
    repeat = True
    while repeat:
        repeat = play_game(player1, player2)

Payoffs are kept as an attribute of the player. At the end of each round, depending on the moves of the players, the game will either continue or end (play_game will return True or False respectively).

How can I make this code run in parallel? That is, how can I play more than 1 pair play each other at once? I've Googled around a bit and found the Python multiprocessing library, but I can't figure out how to apply it to this snippet of code.

Thanks!

Answer 1

I would create a class Game that is inherited from threading.Thread, so it behaves similar to the thread. Game class constructor accepts two player objects and number of the game.

number is required to facilitate returning of the game result into main program through the shared variable resultList (lists are thread-safe in Python). resultList is a list of lists and each Game instance puts the result to the corresponding cell of resultList according to its number.

run() method of each Game() instance is executed in a different thread so all the games are going on in parallel.

import threading
numOfGames = 10
resultList = [[] for x in xrange(numOfGames)]

class Game(threading.Thread):

    def __init__(self, player1, player2, number):
        threading.Thread.__init__(self)
        self.number = number
        self.player1 = player1
        self.player2 = player2

    def run(self):

        #Your game algorithm between self.player1 and self.player2 is here

        #Put game result into shared list
        resultList[self.number] = <result>

To work with the Game class you do the following:

#Create instances of the Game() class, pass your Player() objects
#You can do the step in loop
game0 = Game(<PlayerObj>,<PlayerObj>,0)
game1 = Game(<PlayerObj>,<PlayerObj>,1)

#Start execution of Game.run() methods of all Game() objects in separate threads
#You can do the step in loop
game0.start()
game1.start()

#Wait until all Game.run() methods are executed = all threads are finished
#You can do the step in loop
game0.join()
game1.join()

#In the shared list you have corresponding return values, 
#whatever they are in your case [[result of Game 0],[result of Game 1],[]...]
print resultList

PS: I wouldn't recommend to go with multiprocessing since there is a substantial overhead in creating a process (need to allocate stack etc.). In your case multiprocessing would suffice since your application has no need in memory isolation.

Answer 2

Just to comment on the comments on your post (don't have enough rep for a comment), it was likely slower because of the overhead induced by creating so many processes. Unless play_game is going to be CPU intensive or otherwise long running, you probably don't want separate processes for that. Threads are generally less intensive to start (more true on Windows than Unix/Linux, since Unix/Linux treats threads as processes), and are probably closer to what you need.

Part of the problem is your use of result. It looks like play_game can return False and kill the loop, however this model will not work with threads since they will not be executed in a linear manner anymore. If you just want to run all of them, you could change

for player1, player2 in pairs:
    repeat = True
    while repeat:
        repeat = play_game(player1, player2)

to

thread_list = []
for player1, player2 in pairs:
    thread_list.append(threading.Thread(target=play_game,args=(player1,player2)))
for wait_thread in thread_list:
    wait_thread.join()

to start threads for all of those different pairings at once. If you want to be able to kill off all of the running threads if one of them does not return True you're going to need to look at communication between threads, and you'll need to have a listener thread in your main program to read the output of the threads while they run.