如何通过内存和迭代加深提高我的 alpha beta 剪枝极小极大算法的性能

Question

我在 python 中创建了一个类似于井字游戏的游戏，我可以在其中选择棋盘的大小和连续获胜所需的棋子数量。我还创建了一个具有 minimax、alpha-beta 修剪、转置表和迭代加深的机器人。我正在使用 python 并且我的板表示只是一个二维数组。出于某种原因，当国际象棋引擎每秒计算 100,000 多个节点时，我的算法每秒只计算 600 个节点。我知道 python 很慢而且板的表示会影响速度，但我认为它不应该只计算每秒 600 个左右的节点。我还有一个评估功能，可以对整个棋盘进行循环并评估棋子的位置。我只是想弄清楚如何加速算法，因为它看起来慢得不合理。

我的算法：

def tt_minimax(board, plr, alpha, beta, depth):
    global tt_start_time
    if ITERATIVEDEEPENING and timeit.default_timer()-tt_start_time >= MAXTIME:
        return "UNFINISHED", 0

    alpha_org = alpha

    tt_code = tt_hash(board)
    pv_move = []
    if tt_code in TRANSPOSITION_TABLE:
        tt_entry = TRANSPOSITION_TABLE[tt_code]
        if tt_entry[3] >= depth:
            if tt_entry[2] == 0:  # checking for Exact
                return tt_entry[0], tt_entry[1]
            elif tt_entry[2] == -1:  # lower bound
                alpha = max(alpha, tt_entry[1])
            elif tt_entry[2] == 1:  # upper bound
                beta = min(beta, tt_entry[1])

            if alpha >= beta:
                return tt_entry[0], tt_entry[1]
        else:
            pv_move = tt_entry[0]

    global tt_node_count
    tt_node_count += 1

    moves = find_moves(board)
    #random.shuffle(moves)

    if pv_move:
        moves.insert(0, moves.pop(moves.index(pv_move)))

    # if drawn
    if len(moves) == 0:
        return "none", 0

    # maximizing
    if plr == 1:

        best_score = MIN
        best_move = []
        for movePair in moves:
            y, x = movePair[0], movePair[1]
            board[y][x] = plr

            wt_code = tt_hash(board)
            if wt_code in WIN_TABLE:
                test_result = WIN_TABLE[wt_code]
            else:
                test_result = test_for_win(board)
                WIN_TABLE[wt_code] = test_result

            if test_result == plr:
                evaluation = 1000 + TTD + depth
                if evaluation > best_score:
                    best_score = evaluation
                    best_move = movePair
            elif depth > 0:
                returned = tt_minimax(board, 2, alpha, beta, depth - 1)
                if returned[0] == "UNFINISHED":
                    return returned
                return_eval = returned[1]
                if return_eval > best_score:
                    best_score = return_eval
                    best_move = movePair
            else:
                evaluation = evaluate(board, 2)
                if evaluation > best_score:
                    best_score = evaluation
                    best_move = movePair

            board[y][x] = 0
            alpha = max(alpha, best_score)

            if beta <= alpha:
                break

        tt_store(TRANSPOSITION_TABLE, board, alpha_org, beta,
                 best_move, best_score, depth)

        return best_move, best_score

    # minimizing
    else:
        best_score = MAX
        best_move = []
        for movePair in moves:
            y, x = movePair[0], movePair[1]
            board[y][x] = plr

            wt_code = tt_hash(board)
            if wt_code in WIN_TABLE:
                test_result = WIN_TABLE[wt_code]
            else:
                test_result = test_for_win(board)
                WIN_TABLE[wt_code] = test_result

            if test_result == plr:
                evaluation = -1000 - depth
                if evaluation < best_score:
                    best_score = evaluation
                    best_move = movePair
            elif depth > 0:
                returned = tt_minimax(board, 1, alpha, beta, depth - 1)
                if returned[0] == "UNFINISHED":
                    return returned
                return_eval = returned[1]
                if return_eval < best_score:
                    best_score = return_eval
                    best_move = movePair
            else:
                evaluation = evaluate(board, 2)
                if evaluation < best_score:
                    best_score = evaluation
                    best_move = movePair

            board[y][x] = 0
            beta = min(beta, best_score)

            if beta <= alpha:
                break

        tt_store(TRANSPOSITION_TABLE, board, alpha_org, beta,
                 best_move, best_score, depth)

        return best_move, best_score

Answer 1

C 比 Python 快一点。 C 比 Python 快很多。将其转换为 C 将是巨大的。然后你可以再问一次，因为用 C 语言编码的方式也很庞大。以更快的速度乘以数十，你的程序将在 C 中尖叫。

Python，好吧，我只想说Python并不意味着快。在 Python 的初始设计中速度不是一个因素，现在一切都是对象......可以这么说 Python 变得更好时变得更慢。我喜欢 Python 的目的，但 C 也有目的。您的程序是 C 的用途的完美示例。使用 Python 作为包装器来玩游戏。用C计算下一步。

如何通过内存和迭代加深提高我的 alpha beta 剪枝极小极大算法的性能

How do I increase the performance of my alpha beta pruning minimax algorithm with memory and iterative deepening

python

minimax