Tigers and Goats is a draw
Lim Yew Jin, Jürg Nievergelt · 2009
A bstract . Bagha Chal, or “Moving Tiger”, is an ancient Nepali board game also known as Tigers and Goats . We briefly describe the game, some of its characteristics, and the results obtained from an earlier computer analysis. As in some other games such as Merrill's, play starts with a placement phase where 20 pieces are dropped on the board, followed by a sliding phase during which pieces move and may be captured. The endgame sliding phase had been analyzed exhaustively using retrograde analysis, yielding a database consisting of 88,260,972 positions, which are inequivalent under symmetry. The placement phase involves a search of 39 plies whose game tree complexity is estimated to be of the order 10 41 . This search has now been completed with the help of various optimization techniques. The two main ones are: confronting a heuristic player with an optimal opponent, thus cutting the search depth in half; and constructing a database of positions halfway down the search tree whose game-theoretic value is determined exhaustively. The result of this search is that Tigers and Goats is a draw if played optimally. Introduction Bagha Chal, or “Moving Tiger”, is an ancient Nepali board game, which has recently attracted attention among game fans under the name Tigers and Goats . This game between two opponents, whom we call “Tiger” and “Goat”, is similar in concept to a number of other asymmetric games played around the world–asymmetric in the sense that the opponents fight with weapons of different characteristics, a feature whose entertainment value has been known since the days of Roman gladiator combat.