0
$\begingroup$

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:

  1. Selection: Using a tree policy, like UCT1, nodes are selected while traversing down the tree
  2. Expansion: From the node selected by the tree policy, create a random child node
  3. Simulation: Either use a random simulation from the node or a system with a weighing of moves
  4. 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?)

$\endgroup$
  • $\begingroup$ We're getting closer, but I still don't understand your question. 1. What makes you think that you're not allowed to select a node that has already been fully expanded? Why do you think that MCTS requires you to know which nodes are expandable? I wonder if this might be based on a faulty premise. Can you edit to document the source of these statements, and explain why you think you're only allowed to use expandable nodes? 2. Is this specific to Quoridor somehow? Do I really need to know any of the rules of Quoridor? It seems like this is a general question about MCTS. $\endgroup$ – D.W. Mar 25 '16 at 17:53
1
$\begingroup$

You keep track of your work so far. As you say, a node is expandable if it has a child node which you haven't visited so far. In your program, every time you reach a new node in the expansion phase, you calculate all its children (you can also do this dynamically, but let's keep things simple). As time goes on, you mark each child which has been visited. In order to know whether a node is expandable, you just check whether all its children have been marked.

Of course, you don't really need to check all children. You can keep a counter at each node that counts the number of unvisited children. The next question would be – how do I find an unvisited child. It's a nice elementary exercise finding a way to achieve this efficiently.

$\endgroup$
  • $\begingroup$ Good answer! That's what I was doing before the question was asked... Just wanted to know whether there is a more efficient way to do it. Thanks! $\endgroup$ – APCoding Apr 11 '16 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.