TIC TAC TE con MINIMAX: il computer a volte perdendo quando il giocatore va prima;funziona altrimenti

Question

Sto lavorando su un algoritmo di minimax per l'imbattibile TIC TAC Toe.Ho bisogno che funzioni entrambi per quando il computer va prima come quando il giocatore va per primo.Con la versione corrente, il computer non perderà mai per primo.Tuttavia, sembra che MiniMax non trovi mai una mossa migliore (ritorna sempre -1 come il punteggio) se il giocatore va prima.

Cosa sta causando il punteggio di minimax restituito a essere -1 per il computer se il giocatore rende la prima mossa?

Esempio:

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

.

Ecco la classe '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;
  }
}

.

Ecco la classe 'Bordo':

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

.

Ed ecco la classe 'Mark2' se c'era una confusione:

public enum Mark2 {
  BLANK,
  PLAYER,
  COMPUTER
}

.

Answer 1

Dopo aver preso una pausa estesa, e con l'aiuto della risposta di @Guyadini, ho avuto un'epifania.Ho scritto un test per contare il verificarsi dei tre punteggi possibili restituiti da MINIMAX ().Non ha ceduto nulla per 0 di conseguenza, che mi ha indifferente al fatto che avevo bisogno di 0 per essere considerato dall'algoritmo come un possibile punteggio.

Avevo originariamente cambiato l'inizializzazione del "punteggio" per essere i risultati più bassi / più alti possibili (-1/1) e confrontati contro di loro.Tuttavia, questo ha proibito il risultato di ottenere il valore più basso / più alto esclusivamente dal set di punteggi restituiti e anche includeva anche il valore inizializzato.Questo ha rovinato i risultati.

Ho aggiunto il seguente confronto con il cambio condizionale del 'punteggio':

|| availableIndex == 0

.

Ciò ha costretto tutti i confronti rimanenti da realizzare contro un valore appartenuto al set di punteggi restituiti.

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

Diamo un'occhiata a qualcosa di più semplice - la tavola è 1x1, e il primo giocatore per posizionare un segno vince.

Ora inizia il computer, punteggio= -1. Non c'è soluzione vincente (l'unico set vincente è selezionato, non è un 1-in-a-riga), E c'è uno spazio disponibile. Quindi procediamo con il backtracking per provare la posizione disponibile.

Ora Mark= Player, e la tavola ha una soluzione vincente.Quindi il computer vince, punteggio= -1.

Ritorna alla prima chiamata, la linea "int nextscore= minimax (scheda, nextmark);"restituisce -1 di nuovo, e il punteggio finale è -1.

La stessa cosa ti succede con il problema più grande.

Answer 3

In un gioco TIC Tac Toe, ci sono 3 possibilità e non solo 2: giocatore1 vince, giocatore2 vince, nessuno vince.

Dovresti sostituire linee come questa:

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

.

da qualcosa del genere:

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

.