Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

minimax depth first search game tree

Tags:

tree

minimax

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

like image 341
Arvind Avatar asked Nov 05 '22 16:11

Arvind


1 Answers

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 α
like image 187
Nick Dandoulakis Avatar answered Dec 01 '22 11:12

Nick Dandoulakis