| |
BGonline.org Forums
Thoughts on solving hypergammon
Posted By: Tom Keith In Response To: Hypergammon--information please? (Michael Petch)
Date: Wednesday, 3 September 2014, at 2:20 p.m.
There are 7,959,904 possible checker positions in hypergammon. This may seem a large number but it is actually miniscule compared with regular backgammon (which has 18,528,584,051,601,162,496 positions). The modest number of positions in hypergammon makes it possible to calculate the equity of every position, which is all you need to play perfectly. A table to hold these values fits easily into computer memory.
There are three equities needed for each entry of the table, one for each possible cube position. It is convenient to use "normalized" equities. (A normalized equity assumes the value of the cube is 1. You can get the actual equity of a position by taking the normalized equity and multiplying it by the value of the cube.)
Perhaps the easiest approach to calculating the equities in the table is as follows:
- Find all the terminal positions, that is, all positions in which the game has ended. It is easy to calculate the equity of those positions. Simply note which player won the game and check to see if he won a single game (+1), gammon (+2), or backgammon (+3). Mark those positions as "stable" so we know to not calculate their equities again later.
- For all the other positions, start with arbitrary values (such as zero) for their equities. These numbers are initially wrong, but after enough recalculation they should converge to their true values. The reason they converge is that hypergammon (like regular backgammon) is guaranteed to end with probability 1. It is not possible to get into a loop from which you can never escape, so ultimately the equity of every position depends only on the equities of the terminal positions.
- For the stored equities of each position, assume the player on roll does not double before he rolls. From these numbers you can easily figure out the correct cube decision and thus the actual equity of the position.
- To figure out if a player should double, simply compare the equity assuming no double (that is, with the cube still centered or still owned) with the equity assuming double/take (that is, twice the equity with the opponent owning the cube). Similarly, to figure out if the opponent should take or drop, compare your equity if he takes with your equity if he drops (+1.0) and assume he makes whatever decision minimizes your equity.
- To figure out the correct checker play, make a list of all the legal checker plays and go through the list to find out which play produces the highest equity. That play, and the position it produces gives you your equity. (We may not yet know the correct equity for each position, but that doesn't matter. For now, simply use the value stored in the table and come back and calculate again later if necessary.)
- Recalculate the equities in the table over and over again until they stop fluctuating. Eventually all the values in the table will converge to their correct values. With the final table in hand, it is possible to play perfect hypergammon.
There is only one possible snag. Theoretically it is possible to have a position (like this one from regular backgammon) in which the the value of the cube rises so quickly that the entries in the table never converge, but I don't think that is likely. (And if it did happen we presumably would have heard about it by now.)
---
Michael Petch wrote: When it comes to checker play a bot can make the optimal play for all positions. However the computed data won't tell you what the proper (optimal) cube action is for each position is (assume money play).
You should be able to calculate the correct cube action for each position as well. (See steps 3 and 4 above.)
| |
BGonline.org Forums is maintained by Stick with WebBBS 5.12.