|
|
pl:prolog:pllib:minimax_move [2019/06/27 15:50] |
pl:prolog:pllib:minimax_move [2019/06/27 15:50] (aktualna) |
| ====== Minimax move ====== |
| {{tag>problem_solving}} |
| ===== Description ===== |
| Choosing a move using minimax with alpha-beta pruning |
| |
| **Source**: The Art of Prolog |
| ===== Download ===== |
| Program source code: {{minimax_move.pl}} |
| ===== Listing ===== |
| <code prolog> |
| /* |
| 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,Position1), |
| alpha_beta(D,Position1,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,A)). |
| |
| 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), |
| Alpha1 is -Beta, |
| Beta1 is -Alpha, |
| D1 is D-1, |
| evaluate_and_choose(Moves,Position,D1,Alpha1,Beta1,nil,(Move,Value)). |
| |
| cutoff(Move,Value,D,Alpha,Beta,Moves,Position,Move1,(Move,Value)) :- |
| Value >= Beta. |
| cutoff(Move,Value,D,Alpha,Beta,Moves,Position,Move1,BestMove) :- |
| Alpha < Value, Value < Beta, |
| evaluate_and_choose(Moves,Position,D,Value,Beta,Move,BestMove). |
| cutoff(Move,Value,D,Alpha,Beta,Moves,Position,Move1,BestMove) :- |
| Value =< Alpha, |
| evaluate_and_choose(Moves,Position,D,Alpha,Beta,Move1,BestMove). |
| |
| % Program 20.11 Choosing a move using minimax with alpha-beta pruning |
| </code> |
| ===== Comments ===== |
| |