# Commits

committed 37008f1

Used an easier and faster computation for the nim-sum in matches.pl.

• Participants
• Parent commits 7012599

# File game/matches.pl

% Implementation of the game module.  See game.pl for a description of the
% exported predicates.
:- module(game, [cutoff/4, end_state/3, lookahead/1, move/3]).
+:- use_module(util/misc, [foldl/4, xor/3]).
+

cutoff(P, _, Ss, U) :-
end_state(P, Ss, U).
-cutoff(P, D, [State|_], N) :-
-	D =< 0,
-	winning_state(State),
-	N is P * 666.
-	% smart evaluatuion strategies go here
+cutoff(P, D, [S | _], N) :- D =< 0,
+	(
+		nim_sum(S, 0)
+	->
+		N is P * 555
+	;
+		N is P * -555
+	).
+
+% nim_sum(+State, -Sum).
+% See: http://en.wikipedia.org/wiki/Nim#Mathematical_theory
+nim_sum(S, N) :-
+	maplist(length, S, Ls),
+	foldl(xor, 0, Ls, N).

% Unpack the last game state from the state sequence.
end_state(P, [S | _], U) :-
terminal(P, [[] | T], U) :-
terminal(P, T, U).

-
move(_, [S | Ss], [M, S | Ss]) :-
subst_element(A, B, S, M),
remove(A, B).
remove([_ | R], R1) :-
remove(R, R1).

-% toBinary(+DezimalNumber, -Solution, +InitialBinList)
-% if zero => do nothing
-toBinary(0, A, A) :- !.
-toBinary(Dez, Sol, A) :-
-	0 is Dez mod 2,
-	NewDez is Dez // 2,
-	toBinary(NewDez, Sol, [0|A]).
-toBinary(Dez, Sol, A) :-
-	1 is Dez mod 2,
-	NewDez is Dez // 2,
-	toBinary(NewDez, Sol, [1|A]).
-
-% computes the binary digit sum of two REVERSED lists
-binDigSum([],[],[]) :- !.
-binDigSum(List,[],List) :- !.
-binDigSum([],List,List) :- !.
-binDigSum([A|Rest1], [B|Rest2], [C|Rest3]) :-
-	C is (A+B) mod 2,
-	binDigSum(Rest1,Rest2,Rest3).
-
-winning_state([H1,H2,H3,H4,H5]) :-
-	length(H1,H1L),
-	length(H2,H2L),
-	length(H3,H3L),
-	length(H4,H4L),
-	length(H5,H5L),
-
-	toBinary(H1L,H1B,[]),
-	toBinary(H2L,H2B,[]),
-	toBinary(H3L,H3B,[]),
-	toBinary(H4L,H4B,[]),
-	toBinary(H5L,H5B,[]),
-
-	reverse(H1B,H1R),
-	reverse(H2B,H2R),
-	reverse(H3B,H3R),
-	reverse(H4B,H4R),
-	reverse(H5B,H5R),
-
-	binDigSum(H1R,H2R,S2),
-	binDigSum(S2,H3R,S3),
-	binDigSum(S3,H4R,S4),
-	binDigSum(S4,H5R,S5),
-
-	isZeroList(S5).
-
-isZeroList([]).
-isZeroList([0|R]) :-
-	isZeroList(R).
-
% vim: filetype=prolog

# File util/misc.pl

% A module for miscellaneous general purpose utility functions.
-:- module(misc, [foldl/4, keymax/3, keymin/3, max/3, min/3, replace_nth/4]).
+:- module(misc, [foldl/4, keymax/3, keymin/3, max/3, min/3, replace_nth/4, xor/3]).

% foldl(+TernaryPredicateName, +StartElement, +ListOfElements, ?Result).
% Recursively applies the TernaryPredicate to the StartElement and the head of
Nmm is N - 1,
replace_nth(Nmm, T1, E, T2).

+xor(X, Y, Z) :-
+	Z is X xor Y.
+
% vim: filetype=prolog