Metis: A Compositional DSL for Board Games and Game Tree Search

Abstract

We present Metis, a domain-specific language embedded in Haskell for two-player board games on rectangular boards that exploits their shared structure (setup, rules, win condition) through three composable mini-DSLs. Atomic operations for placing, moving, and capturing pieces combine with filters, union, and sequencing to form rulesets; win conditions and evaluation functions reuse the same compositional pattern. With just 13 rule expressions Metis can express 80% of games from a catalog of 168 abstract games. The structure also supports game-playing agents through composable search and evaluation components.