Nim游戏AI的Minimax算法问题：AI始终选择取1根火柴

问题描述 #

使用Prolog实现经典Nim游戏（规则：两名玩家轮流取1-3根火柴，取走最后一根的玩家落败），人类玩家逻辑正常，但AI对手始终选择取1根火柴，不符合Minimax最优决策逻辑。

原代码问题分析 #

1. 评估函数逻辑错误：
   原评估函数将State=0标记为对手获胜（价值-1），但实际State=0意味着上一个玩家取走了最后一根火柴，当前玩家应该获胜；State=1时当前玩家必须取走最后一根，才是落败状态。

2. Minimax函数未返回动作：
   原minimax函数仅返回状态价值，而play_game_opponent错误地将价值当作动作使用（价值为1或-1，导致AI始终输出1）。

3. 未区分Max/Min玩家逻辑：
   原代码未根据当前玩家类型（最大化玩家/最小化玩家）选择最佳价值，导致决策逻辑混乱。

4. 游戏结束判断错误：
   原play_game_human中，当玩家取完后堆为0时错误判定玩家获胜，实际此时玩家取走了最后一根，应该落败。

修正后的完整代码 #

% 定义AI对手
opponent(ai).

% 评估终止状态的价值
% State=0：当前玩家获胜（上一个玩家取走了最后一根火柴）
evaluate(0, 1).
% State=1：当前玩家落败（必须取走最后一根火柴）
evaluate(1, -1).

% Minimax算法：返回最佳动作和对应状态价值
% 终止状态：无动作，直接返回评估价值
minimax(State, _, _, none, Value) :-
    (State = 0 ; State = 1),
    evaluate(State, Value),
    !.

% 非终止状态，递归计算所有可能移动的价值
minimax(State, Depth, Player, BestAction, Value) :-
    Depth > 0,
    NextDepth is Depth - 1,
    % 生成所有合法移动及其子状态的价值
    findall(Value1-Action,
            (valid_move(State, Action),
             make_move(State, Action, NextState),
             change_player(Player, Opponent),
             minimax(NextState, NextDepth, Opponent, _, Value1)),
            ValuesActions),
    % 根据玩家类型选择最佳动作
    (Player = player ->
        % 人类玩家是Max玩家，选择价值最大的动作
        best_max_value(ValuesActions, BestValue, BestAction)
    ; Player = opponent ->
        % AI是Min玩家，选择价值最小的动作（最小化人类获胜概率）
        best_min_value(ValuesActions, BestValue, BestAction)
    ),
    % 当前状态的价值为子状态最佳价值的相反数（对手回合的价值反转）
    Value is -BestValue.

% 寻找最大价值对应的动作
best_max_value([Value-Action], Value, Action).
best_max_value([Value1-Action1, Value2-Action2|Rest], BestValue, BestAction) :-
    (Value1 >= Value2 ->
        best_max_value([Value1-Action1|Rest], BestValue, BestAction)
    ;
        best_max_value([Value2-Action2|Rest], BestValue, BestAction)
    ).

% 寻找最小价值对应的动作
best_min_value([Value-Action], Value, Action).
best_min_value([Value1-Action1, Value2-Action2|Rest], BestValue, BestAction) :-
    (Value1 =< Value2 ->
        best_min_value([Value1-Action1|Rest], BestValue, BestAction)
    ;
        best_min_value([Value2-Action2|Rest], BestValue, BestAction)
    ).

% 验证移动是否合法：取1-3根，且不超过当前堆数
valid_move(State, Action) :-
    State >= Action,
    Action >= 1,
    Action <= 3.

% 执行移动：计算新的堆数
make_move(State, Action, NewState) :-
    NewState is State - Action.

% 切换玩家
change_player(player, opponent).
change_player(opponent, player).

% 游戏入口
play_game :-
    write("Do you want to play a game? (yes/no) "),
    read(Response),
    (Response = yes -> 
        write("You start with a pile of 21 matchsticks."), nl,
        play_game_human(21)
    ; true).

% 人类玩家回合
play_game_human(Pile) :-
    write("Your turn: "),
    read(Action),
    (valid_move(Pile, Action) ->
        NewPile is Pile - Action,
        (NewPile = 0 -> 
            % 人类取走最后一根，落败
            write("You lost!"), nl 
        ; play_game_opponent(NewPile))
    ;
        write("Invalid move. Choose 1, 2, or 3."),
        nl,
        play_game_human(Pile)
    ).

% AI对手回合
play_game_opponent(Pile) :-
    minimax(Pile, 10, opponent, BestAction, _),
    write("The opponent played: "),
    write(BestAction),
    nl,
    NewPile is Pile - BestAction,
    (NewPile = 0 -> 
        % AI取走最后一根，人类获胜
        write("You won!"), nl 
    ; NewPile = 1 ->
        % 人类必须取最后一根，落败
        write("You lost!"), nl
    ; play_game_human(NewPile)
    ).

:- initialization(play_game).

关键修正说明 #

1. 评估函数修正：明确终止状态的价值定义，State=0对应当前玩家获胜，State=1对应当前玩家落败。
2. Minimax函数重构：新增参数返回最佳动作，区分Max（人类）和Min（AI）玩家的决策逻辑，分别选择最大/最小价值的动作。
3. 游戏结束判断修正：纠正人类和AI回合结束后的胜负判定逻辑，符合“取最后一根者落败”的规则。
4. 动作返回修复：确保play_game_opponent从Minimax函数获取的是合法动作（1/2/3）而非状态价值。

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