COMPUTING TIGERS AND GOATS

Article type: Research Article

Authors: Yew-Jin, Lim^{a; 1} | Nievergelt, J.^{b; 2}

Affiliations: [a] Singapore | [b] Zurich, Switzerland

Note: [1] School of Computing, National University of Singapore, Singapore. Email: [email protected].

Note: [2] Dept. Informatik, ETH Zurich, Zurich, Switzerland. Email: [email protected].

Abstract: Bagha Chal, or Moving Tiger, is an ancient Nepali board game also known as Tigers and Goats. We describe the game, some of its characteristics, and insights gained from an incomplete computer analysis. As in some other games such as Merrill’s, play starts with a placement phase where twenty pieces are dropped on the board, followed by a sliding phase; during both phases pieces may be captured. The endgame-sliding phase is analysed exhaustively using retrograde analysis. After removal of symmetries, the complete database of all positions that arise consists of 88,260,972 entries. The placement phase involves a search whose game-tree complexity is estimated to be of the order 1041. Partial results show that Tigers appears to have the better part of the opening, but Goats may catch up in the long run.

DOI: 10.3233/ICG-2004-27302

Journal: ICGA Journal, vol. 27, no. 3, pp. 131-141, 2004