profondeur Minimax premier arbre de jeu de recherche

Question

Je veux construire un arbre de jeu pour le match de neuf hommes morris. Je veux appliquer l'algorithme minimax sur l'arbre pour faire des évaluations de nœuds. Minimax utilise DFS pour évaluer les nœuds. Alors, dois-je construire l'arbre d'abord jusqu'à une profondeur donnée, puis appliquer Minimax ou puis le processus de construction de l'arbre et l'évaluation se produire ensemble dans Minimax récursive DFS?

Merci Arvind

Answer 1

Vous pouvez jeter un oeil à itérative première recherche .

Answer 2

Oui, vous pouvez construire et évaluer en même temps dans une Minimax récursive.
C'est une bonne approche car elle va économiser de l'espace mémoire.

En fait, vous pouvez même appliquer taille alpha-bêta en même temps.

Modifier est ici de pseudo-code 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 α

Puisque nous (probablement) stocker un état jeu / planche dans chaque nœud, nous pourrions intégrer la la création d'états de jeu
dans l'algorithme de minimax, 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 α