How to adapt my Minimax search tree to deal with no term based game?
I have to do a project where we need to implement mancala board game, and then also implement the AI for it.
We have been instructed that we need to modify or change a minimax tree to be able to work with mancala as in the game it is possible for a player to have multiple turns in a row.
I have implemented my game logic and GUI already, But now before i start with the AI I would like to try and get some idea on the theory behind it. I have searched on the net for non-turn based mini max trees and i cant seem to find anything. But i have seen many people talking about using minimax for mancala.
Now I understand the normal minimax tree and how each level alternates between a minimum node and a maximum node. With the tree that I need now, would i say: min > max > max > min > max if the 2nd player got TWO turns?
We also need to be able to specify the given ply-depth of the Minimax tree. We also need to do alpha beta pruning, but that's for later on, once I actually have a tree.
As far as I understood, your main problem is the following: you have been shown how to use minimax in a situation where max / min go in cycle and now you have a game where sometimes one player can do multiple moves in a row.
I will explain you the general approach which works for basically any game, and then I will add a couple of things that can be done differently for mancala.
So the general approach
Standard minimax goes like this:
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
val := minimax(child, depth - 1, FALSE)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
val := minimax(child, depth - 1, TRUE)
bestValue := min(bestValue, val)
return bestValue
Where you initialize the minimax call with max/min and then it constantly changes. In your case you only need to add one tiny check.
function minimax(node, depth, maximizingPlayer)
if depth = 0 or node is a terminal node
return the heuristic value of node
if maximizingPlayer
bestValue := -∞
for each child of node
# here is a small change
if freeTurn(child):
isMax := TRUE
else:
isMax := FALSE
val := minimax(child, depth - 1, isMax)
bestValue := max(bestValue, val)
return bestValue
else
bestValue := +∞
for each child of node
# here is a small change
if freeTurn(child):
isMax := FALSE
else:
isMax := TRUE
val := minimax(child, depth - 1, isMax)
bestValue := min(bestValue, val)
return bestValue
Where your function freeTurn returns you whether you have a free turn after your current move. Note that there is no difference for this algorithm whether you can do only 2 moves in a row or 5 moves in a row.
Regarding Mancala
There are many variations of mancala, but the branching factor of the game is pretty small (in the one that I know is <= 6). Now assume that you have three moves A , B , C , D and move C allows you to play one more time. From the position C you can do moves C1 , C2 . So you can combine them ( C + C1 , C + C2 ) and treat them as just one move (small bookkeeping should be done to remember that this is actually two moves). So right now you end up with your min max iterations where you have not 4 but 5 moves: A , B , C + C1 , C + C2 , D . Actually there is nothing wrong to use this approach for games with bigger branching factor.
If a side can have multiple moves in a turn then there must be some way to detect that. When detected have the move generator for the opponent generate a list that contains only a null move, ie a move that does nothing. The opponent will be forced to play that move (do nothing) and the first player can then compute his next move.
链接地址: http://www.djcxy.com/p/56328.html