Best-first search
6.1. Best-first search#
We will assume that a predicate eval/2 is defined, which returns for a given node in the search space an estimate of the distance between that node and a goal node. The children of the current node are added to the agenda according to their heuristic evaluation (lowest values first). Thus, the agenda will always be sorted.
% best-first search
% goal/1, children/2 and eval/2 depend on
% the search problem at hand
search_bstf([Goal|Rest],Goal):-
goal(Goal).
search_bstf([Current|Rest],Goal):-
children(Current,Children),
add_bstf(Children,Rest,NewAgenda),
search_bstf(NewAgenda,Goal).
% add_bstf(A,B,C) <- C contains the elements of A and B
% (B and C sorted according to eval/2)
add_bstf([],Agenda,Agenda).
add_bstf([Child|Children],OldAgenda,NewAgenda):-
add_one(Child,OldAgenda,TmpAgenda),
add_bstf(Children,TmpAgenda,NewAgenda).
% add_one(S,A,B) <- B is A with S inserted acc. to eval/2
add_one(Child,OldAgenda,NewAgenda):-
eval(Child,Value),
add_one(Value,Child,OldAgenda,NewAgenda).
add_one(Value,Child,[],[Child]).
add_one(Value,Child,[Node|Rest],[Child,Node|Rest]):-
eval(Node,V),
Value<V.
add_one(Value,Child,[Node|Rest],[Node|NewRest]):-
eval(Node,V),
Value>=V,
add_one(Value,Child,Rest,NewRest).
add_bstf/3 operates by inserting the new children one by one in the current agenda. Note that if the list of children were already sorted, it could more efficiently be merged with the current agenda.
Suppose the call children(Current,Children) results in an ordered list of children. Write a predicate merge/3 which directly merges this list with the current agenda.
As an application of best-first search, consider the following puzzle. We have a board consisting of seven consecutive squares, three black tiles and three white tiles, initially placed on the board as in Figure 6.1. The goal is to move the tiles in such a way that the black tiles are to the right of the white tiles (the position of the empty square is immaterial). Each move consists of moving one tile into the empty square, which is allowed if there are at most two other tiles in between. The cost of such a move is 1 if there are no tiles in between, and equals the number of tiles jumped over otherwise.
Figure 6.1 Initial board position.#
When not to use lists#
Recall (Section 1.3) that [b,b,b,e,w,w,w] is an alternative notation for the term .(b,.(b,.(b,.(e,.(w,.(w,.(w,[]))))))). This term contains, besides the seven constants in the linear notation, one additional constant (’[]’) and seven functors (’.’), each with two arguments. In contrast, a ‘flat’ term p(b,b,b,e,w,w,w) contains only one additional functor, with seven arguments. Recursive datastructures like lists are useful if the number of items to be stored is not fixed, but they require significantly more storage space. In general, if the number of items is fixed, a non-recursive datastructure is preferred as far as memory is concerned. Given a term T holding the items, the call arg(N,T,A) retrieves the Nth argument A. However, arg/3 requires N to be instantiated, and cannot be used to generate all arguments on backtracking. Therefore, lists are sometimes used even if the nature of the data is non-recursive.
This puzzle defines a search space, in which nodes are board positions and arcs are single moves. We choose a simple list representation for board positions: e.g. [b,b,b,e,w,w,w] represents the starting position of Figure 6.1. The following predicates examine and manipulate board positions:
% get_tile(P,N,T) <- pos. P contains tile T at square N
get_tile(Pos,N,T):-
get_tile(Pos,1,N,T).
get_tile([X|_Xs],N,N,X).
get_tile([_X|Xs],N0,N,Y):-
N1 is N0+1,
get_tile(Xs,N1,N,Y).
% replace(P,N,T,P1) <- P1 is P with tile T at square N
replace([_X|Xs],1,Y,[Y|Xs]).
replace([X|Xs],N,Y,[X|Zs]):-
N>1, N1 is N-1,
replace(Xs,N1,Y,Zs).
We use the above best-first search procedure, with a number of changes. First, rather than returning the goal position found, the program should construct a sequence of moves by which the goal position is reached. Therefore, nodes that are examined during the search process are collected in the list Visited. After a goal position has been found, the solution path and its total cost are reconstructed from the list Visited by means of the predicate construct_moves/6.
Secondly, the items on the agenda are represented as pairs v(Value,Move), where Value is the heuristic evaluation of the position reached by Move. Children of the current position are generated by means of the setof/3 predicate, which yields a sorted list. By putting the heuristic Value as the first argument of the functor v, the list Children is therefore sorted according to increasing heuristic value. Therefore, this list can be simply merged with the current agenda to yield the new agenda. The program thus looks as follows:
% tiles(M,C) <- moves M lead to a goal position at cost C
% (best-first search strategy)
tiles(Moves,Cost):-
start(Start),
eval(Start,Value),
tiles_a([v(Value,Start)],Final,[],Visited),
construct_moves(Final,Visited,[],Moves,0,Cost).
% tiles_a(A,M,V0,V) <- goal position can be reached from
% one of the positions on A with last
% move M (best-first strategy)
tiles_a([v(V,LastMove)|Rest],LastMove,Visited,Visited):-
goal(LastMove).
tiles_a([v(V,LastMove)|Rest],Goal,Visited0,Visited):-
show_move(LastMove,V),
setof0(v(Value,NextMove),
( move(LastMove,NextMove),
eval(NextMove,Value) ),
Children),
merge(Children,Rest,NewAgenda), % best-first
tiles_a(NewAgenda,Goal,[LastMove|Visited0],Visited).
%%% merge/3: see exercise 2.3.1
setof0/3 is a variant of setof/3 which succeeds with the empty list if no solutions can be found (see Section 10.2 (appendix)).
A move from OldPos to NewPos is represented by a triple
m(OldPos,NewPos,Cost)
where Cost specifies the cost of the move. According to the principle of data abstraction, this representation is kept local to the following predicates:
% move(m(X,P,Y),m(P,NP,C)) <- position NP can be reached
% from position P in one move
% at cost C
move(m(OldPos,Pos,OldCost),m(Pos,NewPos,Cost)):-
get_tile(Pos,Ne,e),get_tile(Pos,Nbw,BW),not(BW=e),
Diff is abs(Ne-Nbw),Diff<4,
replace(Pos,Ne,BW,Pos1),
replace(Pos1,Nbw,e,NewPos),
( Diff=1 -> Cost=1
; otherwise -> Cost is Diff-1 ).
start(m(noparent,[b,b,b,e,w,w,w],0)).
% reconstruct total cost and path from visited nodes
construct_moves(m(noparent,Start,0),V,Ms,[Start|Ms],Cost,Cost).
construct_moves(m(P,Pos,C),Visited,Ms0,Ms,Cost0,Cost):-
element(m(GP,P,C1),Visited), % GP is parent of P
Cost1 is Cost0+C,
construct_moves(m(GP,P,C1),Visited,[Pos|Ms0],Ms,Cost1,Cost).
show_move(m(P,Pos,C),Value):-
write(Pos-Value),nl.
Finally, we have to choose a heuristic evaluation function. A first idea is to count, for each white tile, the number of black tiles to the left of it:
goal(LastMove):-
eval(LastMove,0).
eval(m(P,Pos,C),Value):-
bLeftOfw(Pos,Value).
bLeftOfw(Pos,Value):-
findall((Nb,Nw),
(get_tile(Pos,Nb,b),get_tile(Pos,Nw,w),Nb<Nw),
L),
length(L,Value).
Note that this program actually counts the number of solutions to the query
?-get_tile(Pos,Nb,b),get_tile(Pos,Nw,w),Nb<Nw.
by determining the length of the list that is returned by the second-order predicate findall/3.
Exercise 6.2 #
Rewrite bLeftOfw/2 such that it uses only first-order predicates.
The program writes every move it considers on the screen, together with its heuristic evaluation. For instance, the query
?-tiles(M,C).
results in the following output:
[b,b,b,e,w,w,w]-9
[b,b,b,w,e,w,w]-9
[b,b,e,w,b,w,w]-8
[b,b,w,w,b,e,w]-7
[b,b,w,w,b,w,e]-7
[b,b,w,w,e,w,b]-6
[b,e,w,w,b,w,b]-4
[b,w,e,w,b,w,b]-4
[e,w,b,w,b,w,b]-3
[w,w,b,e,b,w,b]-2
[w,w,b,w,b,e,b]-1
M = [[b,b,b,e,w,w,w],[b,b,b,w,e,w,w],[b,b,e,w,b,w,w],
[b,b,w,w,b,e,w],[b,b,w,w,b,w,e],[b,b,w,w,e,w,b],
[b,e,w,w,b,w,b],[b,w,e,w,b,w,b],[e,w,b,w,b,w,b],
[w,w,b,e,b,w,b],[w,w,b,w,b,e,b],[w,w,e,w,b,b,b]]
C = 15
Since the only moves that are considered are those that are on the final solution path, there is no backtracking. This seems to suggest that the heuristic works quite well. On the other hand, the first few moves seem a bit awkward: in particular, the first and the fourth move are relatively expensive.
Tip
Try it out in SWISH:
%%% all above code taken together %%%
Let’s try another heuristic, which counts the number of tiles out of place: a wrong tile on the first or seventh square gives 3, on the second or sixth square 2, and on the third or fifth square 1.
eval(Pos,Value):-
outOfPlace(Pos,1,0,Value).
outOfPlace(Pos,8,N,N).
outOfPlace(Pos,K,N0,N):-
K<8, K1 is K+1,
( K<4,get_tile(Pos,K,b) -> N1 is N0-(K-4)
; K>4,get_tile(Pos,K,w) -> N1 is N0+(K-4)
; otherwise -> N1=N0 ),
outOfPlace(Pos,K1,N1,N).
We get the following result:
[b,b,b,e,w,w,w]-12
[b,b,b,w,w,w,e]-9
[e,b,b,b,w,w,w]-9
[b,b,b,w,w,e,w]-10
[b,b,b,w,w,w,e]-9
[b,b,e,w,w,b,w]-9
[e,b,b,w,w,b,w]-7
[w,b,b,e,w,b,w]-7
[w,b,b,w,w,b,e]-4
[w,b,b,w,w,e,b]-4
[w,b,e,w,w,b,b]-3
[w,b,w,w,e,b,b]-2
M = [[b,b,b,e,w,w,w],[b,b,b,w,w,e,w],[b,b,e,w,w,b,w],
[e,b,b,w,w,b,w],[w,b,b,e,w,b,w],[w,b,b,w,w,b,e],
[w,b,b,w,w,e,b],[w,b,e,w,w,b,b],[w,b,w,w,e,b,b],
[w,e,w,w,b,b,b]]
C = 14
We observe a couple of differences with the previous heuristic. First of all, there is backtracking: the first, second and fourth moves are not pursued any further. Furthermore, the solution found requires two moves less, and is also cheaper.
Figure 6.2 Solutions found for different heuristics.#
Tip
You can easily try this out in the SWISH box above, the outOfPlace/4 call is already there in eval/2, but commented out.
This improvement seems to suggest that an increased punishment for wrongly placed tiles might lead to an even cheaper solution. For instance, we could increase the punishment to 4, 3 and 2, respectively, by adapting the predicate outOfPlace/4 (try it!). This leads to the following sequence of moves:
[b,b,b,e,w,w,w]-18
[b,b,b,w,w,w,e]-14
[e,b,b,b,w,w,w]-14
[b,b,b,w,w,e,w]-15
[b,b,e,w,w,b,w]-13
[b,b,w,w,e,b,w]-11
[b,e,w,w,b,b,w]-8
[e,b,w,w,b,b,w]-7
[w,b,e,w,b,b,w]-7
[w,e,b,w,b,b,w]-6
[e,w,b,w,b,b,w]-6
[w,w,b,e,b,b,w]-6
[w,w,b,w,b,b,e]-2
[w,w,b,w,b,e,b]-2
M = [[b,b,b,e,w,w,w],[b,b,b,w,w,e,w],[b,b,e,w,w,b,w],
[b,b,w,w,e,b,w],[b,e,w,w,b,b,w],[e,b,w,w,b,b,w],
[w,b,e,w,b,b,w],[w,e,b,w,b,b,w],[w,w,b,e,b,b,w],
[w,w,b,w,b,b,e],[w,w,b,w,b,e,b],[w,w,e,w,b,b,b]]
C = 15
Obviously, this heuristic works no better than the previous two: it does not find an optimal solution, and it investigates more moves than the first heuristic. In Figure 6.2, the solutions found by the three heuristics are compared. In the next section, we will investigate the conditions under which a heuristic is guaranteed to find an optimal solution.