java生成所有可能的对称Tic-Tac趾板

Question

我正在写一个遗传算法程序，它将开发出解决Tic-Tac-Toe问题的最佳解决方案。我做了很多研究，发现考虑到电路板的对称性，有765种可能的电路板组合。我需要编写一个代码来生成每个组合，但我不知道如何做到这一点。我不熟悉编码，不知道如何将对称性融入到代码中

你将如何创建一个代码来生成Tic-Tac趾板的每一个可能的唯一板组合（考虑到对称性）

Here这是一个很好的解释对称性的文档：

谢谢!

Answer 1

你可以像在minimax中那样通过构建游戏树来实现这一点，但是不要计算棋盘的值，而是将它们放在你首选的数据结构中，用于存储所有765个棋盘。一些示例代码，如果有帮助：

//Where you'll save the unique boards
HashSet<Board> mySavedBoards = new HashSet<Board>();
mySavedBoards.add(emptyBoard) //add the original empty board

//player = 'X' or 'O'
public static void find_all_boards(Board board, String player) {
    for (Move move : board.get_all_possible_moves()) {
        board = board.applyMove(move, player);
        my_saved_boards.add(board);
        if(!board.isWin()) {
            next_player = (player == 'O') ? 'X' : 'O';
            find_all_boards(board, next_player);
        }
    }
}

• get_all_possible_moves(board)只需返回网格中的空方块列表（玩家可以去的任何地方）
• board.applyMove(move)采取一个移动，并返回与玩家（'X'或'O'一起玩该移动所产生的棋盘
• isWin()返回此棋盘是否是某个玩家的胜利（即不要继续寻找更多棋盘）

这段代码将访问所有可能的tic-tac趾板，但会有一些重复，因此您必须隐式地管理这段代码（覆盖您的Board类的equals和hashCode，以便为您执行此检查，这样当您将该板添加到HashSet时，它不会添加重复项）

这在很大程度上取决于你对董事会、行动和球员的陈述，但我希望这个总体想法能有所帮助

编辑：我知道你在问如何生成对称电路板 我会使用两种方法，你可以在黑板上写：flip()，rotate()。您可以使用此方法生成电路板的8种变体，如下所示。您可以编写equals方法来检查给定的电路板是否在另一个电路板的变量集中

boolean equals(Board other) {
    //Insert normal checks for object type here
    HashSet<Board> variantsOfOther = other.variants();
    return variantsOfOther.contains(this)
}