时间戳

首页 > 解决方案 > 使用极小极大树搜索的机器人太慢了

python - 使用极小极大树搜索的机器人太慢了

问题描述

我正在阅读《深度学习和围棋游戏》这本书，我在书中没有走多远；我编写了基础（规则、辅助类）和 Qt GUI 界面。所有的作品，我决定编写极小极大程序的示例，看看我是否能打败它;-) 但它太慢了：玩一个动作需要几分钟，初始棋盘为 9x9。默认深度为 3 步，我认为第一步的计算需要 (9x9)x(9x9-1)x(9x9-2)~ 500 000 个位置。好的，它是 python，而不是 C，但我认为这可以在最多一分钟内计算出来。

我删除了一个对 copy.deepcopy() 的调用，这似乎消耗了很多时间。但它停留得太慢了。

这是一些东西：计算线程：

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)

select move 方法及其类：

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

我几乎可以肯定问题不是来自 GUI，因为本书给出的程序的初始版本完全处于控制台模式，和我的一样慢。

我的要求是什么？好吧，要确定这种缓慢的行为是不正常的，也许是为了知道出了什么问题。minimax算法来自书本，所以没问题。

谢谢你

标签： pythonalgorithmartificial-intelligence

解决方案

机器学习通常在 Python 中完成，因为：

    1. 简单安全
    1. 它很灵活
    1. 所有繁重的工作都在专门的模块中完成，例如 tensorflow 和 keras

在你的情况下， 3. 不成立。所有这些嵌套调用、参数传递、复制和板评估都在 Python 中完成。成本是编译语言的 10 到 100 倍[需要引用]。

流行的 ML 项目似乎都是用 Python 完成的，但实际的 Python 代码只是围绕处理和提供数据、控制对 tensorflow 的调用以及显示结果。这就是他们能做到的原因。

所以，是的，在你的故事中没有什么不寻常的。你查过Leela-zero吗？它更复杂/涉及更多，但开源并且做得很好，它可能已经打败了你。

推荐阅读