井字棋Minimax结合Alpha-Beta剪枝与哈希表后单一场景失效问题

Minimax函数在单独使用Alpha-Beta剪枝、哈希表缓存，或两者都不使用时均运行正常，但同时启用这两种优化后，仅在AI作为后手的某一特定场景下失效。

失效场景 #

落子顺序：

• 人类（执X）落子：9、1、3、6
• AI（执O）落子：5、7、2

最终棋盘状态：

X | O | X 
---+---+---
 4 | O | X 
---+---+---
 O | 8 | X

相关Minimax代码 #

def minimax(depth, alpha, beta):
    new_depth = depth + 1
    avails = core_func.availables()
    if new_depth % 2:  # maximizer
        if core_func.check_win():
            return -1  # previously minimizer
        elif not avails:
            return 0
        best_score = -float('inf')
        for c in avails:
            i = c - 1
            variables.grid[i] = variables.symbol
            t = tuple(variables.grid)
            if t not in variables.states:
                variables.states[t] = minimax(new_depth, alpha, beta)
            best_score = max(best_score, variables.states[t])
            alpha = max(alpha, best_score)
            variables.grid[i] = c
            if beta <= alpha: break
    else:  # minimizer
        if core_func.check_win():
            return 1  # previously maximizer
        elif not avails:
            return 0
        opponent = variables.valid_symbols - {variables.symbol}
        opponent = opponent.pop()
        best_score = float('inf')
        for c in avails:
            i = c - 1
            variables.grid[i] = opponent
            t = tuple(variables.grid)
            if t not in variables.states:
                variables.states[t] = minimax(new_depth, alpha, beta)
            best_score = min(best_score, variables.states[t])
            beta = min(beta, best_score)
            variables.grid[i] = c
            if beta <= alpha: break
    return best_score

完整可运行代码 #

core_func.py #

import variables
import turns_func


def update_grid():
    print(f' {variables.grid[0]} | {variables.grid[1]} | {variables.grid[2]} \n'
          f'---+---+---\n'
          f' {variables.grid[3]} | {variables.grid[4]} | {variables.grid[5]} \n'
          f'---+---+---\n'
          f' {variables.grid[6]} | {variables.grid[7]} | {variables.grid[8]} \n')


def correct_input(message, lst):
    i = int(input(f'{message}: '))
    if i not in lst:
        print(f'input error: input is not valid. valid inputs: {lst}')
        return correct_input(message, lst)
    return i


def initialization():
    option = correct_input(variables.initialization_message, variables.valid_initials)
    if option in {1, 4, 5}:
        variables.turn = 'H'
    else:
        variables.turn = 'C'
    if option in {2, 4}:
        variables.difficulty = 'R'
    if option in {3, 5}:
        variables.difficulty = 'P'
    print('Coordinates of the grid:')
    update_grid()


def check_win():
    for x, y, z in (0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6):
        if variables.grid[x] == variables.grid[y] == variables.grid[z]:
            return True
    return False


def availables():
    availables = []
    for c in variables.grid:
        if c not in variables.valid_symbols:
            availables.append(c)
    return availables


def get_coordinate():
    if not variables.difficulty:
        return turns_func.human_turn()
    elif variables.turn == 'H':
        variables.turn = 'C'
        return turns_func.human_turn()
    else:
        print(f'computer ({variables.symbol}):')
        variables.turn = 'H'
        if variables.difficulty == 'R':
            return turns_func.random_turn()
        else:
            return turns_func.perfect_turn()


def play():
    coordinate = get_coordinate()
    variables.grid[coordinate - 1] = variables.symbol
    update_grid()
    variables.moves += 1
    if check_win():
        print(f'\"{variables.symbol}\" wins in {variables.moves} moves!')
    elif not availables():
        print('\"Game Ties\"')
    else:
        changed = variables.valid_symbols - {variables.symbol}
        variables.symbol = changed.pop()
        play()

turns_func.py #

import variables
import core_func
from random import choice


def human_turn():
    return core_func.correct_input(variables.get_coordinate_message + variables.symbol, core_func.availables())


def random_turn():
    return choice(core_func.availables())


# alpha - maximizer's max - it should be less than its parent node minimizer's min
# beta - minimizer's min - it should be greater than its parent node maximizer's max


def minimax(depth, alpha, beta):
    new_depth = depth + 1
    avails = core_func.availables()
    if new_depth % 2:  # maximizer
        if core_func.check_win():
            return -1  # previously minimizer
        elif not avails:
            return 0
        best_score = -float('inf')
        for c in avails:
            i = c - 1
            variables.grid[i] = variables.symbol
            t = tuple(variables.grid)
            if t not in variables.states:
                variables.states[t] = minimax(new_depth, alpha, beta)
            best_score = max(best_score, variables.states[t])
            alpha = max(alpha, best_score)
            variables.grid[i] = c
            if beta <= alpha: break
    else:  # minimizer
        if core_func.check_win():
            return 1  # previously maximizer
        elif not avails:
            return 0
        opponent = variables.valid_symbols - {variables.symbol}
        opponent = opponent.pop()
        best_score = float('inf')
        for c in avails:
            i = c - 1
            variables.grid[i] = opponent
            t = tuple(variables.grid)
            if t not in variables.states:
                variables.states[t] = minimax(new_depth, alpha, beta)
            best_score = min(best_score, variables.states[t])
            beta = min(beta, best_score)
            variables.grid[i] = c
            if beta <= alpha: break
    return best_score


def perfect_turn():
    max_score = -float('inf')
    coordinate = None
    for c in variables.grid:
        if c in variables.valid_symbols: continue
        i = c - 1
        variables.grid[i] = variables.symbol
        score = minimax(1, -float('inf'), float('inf'))
        variables.grid[i] = c
        if score > max_score:
            max_score = score
            coordinate = c
    return coordinate

variables.py #

initialization_message = ('1. Play with Human\n'
                          'Play with computer:\n'
                          'For computer going first, Difficulties:\n'
                          '\t2. Random\n'
                          '\t3. Perfect\n'
                          'For computer going second, Difficulties:\n'
                          '\t4. Random\n'
                          '\t5. Perfect\n'
                          'Choose an option. Enter the number')

get_coordinate_message = 'Input a coordinate for '

valid_initials = (1, 2, 3, 4, 5)
grid = [1, 2, 3, 4, 5, 6, 7, 8, 9]
valid_symbols = {'X', 'O'}
symbol = 'X'
difficulty = None
turn = None
moves = 0
states = {}

main.py #

import core_func

core_func.initialization()
core_func.play()

哈希表缓存仅以棋盘布局作为键存储评分，但忽略了当前搜索节点的alpha/beta约束和玩家身份。Alpha-Beta剪枝的结果高度依赖搜索路径中的alpha、beta值，相同棋盘布局在不同的约束条件下可能触发不同的剪枝逻辑，直接复用缓存的评分会导致错误的剪枝决策。

在失效场景中，AI评估剩余落子（4和8）时，缓存中存储了该棋盘在其他alpha/beta条件下的评分，导致当前搜索错误触发剪枝，无法找到正确的落子选择，最终出现失效情况。

修改缓存键的构成，将棋盘布局、当前玩家身份（maximizer/minimizer）、alpha值、beta值共同作为缓存键，确保只有在完全相同的搜索上下文下才复用缓存结果。同时，每次AI决策前清空缓存，避免不同回合的搜索上下文互相干扰。

修改后的Minimax函数 #

def minimax(depth, alpha, beta):
    new_depth = depth + 1
    is_maximizer = new_depth % 2 == 1
    avails = core_func.availables()
    
    # 构建包含完整搜索上下文的缓存键
    board_state = tuple(variables.grid)
    cache_key = (board_state, is_maximizer, alpha, beta)
    
    # 优先从缓存获取结果
    if cache_key in variables.states:
        return variables.states[cache_key]
    
    if is_maximizer:  # maximizer逻辑
        if core_func.check_win():
            result = -1
        elif not avails:
            result = 0
        else:
            best_score = -float('inf')
            for c in avails:
                i = c - 1
                variables.grid[i] = variables.symbol
                score = minimax(new_depth, alpha, beta)
                best_score = max(best_score, score)
                alpha = max(alpha, best_score)
                variables.grid[i] = c
                if beta <= alpha:
                    break
            result = best_score
    else:  # minimizer逻辑
        if core_func.check_win():
            result = 1
        elif not avails:
            result = 0
        else:
            opponent = variables.valid_symbols - {variables.symbol}
            opponent = opponent.pop()
            best_score = float('inf')
            for c in avails:
                i = c - 1
                variables.grid[i] = opponent
                score = minimax(new_depth, alpha, beta)
                best_score = min(best_score, score)
                beta = min(beta, best_score)
                variables.grid[i] = c
                if beta <= alpha:
                    break
            result = best_score
    
    # 将结果存入缓存
    variables.states[cache_key] = result
    return result

修改后的perfect_turn函数 #

def perfect_turn():
    max_score = -float('inf')
    coordinate = None
    # 清空缓存，避免上一回合的结果干扰当前决策
    variables.states.clear()
    for c in variables.grid:
        if c in variables.valid_symbols:
            continue
        i = c - 1
        variables.grid[i] = variables.symbol
        score = minimax(1, -float('inf'), float('inf'))
        variables.grid[i] = c
        if score > max_score:
            max_score = score
            coordinate = c
    return coordinate

内容的提问来源于stack exchange，提问作者muminurfahim