java-奥赛罗(Bitboard)中移动计算的优化

我一直在研究Java游戏Othello的实现,我将用于研究目的,并且我需要有一个快速的实现来运行尽可能多的游戏,所以我要做的是:

董事会[] []实施

我的第一种方法是使用board [] []多维数组表示董事会,只是为了使其正常工作,并确保其正常工作.我完成了,很高兴.但是,正如大多数人所知道的那样,这并不是很快,因为我每秒只能玩1,500场游戏(随机移动,仅用于测试).

位板

然后,我将该板实现为BitBoard,从而大大加快了移动计算,并且与以前的实现相比非常快.通过这种实现,它每秒最多可以玩2万个游戏.这是我用于移动计算的代码,效果很好,但是重复了一下:

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方法调用是否昂贵?是因为是从数组调用对象吗?是因为我为每种方法传递了long n的副本?

任何想法都很棒,因为我不太擅长优化代码.

谢谢!

解决方法:

Java字节码与本地asm代码完全不同.使用接口和多态时,它的执行方式与代码中的执行方式相同.方法调用也是如此.

Java字节码生成中没有优化,因此这是较慢的原因.函数调用比重复的内联代码慢,而后期绑定比静态绑定慢.

但是,我比第一个更喜欢您的第二个代码,我相信它应该保持这样.

上一篇:php-网站如何在不重新加载页面的情况下检查登录凭据?


下一篇:Windows高精度时间