Tic Tac Toe with Minimax：当玩家先行时，计算机有时会失败; 否则

我正在为无与伦比的Tic Tac Toe开发Minimax算法。 我需要它同时适用于计算机何时首先以及何时首先播放。 使用当前版本，计算机在首先出现时永远不会丢失。 但是，如果玩家先行，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  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 } 

Answer 1

让我们看一些更简单的东西 – 棋盘是1×1，第一个在那里打上标记的玩家获胜。

现在计算机启动，得分= -1。 没有获胜的解决方案（一个获胜的集合被检查，它不是一个一行），并且有一个可用的空间。 所以我们通过回溯来尝试一个可用的位置。

现在Mark = PLAYER，董事会有一个成功的解决方案。 所以计算机获胜，得分= -1。

返回第一个调用，行“int nextScore = minimax（board，nextMark）;” 再次返回-1，最终得分为-1。

对于更大的问题，你也会遇到同样的事情。

Answer 2

在Tic Tac Toe游戏中，有3种可能性而不仅仅是2：Player1获胜，Player2获胜，没有人获胜。

你应该替换像这样的行：

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

通过这样的事情：

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

Answer 3

在rest了一段时间后，在@GuyAdini的回应帮助下，我顿悟了一下。 我写了一个测试来计算minimax（）返回的三个可能分数的出现次数。 因此，它没有为0产生任何结果，这让我想到这样一个事实，即我需要0才能被算法视为可能的分数。

我最初将’score’的初始化更改为最低/最高可能结果（-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; } }