Minimax algorithm: how to skip a turn?

2
votes

I am using minimax algorithms with tic-tac-toe, reversi, etc.

How to properly add to the algorithm the possibility for one player to skip a turn (when there are no valid moves)?

01 function minimax(node, depth, maximizingPlayer)
02     if depth = 0 or node is a terminal node
03         return the heuristic value of node

04     if maximizingPlayer
05         bestValue := −∞
06         for each child of node
07             v := minimax(child, depth − 1, FALSE)
08             bestValue := max(bestValue, v)
09         return bestValue

10     else    (* minimizing player *)
11         bestValue := +∞
12         for each child of node
13             v := minimax(child, depth − 1, TRUE)
14             bestValue := min(bestValue, v)
15         return bestValue

Thanks.

2
minimax
That should be encoded in the graph, not the minimax algorithm. – kutschkem
It may depend on the game but don't you usually lose when you have no valid moves? That is what your algorithm already implements. – Henk Holterman
It depends on the game. Here is a quote from the reversi rules: "Players take alternate turns. If one player can not make a valid move, play passes back to the other player. When neither player can move, the game ends." – Valeria
Then add the code where node.Children are determined, because that step has to be done again (for other player). That "neither player" can then be addressed too. – Henk Holterman
A node where the player has no moves has exactly one child, which has an unchanged board state. The child also needs an indication that no move was made. The indication is initially 0. It increments when no move is made, and is reset to 0 when either player makes a move. If the indication reaches 2, then neither player had a move and the game is over. – user3386109

2 Answers

1
votes

I implemented Minimax for a game that involved passing. So, pass was an action a user could do. In my case there were a few "re-actions" you could do as a player in the "passed" state, but that's irrelevant here.

You can add the player->pass = true as the new state and add it to the tree, just be sure to also check before any actions are added to the tree if that player has already passed, and skip it.

You then need to handle how many times they will be allowed to pass. Since now, if all players pass, the game can go on indefinitely. This depends on the game. In my case, when a player passed they could no longer do anything (beyond what I mentioned at first), and then when all players passed, the round ended and all pass states were reset.

An example from my game:

std::list<GameState*> GameState::generateChildren(GameState& parent) {
  std::list<GameState*> children;
  PlayerBoard* currentBoard = parent.getCurrentPlayer();

  if (!currentBoard->pass) {
    GameState* childState = new GameState(parent);
    PlayerBoard *childBoard = childState->getCurrentPlayer();
    childBoard->pass = true;
    childBoard->nextPlayer();
    children.push_back(childState);

    //And then all your regular actions...
  }

  return children;
}
0
votes

You can write a function GenerateValidMoves(node, player) that returns the list of all valid moves for the player in a given position. Then the start of minimax routine can be rewritten as follows:

function minimax(node, depth, maximizingPlayer)
    if depth == 0:
        return heuristicValueOfNode
    if generateValidMoves(node, currentPlayer) is empty:
        if generateValidMoves(node, opponentPlayer) is empty:
            return heuristicValueOfNode //here the game is finished since neither player can move
        return minimax(node, depth, not maximizingPlayer) //call minimax for the opponent
    if maximizingPlayer
        bestValue := −∞
        for each child of node
            v := minimax(child, depth − 1, FALSE)
            bestValue := max(bestValue, v)
        return bestValue

    else    (* minimizing player *)
        bestValue := +∞
        for each child of node
            v := minimax(child, depth − 1, TRUE)
            bestValue := min(bestValue, v)
        return bestValue