I tried to make the 23 matches game in SWIPROLOG (compiled here : https://swish.swi-prolog.org/).
What does this game represent? There are 23 matches on the table. There are two players and each of them has to take a few matches from the table. matches. Each player is allowed to take 1, 2, or 3 matches. The player who takes the last but one match loses the game.
I have implemented this as a game against the computer (once the computer chooses, once the user chooses, by entering the number of matches on the keyboard). It chooses the number of matches by a special strategy, in such a way, as to make the user lose, i.e. pick up matches in such a way, as to force the user to choose the penultimate match and lose. The 2 make choices until one of them loses.
That's pretty much what I managed to implement:
% Start game with 23 matches and computer as first player
joc :- joc(23, calculator, in_progress).
% Player's turn
joc(N, player, State) :-
nl,
write('There are '), write(N), write(' matches on the table.'), nl,
(State == finished ->
write('The game has ended.'), nl
;
write('It is your turn. '), nl,
read(M),
(valid_move(M, N) ->
N1 is N - M,
write('You chose '), write(M), write(' matches.'), nl,
(N1 =< 1 ->
write('The game has ended. You '), (State == won -> write('won!'), nl ; write('lost!'), nl),
joc(N1, calculator, finished)
;
joc(N1, calculator, in_progress)
)
;
write('Invalid move. Please try again.'), nl,
joc(N, player, State)
)
).
% Computer's turn
joc(N, calculator, State) :-
nl,
write('There are '), write(N), write(' matches on the table.'), nl,
(State == finished ->
write('The game has ended.'), nl
;
write('It is the computer\'s turn. '), nl,
optimal_move(N, M),
N1 is N - M,
write('The computer chose '), write(M), write(' matches.'), nl,
(N1 =< 1 ->
write('The game has ended. The computer '), (State == won -> write('won!'), nl ; write('lost!'), nl),
joc(N1, player, finished)
;
joc(N1, player, in_progress)
)
).
% Check if move is valid (between 1 and 3 matches, and not more than available matches)
valid_move(M, N) :-
M >= 1,
M =< 3,
M =< N.
% Calculate computer's optimal move
optimal_move(N, M) :-
X is N mod 4,
(X > 1 -> M is min(X-1, 3) ; M is max(min(N-2, 3), 1)).
The problem in this code, is strategy. I could not identify a strategy, in which the computer would always win. Here's an example. If there are 3 matches on the table and it is the computer's turn to pick, it picks 2 and thus loses, while it should pick 1 and the user loses.
My question : is it possible to identify a more efficient startegy, in which the calcualtor would always win(or almost always?) If so, I would be grateful for suggestions, and if possible, code. I'm a beginner in prologue, maybe something will escape me.
A quick analysis:
matches23(N, T) :-
between(1, 23, N),
matches23_(N, T).
matches23_(N, T) :-
% My move
take_matches(N, T, N0),
% Opponent's move, ensuring opponent cannot win
\+ matches23_(N0, _).
take_matches(N, T, N0) :-
between(1, 3, T),
N0 is N - T,
% Leave at least 1 remaining
N0 @>= 1.
Results in swi-prolog:
?- findall(N-T, matches23(N, T), Ps).
Ps = [2-1, 3-2, 4-3, 6-1, 7-2, 8-3, 10-1, 11-2, 12-3,
14-1, 15-2, 16-3, 18-1, 19-2, 20-3, 22-1, 23-2].
So, start the 23 game by removing 2 matches, and you have a guaranteed win if you follow the other steps :-)