Pregunta sobre tic-tac-toe, algorithm, minimax, java – Tic Tac Toe con Minimax: la computadora a veces pierde cuando el Jugador va primero; trabaja de otra manera

4

Estoy trabajando en un algoritmo Minimax para un Tic Tac Toe imbatible. Necesito que funcione tanto para cuando la Computadora se pone primero como para el Jugador primero. Con la versión actual, la computadora nunca perderá cuando vaya primero. Sin embargo, parece que Minimax nunca encuentra un mejor movimiento (siempre devuelve -1 como puntaje) si el Jugador va primero.

¿Qué está causando que la puntuación de Minimax sea -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 'Board':

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 hubo alguna confusión:

public enum Mark2 {
  BLANK,
  PLAYER,
  COMPUTER
}
"Tic Tac Toe inmejorable". ¿Alguna vez has considerado usar tus poderes ... para¿bueno?  ¿Qué diversión tiene un Tic-Tac-Toe inmejorable? ;) Andrew Thompson
Buena pregunta, pero para una mejor ayuda antes, (agregue esas fuentes en un archivo, agregue unmain y) publicar unSSCCE. Andrew Thompson
@AndrewThompson La diversión está en hacer que funcione correctamente, por supuesto. jneander

Tu respuesta

3   la respuesta
0

Player1 gana, Player2 gana, Nadie gana.

Deberías reemplazar líneas como esta:

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

por algo como esto:

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

y con la ayuda de la respuesta de @GuyAdini, tuve una epifanía. Escribí una prueba para contar la ocurrencia de los tres puntajes posibles devueltos por minimax (). Como resultado, no obtuvo nada para 0, lo que me dio la idea de que necesitaba que 0 fuera considerado por el algoritmo como una posible calificación.

Originalmente había cambiado la inicialización de 'puntaje' para que fuera el resultado más bajo / más alto posible (-1/1) y los comparé con ellos. Sin embargo, esto prohibió que el resultado obtuviera el valor más bajo / más alto exclusivamente del conjunto de puntajes devueltos y en su lugar también incluyó el valor inicializado. Esto arruinó los resultados.

Agregué la siguiente comparación al cambio condicional de 'puntuación':

|| availableIndex == 0

Esto obligó a hacer todas las comparaciones restantes contra un valor que pertenecía al conjunto de puntuaciones devueltas.

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

el tablero es 1x1, y el primer jugador que coloca una marca allí gana.

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

Ahora Mark = JUGADOR, y el tablero tiene una solución ganadora. Entonces la computadora gana, puntuación = -1.

Volviendo a la primera llamada, la línea "int nextScore = minimax (board, nextMark);" devuelve -1 de nuevo, y la puntuación final es -1.

Lo mismo te sucede a ti con el problema más grande.

Preguntas relacionadas