Othello (Bitboard)移动计算的优化

Question

我一直致力于在Java中实现Othello游戏，我将用于研究目的，我需要一个快速的实现来运行尽可能多的游戏，所以这就是我所做的：

板实现

我的第一种方法是使用一个板多维数组来表示板，只是为了使它工作，并确保它正常工作。我完成了，我很高兴。但是，正如大多数人所知道的，这并不是很快，因为我只能每秒玩1500场游戏(做随机动作，只是为了测试)。

Bitboard

然后，我将板实现为BitBoard，它大大加快了移动计算的速度，与以前的实现相比，速度更快。有了这个实现，它可以每秒玩多达20k的游戏。这是我用于移动计算的代码，它运行得很好，但重复如下：

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

类

然后我试着用这种方式来清理代码：

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).

由于某些原因，使用这种方法，我只能运行15k的游戏每秒！为什么这段代码要慢得多？Java方法调用昂贵吗？是因为调用和对象来自数组吗？是因为我传递每个方法的长n的副本吗？

任何想法都会很好，因为我并不擅长优化代码。

谢谢!

Answer 1

Java字节码与本机asm代码完全不同。当您使用接口和多态时，它将以与代码中相同的方式执行。方法调用也是如此。

在java字节码的生成过程中没有进行优化，这就是为什么它要慢一些的原因。函数调用比重复内联代码慢，后期绑定比静态绑定慢。

但是，我更喜欢你的第二段代码，而不是第一段代码，我认为它应该保持这样。

Answer 2

使用数组不会增加那么多开销。

我认为方法调用可能会增加最大的开销，特别是如果它们没有得到优化。

您可以尝试类似于原始代码的方法调用，使用方法调用，而不需要包装类，并查看性能是否更好；我似乎还记得Java优化getter和setter，因此可能会将调用的方法放入类中，从而阻止其进行类似的优化。