Frage an algorithm, java, minimax, tic-tac-toe – Tic Tac Toe mit Minimax: Der Computer verliert manchmal, wenn der Spieler an erster Stelle steht. funktioniert anders

4

Ich arbeite an einem Minimax-Algorithmus für unschlagbare Tic Tac Toe. Ich brauche es, um sowohl zu funktionieren, wenn der Computer als auch der Player an erster Stelle steht. Mit der aktuellen Version verliert der Computer niemals, wenn er als Erster gestartet wird. Es scheint jedoch, dass Minimax niemals den besten Zug findet (gibt immer -1 als Punktzahl zurück), wenn der Spieler zuerst geht.

Was hat zur Folge, dass der zurückgegebene Minimax-Wert für den Computer -1 beträgt, wenn der Spieler den ersten Zug macht?

Beispiel:

board.addMark( 1, Mark2.PLAYER ); // add a 'PLAYER' mark to an arbitrary location
Minimax.minimax( board, Mark2.COMPUTER ); // will always return -1

Hier ist die 'Minimax'-Klasse:

public class Minimax {
  public static int minimax( Board board, Mark2 currentMark ) {
    int score = (currentMark == Mark2.COMPUTER) ? -1 : 1;
    int[] availableSpaces = board.getAvailableSpaces();

    if ( board.hasWinningSolution() )
      score = (board.getWinningMark() == Mark2.COMPUTER) ? 1 : -1;
    else if ( availableSpaces.length != 0 ) {
      Mark2 nextMark = (currentMark == Mark2.COMPUTER) ? Mark2.PLAYER : Mark2.COMPUTER;

      for ( int availableIndex = 0; availableIndex < availableSpaces.length; availableIndex++ ) {
        board.addMark( availableSpaces[availableIndex], currentMark );
        int nextScore = minimax( board, nextMark );
        board.eraseMark( availableSpaces[availableIndex] );

        if ( currentMark == Mark2.COMPUTER && nextScore > score
            || currentMark == Mark2.PLAYER && nextScore < score )
          score = nextScore;
      }
    }

    return score;
  }
}

Hier ist die 'Board'-Klasse:

public class Board {
  private Mark2 gameBoard[];
  private int blankSpaces;

  private boolean solutionFound;
  private Mark2 winningMark;

  public final static int winSets[][] = {
      { 0, 1, 2 }, { 3, 4, 5 },
      { 6, 7, 8 }, { 0, 3, 6 },
      { 1, 4, 7 }, { 2, 5, 8 },
      { 0, 4, 8 }, { 2, 4, 6 }
  };

  public Board() {
    gameBoard = new Mark2[9];
    blankSpaces = 9;

    for ( int boardIndex = 0; boardIndex < gameBoard.length; boardIndex++ ) {
      gameBoard[boardIndex] = Mark2.BLANK;
    }
  }

  public void addMark( int spaceIndex, Mark2 mark ) {
    if ( gameBoard[spaceIndex] != mark ) {
      gameBoard[spaceIndex] = mark;

      if ( mark == Mark2.BLANK ) {
        blankSpaces++;
      } else {
        blankSpaces--;
      }
    }
  }

  public void eraseMark( int spaceIndex ) {
    if ( gameBoard[spaceIndex] != Mark2.BLANK ) {
      gameBoard[spaceIndex] = Mark2.BLANK;
      blankSpaces++;
    }
  }

  public int[] getAvailableSpaces() {
    int spaces[] = new int[blankSpaces];
    int spacesIndex = 0;

    for ( int boardIndex = 0; boardIndex < gameBoard.length; boardIndex++ )
      if ( gameBoard[boardIndex] == Mark2.BLANK )
        spaces[spacesIndex++] = boardIndex;

    return spaces;
  }

  public Mark2 getMarkAtIndex( int spaceIndex ) {
    return gameBoard[spaceIndex];
  }

  public boolean hasWinningSolution() {
    this.solutionFound = false;
    this.winningMark = Mark2.BLANK;

    for ( int setIndex = 0; setIndex < winSets.length && !solutionFound; setIndex++ )
      checkSpacesForWinningSolution( winSets[setIndex][0], winSets[setIndex][1], winSets[setIndex][2] );

    return solutionFound;
  }

  public Mark2 getWinningMark() {
    return this.winningMark;
  }

  private void checkSpacesForWinningSolution( int first, int second, int third ) {
    if ( gameBoard[first] == gameBoard[second] && gameBoard[third] == gameBoard[first]
        && gameBoard[first] != Mark2.BLANK ) {
      solutionFound = true;
      winningMark = gameBoard[first];
    }
  }

  public void printBoard() {
    System.out.printf( " %c | %c | %c\n", getMarkCharacter( gameBoard[0] ), getMarkCharacter( gameBoard[1] ),
        getMarkCharacter( gameBoard[2] ) );
    System.out.println( "------------" );
    System.out.printf( " %c | %c | %c\n", getMarkCharacter( gameBoard[3] ), getMarkCharacter( gameBoard[4] ),
        getMarkCharacter( gameBoard[5] ) );
    System.out.println( "------------" );
    System.out.printf( " %c | %c | %c\n", getMarkCharacter( gameBoard[6] ), getMarkCharacter( gameBoard[7] ),
        getMarkCharacter( gameBoard[8] ) );
  }

  public char getMarkCharacter( Mark2 mark ) {
    char result = (mark == Mark2.PLAYER) ? 'O' : ' ';
    result = (mark == Mark2.COMPUTER) ? 'X' : result;
    return result;
  }
}

Und hier ist die 'Mark2'-Klasse, wenn es Verwirrung gab:

public enum Mark2 {
  BLANK,
  PLAYER,
  COMPUTER
}
@AndrewThompson Es macht natürlich Spaß, dafür zu sorgen, dass es richtig funktioniert. jneander
"Unschlagbarer Tic Tac Toe." Haben Sie jemals darüber nachgedacht, Ihre Kräfte einzusetzen?gut?  Was für ein Spaß ist ein unschlagbarer Tic-Tac-Toe? ;) Andrew Thompson
Gute Frage, aber zur schnelleren Hilfe (fügen Sie diese Quellen zu einer Datei hinzu, fügen Sie eine hinzumain &) poste einSSCCE. Andrew Thompson

Deine Antwort

3   die antwort
0

Spieler1 gewinnt, Spieler2 gewinnt, niemand gewinnt.

Sie sollten Zeilen wie diese ersetzen:

int score = (currentMark == Mark2.COMPUTER) ? -1 : 1;

von so etwas:

int score = (currentMark == Mark2.COMPUTER) ? -1 : ((currentMark == Mark2.PLAYER) ? 1 : 0);
0

e ich eine Offenbarung. Ich habe einen Test geschrieben, um das Auftreten der drei möglichen von minimax () zurückgegebenen Punkte zu zählen. Als Ergebnis ergab sich für 0 nichts, was mich darauf hinwies, dass ich 0 brauchte, um vom Algorithmus als mögliche Punktzahl berücksichtigt zu werden.

Ich hatte ursprünglich die Initialisierung von 'score' geändert, um die niedrigstmöglichen / höchstmöglichen Ergebnisse (-1/1) zu erhalten, und sie mit diesen verglichen. Dies verhinderte jedoch, dass das Ergebnis den niedrigsten / höchsten Wert ausschließlich aus der Menge der zurückgegebenen Bewertungen erhielt, und schloss stattdessen auch den initialisierten Wert ein. Das hat die Ergebnisse verdorben.

Ich habe den folgenden Vergleich zur bedingten Änderung von 'score' hinzugefügt:

|| availableIndex == 0

Dies erzwang alle verbleibenden Vergleiche mit einem Wert, der zu der Menge der zurückgegebenen Bewertungen gehörte.

public class Minimax {
  public static int minimax( Board board, Mark2 currentMark ) {
    int score = 0;
    int[] availableSpaces = board.getAvailableSpaces();

    if ( board.hasWinningSolution() )
      score = (board.getWinningMark() == Mark2.COMPUTER) ? 1 : -1;
    else if ( availableSpaces.length != 0 ) {
      Mark2 nextMark = (currentMark == Mark2.COMPUTER) ? Mark2.PLAYER : Mark2.COMPUTER;

      for ( int availableIndex = 0; availableIndex < availableSpaces.length; availableIndex++ ) {
        board.addMark( availableSpaces[availableIndex], currentMark );
        int nextScore = minimax( board, nextMark );
        board.eraseMark( availableSpaces[availableIndex] );

        if ( currentMark == Mark2.COMPUTER && nextScore > score
            || currentMark == Mark2.PLAYER && nextScore < score
            || availableIndex == 0 )
          score = nextScore;
      }
    }

    return score;
  }
}
0

Das Brett ist 1x1, und der erste Spieler, der dort eine Marke platziert, gewinnt.

Jetzt startet der Computer, Score = -1. Es gibt keine Gewinnlösung (der eine Gewinnsatz ist markiert, es ist kein 1-in-1-Satz) und es ist ein freier Platz verfügbar. Also gehen wir zurück, um die eine verfügbare Position auszuprobieren.

Jetzt ist Mark = PLAYER und das Board hat eine gewinnende Lösung. Der Computer gewinnt also, Punktzahl = -1.

Zurück zum ersten Aufruf, die Zeile "int nextScore = minimax (board, nextMark);" gibt wieder -1 zurück und das Endergebnis ist -1.

Das gleiche passiert Ihnen mit dem größeren Problem.

Verwandte Fragen