| Backgammon Variants |
The following position is one of the hardest to reach in hypergammon; it takes 14 rolls to get there from the starting position.
| A hard-to-reach postition |
In Hyper Fun 03, I challenged readers to find a sequence of rolls and plays that reach this position. Here is one solution:
| Start |
| Black | White | |||
| 1. | 6-5: | 24/18, 23/18 | 6-6: | 24/12, 22/10 |
| 2. | 6-6: | 22/10, 18/12(2) | 4-2: | 12/6 |
| 3. | 6-6: | 12/6(2), 10/4, 6/off | 2-2: | 23/21*/19*/15 |
| 4. | 5-1: | bar/24, bar/20 | 5-5: | 15/5*, 10/off |
| 5. | 5-5: | bar/20*/15, 24/19*/14 | 6-6: | bar/13(2) |
| 6. | 6-4: | 15/9, 14/10 | 4-3: | 13/10, 13/9 |
| 7. | 2-1: | 10/8, 9/8 | 2-1: | 10/8, 9/8 |
|
| Finish |
Perfect Backgammon
Nobody knows how to play perfect backgammon. The bots play a very strong game — as strong as anyone — but they make their share of mistakes. And there are some backgammon positions (quite a lot, actually) where the bots have no clue whatsoever. It will probably be several decades before backgammon is completely solved.
Not the case with hypergammon. Hypergammon has relatively few positions compared with backgammon (7,959,904 versus 18,528,584,051,601,162,496). That means it is possible to write a computer program to play perfectly. In fact, Hugh Sconyers was the first to do it in 1991.
Creating a Hypergammon Bot
The way to create a perfect hypergammon-playing bot is to maintain a large table of equities, with one entry for each possible position. This table has 7,959,904 entries, which easily fits in the memory of any computer today. (Such a table did not fit into the memory of most computers back in 1991.)
There are some positions we already know the exact equity of — the final position of each game.
Terminal positions. A terminal position is a position where one side or the other has all their checkers borne off. When you reach a terminal position, the game is over.
Calculating the equity of a terminal position is easy. First check to see which side won. Then check to see if they won a single game, gammon, or backgammon. The equity of the terminal position then is −1, −2, or −3 (from the loser’s point of view) or +1, +2, or +3 (from the winner’s point of view).
Nonterminal positions. Calculating the equity of a nonterminal position is not so easy, because each of those positions depends on the equities of other positions.
To find out the equity of a given position, we go through each of the 21 possible rolls and find the best way to play each roll. Then we average the equities of the 21 resulting positions (giving twice as much weight to mixed rolls as we do to doublets). This average is the equity of the that position.
But there is a problem: How do we know the equities of each of the resulting positions so we can average them? We could do the same calculation for each of those positions too, but this quickly gets out of hand. In fact, such a calculation might never end because of the possibility of cycles. (We saw an example of a cycle in Hyper Fun 01 when we asked about returning to the start.)
Dealing with Cycles
So what do we do? It turns out this is not an insurmountable problem. Every game of hypergammon ends and ultimately the equity of every position depends on the equities of the terminal positions.
We start the table off with arbitrary values, say zero, for the equities of the nonterminal positions. This gives us something to work with. When we need to know the equity of a resulting position, we can use the “equity” found in the table instead of having to look further ahead.
Then go through the table and recalculate the equity of each hypergammon position:
- For each of the 21 possible rolls, figure out the best way to play that roll. There are typically several ways to play a roll, so we find the best play by looking up equities from the table. Choose the play that yields the highest equity.
- Take a weighted average of the 21 rolls. This average is then stored in the table, replacing the previous equity we had for the position.
The first time we do this, most equities will still be wrong. (Most will still be zero.) But computers are fast and we can repeat this procedure over and over again. We continually refine the equities in the table, and they become more and more accurate. Eventually the equities in the table reach a steady state — they no longer change when they are recalculated and the table becomes consistent.
Essentially what happens is, the equities of the terminal positions purcolate up affect the equities of every other position. It takes about 150 iterations for the table of equities to reach a steady state (within the accuracy of a double precision floating point number).
Some Questions
Knowing the equity of every position is all you need to play perfectly: When presented with a choice of what play to make, simply choose the play that gives the you the highest equity. No other strategy does better.
With a bot that plays perfectly, we can investigate some interesting properties of cubeless hypergammon. Here are three fun questions:
- What is the best roll you can throw in cubeless hypergammon? (What position and roll give you the biggest increase in equity?)
- What is the worst roll you can throw in cubeless hypergammon?
- What is the biggest error you can make in cubeless hypergammon? (What position and roll have the biggest difference between best and worst play?)
I will give the answers next time.
|
|
