在 Prolog 中实现 alpha beta 修剪

Question

我正在 Prolog 中开发游戏 Teeko，我尝试实施 alpha beta 修剪，但我不知道从哪里开始。有人可以指导我吗？我已经找到了极大极小算法。

Answer 1

我尝试实施 alpha beta 修剪，但我不知道从哪里开始。

有人可以指导我吗？

我已经找到了极大极小算法。

alpha beta 剪枝算法的简短介绍

使用带 alpha-beta 剪枝的极小极大选择移动

新的关系方案是alpha_beta( Depth, Position, Alpha, Beta, Move, Value )，

它通过用 alpha 和 beta 替换 minimax 标志来扩展 minimax。相同的关系对于 成立evaluate_and_choose。

该程序可以alpha_beta通过测试位置是否为终端来替换基本情况来概括。这在国际象棋程序中是必要的，例如，处理不完整的棋子交换。

evaluate_and_choose ( Moves, Position, Depth, Alpha, Beta, Record, BestMove )

• 从当前的Moves集合中选择BestMove

• 使用带 alpha-beta 截止搜索的极小极大算法定位

• 深度提前层。

• Alpha和Beta是算法的参数。

• Record记录当前最好的走法。

evaluate_and_choose([ Move | Moves ], Position, D, Alpha, Beta, Move1, BestMove ) :-
    move( Move, Position, Positionl ),
    alpha_beta( D, Positionl, Alpha, Beta, MoveX, Value ),
    Value1 is -Value,
    cutoff( Move, Value1, D, Alpha, Beta, Moves, Position, Move1, BestMove ).

evaluate_and_choose( [], Position, D, Alpha, Beta, Move, ( Move, Alpha )).

alpha_beta( 0, Position, Alpha, Beta, Move, Value ) :- 
    value( Position, Value ).
    
alpha_beta( D, Position, Alpha, Beta, Move, Value ) :- 
    findall( M, move( Position, M ), Moves ),
    Alphal is -Beta,
    Betal is -Alpha,
    D1 is D-l,
    evaluate_and_choose( Moves, Position, D1, Alphal, Betal, nil, ( Move, Value )).

    
cutoff( Move, Value, D, Alpha, Beta, Moves, Position, Movel, ( Move,Value )) :- 
    Value > Beta.
cutoff(Move, Value, D, Alpha, Beta, Moves, Position, Movel, BestMove ) :- 
    Alpha < Value, Value < Beta,
    evaluate_and_choose( Moves, Position, D, Value, Beta, Move, BestMove ).

cutoff( Move, Value, D, Alpha, Beta, Moves, Position, Movel, BestMove ) :- 
    Value < Alpha,
    evaluate_and_choose( Moves, Position, D, Alpha, Beta, Move1, BestMove ).