Commits

Sebastian Schwarz committed 37008f1

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

  • Participants
  • Parent commits 7012599

Comments (0)

Files changed (2)

 % 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]).
+
+lookahead(8).
 
 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).
 
-lookahead(1).
-
 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
 % 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