CODEWITHSUNDEEP
prologchessminimaxalpha-beta-pruning
Benny Abramovici
Benny Abramovici

Reputation: 582

Depth limited alpha-beta in prolog

I'm building a chess engine in Prolog. The alpha-beta from "prolog programing for artificial intelligence" is not depth limited. Since it's not possible to search the whole tree in chess I'm trying to modify the code from the book to be depth limited but it's not working properly.

here is the book code:

alphabeta(Pos, Alpha, Beta, GoodPos, Val) :-
   moves(Pos, PosList), !,
   boundedbest( PosList, Alpha, Beta, GoodPos, Val)
    ;
get_pos_value(Pos,Val).                             % static value of Pos

boundedbest([Pos | PosList], Alpha, Beta, GoodPos, GoodVal) :-
   alphabeta( Pos, Alpha, Beta, _, Val),
   goodenough(PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal).

goodenough([],_,_,Pos, Val, Pos, Val) :- !.               % no other candidate

goodenough(_, Alpha, Beta, Pos, Val, Pos, Val) :-
   min_to_move(Pos), Val > Beta, !;                  % Maximizer attained upper bound
   max_to_move(Pos), Val < Alpha, !.                     % Minimizer attained lower bound

goodenough( PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal) :-
   newbounds( Alpha, Beta, Pos, Val, NewAlpha, NewBeta),  % Refine bounds
   boundedbest(PosList, NewAlpha, NewBeta, Pos1, Val1),
   betterof( Pos, Val, Pos1, Val1, GoodPos, GoodVal).

newbounds(Alpha, Beta, Pos, Val, Val, Beta) :-
   min_to_move(Pos), Val > Alpha, !.                    % Mazximizer increased lower bound

newbounds(Alpha, Beta, Pos, Val, Alpha, Val):-
   max_to_move(Pos), Val < Beta, !.                     % Minimizer decreased upper bound

newbounds( Alpha, Beta, _,_,Alpha, Beta).                   % otherwise bounds unchanged.

betterof(Pos, Val, Pos1, Val1, Pos, Val) :-                 % Pos better than Pos1
   min_to_move(Pos), Val > Val1, !;
   max_to_move(Pos), Val < Val1, !.

betterof(_,_,Pos1,Val1,Pos1,Val1).                          % otherwise Pos 1 better

My attempts to modify it to be depth limited are :

alphabeta(Pos, Alpha, Beta, Pos, Val, 0) :- % max depth of search recieved
   get_pos_value(Pos,Val).                      % static value of Pos


alphabeta(Pos, Alpha, Beta, GoodPos, Val, Depth) :-
   Depth > 0,
   moves(Pos, PosList), !,
   boundedbest( PosList, Alpha, Beta, GoodPos, Val,Depth).


alphabeta(Pos, Alpha, Beta, Pos, Val, Depth) :-
   Depth > 0,
   get_pos_value(Pos,Val).


boundedbest([Pos | PosList], Alpha, Beta, GoodPos, GoodVal,Depth) :-
   Depth is Depth - 1,
   alphabeta( Pos, Alpha, Beta, _, Val,Depth1),
   goodenough(PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal).

goodenough([],_,_,Pos, Val, Pos, Val) :- !.               % no other candidate

goodenough(_, Alpha, Beta, Pos, Val, Pos, Val) :-
   min_to_move(Pos), Val > Beta, !;                  % Maximizer attained upper bound
   max_to_move(Pos), Val < Alpha, !.                     % Minimizer attained lower bound

goodenough( PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal) :-
   newbounds( Alpha, Beta, Pos, Val, NewAlpha, NewBeta),  % Refine bounds
   boundedbest(PosList, NewAlpha, NewBeta, Pos1, Val1,_),
   betterof( Pos, Val, Pos1, Val1, GoodPos, GoodVal).

newbounds(Alpha, Beta, Pos, Val, Val, Beta) :-
   min_to_move(Pos), Val > Alpha, !.                % Mazximizer increased lower bound

newbounds(Alpha, Beta, Pos, Val, Alpha, Val):-
   max_to_move(Pos), Val < Beta, !.                     % Minimizer decreased upper bound

newbounds( Alpha, Beta, _,_,Alpha, Beta).                   % otherwise bounds unchanged.

betterof(Pos, Val, Pos1, Val1, Pos, Val) :-                 % Pos better than Pos1
   min_to_move(Pos), Val > Val1, !;
   max_to_move(Pos), Val < Val1, !.

betterof(_,_,Pos1,Val1,Pos1,Val1).                          % otherwise Pos 1 better

I would appreciate any help.

Upvotes: 1

Views: 717

Answers (1)

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

You have a typo in your code. And more importantly, you have a typo in your code that SWI-Prolog found and diagnosed for you. Do not ignore its warnings.

Look:

Warning: /home/isabelle/chess.pl:1:
    Singleton variables: [Alpha,Beta]
Warning: /home/isabelle/chess.pl:11:
    Singleton variables: [Alpha,Beta]
Warning: /home/isabelle/chess.pl:16:
    Singleton variables: [Depth1]
Warning: /home/isabelle/chess.pl:40:
    Singleton variables: [Pos1]

Specifically, in this clause starting on line 16:

boundedbest([Pos | PosList], Alpha, Beta, GoodPos, GoodVal,Depth) :-
   Depth is Depth - 1,
   alphabeta( Pos, Alpha, Beta, _, Val,Depth1),
   goodenough(PosList, Alpha, Beta, Pos, Val, GoodPos, GoodVal).

your use of Depth1 shows that you seem to understand that a new value needs to be computed and passed into the recursion. But you forgot to use this variable on the preceding line:

Depth is Depth - 1,

this should use Depth1 in the left hand side.

It is a mistake to even try to test code that has singleton warnings, since singleton warnings are often an indication of very serious bugs. This is the case here. When you see a singleton warning, the first thing you should do is to understand and fix it---any other interaction with the program is likely meaningless.

It is true that some of these warnings are "benign": The warnings for the clause on the first line do not seem to indicate bugs in that clause. Maybe you have seen some of these warnings and decided that they are harmless. The exact opposite is the case: Accepting such "spurious" singleton warnings means that you risk serious warnings slipping in.

(I haven't tested the corrected program since it's understandably incomplete.)

Upvotes: 3

Related Questions