minimax profondeur première recherche arbre de jeu

Question

Je veux construire un arbre de jeu pour le jeu de morris neuf hommes. Je veux appliquer l'algorithme minimax sur l'arbre pour faire des évaluations de nœuds. Minimax utilise DFS pour évaluer les nœuds. Donc devrais-je construire l'arbre d'abord jusqu'à une profondeur donnée et ensuite appliquer minimax ou est-ce que le processus de construction de l'arbre et de l'évaluation peut se produire ensemble dans un DFS minimax récursif?

Merci Arvind

Answer 1

Vous pouvez jeter un oeil à iterative deepening depth first search.

Answer 2

Oui, vous pouvez construire et évaluer en même temps dans un minimax récursif.
C'est une bonne approche car cela économisera de l'espace mémoire. En fait, vous pouvez même appliquer simultanément alpha-beta pruning.

Edit: ici est pseudocode du 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 α 

Puisque nous (probablement) stocker un état jeu/planche dans chaque nœud, nous pourrions intégrer la création des états de jeu
dans le algorithme Minimax, à savoir

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 α