2010/05/10 by Jean-Vincent Loddo, Loddo, Jean-Vincent, Luca Saiu +1
Computer Science · #08-04 #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Symbolic Computation (cs.SC) #cs.AI #cs.DM #cs.GT #cs.SC #msc:08-04
paper · pdf · doi:10.48550/arxiv.1005.1475
To appear in "Artificial Intelligence and Symbolic Computation, 2010".
openalex publication_date 2010/05/10 · arxiv created 2010/05/11 · arxiv updated 2015/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present tropical games, a generalization of combinatorial min-max games based on tropical algebras. Our model breaks the traditional symmetry of rational zero-sum games where players have exactly opposed goals (min vs. max), is more widely applicable than min-max and also supports a form of pruning, despite it being less effective than alpha-beta. Actually, min-max games may be seen as particular cases where both the game and its dual are tropical: when the dual of a tropical game is also tropical, the power of alpha-beta is completely recovered. We formally develop the model and prove that the tropical pruning strategy is correct, then conclude by showing how the problem of approximated parsing can be modeled as a tropical game, profiting from pruning.