CODEWITHSUNDEEP
prolog
Edem Yovo
Edem Yovo

Reputation: 11

Implementing alpha beta pruning in Prolog

I'm developing the game Teeko in Prolog and I try to implement alpha beta pruning but I do not know where to start. Could someone please guide me? I have already found the minimax algorithm.

Upvotes: 1

Views: 3370

Answers (1)

Anton Danilov
Anton Danilov

Reputation: 1276

I try to implement alpha beta pruning but I do not know where to start.

Could someone please guide me?

I have already found the minimax algorithm.

The short look into alpha beta pruning algorithm

Choosing a move using minimax with alpha-beta pruning

The new relation scheme is alpha_beta( Depth, Position, Alpha, Beta, Move, Value ),

which extends minimax by replacing the minimax flag with alpha and beta. The same relation holds with respect to evaluate_and_choose.

The program can be generalized by replacing the base case of alpha_beta by a test of whether the position is terminal. This is necessary in chess programs, for example, for handling incomplete piece exchanges.

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

  • Chooses the BestMove from the set of Moves from the current

  • Position using the minimax algorithm with alpha-beta cutoff searching

  • Depth ply ahead.

  • Alpha and Beta are the parameters of the algorithm.

  • Record records the current best move.

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 ).

Upvotes: 5

Related Questions