profundidad Minimax primera búsqueda árbol de juego

Question

Quiero construir un árbol de juego de Morris juego de nueve de los hombres. Quiero aplicar el algoritmo Minimax en el árbol para hacer evaluaciones de nodo. Minimax utiliza DFS para evaluar los nodos. Así que debo construir el árbol primero hasta una profundidad determinada y luego aplicar Minimax o puedo el proceso de construir el árbol y la evaluación ocurrir juntos en recursivo Minimax DFS?

Gracias Arvind

Answer 1

Se puede echar un vistazo a iterativo profundidad profundización primero buscar .

Answer 2

Si usted puede construir y evaluar al mismo tiempo en un Minimax recursiva.
Ese es un enfoque bueno ya que ahorrará espacio en la memoria.

De hecho, incluso se puede aplicar poda alfa-beta al mismo tiempo.

Editar aquí es pseudocódigo de 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 α

Ya que (probablemente) almacenamos un estado del juego / tabla en cada nodo, se podría incrustar el creación de juego Unidos | en el algoritmo minimax, es decir,

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 α