% Illustrative 3-ply game tree modified
% from Ivan Bratko's book

moves(X,Y,N) :-
    findall(X,legal(N,X),Y),
    Y \= [].

legal(N,X) :-
    min(N),
    member(V,X),
    var(V),
    V = o.
legal(N,X) :-
    max(N),
    member(V,X),
    var(V),
    V = x.

min(-1).
max(1).

utility(P,V) :- 
    utility1(P,V), 
    write('utility at node '),writeln(P=V).

utility1([X1,X2,X3,_,_,_,_,_,_],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([_,_,_,X1,X2,X3,_,_,_],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([_,_,_,_,_,_,X1,X2,X3],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([X1,_,_,X2,_,_,X3,_,_],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([_,X1,_,_,X2,_,_,X3,_],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([_,_,X1,_,_,X2,_,_,X3],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([X1,_,_,_,X2,_,_,_,X3],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([_,_,X1,_,X2,_,X3,_,_],C) :- X1 == x, X1 == X2, X2 == X3, C is 100.
utility1([O1,O2,O3,_,_,_,_,_,_],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([_,_,_,O1,O2,O3,_,_,_],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([_,_,_,_,_,_,O1,O2,O3],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([O1,_,_,O2,_,_,O3,_,_],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([_,O1,_,_,O2,_,_,O3,_],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([_,_,O1,_,_,O2,_,_,O3],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([O1,_,_,_,O2,_,_,_,O3],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([_,_,O1,_,O2,_,O3,_,_],C) :- O1 == o, O1 == O2, O2 == O3, C is -100.
utility1([X,O1,O2,_,_,_,_,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([O1,X,O2,_,_,_,_,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([O1,O2,X,_,_,_,_,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,_,X,O1,O2,_,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,_,O1,X,O2,_,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,_,O1,O2,X,_,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,_,_,_,_,X,O1,O2],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,_,_,_,_,O1,X,O2],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,_,_,_,_,O1,O2,X],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([X,_,_,O1,_,_,O2,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([O1,_,_,X,_,_,O2,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([O1,_,_,O2,_,_,X,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,X,_,_,O1,_,_,O2,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,O1,_,_,X,_,_,O2,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,O1,_,_,O2,_,_,X,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,X,_,_,O1,_,_,O2],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,O1,_,_,X,_,_,O2],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,O1,_,_,O2,_,_,X],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([X,_,_,_,O1,_,_,_,O2],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([O1,_,_,_,X,_,_,_,O2],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([O1,_,_,_,O2,_,_,_,X],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,X,_,O1,_,O2,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,O1,_,X,_,O2,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([_,_,O1,_,O2,_,X,_,_],C) :- X == x, O1 == o, O2 == O1, C is 50.
utility1([O,X1,X2,_,_,_,_,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([X1,O,X2,_,_,_,_,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([X1,X2,O,_,_,_,_,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,_,O,X1,X2,_,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,_,X1,O,X2,_,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,_,X1,X2,O,_,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,_,_,_,_,O,X1,X2],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,_,_,_,_,X1,O,X2],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,_,_,_,_,X1,X2,O],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([O,_,_,X1,_,_,X2,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([X1,_,_,O,_,_,X2,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([X1,_,_,X2,_,_,O,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,O,_,_,_,X1,_,_,X2],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,X1,_,_,O,_,_,X2,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,X1,_,_,X2,_,_,O,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,X1,_,_,O,_,_,X2],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,X1,_,_,X2,_,_,O],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,O,_,_,X1,_,_,X2],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([O,_,_,_,X1,_,_,_,X2],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([X1,_,_,_,O,_,_,_,X2],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([X1,_,_,_,X2,_,_,_,O],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,O,_,X1,_,X2,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,X1,_,O,_,X2,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,_,X1,_,X2,_,O,_,_],C) :- X1 == x, X2 == X1, O == o, C is -50.
utility1([_,X1,X2,_,_,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([X1,_,X2,_,_,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([X1,X2,_,_,_,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,X1,X2,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,X1,_,X2,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,X1,X2,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,_,_,_,X1,X2],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,_,_,X1,_,X2],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,_,_,X1,X2,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,X1,_,_,X2,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([X1,_,_,_,_,_,X2,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([X1,_,_,X2,_,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,X1,_,_,X2,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,X1,_,_,_,_,_,X2,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,X1,_,_,X2,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,_,X1,_,_,X2],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,X1,_,_,_,_,_,X2],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,X1,_,_,X2,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,X1,_,_,_,X2],C) :- X1 == x, X2 == X1, C is 10.
utility1([X1,_,_,_,_,_,_,_,X2],C) :- X1 == x, X2 == X1, C is 10.
utility1([X1,_,_,_,X2,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,_,_,X1,_,X2,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,X1,_,_,_,X2,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,_,X1,_,X2,_,_,_,_],C) :- X1 == x, X2 == X1, C is 10.
utility1([_,O1,O2,_,_,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([O1,_,O2,_,_,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([O1,O2,_,_,_,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,O1,O2,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,O1,_,O2,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,O1,O2,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,_,_,_,O1,O2],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,_,_,O1,_,O2],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,_,_,O1,O2,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,O1,_,_,O2,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([O1,_,_,_,_,_,O2,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([O1,_,_,O2,_,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,O1,_,_,O2,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,O1,_,_,_,_,_,O2,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,O1,_,_,O2,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,_,O1,_,_,O2],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,O1,_,_,_,_,_,O2],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,O1,_,_,O2,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,O1,_,_,_,O2],C) :- O1 == o, O2 == O1, C is -10.
utility1([O1,_,_,_,_,_,_,_,O2],C) :- O1 == o, O2 == O1, C is -10.
utility1([O1,_,_,_,O2,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,O1,_,O2,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,O1,_,_,_,O2,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,O1,_,O2,_,_,_,_],C) :- O1 == o, O2 == O1, C is -10.
utility1([_,_,_,_,X,_,_,_,_],C) :- X == x, C is 5.
utility1([_,_,_,_,O,_,_,_,_],C) :- O == o, C is -5.
utility1([X,_,_,_,_,_,_,_,_],C) :- X == x, C is 2.
utility1([_,_,X,_,_,_,_,_,_],C) :- X == x, C is 2.
utility1([_,_,_,_,_,_,X,_,_],C) :- X == x, C is 2.
utility1([_,_,_,_,_,_,_,_,X],C) :- X == x, C is 2.
utility1([O,_,_,_,_,_,_,_,_],C) :- O == o, C is -2.
utility1([_,_,O,_,_,_,_,_,_],C) :- O == o, C is -2.
utility1([_,_,_,_,_,_,O,_,_],C) :- O == o, C is -2.
utility1([_,_,_,_,_,_,_,_,O],C) :- O == o, C is -2.
utility1([A,B,C,D,E,F,G,H,I],0) :-
    ground([A,B,C,D,E,F,G,H,I]).
utility1([_,_,_,_,_,_,_,_,_],C) :- C is 0.