Minimax-Algorithmus für TicTacToe

[Zobel92]

Hallo, habe eine Frage zu einem von mir geschriebenen Minimax-Algorithmus. Und zwar hab ich wohl irgendwo einen Denkfehler und finde ihn nicht. Laut meiner Logik sollte der Algorithmus einfach nur sämtliche Äste auf dem Spielbaum bis zur Endstellung durchgehen. Für jede Endstellung soll er mir 1 zu meinem quantity Wert addieren. Wenn er alle Äste durchschritten hat, sollte die main-Methode eigentlich fertig sein. Ist sie aber nicht, scheinbar liegt irgendwo eine Unendliche Schleife oder ähnliches.

Main:

public static void main(String[] args){

  newGame();

  protected static int round = 0;

  Minimax.max(1, 9);

}

Minimax:

public class Minimax {

  private static int savedMove;

  //-------------------------------------------------------------

  private static int move;

  //-------------------------------------------------------------

  protected static int quantity = 0;

  //-------------------------------------------------------------

  protected static int max(int player, int depth){

    if(depth == 0){

      quantity += 1;

      System.out.println(quantity);

      return 1;

    }

    int maxValue = Integer.MIN_VALUE;

    int[] possibleMoves = generateMoves();

    while(depth > 0) {

      for (int no = 0; no < possibleMoves.length; no++) {

        moveForward(player, possibleMoves[no]);

        ++Game.round;

        int value = min(-player, depth - 1);

        moveBack(possibleMoves[no]);

        --Game.round;

        if (value > maxValue) {

          maxValue = value;

          if (depth == 1) {

            savedMove = move;

          }

        }

      }

    }

    return maxValue;

  }

  //-------------------------------------------------------------

  /* private static int rating(){

    if

  } */

  //-------------------------------------------------------------

  private static void moveForward(int player, int fieldno){

    Game.game[fieldno] = player;

    move = fieldno;

  }

  //-------------------------------------------------------------

  private static void moveBack(int fieldno){

    Game.game[fieldno] = 0;

  }

  //-------------------------------------------------------------

  private static int min(int player, int depth){

    if(depth == 0){

      quantity += 1;

      System.out.println(quantity);

      return 1;

    }

    int minValue = Integer.MAX_VALUE;

    int[] possibleMoves = generateMoves();

    while(depth > 0) {

      for (int no = 0; no < possibleMoves.length; no++) {

        moveForward(player, possibleMoves[no]);

        ++Game.round;

        int value = max(-player, depth - 1);

        moveBack(possibleMoves[no]);

        --Game.round;

        if (value > minValue) {

          minValue = value;

        }

      }

    }

    return minValue;

  }

  //-------------------------------------------------------------

  private static int[] generateMoves(){

    int[] free = new int[(9 - (Game.round))];

    int j = 0;

    for(int i = 0; i < 9; i++) {

      if(Game.game[I] == 0) {

        free[j] = i;

        j++;

      }

    }

    return free;

  }

}

 

[mrBrown]

Wird irgendwo in #max depth verringert?

 

[fhoffmann]

while(depth > 0)

führt zu einer Unendlichschleife. In jedem Aufruf von min() bzw. max() gibt es eine neue Variable depth.

 

[CSHW89]

So wie ich das sehe, kannst du, glaub ich, die Zeile 'while (depth > 0)' einfach rausschmeißen. Die Tiefe erreicht du ja mit den rekursiven Aufrüfen.

 

[JStein52]

In jedem Aufruf von min() bzw. max() gibt es eine neue Variable depth

Aber bei jedem Aufruf von max bzw. min wird depth um eins verringert. Das ist schon ok. Aber da in max bzw. min selber ja depth nie verändert wird ist es natürlich eine Endlosschleife. Der rekursive Aufruf von min und max geschieht ja jeweils per value und nicht per reference ....

 

[Zobel92]

Danke, genau das war auch der Fehler gewesen. Habe den Code jetzt noch einmal überarbeitet und der Algorithmus läuft auch schon, allerdings mit ein paar kleinen Macken. Er versucht zwar selber zu gewinnen, aber er versucht nicht meinen Sieg zu blockieren....

Hab das ganze jetzt nur einfachheitshalber mal in einen Negamax-Algorithmus umgeschrieben. Und verwende jetzt kopierte Int bzw. Int[] für die Runde und das Feld, um die Originale unverändert zu lassen.

private static int negamax(int player, int depth) {

  if (rounddouble >= 4) {

    if (WinCheck.Check(fielddouble, move) != 0) {

      return -player;                                         //Wenn gewonnen, dann anderen Spieler als Wertung zurückgeben!

    }

  }

  if (depth == 9 - Game.round) {

    return 0;

  }

  int maxValue = Integer.MIN_VALUE;                           //maxValue so klein wie möglich setzen!

  if (depth < 9 - Game.round) {

    int[] possibleMoves = generateMoves();                    //Array mit möglichen Zügen füllen

    for (int no = 0; no < possibleMoves.length; no++) {

      moveForward(player, possibleMoves[no]);

      rounddouble++;

      int value = -negamax(-player, depth + 1);                //Rekursiver Aufruf des Negamax-Algorithmus

      moveBack(possibleMoves[no]);

      rounddouble--;

      if (value > maxValue) {

        maxValue = value;

        if (depth == 0) {

          savedMove = move;

        }

      }

    }

  }


  maxValue = maxValue * player;

  return maxValue;

}