move([X|T],[P|T]) :- X>0,P is X-1.
move([H|X],[H|Y]) :- move(X,Y).
move([X|T],[Y|T]) :- P is X-1, P>0,move([P|T],[Y|T]).


gagne(L):-move(L,G), not(gagne(G)),!.


dec2bin_inv(0,[0]):-!.
dec2bin_inv(1,[1]):-!.
dec2bin_inv(N,[X|L]):-X is N mod 2, K is N//2, dec2bin_inv(K,L).

somme_xor([],L,L).
somme_xor(L,[],L).
somme_xor([X|L],[X|G],[0|R]):-!,somme_xor(L,G,R).
somme_xor([_|L],[_|G],[1|R]):-somme_xor(L,G,R).

somme_xor_iteree([],[]).
somme_xor_iteree([L],L).
somme_xor_iteree([L1,L2|L],R):-somme_xor(L1,L2,U),somme_xor_iteree(L,T),
somme_xor(U,T,R).


bin_inv2dec([],0).
bin_inv2dec([X|L],R):- bin_inv2dec(L,T), R is X + 2*T.


convert([],[]).
convert([N|L],[X|R]):-dec2bin_inv(N,X),convert(L,R).


somme_nim(L,R):-convert(L,B),somme_xor_iteree(B,C),bin_inv2dec(C,R).


gagne_bis(L):-somme_nim(L,R), R>0.

/* l interface minimale */

montre_ligne(0):-nl.
montre_ligne(N):-N>0,write('|'),M is N-1,montre_ligne(M).

montreblanc(3):-write('   ').
montreblanc(2):-write('  ').
montreblanc(1):-write(' ').

montre_pos1([]):-!.
montre_pos1([X|L]):-
montre_ligne(X), montre_pos1(L).

montre_pos(L):-write('\n'),montre_pos1(L),write('\n').

bouge(X,Y):-write('de quelle rangée?'),nl,read(X),
            write('combien?'),nl,read(Y).

/* change(Current,Rangee,Combien,Result)*/

change([],[]).
change([X|L],1,N,[Y|L]):-Y is X-N.
change([X|L],M,N,[X|G]):- M>1, P is M-1, change(L,P,N,G).

verifie(L,X,Y,Z):-change(L,X,Y,Z),move(L,Z).


/* choix du prochain coup par le programme */
   
    prochain(L,N):- move(L,N),not(gagne_bis(N)),!. 
    prochain(L,N):-move(L,N),!.

/* test de pos finale */

somma([],0).
somma([M|L],N):-somma(L,K),N is K+M.

finale(L):-somma(L,N), N=0.

jeu(L):-
montre_pos(L), 
(finale(L)->(nl,write('je gagne'),nl,!);bouge(X,Y)),
verifie(L,X,Y,Z),
montre_pos(Z), 
(finale(Z)->(nl,write('tu gagnes\n'),nl,!); prochain(Z,Next)),
write('\na moi\n'),
jeu(Next).