Progressive Widening

Games with a large number of possible successor states are a big problem for MCTS. Centurio would need a huge number of random games to gain enough information for every child to make an intelligent move. Remember that every child from a node is a successor state. In sequential games this problem occurs when a state has a huge number of legal moves. The good news is that the most sequential games don't have so much legal moves per state. But the bad news is that parallel games often have a huge number of successor states. This is because the set of all successor states is the cross product of all legal moves from each player.

To handle this problem Centurio uses progressive widening. The idea is to gain a minimum set of information (n(s)) for every successor state e.g. with UCT-RAVE. When the minimum set of information is available (n(s) = T) the most successor states becoming hidden for MCTS. Only the most promising child's are left and this small set of successor states is called kinit. The following MCTS steps only uses kinit until enough new information are available (n(s) > T). Every time when enough new information are available a new action becomes visible for MCTS. The kth action becomes visible when the formula below is valid for k.

A is the set of all possible actions

All possible successor states were ordered by the heuristic (e.g. UCT-RAVE) from each child at the time of n(s) = T. The values of kinit, T, A and B should be different from game to game and T must be a multiple of the number of possible successor states to gain enough information.

In some cases the problem is so big that it is not possible to play the minimum of one random game per child. Progressive widening doesn't help in this worst case.