Minimax-Tiefensuche Spielbaum

Question

Ich möchte ein Spiel Baums für neun Männer morris Spiel bauen. Ich möchte dafür Knoten Auswertungen Minimax-Algorithmus auf dem Baum anzuwenden. Minimax verwendet DFS-Knoten zu bewerten. Also soll ich den Baum zuerst bis zu einer bestimmten Tiefe bauen und Minimax dann anwenden oder kann der Prozess um den Baum und die Bewertung des Gebäudes auftritt zusammen in rekursiven Minimax DFS?

Danke Arvind

Answer 1

Sie können einen Blick auf iterative Vertiefung Tiefensuche .

Answer 2

Ja, Sie können zur gleichen Zeit in einer rekursiven Minimax bauen und zu bewerten.
Das ist ein guter Ansatz, da es wird Speicherplatz sparen.

Eigentlich kann man auch anwenden alpha-beta zugleich Beschneiden .

Edit: hier ist Pseudo-Code aus dem 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 α

Da wir (wahrscheinlich) speichern ein Spiel / Board Zustand in jedem Knoten, könnten wir einbetten die Schaffung von Spiel heißt
in dem Minimax-Algorithmus, dh

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 α