Simple game tree example

Example tree from Bratko chapter 11

tree1.gv

tree1.pl

% tree1.pl
:- module(tree1, [plie/3, goal/1]).
plie(a, 1, b).
plie(a, 2, c).
plie(b, 1, d).
plie(b, 2, e).
plie(c, 1, f).
plie(c, 2, g).
plie(d, 1, h).
plie(e, 1, i).
plie(e, 2, j).
plie(f, 1, k).
plie(h, 1, d).
goal(f).
goal(j).

Unit Tests

Based on example

%solve.plt
:- begin_tests(solve).
:- consult('solve.pl').

test(start_a, [nondet]) :- solve(a, [2, 1]).
test(start_b, [nondet]) :- solve(b, [2, 2]).
test(start_c, [nondet]) :- solve(c, [1]).
test(start_f, [fail]) :- solve(f, []).

:- end_tests(solve).

To run the tests:

?- consult('solve.plt').
true.

?- load_test_files([make(all)]).
true.

?- run_tests.
% PL-Unit: solve .... done
% All 4 tests passed
true.

Template

Using the breadth-first example from Bratko as the template.

% Figure 11.11  A more efficient program than that of Figure 11.10 for 
% the breadth-first search. The improvement is based on using 
% the difference-pair representation for the list of candidate paths. 
% Procedure extend is as in Figure 11.10.


% solve( Start, Solution):
%   Solution is a path (in reverse order) from Start to a goal

solve( Start, Solution)  :-
  breadthfirst( [ [Start] | Z] - Z, Solution).

breadthfirst( [ [Node | Path] | _] - _, [Node | Path] )  :-
  goal( Node).

breadthfirst( [Path | Paths] - Z, Solution)  :-
  extend( Path, NewPaths),
  append( NewPaths, Z1, Z),              % Add NewPaths at end
  Paths \== Z1,                        % Set of candidates not empty
  breadthfirst( Paths - Z1, Solution).

extend( [Node | Path], NewPaths)  :-
  findall( [NewNode, Node | Path],
         ( s( Node, NewNode), \+ member( NewNode, [Node | Path] ) ),
         NewPaths).

Function that satisfies the tests

This is modified to return the edge labels rather than the states traversed in reverse order.

%solve.pl
:-use_module(tree1).

s(_Move0-State0, Move-State1) :- plie(State0, Move, State1).

% solve( Start, Solution):
%   Solution is a path (in reverse order) from Start to a goal

solve( Start, Solution)  :-
  breadthfirst( [ [noop-Start] | Z] - Z, Path),
  findall(Move, member(Move-_State, Path), Moves),
  reverse(Moves, [noop|Solution]).

breadthfirst( [ [Move-State | Path] | _] - _, [Move-State | Path] )  :-
  goal(State).

breadthfirst( [Path | Paths] - Z, Solution)  :-
  extend( Path, NewPaths),
  append( NewPaths, Z1, Z),              % Add NewPaths at end
  Paths \== Z1,                        % Set of candidates not empty
  breadthfirst( Paths - Z1, Solution).

extend( [Node | Path], NewPaths)  :-
  findall( [NewNode, Node | Path],
         ( s( Node, NewNode), \+ member( NewNode, [Node | Path] ) ),
         NewPaths).