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 α

Ticon

if you could explain more about all of variables, we could probably help... – Publicist

@Dhaivat Pandya the code extract is taken from wiki en.wikipedia.org/wiki/Negamax – Ticon

ah. So, this isn't quite game-development, now is it? – Publicist

@Dhaivat: Why isn't it? You could use this in a draughts/checkers evaluation function, for example. – External

@John: Why don't you think it's right? It looks fine to me. – External

@TonyK: my computer player doesn't behave right and I assumed this function is the one to blame – Ticon

@JohnRetallack Post the code you're using, then. – Radii

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.

Ocko

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!

Magda

I wasn't clear enough, the player can move multiple times if some conditions are met. So if I would implement your solution I would be dealing with a new tree structure just for finding the successors of the node. – Ticon

@JohnRetallack- Yes, that would be correct. I think the key idea is to realize that a "move" is not just one play, but rather a complete sequence of plays by one player in which the other player cannot intervene. Alternatively, you could think of a series of moves by one player as a series of alternating moves in which the other player is forced to play a "no-op" move. – Magda

@templatetypedef: What's wrong with the OP's code? It looks fine to me. – External

@TonyK- My concern is that if one player can keep playing moves over and over again, the negamax code won't ever allow the other player to make their move and so won't give an accurate assessment of the game at the appropriate depth. Bundling moves together forces players to alternate turns until the depth is reached, giving a better reading on the game state. – Magda

@templatetypedef: Conversely, doing it your way risks a combinatorial explosion when the first player has a large tree of consecutive moves to choose from. – External

Answer 3

When condition is met, don't decrement depth.

Slick