Win, Lose, or Get Out the Way - Eliminating Unnecessary Evaluation in Game Search

Hsiu-Chin Lin, Colleen van Lent

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In this paper we present our approach of improving the traditional alpha-beta search process for strategic board games by modifying the method in two ways: 1) forgoing the evaluation of leaf nodes that are not terminal states and 2) employing a utility table that stores the utility for subsets of board configurations. In this paper we concentrate our efforts on the game of Connect Four. Our results have shown significant speed-up, as well as a framework that relaxes common agent assumptions in game search. In addition, it allows game designers to easily modify the agent's strategy by changing the goal from dominance to interaction.
Original languageEnglish
Title of host publicationProceedings of the Twenty-First International Florida Artificial Intelligence Research Society Conference, May 15-17, 2008, Coconut Grove, Florida, USA
PublisherThe AAAI Press
Number of pages2
Publication statusPublished - 2008

Cite this