Minimax가있는 Tic Tac Toe : 컴퓨터가 먼저 진행될 때 때로는 컴퓨터가 잃어 버렸습니다.그렇지 않으면 작동합니다
-
12-12-2019 - |
문제
저는 탁월한 TIC TAC TOE를 위해 MiniMax 알고리즘을 연구하고 있습니다.컴퓨터가 먼저뿐만 아니라 플레이어가 먼저가는시기를 위해서 작업 할 수 있습니다.현재 버전을 사용하면 먼저 컴퓨터가 끊어지지 않을 것입니다.그러나 플레이어가 먼저가는 경우 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
.
'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의 응답에 도움이되면서 Epiphany가있었습니다.나는 minimax ()가 반환 한 세 가지 가능한 점수의 발생을 계산하는 테스트를 썼습니다.결과적으로 0에 대해 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이고 첫 번째 플레이어가 일시적으로 이긴다.
이제 컴퓨터가 시작됩니다. Score= -1. 우승 솔루션이 없습니다 (하나의 승리 세트가 선택되면, 그것은 1 인 - 행이 아닙니다). 사용 가능한 공간이 있습니다. 그래서 우리는 하나의 사용 가능한 위치를 시도하기 위해 역 추적을 수행합니다.
이제 mark= player이고 보드에는 워킹 솔루션이 있습니다.그래서 컴퓨터가 이기고 점수= -1.
첫 번째 호출로 돌아가는 "int nextScore= Minimax (보드, NextMark)"라인. "다시 -1을 반환하고 마지막 점수는 -1입니다.
더 큰 문제가있는 것과 동일한 일이 일어납니다.
Tic Tac Toe 게임에서는 3 가지 가능성이 있으며 2 : Player1 WINS, Player2 Wins, 아무도 승리하지 않습니다.
이런 일을 교체해야합니다.
int score = (currentMark == Mark2.COMPUTER) ? -1 : 1;
.
다음과 같은 것 :
int score = (currentMark == Mark2.COMPUTER) ? -1 : ((currentMark == Mark2.PLAYER) ? 1 : 0);
.