Mathematics – Combinatorics
Scientific paper
2012-02-04
Mathematics
Combinatorics
10 pages, 1 figure
Scientific paper
e-Valuate is a game on arithmetic expressions. The players have contrasting roles of maximizing and minimizing the given expression. The maximizer proposes values and the minimizer substitutes them for variables 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.
Aravamuthan Sarang
Ganguly Biswajit
No associations
LandOfFree
e-Valuate: A Two-player Game on Arithmetic Expressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with e-Valuate: A Two-player Game on Arithmetic Expressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and e-Valuate: A Two-player Game on Arithmetic Expressions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-329952