Prolog实现双人数字博弈求解失败问题排查与修复

问题背景 #

存在数字对(x, y)，两名玩家轮流行动，每次可将任一数字加1或乘2，使x+y≥77的玩家获胜。初始位置为(8, x)，需找到最小x使第二名玩家在最少回合获胜。

解析法求解 #

双方均选择将x乘2的最优策略，可得不等式：
8 + 2*2*x ≥77
推导得4x≥69，即x≥17.25，取最小整数x=18。

尝试的Prolog实现代码 #

:- use_module(library(clpfd)).

top(77).

% 玩家的可行操作
next_state(X1, X2, Y1, Y2) :- Y1 #= X1 + 1,
                              Y2 #= X2.

next_state(X1, X2, Y1, Y2) :- Y1 #= X1,
                              Y2 #= X2 + 1.

next_state(X1, X2, Y1, Y2) :- Y1 #= 2*X1,
                              Y2 #= X2.

next_state(X1, X2, Y1, Y2) :- Y1 #= X1,
                              Y2 #= 2*X2.

% 获胜状态判断
win(X1, X2) :- top(X),
               X1 + X2 #>= X.

% 合法状态序列判断
sequence_correct([[X1, X2]]) :- win(X1, X2).
sequence_correct([[X1, X2], [Y1, Y2] | T]) :- next_state(X1, X2, Y1, Y2),
                                              sequence_correct([[Y1, Y2] | T]).

% 寻找满足条件的最小X
min(X) :- sequence_correct([[8, X], _, _]), \+ (sequence_correct([[8, Y], _, _]), Y #< X).

运行异常现象 #

调用min(X)返回false，但直接调用min(18)返回true，min(17)和min(19)返回false。

疑问 #

1. 代码存在什么问题？
2. 如何修复该代码？

问题1：代码存在的问题 #

• CLPFD约束与否定操作不兼容：\+/1是Prolog的否定失败操作符，它无法正确处理CLPFD的约束变量。当min(X)中的sequence_correct([[8, X], _, _])生成X的约束后，\+ (sequence_correct([[8, Y], _, _]), Y #< X)无法对约束状态下的X进行有效比较和否定判断，导致整个查询失败。
• 序列长度约束模糊：sequence_correct([[8, X], _, _])仅匹配长度≥3的序列，但没有强制约束序列恰好为3个状态（对应第二名玩家在第2步获胜），不过这不是导致查询失败的核心原因。

问题2：修复方案 #

方案一：收集合法值后取最小值

利用findall/3收集所有满足条件的X，再通过min_list/2提取最小值，避开否定操作对约束变量的影响：

min(X) :-
    findall(Y, sequence_correct([[8, Y], _, _]), ValidXs),
    min_list(ValidXs, X).

方案二：使用CLPFD原生约束否定替代\+

用CLPFD的#\（约束否定）替换\+，同时给X设定合理范围，确保约束能被正确处理：

min(X) :-
    X #>= 1, X #=< 35,  % 设定X的合理取值范围
    sequence_correct([[8, X], _, _]),
    #\ (Y #< X, Y #>=1, sequence_correct([[8, Y], _, _])).

方案三：明确模拟两步获胜场景

直接定义谓词模拟两名玩家各走一步后获胜的逻辑，避免模糊的序列匹配，可读性和准确性更高：

% 第二名玩家两步内获胜的判断
second_player_wins(X) :-
    next_state(8, X, M1X, M1Y),  % 玩家1走第一步
    next_state(M1X, M1Y, M2X, M2Y),  % 玩家2走第二步后获胜
    win(M2X, M2Y).

% 寻找最小X
min(X) :-
    findall(Y, second_player_wins(Y), ValidXs),
    min_list(ValidXs, X).

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