minimax depth first search game tree

Question

Hi

I want to build a game tree for nine men's morris game. I want to apply minimax algorithm on the tree for doing node evaluations. Minimax uses DFS to evaluate nodes. So should I build the tree first upto a given depth and then apply minimax or can the process of building the tree and evaluation occur together in recursive minimax DFS?

Thank you Arvind

Answer 1

You could take a look at iterative deepening depth first search.

Answer 2

Yes you can build and evaluate at the same time in a recursive minimax.
That is a good approach since it'll save memory space.

Actually, you can even apply alpha-beta pruning at the same time.

Edit: here is pseudocode from wiki Minimax:

function integer minimax(node, depth)
    if node is a terminal node or depth == 0:
        return the heuristic value of node
    α = -∞
    for child in node: # evaluation is identical for both players 
        α = max(α, -minimax(child, depth-1))
    return α

Since we (probably) store a game / board state in each node, we could embed the creation of game states
in the minimax algorithm, ie

function integer play_minimax(node, depth)
    if node is a terminal node or depth == 0:
        return the heuristic value of node
    α = -∞
    LOOP: # try all possible movements for this node/game state
        player = depth mod 2
        move = make_game_move(node, player)
        break if not any move
        α = max(α, -play_minimax(move, depth-1))
    return α