Optimization of moves calculation in Othello (Bitboard)

Question

I've been working on an implementation of the game Othello in Java that I will to use for research purposes, and I need to have a fast implementation to run as many games as I can, so this is what I did:

Board[][] implementation

My first approach was to use a board[][] multidimensional array to represent the board, just to make it work, and to be sure that it was working properly. I finished it, and I was happy. But, as most people know, that's not very fast, since I was able to play only 1,500 games per second (making random moves, just for testing).

Bitboard

Then, I implemented the board as a BitBoard, which speeds up the move calculation a lot, and is blazing fast compared to the previous implementation. With this implementation it can play up to 20k games per second. This is the code that I use for move calculation, which works very nice, but is repeated:

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 clean up the code a bit this way:

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;
    }
}

// and so on for the rest of the moves (LeftFinder, RightFinder, etc).

For some reason, with this approach I'm able to run only 15k games per second! Why is this code much slower? Are Java method calls expensive? Is it because is calling and object from an array? Is it because I pass copies of the long n for each method?

Any ideas would be great, because I'm not really good at optimising code.

Thanks!

I used JProfiler and 50% of the time is spent in the move calculations, but I can't figure out why calling a method is slower, I don't see that in the profiler. Any ideas? — David Robles, May 10 '11 at 01:39
You should take your results with an extremely large grain of salt. Have you seen [How do I write a correct micro-benchmark in Java?](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java) — Matt Ball, May 10 '11 at 01:52

score 2 · Accepted Answer · answered May 10 '11 at 01:46

2

Java bytecode is nothing like native asm code. When you use interfaces and polymorphism, it is executed in the same way than it is in your code. Same goes for methods calls.

There are no optimisations done in the java bytecode generation so that's why it is slower. A function call is slower than duplicate inline code, and a late binding is slower than a static binding.

However, i like your second code more than the first and i believe it should stay like that.

answered May 10 '11 at 01:46

Joel

3,427
5
38
60

Yes, I like the second approach as well. But the thing is that for what I need to do (simulations), I need it to be as fast as possible. :S – David Robles May 10 '11 at 01:49

score 1 · Answer 2 · answered May 10 '11 at 01:53

Using the array shouldn't add that much overhead.

I think the method call is likely adding the most overhead, especially if they don't get optimized out.

You could try something like the original code and use method calls without the classes wrapping them and see if the performance is any better; I seem to recall Java optimizing getters and setters, so it may be possible putting the method called inside a class is keeping it from doing a similar optimization.

Optimization of moves calculation in Othello (Bitboard)

2 Answers2