Tic Tac Toe с MiniMax: компьютер иногда проигрывает, когда игрок идет первым;работает иначе
-
12-12-2019 - |
Вопрос
Я работаю над алгоритмом MiniMax для непревзойденного TIC TAC TAC.Мне нужно, чтобы он работал как для того, когда компьютер пойдет первым, так и когда игрок пойдет первым.С текущей версией компьютер никогда не проиграет при первом ходе.Однако, похоже, что MiniMax никогда не находит лучшее движение (всегда возвращает -1 в качестве оценки), если проигрыватель идет первым.
Что вызывает балл MiniMax, возвращаемую, чтобы быть -1 для компьютера, если игрок делает первый шаг?
Пример:
board.addMark( 1, Mark2.PLAYER ); // add a 'PLAYER' mark to an arbitrary location
Minimax.minimax( board, Mark2.COMPUTER ); // will always return -1
.
Вот класс 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;
}
}
.
Вот класс доски:
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
}
. Решение 3
После принятия расширенного перерыва и с помощью ответа @Guyadini у меня было эпопание.Я написал тест для подсчета возникновения трех возможных оценок, возвращаемых 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;
}
}
. Другие советы
Давайте посмотрим на что-то проще - доска 1x1, а первый игрок поместил там марки, выигрывает.
Теперь компьютер начинается, оценка= -1. Нет выигрышного решения (проверяется один выигрышный набор, это не 1-in-ряд), И есть доступное пространство. Таким образом, мы продолжаем обратно, чтобы попробовать одну доступную позицию.
Теперь mark= player, а доска имеет выигрышное решение.Так что компьютер выигрывает, оценка= -1.
Возвращение к первому вызову, строка "int nextscore= miniMax (доска, следующая оценка);"Возвращает -1 снова, и окончательный счет --1.
То же самое происходит с вами с большей проблемой.
в Tic Tac Toe Game есть 3 возможности, а не только 2: Player1 выигрывает, Player2 выигрывает, никто не выигрывает.
Вы должны заменить строки, подобные этой:
int score = (currentMark == Mark2.COMPUTER) ? -1 : 1;
.
что-то вроде этого:
int score = (currentMark == Mark2.COMPUTER) ? -1 : ((currentMark == Mark2.PLAYER) ? 1 : 0);
.