Advances in high energy physics have created the need to increase computational capacity. Project HEPGAME was composed to address this challenge. One of the issues is that numerical integration of expressions of current interest have millions of terms and takes weeks to compute. We have investigated ways to simplify these expressions, using Horner schemes and common subexpression elimination. Our approach applies MCTS, a search procedure that has been successful in AI. We use it to find near-optimal Horner schemes. Although MCTS finds better solutions, this approach gives rise to two further challenges. (1) MCTS (with UCT) introduces a constant, @math that governs the balance between exploration and exploitation. This constant has to be tuned manually. (2) There should be more guided exploration at the bottom of the tree, since the current approach reduces the quality of the solution towards the end of the expression. We investigate NMCS (Nested Monte Carlo Search) to address both issues, but find that NMCS is computationally unfeasible for our problem. Then, we modify the MCTS formula by introducing a dynamic exploration-exploitation parameter @math that decreases linearly with the iteration number. Consequently, we provide a performance analysis. We observe that a variable @math solves our domain: it yields more exploration at the bottom and as a result the tuning problem has been simplified. The region in @math for which good values are found is increased by more than a tenfold. This result encourages us to continue our research to solve other prominent problems in High Energy Physics.
Expression simplification is a widely studied problem. We have already mentioned Horner schemes @cite_20 , and common subexpression elimination (CSEE) @cite_4 , but there are several other methods, such as partial syntactic factorization @cite_12 and Breuer's growth algorithm @cite_24 . Horner schemes and CSEE do not require much algebra: only the commutative and associative properties of the operators are used. Much research is put into simplifications using more algebraic properties, such as factorization, especially because of its interest for cryptographic research. In section we will introduce modifications to UCT, in order to make the importance of exploration versus exploitation iteration-number dependent. In the past related changes have been proposed. For example, Discounted UCB @cite_14 and Accelerated UCT @cite_22 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 @math and on the role of exploration during the simulation.
@cite_14 @cite_4 @cite_22 @cite_24 @cite_20 @cite_12
1468005580 2066433655 1981663184 2141600282
Monte-Carlo Tree Search (MCTS) is a successful approach for improving the performance of game-playing programs. This paper presents the Accelerated UCT algorithm, which overcomes a weakness of MCTS caused by deceptive structures which often appear in game tree search. It consists in using a new backup operator that assigns higher weights to recently visited actions, and lower weights to actions that have not been visited for a long time. Results in Othello, Havannah, and Go show that Accelerated UCT is not only more effective than previous approaches but also improves the strength of Fuego, which is one of the best computer Go programs. Given a set of expressions which are to be compiled, methods are presented for increasing the efficiency of the object code produced by first factoring the expressions, i.e. finding a set of subexpressions each of which occurs in two or more other expressions or subexpressions. Once all the factors have been ascertained, a sequencing procedure is applied which orders the factors and expressions such that all information is computed in the correct sequence and factors need be retained in memory a minimal amount of time. An assignment algorithm is then executed in order to minimize the total number of temporary storage cells required to hold the results of evaluating the factors. In order to make these techniques computationally feasible, heuristic procedures are applied, and hence global optimal results are not necessarily generated. The factorization algorithms are also applicable to the problem of factoring Boolean switching expressions and of factoring polynomials encountered in symbol manipulating systems. Indicia receiving matte sheet materials, comprising a polyester base support precoated with a cellulosic film-forming polymer and having an outermost layer of an antistatic composition comprising a sulphonated polystyrene and a cycloaliphatic amine salt of an alcohol sulphate. Minimizing the evaluation cost of a polynomial expression is a fundamental problem in computer science. We propose tools that, for a polynomial P given as the sum of its terms, compute a representation that permits a more efficient evaluation. Our algorithm runs in d(nt)O(1) bit operations plus dtO(1) operations in the base field where d, n and t are the total degree, number of variables and number of terms of P. Our experimental results show that our approach can handle much larger polynomials than other available software solutions. Moreover, our computed representation reduce the evaluation cost of P substantially.