<!--H3: Section 6.1-->
(sec: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.
```Prolog
% 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.

```{exercise} ex:6.1
```

+++

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 {numref}`fig: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} /src/fig/part_ii/image016.svg
---
name: 'fig:6.1'
width: 40%
---
Initial board position.
```

```{infobox}
---
title: When not to use lists
---
<!--section 1.3-->
Recall ({numref}`sec: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 `N`th 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 {numref}`fig:6.1`. The following predicates examine and manipulate board positions:
```{swish} swish:get_tile
```

+++

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:
```Prolog
% 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
```
<!--exercise 6.1 {numref}`ex:6.1`-->
`setof0/3` is a variant of `setof/3` which succeeds with the empty list if no solutions can be found (see {numref}`Section %s (appendix)<apx:a.2>`).
<!--Appendix A.2-->

+++

A move from `OldPos` to `NewPos` is represented by a triple
```Prolog
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:
```Prolog
% 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:
```Prolog
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
```Prolog
?-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} ex:6.2
```

+++

The program writes every move it considers on the screen, together with its heuristic evaluation. For instance, the query
```Prolog
?-tiles(M,C).
```
results in the following output:
```Prolog
[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:
```{swish} swish:tiles
---
source-text-end: tiles-end
---
```
````

+++

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.
```Prolog
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:
```Prolog
[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} /src/fig/part_ii/image018.svg
---
name: 'fig:6.2'
width: 100%
---
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:
```Prolog
[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 {numref}`fig: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.