Abstract. 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 1041. 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.