prolog - 如何返回 alpha-beta 算法中的下一步？

Question

我正在实现一个 AI 来玩井字棋，我正在使用 alpha-beta 算法来搜索最佳着法。下面是我到目前为止的代码。我设法让算法工作——状态的值似乎是正确的，但我无法返回正确的下一步/棋盘。

当我执行目标时 Board = ['-','-','-','o','-','-','-','-','-'] , alpha_beta(max, Board, V, NB).，这是输出:

?- Board = ['-','-','-','o','-','-','-','-','-'], alpha_beta(max, Board, V, NB).

Board = [-, -, -, o, -, -, -, -, -],
V = 0,
NB = [-, -, -, o, -, -, -, -, x].

值V是正确的(它表示比赛结果将是平局)，但是代表'x'玩家下一步的NB不是.

测试，我打败了人工智能，这是不应该发生的事情。 在图像中，我多次执行目标，模拟井字游戏。 AI 玩“x”符号。关于输出:第一个棋盘是当前棋盘，作为输入提供的棋盘，第二个棋盘是 NextBoard，AI 的着法:

我已经尝试了一些东西。我尝试使用 guitracer，我尝试阅读其他实现，但找不到适合我的实现的解决方案。谁能告诉我我做错了什么？

alpha_beta(max,Board,Value, NextBoard):-
    ab_minimax(max,Board,-inf,inf,Value, NextBoard).
    
ab_minimax(max,Board,_,_,-1, NextBoard):-
    is_winning_state_o(Board), !.
ab_minimax(min,Board,_,_,1, NextBoard):-
    is_winning_state_x(Board), !. 
ab_minimax(_,Board,_,_,0, NextBoard):-
    is_a_draw(Board), !.
ab_minimax(max,Board,Alfa,Beta,Value, NextBoard):-
    children(Board, max, Children),
    ab_max_children(Children,Alfa,Beta,-inf,Value, NB, NextBoard).
ab_minimax(min,Board,Alfa,Beta,Value, NextBoard):-
    children(Board, min, Children),
    ab_min_children(Children,Alfa,Beta,inf,Value, NB, NextBoard).

ab_max_children([],_,_,Max,Max, NextBoard, NextBoard).
ab_max_children([H|T],Alfa,Beta,Max1,Max, NB, NextBoard):-
    ab_minimax(min,H,Alfa,Beta,Value, NextBoardX),
    ( 
        Value > Beta -> % Beta cut
            Max = Beta,
            NextBoard = H
        ; (
            max(Value,Alfa,Alfa1), % updates Alpha
            max(Value,Max1,Max2),
            (Max2 == Value -> NB1 = H; NB1 = NB),
            ab_max_children(T, Alfa1, Beta, Max2, Max, NB1, NextBoard)
        )
    ).

ab_min_children([],_,_,Min,Min, NextBoard, NextBoard).
ab_min_children([H|T],Alfa,Beta,Min1,Min, NB, NextBoard):-
    ab_minimax(max,H,Alfa,Beta,Value, NextBoardX),
    (
        Alfa > Value -> % Alpha cut
            Min = Alfa,
            NextBoard = H
        ; (
            min(Value,Beta,Beta1), % updates Beta
            min(Value,Min1,Min2),
            (Min2 == Value -> NB1 = H; NB1 = NB),
            ab_min_children(T, Alfa, Beta1, Min2, Min, NB1, NextBoard)
        )
    ).

is_winning_state_x(S) :-
    winning_state_x(S), !.

winning_state_x(['x','x','x',_,_,_,_,_,_]). % [1,2,3]
winning_state_x([_,_,_,'x','x','x',_,_,_]). % [4,5,6]
winning_state_x([_,_,_,_,_,_,'x','x','x']). % [7,8,9]
winning_state_x(['x',_,_,'x',_,_,'x',_,_]). % [1,4,7]
winning_state_x([_,'x',_,_,'x',_,_,'x',_]). % [2,5,8]
winning_state_x([_,_,'x',_,_,'x',_,_,'x']). % [3,6,9]
winning_state_x(['x',_,_,_,'x',_,_,_,'x']). % [1,5,9]
winning_state_x([_,_,'x',_,'x',_,'x',_,_]). % [3,5,7]

is_winning_state_o(S) :-
    winning_state_o(S), !.

winning_state_o(['o','o','o',_,_,_,_,_,_]). % [1,2,3]
winning_state_o([_,_,_,'o','o','o',_,_,_]). % [4,5,6]
winning_state_o([_,_,_,_,_,_,'o','o','o']). % [7,8,9]
winning_state_o(['o',_,_,'o',_,_,'o',_,_]). % [1,4,7]
winning_state_o([_,'o',_,_,'o',_,_,'o',_]). % [2,5,8]
winning_state_o([_,_,'o',_,_,'o',_,_,'o']). % [3,6,9]
winning_state_o(['o',_,_,_,'o',_,_,_,'o']). % [1,5,9]
winning_state_o([_,_,'o',_,'o',_,'o',_,_]). % [3,5,7]

has_empty_position(['-'|_]) :- !.
has_empty_position([_|T]) :- has_empty_position(T).

is_a_draw(S) :-
    not(has_empty_position(S)).

children(Board, Player, Children) :-
    findall(NewBoard, make_move(Player, Board, NewBoard), Children).

make_move(max, ['-'|T], ['x'|T]).
make_move(min, ['-'|T], ['o'|T]).
make_move(Player, [H|T1], [H|T2]) :- make_move(Player, T1, T2).

Answer 1

问题是，“正确”的下一步行动是什么，因为通常有不止一个最佳行动。

您正在做的是评估董事会的 child 。上表显示了每个子项及其值、当前的 Alpha 和当前的 Beta:

  [[x,-,-,o,-,-,-,-,-],0,-inf,inf]
  [[-,x,-,o,-,-,-,-,-],0,0,inf]
  [[-,-,x,o,-,-,-,-,-],0,0,inf]
  [[-,-,-,o,x,-,-,-,-],0,0,inf]
  [[-,-,-,o,-,x,-,-,-],0,0,inf]
  [[-,-,-,o,-,-,x,-,-],0,0,inf]
  [[-,-,-,o,-,-,-,x,-],0,0,inf]
  [[-,-,-,o,-,-,-,-,x],0,0,inf]

由于所有 child 的值都相同，所以下一个棋盘当然是最后一个 child 。

有两个问题:

1. 您以这样一种方式实现它，对于每个板，您最多有一个下板，而可能有多个最佳下一个板。

2. 我认为您对 child 的评价不正确。当我运行良好的旧 minimax 时，我得到:

[x,-,-,o,-,-,-,-,-]  0
[-,x,-,o,-,-,-,-,-] -1
[-,-,x,o,-,-,-,-,-] -1
[-,-,-,o,x,-,-,-,-] 0
[-,-,-,o,-,x,-,-,-] 0
[-,-,-,o,-,-,x,-,-] 0
[-,-,-,o,-,-,-,x,-] -1
[-,-,-,o,-,-,-,-,x] -1

Alpha-beta 剪枝不应该只考虑某些替代方案并因此使搜索更快，但产生相同的结果吗？