Różnice między wybraną wersją a wersją aktualną.
| — |
pl:prolog:pllib:minimax_move [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| + | ====== 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 ===== | ||
