I'm making a program to play the board game Quoridor. I build a move tree using Monte Carlo Tree Search (MCTS). MCTS requires me to test whether a node is expandable. A node is said to be expandable if it has a child node that hasn't already been visited.
How can I test whether a given node is expandable?
I know you could always try out every play possible given a node, and test whether each generated node is already a node in the tree, but that seems inefficient. Is there a more efficient algorithm?
The rules of Quoridor are (quoting from Wikipedia):
Quoridor is played on a game board of 81 square spaces (9x9). Each player is represented by a pawn which begins at the center space of one edge of the board (in a two-player game, the pawns begin opposite each other). The objective is to be the first player to move their pawn to any space on the opposite side of the gameboard from which it begins.
The distinguishing characteristic of Quoridor is its twenty walls. Walls are flat two-space-wide pieces which can be placed in the groove that runs between the spaces. Walls block the path of all pawns, which must go around them. The walls are divided equally among the players at the start of the game, and once placed, cannot be moved or removed. On a turn, a player may either move their pawn, or, if possible, place a wall.
Pawns can be moved to an adjacent space (not diagonally), or, if adjacent to another pawn, jump over that pawn. If an adjacent pawn has a third pawn or a wall on the other side of it, the player may move to any space that is immediately adjacent to other adjacent pawns. The official rules are ambiguous concerning the edge of the board.
Walls can be placed directly between two spaces, in any groove not already occupied by a wall. However, a wall may not be placed which cuts off the only remaining path of any pawn to the side of the board it must reach.
I'm using the Monte Carlo Tree Search algorithm, which follows these steps:
- Selection: Using a tree policy, like UCT1, nodes are selected while traversing down the tree
- Expansion: From the node selected by the tree policy, create a random child node
- Simulation: Either use a random simulation from the node or a system with a weighing of moves
- Backpropagation: If the simulation is victorious for the computer, add say each node "won" all the way up the tree. If it lost, then each node "lost" up the tree.
During the Selection step, one cannot select a node that is fully expanded. Is there a better way to check whether a node is expandable than just trying out every possible move from that node, and check if it is already in the tree? What algorithms exist for this (if any?)