Adversarial N-player Search using Locality for the Game of Battlesnake

Abstract

This paper presents an approach to designing a planning agent for simultaneous N-player games. We propose to reduce the complexity of such games by limiting the search to players in the locality of the acting agent. For Battlesnake, the game at hand, an iterative deepening search strategy utilizing both alpha-beta and max^n search is suggested. Useful metrics for estimating player advantage are presented, especially using a diamond flood filler for measuring board control. Furthermore, the process of our heuristic parameter tuning with a grid search and a genetic algorithm is described. We provide a qualitative analysis of our algorithm's performance at the international artificial intelligence competition Battlesnake, Victoria. Here, our agent placed second in the intermediate division.