% nim.prolog
%
%
% Copyright 2007 Kozma Laszlo (www.LKozma.net)
%
% This is free software; you can redistribute it and/or modify
% it under the terms of the GNU General Public License as published by
% the Free Software Foundation; either version 2 of the License, or
% (at your option) any later version.
%
%
%
% Tested with GNU Prolog (gprolog)
% Open with:
% consult('nim.prolog').
%
% Functions to call:
%
% nim_value(K,X).   % returns in X the nim-value of a board of size K
% grundy(K,X).      % returns in X the nim-values of all boards of size 0..K
% solve(K,X).       % returns in X whether K is Winner or Loser
% win_or_lose(K,X)  % returns Win/Lose for all board-sizes 0..K
% next_move(P,X)    % returns the next position where player should move from position P
%
% Examples:
%
% nim_value(10,X).
% next_move([4,5],X).
%

% List of all possible splits in two of a number 
splits(0,[]):-!.
splits(1,[]):-!.
splits(X,[[1,X1]|NS]):-
	X1 is X-1, 
	splits(X,2,NS).
splits(X,Y,[]):-2*Y>X,!.
splits(X,X1,[[X1,R1]|RX]):-
	R1 is X-X1, 
	X2 is X1+1, 
	splits(X,X2,RX).


% Possible successors for a position
successor(0,[]):-!.
successor(1,[[0]]):-!.
successor(2,[[0]]):-!.
successor(X,[[X2],[X3]|RX]):-
	X2 is X-2, 
	X3 is X-3, 
	splits(X3,RX).


% Nim-value for a board of size n
:-dynamic(nim_value/2).
nim_value(0,0):-!.
nim_value(1,1):-!.
nim_value(X,N):-
	successor(X,S),
	solve_all(S,NS), 
	mex(NS,N), 
	asserta(nim_value(X,N)),  % saving the nim-value for later use 
	!.

% Replace a list of positions with their nim-values
solve_all([],[]):-!.
solve_all([H|T],[NH|NT]):-
	nim_sum(H,NH), 
	solve_all(T,NT).


% Nim-sum (bitwise XOR)
nim_sum([],0):-!.
nim_sum([H|T],N):- 
	nim_value(H,NH), 
	nim_sum(T,NT), 
	N is NH^NT,
	!.


% Minimum-excluded value
mex([],0).
mex(N,M):-
	length(N,L), 
	generate(L,G), 
	mex(G,N,M).
mex([H|_],[],H):-!.
mex([H|T],N,X):-
	find(N,H),
	!,
	mex(T,N,X).
mex([H|_],_,H).


% Generate a list with numbers from 0 to K
generate(K,X):-
	NK is K+1,
	gen(NK,0,X).
gen(K,K,[]):-!.
gen(K,I,[I|T]):-
	NI is I+1, 
	gen(K,NI,T).


% See if an element exists in a list or not
find([H|_],H):-!.
find([_|T],X):-find(T,X).


% Find if a board with size K is Win or Lose
solve(0,'Lose'):-!.
solve(K,'Lose'):-
	nim_value(K, T), 
	T==0,
	!.
solve(_,'Win').


% Build list with nim-values of board-sizes from 0 to K
grundy(K,X):-
	generate(K,GK), 
	grundy_all(GK,X).
grundy_all([],[]):-
	!.
grundy_all([H|T],[[H,GH]|GT]):-
	nim_value(H,GH),
	grundy_all(T,GT).


% Build list with Win/Lose for all board-sizes from 0 to K
win_or_lose(K,X):-
	generate(K,GK), 
	wol_all(GK,X).
wol_all([],[]):-!.
wol_all([H|T],[[H,GH]|GT]):-
	solve(H,GH),
	wol_all(T,GT).


% Find best move in a position
next_move(P,'No good moves, this is a Lose position.'):- 
	solve_all([P],SP),
	nim_sum(SP,NS),
	NS==0,
	!.
next_move(P,PN):- 
	pick(P,E),
	move_in(P,E,PN),
	solve_all([PN],SP),
	nim_sum(SP,NS),
	NS==0,
	!.


% Pick one element after another from a list
pick([H|_],H).
pick([_|T],X):-pick(T,X).


% Move on element E of the board in every possible way. Return the resulting full board.
move_in(P,E,PN):-
	successor(E,S),
	pick(S,K),
	replace(P,E,K,PN).


% Replace element in the list with new list of element's partitions 
replace([H|T],H,X,R):-!,append(X,T,R).
replace([H|T],Y,X,[H|RT]):-replace(T,Y,X,RT).