是否可以使用jGraphT检查TicTacToe游戏的获胜条件？

Question

我发现这个有效的解决方案

private int[] winningPatterns = { 0b111000000, 0b000111000, 0b000000111, // rows
        0b100100100, 0b010010010, 0b001001001, // cols
        0b100010001, 0b001010100 // diagonals
};

/** Returns true if thePlayer wins */
private boolean hasWon(int thePlayer) {
    int pattern = 0b000000000; // 9-bit pattern for the 9 cells
    for (int row = 0; row < 3; ++row) {
        for (int col = 0; col < 3; ++col) {
            if (cells[row][col].content == thePlayer) {
                pattern |= (1 << (row * 3 + col));
            }
        }
    }
    for (int winningPattern : winningPatterns) {
        if ((pattern & winningPattern) == winningPattern)
            return true;
    }
    return false;
}

但我想知道使用图形逻辑是否有更优雅的解决方案.

更新:我也在研究在3x3板的不同和更大的变体中使用我的知识,我相信这种方法在美学上不能很好地扩展.

例如:https://en.wikipedia.org/wiki/Teeko

Answer 1

对于 25 x 25 板，我认为您的方法是可行的，但改进它的一些方法如下。

1. 在用户添加棋子的同时创建模式，因为这样只需要花费时间来遍历 WinningPatterns 数组。

2. 要改进第二部分，您可以尝试更有效地存储它。以可以同时检查多个的方式存储获胜模式。例如，如果第一个位置是 0，那么它可以从获胜模式中删除 3 种可能性，而不是仅一种（111 000 000、100 100 100、100 010 001）。

3. 您可以通过检查最有可能正确的位置来改进平均情况。例如，玩家将棋子放在中间有 4 种获胜方式，因此请按顺序检查。

4. 如果将玩家位置存储在单独的数组中，其中 p1Tiles 和 p2Tiles。那么这可能会大大增加平均情况，因为大多数时候董事会都是空的。在游戏板重置之前，它只会在该游戏的 1 个实例中充满。

5. 您实际上不需要检查玩家赢得的所有棋子，您只需要检查当前用户放置的棋子是否获胜。因此，使用这种方法，即使棋盘的尺寸为 99..999 x 99..999，您也只需要检查最坏情况下的 12 个其他点。（12 因为当前插槽周围的所有插槽加上如果有两个彼此相邻的相同颜色，那么您将不得不查看以下插槽）