TIC TAC TOE AVEC MINIMAX: L'ordinateur perdant parfois lorsque le joueur va d'abord;fonctionne autrement

Question

Je travaille sur un algorithme minimax pour Tic Tac Toe Tic.J'en ai besoin pour travailler les deux lorsque l'ordinateur va d'abord et lorsque le joueur va d'abord.Avec la version actuelle, l'ordinateur ne perdra jamais lorsque vous allez d'abord.Cependant, il semble que Minimax ne trouve jamais un meilleur mouvement (retourne toujours -1 comme score) si le joueur va d'abord.

Qu'est-ce qui cause le score minimax renvoyé à -1 pour l'ordinateur si le joueur fait le premier mouvement?

Exemple:

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

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

Voici la classe "Conseil":

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

Et voici la classe "Mark2" s'il y avait une confusion:

public enum Mark2 {
  BLANK,
  PLAYER,
  COMPUTER
}

Answer 1

Après avoir pris une pause prolongée et avec l'aide de la réponse de @GuyaDini, j'ai eu une épiphanie.J'ai écrit un test pour compter la survenue des trois scores possibles retournés par Minimax ().Cela ne céda rien pour 0 en conséquence, qui m'a signé dans le fait que j'avais besoin de 0 pour être considéré par l'algorithme comme un score possible.

J'avais modifié à l'origine l'initialisation du "score" pour être les résultats les plus bas / les plus élevés possibles (-1/1) et comparé contre eux.Cependant, cela empêchait d'obtenir la valeur la plus basse / la plus élevée exclusivement à partir de l'ensemble des scores retournés et incluait également la valeur initialisée.Cela a gâché les résultats.

J'ai ajouté la comparaison suivante à la modification conditionnelle de "Score":

|| availableIndex == 0

Cela a forcé toutes les comparaisons restantes à effectuer contre une valeur appartenant à l'ensemble des scores retournés.

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

Regardons quelque chose de plus simple - le tableau est 1x1 et le premier joueur de placer une marque là-bas gagne.

Maintenant, l'ordinateur commence, Score= -1. Il n'y a pas de solution gagnante (le seul ensemble gagnant est coché, ce n'est pas une rangée de 1 in A-Row), et il y a un espace disponible. Nous procédons donc en arrière pour essayer la seule position disponible.

Maintenant Mark= Player, et le tableau a une solution gagnante.Donc l'ordinateur gagne, score= -1.

retour au premier appel, la ligne "INT NEXTSCORE= minimax (tableau, SUIMARMARK);"retourne -1 à nouveau et le score final est -1.

La même chose vous arrive avec le problème plus large.

Answer 3

Dans un jeu TIC TAC TOE, il y a 3 possibilités et non seulement 2: joueur1 gagne, joueur2 gagne, personne ne gagne.

Vous devez remplacer des lignes comme celle-ci:

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

Par quelque chose comme ça:

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