Checkers-Algorithmus: Wie verschachtelte For-Loops zu reduzieren

Question

Ich versuche ein Programm zu erstellen, das Entwürfe/Checker spielt. Im Moment versuche ich, die Funktion zu machen, die es dem Computer ermöglicht, Bewegungen zu machen und auszuwerten. Meine Idee ist, dass der Computer alle möglichen Moves betrachtet und für jeden dieser Moves die möglichen Moves des Gegners betrachtet und dann für jeden dieser Moves wieder eigene Moves betrachtet.

Mit jeder Lage wird bewertet, ob die Bewegung gut oder schlecht für den Spieler ist und Punkte vergeben, am Ende werden die Züge mit den höchsten Punkten ausgewählt.

Bis jetzt habe ich es geschafft, eine Version von dieser Arbeit zu bekommen, aber beinhaltet eine Menge von verschachtelten For-Schleifen. Der Code ist eine Unordnung und im Moment nicht sehr lesbar, aber dies ist ein einfaches Modell des gleichen Konzepts. Anstatt mehr Listen zu bewerten und zu produzieren, multipliziert es sich einfach um zwei für die neue Liste.

counter = 0 
    for x in list: 
     counter += 1 
     list_2 = [x * 2 for x in list] 
     print 'list_2', list_2, counter 
     for x in list_2: 
      counter += 1 
      list_3 = [x * 2 for x in list_2] 
      print 'list_3',list_3, counter 
      for x in list_3: 
       counter += 1 
       list_4 = [x * 2 for x in list_3] 
       print 'list_4', list_4, counter 

Wenn ich diesen Code ausführen, bekomme ich, was ich will, mit der Ausnahme, dass ich nicht einfach die Tiefe der Suche steuern kann für Schleifen in mehr ohne sie zu kopieren. Ich dachte, Rekursion wäre eine Möglichkeit, dies zu tun, aber ich kann nicht herausfinden, wie man die Rekursion nach x Ebenen der Suchtiefe stoppt.

Gibt es eine bessere Möglichkeit, die gleiche Ausgabe aus dem obigen Code zu erhalten, während alle For-Schleifen loswerden? Wenn ich das zur Arbeit bringen kann, denke ich, dass ich den Rest selbst machen kann.

Answer 1

Hier ist eine entsprechende Funktion, die Rekursion verwendet. Es steuert die Rekursion mit zwei Parametern, die die aktuelle Tiefe und maximale Tiefe verfolgen. Wenn die aktuelle Tiefe, um die maximale Tiefe übersteigt, wird es sofort wieder so die Rekursion Stoppen:

def evaluate(l, max_depth, cur_depth=0, counter=0): 
    if cur_depth > max_depth: 
     return counter 

    for x in l: 
     counter += 1 
     l2 = [x * 2 for x in l] 
     print cur_depth, l2, counter 
     counter = evaluate(l2, max_depth, cur_depth + 1, counter) 

    return counter 

Wenn mit max_depth=2 genannt wird erzeugen sie den gleichen Ausgang der Ausnahme, dass anstelle des Variablennamens die aktuelle Tiefe gedruckt wird.

Answer 2

Ich dachte, Rekursion könnte eine Möglichkeit, dies zu tun, aber ich kann nicht herausfinden, wie die Rekursion nach x Ebenen der Suchtiefe zu stoppen.

Ihre Intuition ist korrekt, und eine einfache Möglichkeit wäre, eine inkrementierende Zahl an jede Ebene zu übergeben. Wenn die Rekursion den Maximalwert erhält, ist die Rekursion abgeschlossen. Ein triviales Beispiel ist unten zu demonstrieren.

Für Ihren Algorithmus benötigen Sie einen Wert, um die Board-Auswertung darzustellen. Zum Beispiel im Bereich [-1,1]. Spieler A könnte als Gewinner bezeichnet werden, wenn die Bewertung -1 lautet und Spieler B gewinnt, wenn die Bewertung beispielsweise 1 lautet. Ein rekursiver Algorithmus könnte wie folgt aussehen.

def evaulate(board, player, depth=0): 
    if depth==MAX_DEPTH: return hueristicEvaluation(board) 
    bestMove = None 
    if player==PLAYER_A: 
    val=999 # some large value 
    for move in get_moves(): 
     newboard = board.makeMove(move) 
     eval, _ = evaluate(newboard, PLAYER_B, depth+1) 
     if eval < val: 
     bestMove = move 
     val = eval 
    elif player==PLAYER_B: 
    val=-999 # some large negative value 
    for move in get_moves(): 
     newboard = board.makeMove(move) 
     eval, _ = evaluate(newboard, PLAYER_A, depth+1) 
     if eval > val: 
     bestMove = move 
     val = eval 
    return val, bestMove 

Das ist abstrakt, aber die Idee ist da. Passen Sie an, wie Sie die board oder die player s darstellen. Die Funktion hueristicEvaluation könnte so einfach sein wie das Zählen der Teile auf dem Spielfeld für jeden Spieler und wie nah sie sich auf der anderen Seite befinden. Denken Sie daran, dass diese Funktion eine Zahl zwischen [-1,1]

Edge-Fälle zurückgeben muss berücksichtigen, die ich nicht berücksichtigt habe:

• Wenn alle Züge gewinnen und/oder zu verlieren
• Wenn das sind KEINE bewegt sich in der Position, zum Beispiel, wenn deine Teile alle von den Steinen deines Gegners blockiert werden

Viele Verbesserungen existieren für eine einfache Suche wie diese.Lesen Sie, wenn Sie interessiert sind :)

• Für Checker, vielleicht Memoization würde Dinge viel beschleunigen. Ich bin mir nicht sicher, aber ich denke, es wäre besonders am Anfang. See python's way of doing this.
• Pruning
• Alpha-beta pruning
• Branch and bound