SA-UCT Sample Clauses

SA-UCT. Since NMCS is unsuitable for simplifying large expressions, we return our focus to MCTS, but this time on the UCT best child criterion. We now consider the role of the exploration-exploitation constant Cp. We notice that in the first iterations of the simulation there is as much exploration as there is in the final iterations, since Cp remains constant throughout the search. For example, the final 100 iterations of a 1000 iterations MCTS run are used to explore new branches even though we know in advance that there is likely not enough time to reach the final nodes. Thus we would like to modify the Cp to change during the simulation to emphasise exploration early in the search and emphasise exploitation towards the end. We introduce a new, dynamic exploration-exploitation parameter T that decreases linearly with the iteration number: p T(i) = C N − i , (9) N where i is the current iteration number, N the preset maximum number of iterations, and Cp the initial exploration-exploitation constant at i = 0. We modify the UCT formula to become: argmax children c of s x¯(c) + 2T(i) 2 ln n(s) , (10) n(c) where c is a child of node s, x¯(c) is the average score of child c, n(c) the number of visits at node c, and T(i) the dynamic exploration-exploitation parameter of formula (9). The role of T is similar to the role of the temperature in Simulated Annealing [69]: in the beginning of the simulation there is much emphasis on exploration, the analogue of allowing transitions to energetically unfavourable states. During the simulation the focus gradually shifts to exploitation, analogous to annealing. Hence, we call our new UCT formula “Simulated Annealing UCT (SA-UCT)”. In the past related changes have been proposed. For example, Discounted UCB [70] and Accelerated UCT [71] both modify the average score of a node to discount old wins over new ones. The difference between our method and past work is that the previous modifications alter the importance of exploring based on the history and do not guarantee that the focus shifts from exploration to exploitation. In contrast, this work focuses on the exploration-exploitation constant Cp and on the role of exploration during the simulation. We implemented four improvements over UCT. (1) The final iterations are used effectively. (2) There is more exploration in the middle and at the bottom of the tree. This is due to more nodes being expanded at lower levels, because the T is lowered. As a consequence, we see that (3) more...