Вопрос по algorithm, java – Tic Tac Toe с минимаксом: компьютер иногда проигрывает, когда игрок идет первым; работает иначе

4

Я работаю над алгоритмом Minimax для непревзойденного Tic Tac Toe. Мне нужно, чтобы он работал как для того, когда компьютер запускается первым, так и для того, когда проигрыватель идет первым. С текущей версией, компьютер никогда не проиграет, когда пойдет первым. Тем не менее, кажется, что Minimax никогда не находит лучший ход (всегда возвращает -1 в качестве результата), если игрок идет первым.

Что приводит к тому, что минимаксное значение, возвращаемое для компьютера, равно -1, если игрок делает первый ход?

Пример:

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

Здесь «минимакс»; учебный класс:

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

Вот это «доска» учебный класс:

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

А вот это и есть "Mark2". класс, если была какая-то путаница:

public enum Mark2 {
  BLANK,
  PLAYER,
  COMPUTER
}
"unbeatable Tic Tac Toe." Вы когда-нибудь задумывались об использовании своих сил ... дляgood?  Какое удовольствие это непобедимый крестики-нолики? ;) Andrew Thompson
Хороший вопрос, но для более быстрой помощи (добавьте эти источники в один файл, добавьтеmain & amp;) опубликоватьSSCCE. Andrew Thompson
@ AndrewThompson Самое интересное, конечно, заставить его работать должным образом. jneander

Ваш Ответ

3   ответа
0

и выигрывает первый игрок, поставивший там отметку.

Теперь компьютер запускается, оценка = -1. Нет выигрышного решения (проверяется один выигрышный набор, он не один в ряд), и есть свободное место. Итак, мы возвращаемся назад, чтобы попробовать одну доступную позицию.

Теперь Марк = ИГРОК, и у доски есть выигрышное решение. Итак, компьютер побеждает, оценка = -1.

Возвращаясь к первому звонку, строка "int nextScore = minimax (board, nextMark); & quot; возвращает -1 снова, и окончательный результат равен -1.

То же самое происходит с вами с большей проблемой.

0

игрок 1 выигрывает, игрок 2 выигрывает, никто не выигрывает.

Вы должны заменить строки следующим образом:

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

примерно так:

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

ло прозрение. Я написал тест для подсчета появления трех возможных результатов, возвращаемых minimax (). В результате он ничего не дал для 0, что подсказало мне тот факт, что мне нужно было 0, чтобы алгоритм рассматривал его как возможную оценку.

Первоначально я изменил инициализацию «баллов» быть самыми низкими / самыми высокими возможными результатами (-1/1) и сравниваться с ними. Однако это запретило результату получать наименьшее / наибольшее значение исключительно из набора возвращенных баллов и вместо этого также включало инициализированное значение. Это испортило результаты.

Я добавил следующее сравнение к условному изменению «показателя»:

|| availableIndex == 0

Это заставило все оставшиеся сравнения сравнивать со значением, которое принадлежало набору возвращенных результатов.

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

Похожие вопросы