Minimax depth of the first search game tree

Question

I want to build a game tree for a game of nine morris men. I want to apply a minimax algorithm for a tree to perform node evaluations. Minimax uses DFS to evaluate nodes. So do I have to first build the tree to a given depth and then apply minimax, or can the tree-building and evaluation process work together in recursive minimax DFS?

Thanks. Erwind

Answer 1

You can take a look at the iterative deepening of the depth of the first search .

Answer 2

Yes, you can build and evaluate recursive minimax at the same time.
This is a good approach as it will save memory space.

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

Edit: here is the pseudocode from the Minimax wiki:

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 (possibly) save the state of the game / board in each node, we can insert the creation of game states
in the minimax algorithm, i.e.

 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 α