Thread-Parallelization

The Centurio thread parallelization uses local mutexes (soft barriers) to ensure that all threads can access the game tree without any race conditions. In other words every node has an own mutex. When a thread access a node, it reduces the node's UCT value with the formula

where t(s, a) is the number of threads with state s including action a and A is the set of all possible actions. In the most cases the UCT values are small and a reduced UCT value cause other threads to choose a node with a higher value. The result of this case is, that every thread choose another way through the game tree. A very promising way to victory consist of nodes with very high UCT values. In this case it is possible, that threads take the same way through the game tree. With this strategy the UCT heuristic doesn't lose much influence and Centurio distributes the processor cores over the most interesting branches.