Who Wins Bagh-Chal When Nobody Makes a Mistake?

The rules

The four tigers start on the four corners, and the goats move first. A move is one player’s turn.

• a.Placing. While goats are left to place, each goat move puts one new goat on any empty point. The tigers move in between, so placing all 20 goats takes 39 moves.
• b.Moving. Once all the goats are on the board, a goat moves by stepping along a line to an empty point next to it. A tiger always moves like that, from the start.
• c.Jumping. A tiger may instead jump over a goat next to it, in a straight line along the lines, to the empty point just beyond, and the goat is taken off the board. One goat a jump; a tiger can’t jump over a tiger.
• d.Winning. The tigers win when they have taken five goats. The goats win when no tiger can move. (In the rare case where the goats can’t move, the tigers win.)

The lines matter. Every point has lines to the points beside it, above and below; the points where the diagonals cross also have lines corner to corner. On this board, those are the points whose row and column add up to an even number: the corners, the middle, and every other point between them.

Rule sheets differ a little: some say that once all the goats are placed, no move may bring back a position seen before. And a game where neither side can win could go on forever. So this page’s board has two rules of its own, the same for both sides: a game is a draw when the same position comes up a third time, or when 50 moves (25 each) go by with no goat placed or taken. They end some long games that one side might have won with more time.

Where the first goat goes

Press New game and put your first goat on b5, the point next to the top left corner. Watch what the tiger on a5 does.

Goats against tigers

Now let the computer play both sides. The page’s goats, Looks 2, look two moves ahead: their own move and the tigers’ reply. They judge a position only by how many goats are left. Press Play 20 games.

Solving a game

A game like Bagh-Chal, where the two players take turns, both see everything, and no dice are thrown, has a right answer: with perfect play from both sides, either the first player wins, or the second does, or it is a draw. Finding that answer is called solving the game. In the tic-tac-toe topic, a short program solved tic-tac-toe by playing out all 255,168 games. Chess has about 10¹²⁰ games and has not been solved.

Bagh-Chal is in between. Its board is small, but each goat can be placed on any empty point, so each goat placed early in the game has about 20 points to choose from. Lim and Nievergelt estimated that the tree of every way the 39 moves of the placing could go has about 10⁴¹ positions in it: playing out every game, as in tic-tac-toe, is out of the question.

Proving something about the game

They didn’t try to find the best move in every position. Instead, they asked questions with a yes or no answer, such as: can the tigers be sure of taking a goat within 10 moves? A search answers such a question with two rules:

• When it is the tigers’ move, the answer is yes if one tiger move leads to yes. The search can stop at the first one it finds.
• When it is the goats’ move, the answer is yes only if every goat move leads to yes. The search can stop at the first goat move that leads to no: one escape is enough for the goats.

Here is that search on a small made-up tree, written as lists inside lists. The tigers have three moves to choose from; after each, the goats have two replies. After one of those replies, the tigers choose again between two moves. At the ends of the lines, “taken” means a goat is taken there, and “safe” that it isn’t.

From both ends of the game

Lim and Nievergelt worked from both ends of the game.

• From the end. Once all 20 goats are placed, the game is a matter of moving, with at most 4 goats already taken (a fifth ends it). They listed every position that can happen then, 88,260,972 of them (counting a position and its turned or flipped copies once), and worked out the result of each one backwards from the positions where the game is over, a method called retrograde analysis.
• From the start. For the 39 moves of the placing they used searches like the one above, with a trick to halve the work: one side was played by a strong program that suggested only one or a few good moves, while the other side tried every move. If the strong player still got its result against every reply, the claim was proved.

Their earlier work built the endgame database, and computer runs over a couple of months proved that the goats can be sure of at least a draw. Proving that the tigers can always draw too, so that the goats can’t win, was harder. The search stored the results of positions met halfway through the placing, after 10 goats were placed: 216,519,984 of them in the end. After five months of trying and improving their programs, it finished, and separately written programs checked it. Bagh-Chal is a draw.

Step 1: the rules, and how fast the game grows

The page has the rules of Bagh-Chal in Python, in a file called baghchal.py that every program in this topic imports. A board is a list of 5 strings, one for each row of points from the top: 'T' a tiger, 'G' a goat and '.' an empty point. Placing a goat is a move of two numbers, the row and column of the point; a step or a jump is four, where the piece is and where it goes.

This program shows the start, then counts how many positions the game can reach in 1, 2, 3 and 4 moves, as the chess topic did: count tries every move and counts what each leads to.

from baghchal import START, moves, play, other, show def count(board, side, to_place, depth):    if depth == 0:        return 1    total = 0    for m in moves(board, side, to_place):        left = to_place - 1 if len(m) == 2 else to_place        total = total + count(play(board, m), other(side), left, depth - 1)    return total show(START)for depth in [1, 2, 3, 4]:    print(f'{depth} ahead: {count(START, "goats", 20, depth)} positions')

5 T . . . T4 . . . . .3 . . . . .2 . . . . .1 T . . . T  a b c d e1 ahead: 21 positions2 ahead: 252 positions3 ahead: 5052 positions4 ahead: 68204 positions

These are exactly the numbers in a table of Lim and Nievergelt’s 2009 paper: 21, 252, 5,052 and 68,204. The game grows 12 to 20 times with every move, faster than minichess’s 9.

Step 2: how many boards are there?

How many different boards can the placing produce? Choose 4 of the 25 points for the tigers; then, for each number of goats from 1 to 20, choose their points among the 21 left. Python’s math.comb(n, k) counts the ways to choose k things from n.

from math import comb boards = 0for g in range(1, 21):    boards = boards + comb(25, 4) * comb(21, g)print(f'{boards:,} boards')print(f'about {boards // 8:,} if a board turned or flipped counts as the same')

26,528,947,500 boardsabout 3,316,118,437 if a board turned or flipped counts as the same

A square board can be turned 4 ways and flipped, so most boards come in groups of 8 that play alike. Lim and Nievergelt counted the different ones exactly, with George Pólya’s counting theory: 3,316,529,500. That is a little more than a straight division by 8, because a few boards look the same when turned (a goat only in the middle, say), so their groups are smaller. With either side to move and different numbers of goats already taken, they estimated about 33 billion positions in the placing.

Step 3: where should the first goat go?

Now the question from Try it, answered for certain. tigers_can_take is the search from How it works, on the real game: can the tigers be sure of taking a goat within moves_left moves, whatever the goats do? It remembers every answer it works out in memo, as the tic-tac-toe topic did, because the same board is reached in many orders.

The program tries the five really different places for the first goat: next to a corner (b5), diagonally next to a corner (b4), c4, the middle (c3) and the middle of an edge (c5). Every other point is one of these turned or flipped.

from baghchal import START, moves, play, goats, name memo = {} def tigers_can_take(board, side, to_place, moves_left):    """Can the tigers be sure of taking a goat within moves_left moves,    whatever the goats do?"""    if moves_left == 0:        return False    key = (tuple(board), side, moves_left)    if key in memo:        return memo[key]    if side == 'tigers':        answer = False        for m in moves(board, 'tigers', to_place):            after = play(board, m)            if goats(after) < goats(board) or tigers_can_take(after, 'goats', to_place, moves_left - 1):                answer = True        # one tiger move that works is enough                break    else:        answer = True        for m in moves(board, 'goats', to_place):            if not tigers_can_take(play(board, m), 'tigers', to_place - 1, moves_left - 1):                answer = False       # one escape is enough for the goats                break    memo[key] = answer    return answer for first in [(0, 1), (1, 1), (1, 2), (2, 2), (0, 2)]:    board = play(START, first)    lost = None    for n in [1, 3, 5, 7]:        if tigers_can_take(board, 'tigers', 19, n):            lost = n + 1            break    if lost:        print(f'First goat on {name(first)}: a goat is lost by move {lost}')    else:        print(f'First goat on {name(first)}: no goat has to be lost in the first {n + 1} moves')

First goat on b5: a goat is lost by move 2First goat on b4: a goat is lost by move 2First goat on c4: a goat is lost by move 4First goat on c3: a goat is lost by move 8First goat on c5: no goat has to be lost in the first 8 moves

n counts the moves after the goat’s first; the tigers take goats only on their own moves, so it goes 1, 3, 5, 7. Four of the five first moves lose a goat by force within 8 moves, however well the goats play. Only the middle of an edge is safe, as Lim and Nievergelt found: “Goat loses a goat within 10 plies unless his first move is on the center spot of a border.” (A ply is what this topic calls a move: one player’s turn.)

Step 4: teach the goats what a good position is

The page’s goats lost because they counted only goats. In the chess topic, a better evaluation function, a function that guesses how good a position is, won games with the same look-ahead. Do the same for the goats. Your evaluate(board) gives a score from the goats’ side: high is good for the goats.

A first idea: count the goats, but also count the goats the tigers could jump right now. Every jump the tigers can make is a goat in danger.

from baghchal import tiger_moves, goats, show def evaluate(board):    danger = 0    for m in tiger_moves(board):        if abs(m[2] - m[0]) == 2 or abs(m[3] - m[1]) == 2:   # a jump            danger = danger + 1    return 10 * goats(board) - 5 * danger board = ['T...T',         '.GG..',         '.....',         '.....',         'T...T']show(board)print(evaluate(board))

5 T . . . T4 . G G . .3 . . . . .2 . . . . .1 T . . . T  a b c d e15

Two goats, 20 points; the goat on b4 can be jumped by the tiger on a5, so 5 less. The board below plays the goats with your evaluate from the program just above (press Edit to change it): it looks two moves ahead, like the page’s Looks 2 goats, and scores the positions where it stops with your function. All those positions are the same number of moves ahead, so fewer goats on the board means goats taken.

Step 5: squeeze the tigers

The goats win only by taking away every tiger move, so give them a reason to: count the tigers’ moves, and score fewer as better.

from baghchal import tiger_moves, goats def evaluate(board):    tigers = tiger_moves(board)    danger = 0    for m in tigers:        if abs(m[2] - m[0]) == 2 or abs(m[3] - m[1]) == 2:   # a jump            danger = danger + 1    return 10 * goats(board) - 5 * danger - len(tigers) print(evaluate(['T...T', '.GG..', '.....', '.....', 'T...T']))print(evaluate(['TGGGT', 'GG.GG', 'G...G', '.....', 'T...T']))

372

On the first board the tigers have 12 moves, so the score drops from 15 to 3. On the second, 9 goats hem in the two top tigers: the tigers could make 2 jumps, but they have only 8 moves in all, and the bottom two make most of them.

• a.The game grows fast. Your Step 1 counted 21, 252, 5,052 and 68,204 positions in the first 4 moves, the same as Lim and Nievergelt’s table, and your Step 2 counted about 3.3 billion different boards in the placing alone.
• b.The goats must be nearly perfect from the first move. Your Step 3 proved that four of the five first moves lose a goat by force within 8 moves. Only the middle of an edge is safe. This is why the tigers usually win between people: the goats’ mistakes are punished, and they are easy to make.
• c.A search is only as good as its judgment. Your goats looked exactly as far ahead as the page’s, but by seeing danger and squeezing the tigers, they went from losing 97 games in 100 to winning more than half of them.
• d.Yes or no questions can be proved by search. One tiger move that works is enough; every goat reply must be covered. With such searches, and a database built backwards from the end, two people and their computers settled who wins Bagh-Chal: nobody.

Few goats, many positions?

Your Step 1 counted every position, including boards that are only another board turned or flipped. Lim and Nievergelt’s table also counted the really different ones: 5, 33, 354 and 2,709 in the first 4 moves.

Questions nobody has answered

Lim and Nievergelt found no easily stated advice beyond rules of thumb such as “goats cautiously hug the border, tigers patiently wait to spring a surprise attack”: the perfect goat player is a database, not a list of tips. Can a person learn to play the goats perfectly? And would the game still be a draw if the tigers won with four goats instead of five? We could find no published answer. Change the rules in your Step 3 program and see what changes in the first moves.

Three challenges, each checked on the page: write your function in the program above the checker (press Edit), then press Check my program. The examples show what your function should give; there are more tests you can’t see. These programs don’t import baghchal.py: everything they need is in them.

★ The lines on the board

Write neighbors(r, c): the points joined to the point in row r, column c by a line, as a list of (row, column) pairs, in any order. Remember: every point has lines to the points beside it, above and below, and a point whose row and column add up to an even number also has diagonal lines.

def neighbors(r, c):    # Give back a list of (row, column) pairs.    return [] print(neighbors(0, 0))

★★ Goats in danger

Write in_danger(board): how many goats a tiger could jump right now. Count each goat once, even if two tigers could jump it, or one tiger could jump it two ways. A board is as in this topic: 5 strings of 'T', 'G' and '.'.

def in_danger(board):    # Give back how many different goats a tiger could take now.    return 0 print(in_danger(['T...T', '.G...', '.....', '.....', 'T...T']))

★★★ Trap them in one move

The goats win when no tiger can move. Write trap(board): once all the goats are placed, a goat move (r, c, to_r, to_c) (a goat stepping along a line to an empty point next to it) after which no tiger can step or jump, or None if there isn’t one. If there are several, give back any of them.

def trap(board):    # Give back a goat move (r, c, to_r, to_c) that leaves the tigers no move, or None.    return None print(trap(['TGGGT',            'GG.GG',            'GGGGG',            'GGGGG',            'TG.GT']))

• How Can a Computer Never Lose at Tic-Tac-Toe?: a game small enough to solve by playing out every game.
• How Does a Computer Play Chess?: a game far too big to solve, played by looking a few moves ahead and guessing.
• Can matchboxes learn to play? A machine of matchboxes and beads that learns tic-tac-toe from its wins and losses, with no search at all.
• Grade 11, Recursion: functions that call themselves, and how to be sure they stop.
• Grade 12, Algorithms for Hard Problems: remembering answers so the same question is never worked out twice.
• Grade 12, The Limits of Computing: problems that grow too fast to solve by trying everything.