OddThinking

A blog for odd things and odd thoughts.

Analysis of the Australian Bush Game

Introduction

A friend kindly bought me a novel little game for my birthday in 2001. We opened it up and played it for the first, and last, time. While I appreciated the thought behind the gift, the actual game didn’t keep us amused for very long – it quickly ended up in a endless stalemate.

On the other hand, the analysis of the game kept me amused for hours. I tried to prove competent players would always end up in a pointless stalemate.

The analysis took me a few years to complete – it required some brute force, and I got distracted for three years- but I have finally completed it. The technique I originally had conceived had to be substantially modified before it worked.

About the Game

Called the “Australian Bush Game”, the packaging had a back-story which I am confident was completely apocryphal, and thus slightly offensive. It allegedly was played by young Australian Aborigines to teach them the type of cunning that they required to hunt. It mentioned in particular the patience required.

[The game indeed requires patience – to an inhuman level. As I will show, the players are stuck in an endless loop, waiting for the other player to either make a stupid mistake or to concede the game from boredom.]

The game is a variant of noughts-and-crosses. (I’ll mention the word “tic-tac-toe” here, so Google knows what I am talking about.) Rather than playing with a pencil and paper, the package includes three black stones (equivalent to noughts), three white stones (equivalent to crosses) and a noughts-and-crosses board.

Both the goal of the game and also the first six moves of the game are identical to noughts-and-crosses. Each player takes it in turns to place a piece, trying to get three in a row.

After all six pieces are played, the difference from noughts-and-crosses appears. Each player takes turns to move one of their stones (horizontally, vertically or diagonally) one square to an empty square, while still trying to complete a line of three stones.

The Analysis

I set out to prove that a competent player of this game could never be beaten – and the corollary, that two competent players could never finish.

Canonical Form

Each board position is logically equivalent to the same board position rotated 90 degrees, or flipped horizontally. Adding combinations of such transformations, up to eight different layouts can be seen to be equivalent.

By producing a “canonical form”, the size of the problem can be greatly reduced.

For example, the first move can place a black piece in any of 9 positions, but only 3 of them are distinct (middle, corner and edge).

The second move can place a white piece in any of the 8 remaining positions, but rather than 3 first moves * 8 second moves = 24 positions, only 12 of them are distinct.

By the time you add all six pieces to the board, there are only 540 distinct positions. [Actually, there is twice as many if you consider whose turn it is.] This excludes some impossible situations, where both players find themselves in a winning position.

Compared to the initial estimate of the initial 9 * 8 * 7 * 6 * 5 * 4 = 60,480 different positions, this simple canonical form makes the situation far more tractable for analysis.

The software used a simple system to calculate the canonical form. Substituting 0 for a blank, 1 for black and 2 for white, it concatenated the value in each square in a fixed order (left-to-right, top-to-bottom), and produced an integer value for each arrangement. It then produced all 8 different transformations, and took the highest integer value for the set and declared it to be the canonical form.

Theory

The normal way to write software to play this sort of game optimally is to use the minimax algorithm. In a nutshell, the algorithm says my opponent’s next move after my move is going to put me in the worst situation they can manage. I should choose the move that gives the poorest choice to my opponent. This repeats, recursively predicting their possible moves, and where that will leave me, until either you can see the way the game will turn out, or until you get bored (when you drop to a simpler heuristic evaluation of the hyophethical board-state.

Perhaps that wasn’t the clearest explanation. Sorry, but no matter – the point is that basic minimaxing isn’t going to work well with games that might well last forever, because the recursion never ends. There is probably accepted game theory technique for dealing with this, but I don’t know what it is, so I made up my own! It took me four tries, and almost as many years, but I finally got it! The technique is to minimax backwards from losing positions, until you can show there is no winning positions. I dubbed it “Xaminiming” in my head, but that’s because I didn’t have to pronounce it to myself.

Assume we are playing White.

Consider the positions where it is our turn and we discover that Black has just won.

My software figures (by brute force) that there are a total of 42 of those positions.

We want to avoid those positions, so working backwards, we don’t want to leave the board in a position where Black can move to one of those locations.

There are 197 board positions where Black can move into one of the above positions. I dub these the “Mate In 1” positions, by analogy to chess. We do not want to make a move that leaves Black in any of these positions, because the game will be over once Black makes a move.

Black, on the other hand, wants to force us into one of these positions, so Black wants to find a position where, no matter what move we make, we end up in one of these (bad) Mate in 1 positions.

There are a total of 25 of these “Mate in 2” positions, where it is our turn to move, but no matter what action we take, Black will be able to move and win.

So now we want to avoid being forced to play in a Mate In 2 position. Well, working backwards once again, there are 115 different “Mate in 3” positions where Black could move us into a Mate in 2 position.

We want to avoid leaving Black in a Mate in 3 position. Are there any “Mate in 4” positions Black could put us in, which would force us to be in a Mate in 3 position?

Before I wrote any software I was fairly confident that there would not be any such positions, even though I hadn’t proved it. Actually, however, there are a total of four Mate in 4 positions. If we ever find it is our turn, and this is the board set-up, then we have effectively already lost.

Note: All of these positions happen to occur during the sixth move of the game Correction! All of these positions happen to occur during the fifth or sixth move of the game – White’s next move is to place a piece on an empty square. These are almost little puzzles to solve. For each one, can you see how (with White to move), Black will always win?

You might be getting the hang of this now. How many “Mate in 5” positions are there from which Black can move to a “Mate in 4” position? The answer is 11.

So, how many “Mate in 6” positions are there? None! There are no positions from which there is no escape but into a “Mate in 5” position.

So there is no way for Black to say “Aha! I have got you now! I will win in 6 moves, no matter what you do!”

This means that if we play competently, and we can stay alive for at least 6 moves from the start, we should never find ourselves losing. We know we can stay alive for the first 6 moves (from our experience with noughts-and-crosses), so we should never lose this game

Reversing the Roles

If Black can’t win, what about White?

There was no loss of generality here. The Black side could equally prove that they could not lose. Given there are no provisions for a draw, when played competently, the game must therefore continue forever.

QED


Comments

  1. Hi,

    I was reading your site and found it very helpful and comprehensive. I was wondering though, you stated that there are 11 ‘mate in 5’ positions, though you did not display them; what are they?

    Thanks a lot for your help,

    Rafie

  2. Rafie,

    That sounded like a simple question, but in answering it, I found two errors in my calculation. Both of them turned out to be trivial and had no impact on the final solution. However, they took me a while to (get around to) working out.

    The first error, I have corrected directly in the text above – one of the Mate in 4 positions wasn’t the sixth move of the game, as claimed, but only the fifth move. That has no impact at all on the analysis – it was just an aside to help explain what was being shown – but upon re-reading it, it left me confused for a while.

    The second error becomes clear when we look at the answer to your question:

    I asked my script to draw the eleven “mate in 5” moves:











    For each one, it is Black’s turn to move.

    Now, what is peculiar about this list is that the last two positions are actually “Mate in 1” moves. If you squint, you may be able to see that they are also “Mate in 5” moves, but the ability to make an immediate move to win should gazump that.

    I scratched my head when I saw this list, because I had already thought through this problem. When calculating the set of Mate in 5 moves, I had subtracted the previously calculated “Mate in 1” and “Mate in 3” moves – so why were these appearing here?

    The answer is that I had previously excluded from the Mate-in-1 set, all the moves that lead to a win in under six moves. As I described in the main article, we know from analysis of the normal noughts-and-crosses that a competent player won’t lose in the first six moves. However, having excluded the move from the mate-in-1 set, these “mate-in-1-after-less-than-6-moves” moves failed to be excluded from the “mate in 5” set.

    That explanation may not be very clear, so let me summarise:

    I was wrong: there really is only nine legal “mate in 5” moves, not eleven. My estimate of 115 “mate in 3” moves may be similarly exaggerated.

    However, my mistake in the interim step of over-estimating these figures makes the burden of proof harder, not easier. The conclusion that there is no “mate-in-6” moves still stands.

Leave a comment

You must be logged in to post a comment.