0

I'm working on implementing an AI opponent using the Minimax algorithm for the well-known game of "Nim", which is a two-player game where each player takes turns removing 1 to 3 matchsticks from a pile. The player who removes the last matchstick loses the game.

I've implemented the game in Prolog, and the human player's side is working as expected. However, I'm facing an issue with the AI opponent's decision-making. The AI is always selecting 1 matchstick as its best move, which isn't the expected behavior.

Here's the code I am working on:

% Predicate for the artificial opponent
opponent(ai).

% Simple evaluation function for the Minimax algorithm
evaluate(0, -1). % Opponent wins if the other player has to remove the last matchstick
evaluate(_, 1).  % Player wins if the opponent has to remove the last matchstick

% Minimax algorithm
minimax(State, Depth, _, Value) :-
    evaluate(State, Value), % Base case: evaluate the state
    !.
minimax(State, Depth, Player, Value) :-
    Depth > 0,
    NextDepth is Depth - 1,
    findall(Value1-Action,
            (valid_move(State, Action), make_move(State, Action, NextState), 
             change_player(Player, Opponent), minimax(NextState, NextDepth, Opponent, Value1)),
            ValuesActions),
    best_value(ValuesActions, BestValue),
    select(BestValue-Action, ValuesActions, _),
    Value is -BestValue.

% Find the best value among possible values
best_value([Value-_|Rest], BestValue) :-
    best_value(Rest, Value, BestValue).

best_value([], BestValue, BestValue).
best_value([Value-_|Rest], CurrentBest, BestValue) :-
    Value > CurrentBest,
    best_value(Rest, Value, BestValue).
best_value([_|Rest], CurrentBest, BestValue) :-
    best_value(Rest, CurrentBest, BestValue).

% Check if a move is valid
valid_move(State, Action) :-
    State >= Action,
    Action >= 1,
    Action =< 3.

% Perform a move
make_move(State, Action, NewState) :-
    NewState is State - Action.

% Change the active player
change_player(player, opponent).
change_player(opponent, player).

% Predicate to play a game
play_game :-
    write("Do you want to play a game? (yes/no) "),
    read(Response),
    (Response = yes -> 
        write("You start with a pile of 21 matchsticks."), nl,
        play_game_human(21)
    ; true).

% Predicate to play the human player's turn
play_game_human(Pile) :-
    write("Your turn: "),
    read(Action),
    (valid_move(Pile, Action) ->
        NewPile is Pile - Action,
        (NewPile = 0 -> write("You won!"), nl ; play_game_opponent(NewPile))
    ;
        write("Invalid move. Choose 1, 2, or 3."),
        nl,
        play_game_human(Pile)
    ).

% Predicate to play the opponent's turn
play_game_opponent(Pile) :-
    minimax(Pile, 10, opponent, BestAction), % Depth set to 10
    write("The opponent played: "),
    write(BestAction),
    nl,
    NewPile is Pile - BestAction,
    (NewPile = 0 -> write("You lost!"), nl ; play_game_human(NewPile)).

:- initialization(play_game).

Despite implementing the algorithm as I understand it, the AI opponent consistently chooses 1 matchstick as its best move, even when other options are available.

I suspect that there might be an issue with how I'm calculating the best move or possibly how the evaluation function interacts with the Minimax algorithm. I've tried debugging and reviewing my code, but I can't seem to identify the root cause of the problem.

Could someone help me troubleshoot this issue? I'd like to ensure that my AI opponent correctly selects the best move based on the Minimax algorithm's logic.

false
  • 10,264
  • 13
  • 101
  • 209
dya47
  • 11
  • 2
  • `minimax(State, Depth, _, Value) :- evaluate(State, Value), % Base case: evaluate the state !.` looks suspicious. In what way is it a base case? It looks like it will always succeed and CUT CUT CUT the search tree. – TessellatingHeckler Aug 24 '23 at 14:24
  • Good point ! The '!' is useless here, I removed it, but I keep getting 1 as the best move for the AI opponent – dya47 Aug 24 '23 at 14:31
  • By that rule `evaluate(State, Value)` -> `evaluate(_, 1).` so value 1 is always a correct solution for any pile state. There's nothing pushing it to do the second minimax rule, I think (I haven't tried to run it). The cut explicitly stopped it from doing the big search, but now it will leave a choicepoint and not do the big search unless backtracking happens. – TessellatingHeckler Aug 24 '23 at 14:46
  • Very related: https://stackoverflow.com/questions/75950249/the-game-of-23-matches-in-swiprolog – brebs Aug 24 '23 at 17:05

0 Answers0