Threading innerhalb des Minimax-Algorithmus

Question

Ich entwerfe ein 3D-Tic-Tac-Toe-Spiel und finde Zeit, um eine Grenze dafür zu setzen, wie tief mein Minimax-Algorithmus gehen kann. Während Tiefen bis zu 6 in der Zeit vernachlässigbar sind (< 1s), dauert es für höhere Tiefen etwas Zeit.

>Depth 7 = 6 seconds 
>Depth 8 = 49 seconds 
>Depth 9 = 314 seconds 

Ich habe nicht die Zeit (hah!), Höhere Tiefen zu überprüfen. Die maximale Tiefe ist 22, was meine KI jeden möglichen Spielzustand von Move 1 analysieren lässt und niemals zu einem User-Gewinn führt.

Ich möchte Threading in meiner Minimax-Funktion implementieren, bin aber relativ neu im Threading. Meine Minimax Funktion ist wie folgt:

//player is -1 for human, +1 for AI 
function minimax(board_state, depth, player) 
    if depth <= 0 or board == full //full board means no further states 
     return score * player 
    bestScore = -1000; 
    foreach possible move 
     if valid move 
      /* */ 
      make_move() 
      bestScore = max(bestScore, minimax(board_state, depth-1, -player) 
      undo_move() 
      /* */ 
    return bestScore 

ich etwas möchte, wo die Bits zwischen /* */ neue Themen sind, aber ein Problem: auch bei depth = 1, dass 8 Threads ist. Für depth = 8 sind das 16534863 Threads. Was sind die Beschränkungen für Threads? Ist es verknüpft mit wie vielen physischen Kernen hat meine CPU?

Answer 1

Zuerst überlegen, wie viel Sie auf einem 8-Kern-System beschleunigen können ... das ist 8 mal (es sei denn, Ihr Problem ist Speicher gebunden, in diesem Fall können Sie ein wenig besser bekommen). Lesen Sie weiter unter Amdahl's law und Gustafson's law

Ihr Problem sieht aus wie ein a! N-Problem, es explodiert in der Zeit. Sie müssen in Erwägung ziehen, den Code zu ändern, um die Anzahl der Optionen erheblich zu verringern.

Sie scheinen bereits mit Ihrem Minmax-Algorithmus die Spieltheorie zu gehen.

Sobald Sie in einer Tiefe des Baumes einen gewinnenden Zug für den gegnerischen Spieler gefunden haben, müssen Sie den Rest möglichen Zug nicht testen und können den Gewinner für diesen Teilbaum zurückgeben.

Answer 2

Ihre Lösung ist nicht in Multi Threading. versuchen Sie stattdessen in Alpha–beta pruning suchen. Naive Minimax untersucht am Ende viele redundante Knoten.

Auch ich Ihr Code ist falsch an

return score * player 

Eine Vollpension bedeutet wahrscheinlich ein Unentschieden, was bedeutet, dass niemand gewonnen:

oxo 
oxx 
xox 

Während diese Position ein Gewinn ist, so müssen Sie Ergebnis:

Answer 3

Es gibt eine perfekte Strategie für Tic Tac Toe, clearly described in Wikipedia. Ich habe es in einem Javascript-Spiel implementiert und es ist einfach. Kein Threading, kein Alpha Beta Schnitt, kein Minimax, nichts ...

Die perfekte Staregie sieht nicht zwei Züge voraus (um die gegnerische Gabel zu blockieren), so dass man sie live benutzen kann (und sollte).

Hinweis: Die Karte für Tic Tac Toe ist hochsymmetrisch, so dass die Anzahl der gültigen Züge bei jeder verwendeten Methode stark reduziert werden kann. Wenn Sie sich die perfekte Strategie ansehen, wird die Anzahl der Züge in Klassen aggregiert ("Mitte", "Gegenüberliegende Ecke", "Leere Ecke", "Leere Seite", etc ...).