Tic Tac Toe mit Alpha-Beta-Prunning in Java

Question

Ich versuche, Tic Tac Toe mit iterativen Alpha-Beta-Prunning, Ich habe eine zweite Grenze für eine Bewegung, aber aus irgendeinem Grund funktioniert nicht gut.

ich den regelmäßigen Alpha-Beta-Code, so dass anstelle der Rücksendung Alpha- oder Beta geändert, gibt es einen Zustand (das ist die Platine mit dem nächsten Zuge ist)

Jedes Mal, wenn ich Kinder erstelle ich ihre Tiefe aktualisieren.

Aber wieder aus irgendeinem Grund verliere ich weiter und ich sehe, dass mein Alpha-Beta sieht nicht die beste Bewegung zu machen.

Hier ist mein Code:

Die äußere Schleife:

while (watch.get_ElapsedMilliseconds() < 900 && d <= board.length * board[0].length - 1) 
     { 
      s = maxiMin(beginSt, d, watch); 
      if (s.getNextMove().getIsWin() == true) 
      { 
       break; 
      } 
      d++; 
     } 
     return new location(s.getNextMove().getRow(), s.getNextMove().getCol()); 

Die alpha beta:

public State maxiMin(State s, int depth, Stopwatch timer) 
    { 
     if (s.getDepth() == 7) 
     { 
      Console.WriteLine(); 
     } 
     if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     LinkedList<State> children = createChildren(s, true); 
     // No winner, the board is full 
     if (children.get_Count() == 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     while (children.get_Count() > 0) 
     { 
      State firstChild = children.get_First().get_Value(); 
      children.RemoveFirst(); 
      State tmp = miniMax(firstChild, depth, timer); 
      int value = tmp.getBeta(); 
      if (value > s.getAlpha()) 
      { 
       s.setAlpha(value); 
       s.setNextMove(tmp); 
      } 
      if (s.getAlpha() >= s.getBeta()) 
      { 
       return s; 
      } 
     } 
     return s; 
    } 

    public State miniMax(State s, int depth, Stopwatch timer) 
    { 
     if (s.getDepth() == 7) 
     { 
      Console.WriteLine(); 
     } 
     if (timer.get_ElapsedMilliseconds() > 850 || s.getDepth() == depth || goalTest(s.getBoard()) != 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     LinkedList<State> children = createChildren(s, false); 
     // No winner, the board is full 
     if (children.get_Count() == 0) 
     { 
      s.evaluationFunc(line_length, PlayerShape); 
      s.setAlpha(s.getEvaluation()); 
      s.setBeta(s.getEvaluation()); 
      return s; 
     } 
     while (children.get_Count() > 0) 
     { 
      State firstChild = children.get_First().get_Value(); 
      children.RemoveFirst(); 
      State tmp = maxiMin(firstChild, depth, timer); 
      int value = tmp.getAlpha(); 
      if (value < s.getBeta()) 
      { 
       s.setBeta(value); 
       s.setNextMove(tmp); 
      } 
      if (s.getAlpha() >= s.getBeta()) 
      { 
       return s; 
      } 
     } 
     return s; 
    } 

Würde viel appriciate, wenn jemand kann mir sagen, wenn etwas nicht stimmt. Ich vermute, vielleicht es etwas damit zu tun, dass ich "s" anstelle der regulären Alpha-Beta zurückgeben, die die Auswertung zurückgibt, aber ich habe es nicht geschafft, den Fehler zu finden.

Vielen Dank im Voraus,

Lena

Answer 1

Zum einem Tic-Tac-Toe ist ein sehr einfaches Spiel, und ich glaube, dass es mit einem viel einfacheren Code auflösbar ist, vor allem, weil wir wissen, dass es immer eine Krawatte Option und die Gesamtzahl der Staaten ist weniger als 3^9 (einschließlich der symmetrischen und viele unmögliche Staaten).

Wie für Ihren Code glaube ich eines Ihrer Probleme ist, dass Sie nicht scheinen, Ihre Tiefe in den rekursiven Anrufe zu erhöhen.

Sie haben auch viele Probleme mit schlechtem Stil in Ihrem Code, Sie trennten miniMax und MaxiMin in zwei Funktionen, obwohl sie grundsätzlich gleich sind. Sie iterieren über eine Sammlung, indem Sie Elemente daraus entfernen, anstatt for-each oder einen Iterator (oder sogar einen int-Iterator) zu verwenden.