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 α
Dont try changing the minimax algorithm itself for this, instead modify the game representation to accommodate. There are basically two solutions:
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.
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!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With