% A solution for exercise 5.4

flip(max, min).
flip(min, max).

% Relate states to their successor states
trans(state(N, P), state(N1, P1)) :-
    N >= 1,
    N1 is N - 1,
    flip(P, P1).

trans(state(N, P), state(N1, P1)) :-
    N >= 2,
    N1 is N - 2,
    flip(P, P1).

trans(state(N, P), state(N1, P1)) :-
    N >= 3,
    N1 is N - 3,
    flip(P, P1).

% find the maximum in a list, or -1 if empty
max_value([], -1).
max_value(Vs, N) :-
    max_list(Vs, N).            % We can utilise the predicate from
                                % the standard library

% find the minimum in a list, or 1 if empty
min_value([], 1).
min_value(Vs, N) :-
    min_list(Vs, N).

% relate a state to the minmax value (-1 or 1)
value(state(N, max), V) :-
    findall(S, trans(state(N, max), S), States), % find all successor states
    maplist(value, States, Values),              % compute their max values
    max_value(Values, V).                        % find the maximum
    
value(state(N, min), V) :-
    findall(S, trans(state(N, min), S), States), % find all successor states
    maplist(value, States, Values),              % compute their min values
    min_value(Values, V).                        % find the minimum

% We always expand all the way to the bottom of the search tree, so:
% value(S, 1)  <=> max wins from state S
% value(S, -1) <=> min wins from state S