MiniMax Implementation

Question

I am trying to write a small AI algorithm in Java implementing the miniMax algorithm.

The game upon which this is based is a two-player game where both players make one move per turn, and each board position resulting in each player having a score. The "quality" of a position for player X is evaluated by subtracting the opponent's score from player X's score for that position. Each move is represented by an integer (i.e. Move one is made by inputting 1, move two by inputting 2 etc)

I understand that miniMax should be implemented using recursion. At the moment I have:

An evaluate() method, which takes as parameters an object representing the board state (Ie "BoardState" object and a boolean called "max" (the signature would be evaluate(BoardState myBoard, boolean max)).

max is true when it is player X's turn. Given a board position, it will evaluate all possible moves and return that which is most beneficial for player X. If it is the opponent's turn, max will be false and the method will return the move which is LEAST beneficial for player X (ie: most beneficial for player y)

However, I am having difficulties writing the actual miniMax method. My general structure would be something like:

public int miniMax(GameState myGameState, int depth)

Whereby I submit the initial gameState and the "depth" I want it to look into.

I would then be having something like:

int finalMove = 0;
while(currentDepth < depth) {
    GameState tmp = myGameState.copy();
    int finalMove = evaluate(tmp, true or false);
    iniMax(tmp.makeMove(finalMove));

}
return finalMove;

Would this sound like a plausible implementation? Any suggestions? :)

Thanks!

In recursion, you write a method that calls itself, but for a smaller problem size. The while loop is not what you're looking for, you want to call `Evaluate` plenty times for decreasing depth. — flup, Apr 25 '13 at 18:12
When defining Evaluate, you define it in terms of other calls to Evaluate, but with smaller problem size (one less depth). http://stackoverflow.com/questions/717725/understanding-recursion — flup, Apr 25 '13 at 19:25

score 3 · Answer 1 · answered Apr 27 '13 at 01:56

that wont work.

details :

it will cause infinite loop. currentdepth never gets incremented
your definition of evaluation seems to be different than the majority. Normally evaluation function will return the predicted value of the game state. Isnt your definition of evaluate function is just the same as what the minimax function do ?
is miniMax and MiniMax different? because if you meant recursion then you need to pass depth-1 when calling the next miniMax

the idea of minimax is depth first search. and only evaluate leaf nodes(nodes with maximum depth or nodes that is a win or tie) and pick one that is max if the current player is the maximizing one and pick min if the current player is the minimizing one.

this is how i implemented it :

function miniMax(node, depth)
    if(depth == 0) then --leaf node     
        local ret = evaluate(node.state)
        return ret
    else -- winning node
        local winner = whoWin(node.state)       
        if(winner == 1) then -- P1      
            return math.huge
        elseif(winner == -1) then -- P2         
            return math.huge*-1
        end 
    end

    local num_of_moves = getNumberOfMoves(node.state)   
    local v_t = nil
    local best_move_index = nil 
    if(getTurn(node.state) == 1) then -- maximizing player      
    local v = -math.huge 
        for i=0, num_of_moves-1 do                      
            local child_node = simulate(node.state, i)) -- simulate move number i
            v_t = miniMax(child_node, depth-1)
            if(v_t > v) then 
                v = v_t 
                best_move_index = i             
            end
        end             
        if(best_move_index == nil) then best_move_index = random(0, num_of_moves-1) end 
        return v, best_move_index
    else -- minimizing player
    local v = math.huge
        for i=0, num_of_moves-1 do          
            local child_node = simulate(node.state, i)
            v_t = miniMax(child_node, depth-1)
            if(v_t < v) then                
                v = v_t             
                best_move_index = i             
            end
        end
        if(best_move_index == nil) then best_move_index = random(0, num_of_moves-1) end
        return v, best_move_index                               
    end 
end

Note:

return v, best_move_index means returning two values of v and best_move_index(above code is in lua and lua can return multiple values)
evaluate function returns the same score for both players(ie game state A in point of view P1 is scored 23, and in point of view P2 is also scored 23)
this algo will only work if the two player run alternately(no player can run two moves consecutively), you can trick this restriction by giving the opponent one move, that is move PASS(skip his/her turn) if the other player need to move twice.
this minimax can be further optimized(sorted from the easiest one) :
1. alpha-beta pruning
2. iterative deepening
3. move ordering

score 0 · Answer 2 · answered Apr 28 '13 at 05:06

I made an implementation of minimax in lua. I hope it helps give you an idea of how to tackle the algorithm form a Java perspective, the code should be quite similar mind you. It is designed for a game of tic-tac-toe.

--caller is the player who is using the minimax function
--initial state is the board from which the player must make a move
local function minimax(caller,inital_state)
    local bestState = {}; --we use this to store the game state the the player will create
      --this recurse function is really the 'minimax' algorithim 
    local function recurse(state,depth)
        --childPlayer is the person who will have their turn in the current state's children
        local ChildPlayer = getTurn(state)
        --parentPlayer is the person who is looking at their children
        local ParentPlayer = getPreviousTurn(state)
        --this represents the worst case scenario for a player
        local alpha =  - (ChildPlayer == caller and 1 or -1 );
        --we check for terminal conditions (leaf nodes) and return the appropriate objective value
        if win(state) then
            --return +,- inf depending on who called the 'minimax'
            return ParentPlayer == caller and 1 or -1;
        elseif tie(state) then 
            --if it's a tie then the value is 0 (neither win or loss)
            return  0;
        else
            --this will return a list of child states FROM the current state
            children = getChildrenStates(state,ChildPlayer)
            --enumerate over each child
            for _,child in ipairs(children) do
                --find out the child's objective value
                beta = recurse(child,depth+1);
                if ChildPlayer == caller then 
                    --We want to maximize
                    if beta >= alpha then 
                        alpha = beta
                        --if the depth is 0 then we can add the child state as the bestState (this will because the caller of minimax will always want to choose the GREATEST value on the root node)
                        if depth == 0 then
                            bestState = child;
                        end 
                    end 
                --we want to MINIMIZE
                elseif beta <= alpha then 
                    alpha = beta;
                end 
            end 
        end
         --return a non-terminal nodes value (propagates values up the tree)
        return alpha;           
    end
     --start the 'minimax' function by calling recurse on the initial state
    recurse(inital_state,0);
     --return the best move
    return bestState;
end

MiniMax Implementation

2 Answers2