Early training results: new benchmark player

After just 200k training runs using an alpha of 0.1 I had a player that was beating my previous best player by 0.75ppg. That previous-best player has a single network with win and gammon win/loss outputs, no bearoff database, 80 hidden nodes, and had an input for whose turn it is (no symmetry assumption). That player was trained incorrectly because of the bug I mentioned earlier, but it was still pretty good - +0.7ppg-ish against pub eval, and it got lucky and beat me in a set of 10 games once.

This new player is my new benchmark, and I think the first one that's got most everything correct. I'm naming it Benchmark 1. I know, over-brimming with creativity on the name.

I played 20 games against it myself and won 0.1ppg, but I was a bit lucky in the first half of the games (I won 0.7ppg in the first ten but lost 0.5ppg in the second ten). So even after a limited number of training runs it plays at an intermediate level (which is where I place my own meager backgammon skills). It didn't make any big errors in checker play that I noticed.

That's not many training runs, and I'm continuing to train now with more runs. I'm also trying alpha-damping, since after 200k runs it didn't seem to be getting noticeably better with more runs. At 200k runs I'm dropping alpha to 0.02, then to 0.004 at 1M runs, then to 0.0008 at 10M runs. I'm not sure how sensible that is, but I had a hard time finding any references to a good way to determine how to damp alpha for TD training.

This player uses two networks (race and contact) and one-sided bearoff databases for nine points and fifteen checkers. Both networks have outputs for probability of any win, probability of gammon win, probability of gammon loss, probability of backgammon win, and probability of backgammon loss. Both have 80 nodes in their hidden layers. The relatively large bearoff database parameter space means two things: the player is more accurate in most late races; and I can train the race network directly with supervised learning, which is more efficient than the usual TD learning that the network has to do when there's no direct benchmark for probability.

However, to load the two bearoff databases requires a process a bit over 4GB of RAM, which even on a big machine limits the number of calculations I can do in parallel. Once the training is complete I'll try using a much smaller bearoff database to see how well the supervised learning makes the race network approximate the more exact calculation.

Also this player does not include a "crashed" network, which GnuBG does. Partly that's because I want to try something simpler to start, and partly it's because I don't really understand the definition of a crashed board in this context - that is, why the definition GnuBG uses is an interesting one in terms of a phase of play.

Ah ha! Another bug squashed

Once again I was burned by subtleties around who's holding the dice.

The rule the strategies use to determine the optimal move given a board layout and dice throw is to look at all the possible moves and choose the one that has the highest equity. BUT: that equity needs to be calculated assuming that the opponent holds the dice, not the player, since after the move the dice switch hands.

I'd been erroneously calculating the equity in those cases still assuming the player holds the dice, so no surprise that the learning wasn't converging properly.

I've fixed that and am now training a player that uses one-sided bearoff databases, a race net, and a contact net. After 31k training runs it's already beating my best-performing previous network by 0.38ppg, so that definitely looks to have been a significant error!

Results coming when I get a decent number of training results complete.

More on One-Sided Bearoff Databases

In my last post I mentioned that, when the bearoff database runs out to the full fifteen checkers, you need to build a second database to track the distribution of number of steps to take off the first checker, which is used in approximating the probability of a gammon win or loss.

A few more words on this.

First, my initial guess was that this database would be much smaller than the regular one-sided bearoff database (which tracks the distribution of the number of steps to take off the final checker), because it seemed like there should far fewer positions that are relevant. In fact, that's not the case: the number of possible board layouts of fifteen checkers is large and contains many layouts where there is more than one step to taking off the first checker.

For example, for a database covering nine points and fifteen checkers, there are 1.3M board layouts in the regular one-sided database. After trimming it down to just the ones relevant for the gammon bearoff database, there are 490k layouts. Not as big, but more than 1/3 the size of the full set of layouts. The ratio of data in the two databases is actually smaller than the ratio of board layouts, however, because many of the gammon db entries have only a few entries in their probability distribution, whereas the bearoff database is close to the maximum 10 probability entries for most of the layout entries. (10 is the maximum number of points I chose to track in the probability distributions, which I estimated based on impact on the approximate equity calculations vs the exact equity calculations in the two-sided database. Anything over 8 entries did not affect the approximation for that smaller parameter space.) The file containing the gammon bearoff data is 18% of the size of the regular one.

The other point worth mentioning is that a lot of the layouts tracked in the gammon database are not ones that would reasonably come up in a game - for example, a few checkers in the home board and the rest piled up on the points just outside the home board.

That's true of many of the entries in the regular one-sided database as well. I suspect I could trim down the size of both database significantly by running many test games using a reasonable player and including only database entries that are accessed more than 1 in every 1,000 games or something like that. Occasionally in a real game we'd hit a layout that's not cached in the database, and in those rare cases we'd just calculate it on the fly.

Also, currently I store the data in a hash of string representation of board->probabilities. I suspect a fair amount of space is taken up by the string names and the hash overhead, and I'm wondering whether there's a nice way to map the board layout to an integer, where the integers run from 1->max number of board layouts without any gaps or overlaps. Then I could store the data as a standard vector and hopefully reduce memory usage.

One-Sided Bearoff Databases

The two-sided bearoff database I put together before is beautiful because it is exact; but the size of the database quickly becomes cumbersome. In practice I've been using a database for up to six points and nine checkers, which already needs 580MB of disk space to store and around 2GB of RAM to pull in-process. That limit on the number of points and checkers means it does not get used for much of each game and does not help performance significantly.

An alternative, which is an approximation but uses a lot less memory, is to use a one-sided bearoff database. The number of positions in a two-sided database is the square of the number in a one-sided database, so a one-sided database is significantly smaller.

To give a sense of scale: a two-sided database for 6 points and 9 checkers has 25M positions. A one-sided database for 6 points and 9 checkers has 5k positions. A one-sided database for 10 points and 15 checkers has 3.3M positions; assuming roughly 10 probabilities to define the distribution for each position (I limit the distribution to a maximum of 10 points), that's around 30M numbers, so roughly the same amount of memory as the two-sided 6x9 database. That larger parameter set should cover a significant chunk of race positions, and also gives us a benchmark to directly train a race network against using supervised learning instead of TD learning (for some significant fraction of race positions).

The idea here: we look at just one player's position on the board and ignore the other player, and build up the full probability distribution of number of steps to take off all the checkers.

The approximation: when calculating the probability distribution we need to make some assumption about how to make the optimal move. In reality the optimal move will depend on the other player's layout as well, but we approximate the optimal move as the one that minimizes the expected number of steps to finish. That approximation makes the optimal move independent of the opponent's position, which lets us have a much smaller database.

Once we have the probability distribution of both players we can calculate the probability that one of the players wins the game: if that player is on move, it's the probability that their number of steps to finish is less than or equal to the opponent's number of steps. Those two probability distributions are independent because they're generated from independent dice throws, so we can write the probability of player winning the game, as seen before their roll, as:

Prob of Player Win = Sum[ PO(i) Sum[ PP(j), { j, 1, i } ], { i, 1, Infinity } ]

where PP(i) is the probability of the player taking off the last checker in i steps, and PO(i) is the probability of the opponent taking off their last checker in i steps.

Again, this is an approximation based on the assumption that, when generating the distribution of number of steps, we can choose the optimal move based on minimizing the expected number of steps to finish. We can test that approximation against the two-sided database for that smaller parameter space.

I compared the one-sided equity approximation against the exact two-sided equity for up to six points and nine checkers in all of the 9M two-sided positions. The average equity difference was +0.00019; the standard deviation of the difference was 0.0024; and the maximum and minimum differences were +0.023 and -0.026 respectively. So most of the time the approximation is accurate to within 0.003ppg, which is quite good. The average difference is statistically significant, so in principle there is a bias but in practice it is so small as to be irrelevant.

This all assumes that the probability of gammon and backgammon are zero, so that the equity is the usual 2 * prob of win - 1.Ignoring the probability of backgammon is fine since we will not build even a one-sided database that includes points out to the opponent's home board; but the probability of gammon is an important one to track.

We can generalize by building another one-sided database that tracks the distribution of the number of steps before the first checker is taken in. The size of that database will be significantly smaller than the regular one-sided database since we care only about positions that have checkers outside the player's home board and where there are exactly 15 player checkers on the board.

I haven't checked the literature yet on this, so maybe there's a more elegant way to construct a one-sided database with a superior approximation to the one I described above.

The symmetry constraint is not good

I ran the test described in the previous post out to 400k training runs, and the results were relatively unchanged. In head to head competitions the Normal network started to edge out the Symmetric one, and they started to comparably against the pub eval benchmark, with Symmetric still performing a little better on average.

However, I did some more granular benchmarking and Symmetric did much worse. I looked at the network estimate of probability of win from a pair of end games: one where white is almost sure to win, and one where white is almost sure to lose. Both networks started out estimating both probabilities near 50%, as expected with random weights. But the Normal network over time correctly identified the near-certain win and loss fairly accurately after some tens of thousands of training runs, and the Symmetric network did not. In the certain-to-win case it converged to around 97.5% chance of win, so not far off (but should be very close to 100%); but in the certain-to-lose case it converged to around 20% chance of win, which is way off.

Also, I spent some more time thinking about the basic implications of the Symmetric constraint on the hidden->input weights. In particular: the network probability estimates can ever only depend on the difference between the white and black layouts, not on either one independently. That does not seem to afford sufficient flexibility high-level to the network in making probability estimates.

There might be other ways to enforce the symmetry constraint, but at this point I'm just going to drop the whole thing and follow the same approach as GNU backgammon: always evaluate the board from the perspective of the person holding the dice, and drop the input that represents whose turn it is.

Testing the value of the symmetry constraint

Most of the players I've built so far make the "symmetry" assumption: that it's good to ensure explicitly that when you flip the perspective of the board (including an input that signifies whose turn it is), the network probabilities transform as they should. That is, probability of any win transforms to probability of loss, probability of gammon win transforms to probability of gammon loss, and so on.

Satisfying the symmetry adds a constraint to the hidden->input weights. The inputs are set up in pairs, where the inputs for the second player mirror the inputs for the first one, just in different positions in the inputs list. The constraint is that the weight for a mirror input must be the negative of the weight for the corresponding input.

There are two benefits to this approach: first, there are roughly half the number of network weights, so training should be faster; and second, a known symmetry is enforced so the network probability estimates should be more accurate in some general way.

The downside, it seems to me, is that there are half the number of weights, so the network is less flexible than it is without the constraint. So perhaps if we do not explicitly enforce the relationship between weights for regular and mirror inputs, the network can find more powerful strategies.

I designed a simple experiment to test out the net benefit of adding the symmetry constraints. This is not conclusive for more powerful networks, but it should be suggestive.

I designed two networks:

• "Normal": a network setup that does not include the symmetry constraint. The inputs also do not include a flag for whose turn it is; the evaluator always assumes "player 1" is on turn.
• "Symmetric": a network setup that does include the symmetry constraint, and also includes two inputs that reflect whose turn it is (1 for player on turn, 0 otherwise).

Both networks contain only one output for probability of win, and are trained in the usual TD approach. The inputs (aside from the variance on the "whose turn is it" inputs) are the original Tesauro inputs. So not particularly sophisticated networks, but pared down to highlight the difference I want to test out.

I trained both networks with constant alpha=0.1 and lambda=0 for 100k iterations, and every 1k iterations I ran benchmarking. Both strategies were benchmarked on 1k games against the pub eval standard, and against each other. Both networks had 10 hidden nodes.

Conclusions and Results

For this simple network setup, adding the symmetry constraint is marginally superior. The Symmetric network trains more quickly than the Normal network and has a comparable final performance against both pub eval and the Normal network in benchmarking games. That is, the Normal network's extra flexibility from a larger set of weights did not seem to have much of a net benefit.

100k iterations is not that much for backgammon training, and perhaps the Normal network would do better on a longer run. These are pretty simple networks that might not be representative of more complex ones. And the benchmarks I tried are simple and do not say much about network performance in more granular aspects of the game.

Nonetheless, this suggests minimally that adding the symmetry constraint does not make the trained player net worse, and a smaller number of network weights should make it more stable and easier to train.

This chart shows the results of the experiment:

The x-axis is the training run. The y-axis is the fraction of games won in the 1k benchmark games, run every 1k training runs. The green points and line show the Normal setup against the pubeval benchmark; the orange points and line show the same for the Symmetric setup. The blue points and line show the results of a matchup between Normal and Symmetric. The points are the individual 1k-game competitions and the lines are a rolling 10-set average.

Note: results against pubeval are incorrect. Also the training was done incorrectly. Updated results are later in the blog; but the conclusion doesn't change. Symmetric is worse than Normal, and by a more significant margin than is clear here.

Both the Symmetric and Normal networks train quite quickly (within 20k training runs or so), though the Symmetric network trains substantially quicker than the Normal one - by 5k training runs it is winning around 70-75% of games against pub eval.

Symmetric does generally better against pub eval than Normal, even after 100k training runs.

Normal tends to lose by a small margin to Symmetric. By the later training runs they are roughly on par when playing against each other.

Neither player is particularly good on an absolute scale, which is as expected with this relatively simple pair of setups. 

I'm baaack

It's been a while, but I'm back onto the computational backgammon hobby. I took the free Stanford machine learning course, which was a really interesting high level overview of many machine learning techniques, including neural networks. In the end I don't think it much changes my approach here even if it did give me some interesting context.

The next step: generalize to a more complex evaluator of the board value. I'll use a bearoff database in the appropriate end game, and separate neural networks for different game phases. To start with I'll just use  two, race and contact networks. But the framework will be generic so I can define however many networks I like, along with a generic way to decide which network (or other technique like bearoff) is appropriate for a given stage of the game.

I never did figure out why the previous version didn't converge properly, but I'm going to try a fresh implementation to see if there was some hidden bug. And hopefully the bearoff bit will help it get more sensible results near the end of a (race) game.