CODEWITHSUNDEEP
pythonalgorithmartificial-intelligence
lolveley
lolveley

Reputation: 1719

go bot with minimax tree search too slow

I am reading the book "deep learning and the game of go" and I not went far in the book; I wrote the foundations (rules, helper classes) and a Qt GUI interface. All works and I decided to write the examples of minimax program, to see if I can beat it ;-) but it's too slow : it take minutes to play one move, with an initial board of 9x9. With a default depth of 3 moves, I think the computation of the first move would take (9x9)x(9x9-1)x(9x9-2)~ 500 000 positions. Ok, it's python, not C, but I think this could be computed in one minute max.

I removed one call to copy.deepcopy(), which seemed to consume a lot of time. But it stay too slow.

Here is some stuff: the computing thread:

class BotPlay(QThread):
    """
    Thread de calcul du prochain coup par le bot
    """

    def __init__(self, bot, bots, game):
        """
        constructeur, pour le prochain coup à jouer

        :param bot: le bot qui doit jouer
        :param bots: l'ensemble des 2
        :param game: l'état actuel du jeu (avant le coup à jouer)
        """
        QThread.__init__(self)
        self.bot = bot
        self.bots = bots
        self.game = game

    played = pyqtSignal(Move, dict, GameState)

    def __del__(self):
        self.wait()

    def run(self):
        self.msleep(300)
        bot_move = self.bot.select_move(self.game)
        self.played.emit(bot_move, self.bots, self.game)

the select move method and its class:

class DepthPrunedMinimaxAgent(Agent):

    @bot_thinking(associated_name="minimax prof. -> LONG")
    def select_move(self, game_state: GameState):
        PonderedMove = namedtuple('PonderedMove', 'move outcome')
        best_move_so_far = None
        for possible_move in game_state.legal_moves():
            next_state = game_state.apply_move(possible_move)
            our_best_outcome = -1 * self.best_result(next_state, capture_diff)
            if best_move_so_far is None or our_best_outcome > best_move_so_far.outcome:
                best_move_so_far = PonderedMove(possible_move, our_best_outcome)
        return best_move_so_far.move

    def best_result(self, game_state: GameState, eval_fn, max_depth: int = 2):
        if game_state.is_over():
            if game_state.next_player == game_state.winner():
                return sys.maxsize
            else:
                return -sys.maxsize

        if max_depth == 0:
            return eval_fn(game_state)

        best_so_far = -sys.maxsize
        for candidate_move in game_state.legal_moves():
            next_state = game_state.apply_move(candidate_move)
            opponent_best_result = self.best_result(next_state, eval_fn, max_depth - 1)
            our_result = -opponent_best_result
            if our_result > best_so_far:
                best_so_far = our_result
        return best_so_far

I am nearly sure the problem does not come from the GUI, because the initial version of the program, given by the book , and entirely in console mode, is as slow as mine.

What is my request? Well, to be sure that this slow behavior is not normal, and maybe to have a clue to what goes wrong. The minimax algorithm comes from the book, so it's ok.

thank you

Upvotes: 1

Views: 268

Answers (2)

Nathan S.
Nathan S.

Reputation: 5388

It can be difficult to write performant (fast) search code in Python. But, if you want to use Python, the first/primary thing to worry about is avoiding all memory allocation. Try to pre-allocate any memory that will be used. The second thing to worry about is unnecessary copying - make sure that you aren't copying data unnecessarily. These two changes, which may not be simple to apply, will go a long ways towards speeding up your code.

These are easier to control in a language like C or C++, but can still be done in Python. In my experience, a search-based program written poorly (with memory allocation and unnecessary copying) in Python can be 100x or even 1000x slower than a well-written C/C++ program.

As an aside, Monte-Carlo Tree Search (MCTS) is the predominant approach in Go these days, so you may want to look into MCTS. But, either way you'll need to get your code to run faster to be able to have it play well.

Upvotes: 2

Jeffrey
Jeffrey

Reputation: 11430

Machine learning is often done in Python, because:

    1. it is simple and safe
    1. it is flexible
    1. all the heavy-lifting is done in specialized module, like tensorflow and keras

In your case, 3. doesn't hold. All those nest calls, parameter passing, copying and board evaluation get done in Python. Costing you 10 to 100 times more than in a compiled language [citation needed].

Popular ML project seems to all be done in Python, but the actual Python code is only around processing and feeding the data, controlling the calls to tensorflow, and displaying the results. That's why they could do it.

So, yeah, nothing unusual in your story. Did you look up Leela-zero? It's much more complex/involved, but open-source and very well done, and it probably beats you, already.

Upvotes: 2

Related Questions