After experimenting again with how to store each move and score and looking at Java streams I found this code example. As the example used a new class with instance variables for each important value.
I created a new class called BestScore and gave it the instance variables move and score.
public static class BestScore {
private final int move;
private final int moveScore;
public BestScore(int move, int moveScore) {
this.move = move;
this.moveScore = moveScore;
} public int getMoveScore() {
return moveScore;
} public int getMove() {
return move;
}}
Each time I looped over a move instead of pushing the current move and its score into a hash, I created a new instance of BestScore with the current move and score.
private List<BestScore> scores = new ArrayList<>(); public int findBestMove(Board board, Boolean maximisingPlayer) {
Mark opponentMark = mark == Mark.O ? Mark.X : Mark.O;
if (board.gameIsOver()) {
if (board.playerHasWon(mark)) {
return 1;
} else if (board.playerHasWon(opponentMark)) {
return -1;
} else if (board.gameIsTied()) {
return 0;
}
} if (maximisingPlayer) {
int bestScore = -10;
List<Integer> possibleMoves = board.availableMoves();
for (int move : possibleMoves) {
board = board.updateMove(move, mark);
int currentScore = findBestMove(board, false);
bestScore = bestScore > currentScore ? bestScore : currentScore;
board = board.updateMove(move, Mark.EMPTY);
scores.add(new BestScore(move, bestScore));
}
bestMove = maxMove(scores).getMove();
return maxMove(scores).getMoveScore();
} else {
int bestScore = +10;
List<Integer> possibleMoves = board.availableMoves();
for (int move : possibleMoves) {
board = board.updateMove(move, opponentMark);
int currentScore = findBestMove(board, true);
bestScore = bestScore < currentScore ? bestScore : currentScore;
board = board.updateMove(move, Mark.EMPTY);
scores.add(new bestScore(move, bestScore));
}
bestMove = minMove(scores).getMove();
return minMove(scores).getMoveScore();
}
}
Each time a new move was played, I add it to the scores array with this line.
scores.add(new BestScore(move, bestScore));Instead of sorting the list of scores from largest to smallest, I used the Java Stream methods max and min. These methods use an instance of Comparator and compare values in a stream to get the maximum or minimum value.
public BestScore maxMove(List<BestScore> scores) {
BestScore highestScoringMove = scores.stream()
.max(Comparator.comparing(BestScore::getMoveScore))
.orElse(new BestScore(-1, -1));
return highestScoringMove;
}public BestScore minMove(List<BestScore> scores) {
BestScore lowestScoringMove = scores.stream()
.min(Comparator.comparing(BestScore::getMoveScore))
.orElse(new BestScore(-1, -1));
return lowestScoringMove;
}
I thought this would be my solution and in theory it seemed to answer all of my problems. Though it seemed to work when it choosing the best move for my player in a winning game state, when it had to choose a move to block a player win, it didn’t work.
I used System.out all of the findBestMove() method to try and figure out was was going on. I tried tweaking the method in numerous places to see if it helped me solve the problem and changed the outcome. I was going in circles.
I’m still not sure 100% why the min and max methods weren’t working in the game flow as they should. I have a theory it’s because when the player type switched to simulate each game state the scores list got populated incorrectly. I stopped at that point to reassess how best to move forward with the code.
I decided to go back to basics. I needed to figure out what was happening with my code. I needed a better strategy and a series of next steps. Below are the things I tried:
- Identify patterns with regards to where the computer player isn’t playing as it should. For example, it seemed like if the computer played position 3 first then it ended up losing. Whereas, if I played position 3 first then the computer played the correct steps.
After trying the step above, it didn’t seem like I identified a consistent and helpful pattern, just one of many issues with the algorithm not working as expected.
2. My next idea was to visit other people’s code and look at pseudocode to see if there were issues within my implementation. Perhaps the maximising and minimising players were not switching as they should or there were other issues that I was overlooking.
After printing the value of my move in various places in my code I could see that the best move was correct until it was sent to the minMove or maxMove methods. After coming back from being passed to those methods, it would just return whatever move had been played before.
bestMove = minMove(scores).getMove();
return minMove(scores).getMoveScore();The only two things I cared about were the best move and score. If those were being filtered by the If statement then why did I need the minMove and maxMove methods? I decided to keep it simple and return a list of the move and score.
I also noticed an if statement in another person’s code that acted like a filter to re-write both bestMove and bestScore instead of just rewriting just the bestScore using the turnery operator.
Before:bestScore = bestScore < currentScore ? bestScore : currentScore;After:// This is for the minimising player, for the maximising player the condition is if currentScore is greater than bestScore.if (currentScore < bestScore) {
bestScore = currentScore;
bestMove = move;
}
I used this code in mine to remove the turnery operator and changed the code to return a list of bestMove and bestScore.
if (maximisingPlayer) {
int bestScore = -10;
List<Integer> possibleMoves = board.availableMoves();
for (int move : possibleMoves) {
board = board.updateMove(move, mark);
int currentScore = findBestMove(board, false).get(1);
if (currentScore > bestScore) {
bestScore = currentScore;
bestMove = move;
}
board = board.updateMove(move, Mark.EMPTY);
}
return asList(bestMove, bestScore);
} else {
int bestScore = +10;
List<Integer> possibleMoves = board.availableMoves();
for (int move : possibleMoves) {
board = board.updateMove(move, opponentMark);
int currentScore = findBestMove(board, true).get(1);
if (currentScore < bestScore) {
bestScore = currentScore;
bestMove = move;
}
board = board.updateMove(move, Mark.EMPTY);
}
return asList(bestMove, bestScore);
} This worked perfectly and suddenly I had successfully implemented Minimax!
