Tic Tac Toe con Minimax: la computadora a veces pierde cuando el jugador va primero;trabaja de lo contrario

Question

Estoy trabajando en un algoritmo de Minimax para un tac tac tac inmejorable.Lo necesito para trabajar tanto cuando la computadora va primero, así como cuando el jugador va primero.Con la versión actual, la computadora nunca perderá cuando se vaya primero.Sin embargo, parece que Minimax nunca encuentra un mejor movimiento (siempre devuelve -1 como la puntuación) Si el jugador va primero.

¿Qué está causando la puntuación de Minimax devuelta a ser -1 para la computadora si el jugador hace el primer movimiento?

Ejemplo:

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

Aquí está la clase 'Minimax':

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;
  }
}

Aquí está la clase 'Junta':

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;
  }
}

y aquí está la clase 'Mark2' si hubiera alguna confusión:

public enum Mark2 {
  BLANK,
  PLAYER,
  COMPUTER
}

Answer 1

Después de tomar un descanso extendido, y con la ayuda de la respuesta de @guyadini, tuve una epifanía.Escribí una prueba para contar la ocurrencia de las tres puntuaciones posibles devueltas por Minimax ().No cedió nada para 0 como resultado, que me indicó el hecho de que necesitaba 0 para ser considerado por el algoritmo como una puntuación posible.

originalmente había cambiado la inicialización de 'puntuación' para ser los resultados más bajos / más altos posibles (-1/1) y comparado contra ellos.Sin embargo, esto prohibió el resultado de obtener el valor más bajo / más alto exclusivamente del conjunto de puntuaciones devueltas y, en cambio, también incluía el valor inicializado.Esto arruinó los resultados.

Añadido la siguiente comparación con el cambio condicional de 'Puntuación':

|| availableIndex == 0

Esto obligó a todas las comparaciones restantes que se realizarán contra un valor que pertenecía al conjunto de puntajes devueltos.

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;
  }
}

Answer 2

Veamos algo más sencillo: la placa es 1x1, y el primer jugador colocar una marca allí gana.

Ahora comienza la computadora, puntuación= -1. No hay una solución ganadora (el único conjunto de ganador está marcado, no es una 1 en una fila), Y hay un espacio disponible. Así que procedemos por retroceder para probar la posición disponible.

Ahora Mark= Player, y la Junta tiene una solución ganadora.Así que la computadora gana, puntuación= -1.

Volviendo a la primera llamada, la línea "INT NEXTSCORE= MINIMAX (PABITACIÓN, PREVISTO MARCHO);"Devuelve -1 de nuevo, y la puntuación final es -1.

Te sucede lo mismo con el problema más grande.

Answer 3

En un juego de Tic Tac Toe, hay 3 posibilidades y no solo 2: Player1 Wins, Player2 Wins, nadie gana.

Debe reemplazar líneas como esta:

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

por algo como este:

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