e-Valuate: A Two-player Game on Arithmetic Expressions
Sarang Aravamuthan, Biswajit Ganguly · arXiv (Cornell University) · 2012
e-Valuate is a game on arithmetic expressions. The players have con-trasting roles of maximizing and minimizing the given expression. The maximizer proposes values and the minimizer substitutes them for vari-ables of his choice. When the expression is fully instantiated, its value is compared with a certain minimax value that would result if the players played to their optimal strategies. The winner is declared based on this comparison. We use a game tree to represent the state of the game and show how the minimax value can be computed efficiently using backward induction and alpha-beta pruning. The efficacy of alpha-beta pruning depends on the order in which the nodes are evaluated. Further improvements can be obtained by using transposition tables to prevent reevaluation of the same nodes. We propose a heuristic for node ordering. We show how the use of the heuristic and transposition tables lead to improved performance by comparing the number of nodes pruned by each method.