Negamax - player moves twice

Question

How do you handle games where, if a condition is met, the same player moves ?

I tried something like this but I don't think it's quite right:

function negamax(node, depth, α, β, color)
    if node is a terminal node or depth = 0
        return color * the heuristic value of node
    else
        foreach child of node
            if (condition is met) // the same player moves
               val := negamax(child, depth-1, α, β, color)
            else
               val := -negamax(child, depth-1, -β, -α, -color)
            if val≥β
                return val
            if val≥α
                α:=val
        return α

Answer 1

Dont try changing the minimax algorithm itself for this, instead modify the game representation to accommodate. There are basically two solutions:

1. Represent the sequences of moves made by a single player as one move. This works when the game is simple, but wont always. I wrote an AI engine for a game where generating this tree (described as one "move" in the game rules) is PSPACE hard (and had a very large n for real games) meaning it was not computationally feasible. On the other-hand, if modeling it this way is easy for your particular game, do it that way
2. Represent the sequences of moves made by one player as a sequences of moves alternating moves, where the other player does do anything. That is, you add a piece of information to the game state whenever your condition is met, such that the only move the other player can make does not change the state. This method is mathematically correct, and when I used it worked pretty well in practice. The only complexity to keep in mind is that if you use iterative deepening you will under evaluate game trees where one player moves many times in a row. You also may need to be careful when designing storage heuristics to be used with the transposition table and other hashes

I know of no literature that discuses your particular problem. I felt clever when I came up with solution 2 above, but I suspect many other people have invented the same trick.

I should say, getting the minimax family right is surprisingly hard. A trick when designing game search AIs in high level languages is to test your search algorithms on simpler games (reduced board size, use tic-tac-toe, etc) to ensure correctness. If the game is small engough you can a. make sure its results make sense by playing the game out by hand and b. test advanced algorithms like negascout by making sure they give the same answer as naive negamax. It is also a good idea to try to keep code with game specific behavior (evaluation functions, board representations, search and storage heuristics, etc) away from the code that does tree searches.

Answer 2

In negamax, you are exploring a tree structure in which each node has children corresponding to the moves made by a player. If in some case a player can move twice, you would probably want to think of the "move" for that player as the two-move sequence that player makes. More generally, you should think of the children of the current game state as all possible states that the current player can get the game into after their turn. This includes all game states reachable by one move, plus all the game states reachable in two moves if the player is able to make two moves in one turn. You should, therefore, leave the basic logic of negamax unchanged, but update your code to generate successor states to handle the case where a single player can move twice.

Hope this helps!

Answer 3

When condition is met, don't decrement depth.