I am working on an implementation of the Othello game in Java, which I will use for research purposes, and I need to have a quick implementation to run as many games as possible, so this is what I did:
Tip [] [] implementation
My first approach was to use the multidimensional array [] [] to represent the board so that it worked, and to be sure that it was working correctly. I finished and I was happy. But, as most people know, this is not very fast, since I could only play 1,500 games per second (making random moves, just for testing).
Bitboard
Then I implemented the board as BitBoard, which significantly speeds up the calculation of movement and grows rapidly compared to the previous implementation. With this implementation, he can play up to 20 thousand games per second. This is the code I use to calculate the displacement, which works very well, but repeats:
private void calculateMoves() {
legal = 0L;
long potentialMoves;
long currentBoard = getCurrentBoard();
long opponentBoard = getOpponentBoard();
long emptyBoard = emptyBoard();
// UP
potentialMoves = (currentBoard >> SIZE) & DOWN_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves >> SIZE) & DOWN_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
// DOWN
potentialMoves = (currentBoard << SIZE) & UP_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves << SIZE) & UP_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
// LEFT
potentialMoves = (currentBoard >> 1L) & RIGHT_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves >> 1L) & RIGHT_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
// RIGHT
potentialMoves = (currentBoard << 1L) & LEFT_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves << 1L) & LEFT_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
// UP LEFT
potentialMoves = (currentBoard >> (SIZE + 1L)) & RIGHT_MASK & DOWN_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves >> (SIZE + 1L)) & RIGHT_MASK & DOWN_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
// UP RIGHT
potentialMoves = (currentBoard >> (SIZE - 1L)) & LEFT_MASK & DOWN_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves >> (SIZE - 1L)) & LEFT_MASK & DOWN_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
// DOWN LEFT
potentialMoves = (currentBoard << (SIZE - 1L)) & RIGHT_MASK & UP_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves << (SIZE - 1L)) & RIGHT_MASK & UP_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
// DOWN RIGHT
potentialMoves = (currentBoard << (SIZE + 1L)) & LEFT_MASK & UP_MASK & opponentBoard;
while (potentialMoves != 0L) {
long tmp = (potentialMoves << (SIZE + 1L)) & LEFT_MASK & UP_MASK;
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
moves.clear();
}
Classes
Then I tried to clear the code a bit as follows:
private MoveFinder[] finders = new MoveFinder[] {new UpFinder(), new DownFinder(), new LeftFinder(),
new RightFinder(), new UpLeftFinder(), new UpRightFinder(), new DownLeftFinder(), new DownRightFinder()};
private void calculateMoves() {
legal = 0L;
long potentialMoves;
long currentBoard = getCurrentBoard();
long opponentBoard = getOpponentBoard();
long emptyBoard = emptyBoard();
for (MoveFinder finder : finders) {
potentialMoves = finder.next(currentBoard) & opponentBoard;
while (potentialMoves != 0L) {
long tmp = finder.next(potentialMoves);
legal |= tmp & emptyBoard;
potentialMoves = tmp & opponentBoard;
}
}
moves.clear();
}
private interface MoveFinder {
long next(long next);
}
private class UpFinder implements MoveFinder {
@Override
public long next(long n) {
return (n >> SIZE) & DOWN_MASK;
}
}
private class DownFinder implements MoveFinder {
@Override
public long next(long n) {
return (n << SIZE) & UP_MASK;
}
}
For some reason, with this approach, I can only run 15 thousand games per second! Why is this code so much slower? Is the Java method expensive? Is it because the call and the object are from an array? Is it because I pass copies of long n for each method?
Any ideas would be great, because I'm not very good at optimizing the code.
Thank!