Monday, March 12, 2012

The doubling cube and money games

Money games are not match games - in a money game you simply try to win as many points as possible. The doubling cube can be used in money games, doubling up to a maximum value of 64.

In some ways doubling strategy for matches is simpler than for money games because there is a well defined end point. But the standard methodology for cubeful money play ends up being much simpler than match play.

The standard approach was defined in a paper by Rick Janowski, where he proposed an approximation where you linearly interpolate cubeful equity between the "dead" and "live" cube limits.

The dead cube limit is one where you assume that after accepting a double, neither player can double again. The equity in this limit is straightforward.

The live cube limit is one where you assume an infinite number of possible redoubles, but (crucially) gameplay where the probability of win diffuses continuously, instead of jumping from step to step. The equity in this limit is slightly more complex but still has a nice general formulation.

The approximation for real cubeful play is that the cubeful equity is a linear interpolation between these two limits, using an "cube life index" as the interpolation variable that runs from 0 (the dead cube limit) to 1 (the live cube limit).

The cube life index is an input to the model and can be different for each player. Typical values are 0.6-0.7.

GNUbg uses this approximation itself, with a state-dependent cube life index. The backgammon iPhone app Backgammon NJ also uses the Janowski approximation.

Under this approximation, and given a cube life index for each player, there are simple linear forms for equity in the different cube states for each player, which can then be used to determine when to double (when your equity from doubling and giving the opponent the cube is greater than the equity from not doubling) and when to take vs pass (take if the equity from doubling and receiving the cube is greater than the amount you lose from passing).

The inputs to the model are the cube life index, plus the cubeless equities (eg from a neural network).

An alternative approach in the end game is to use two-sided bearoff databases - three of them. One corresponds to equity for a centered cube, one for equity assuming the player owns the cube, and one for equity assuming the opponent owns the cube. This gives exact cubeful equities, since the Janowski approximation can break down (in the sense that a fixed cube life index is not appropriate) near the end of the game.

2 comments:

1. A small technical point: The maximum value of the doubling cube is technically unlimited, even though the cube only goes to 64.

People who have developed "anti-bot" strategies have used this to their advantage. If they can get into a position that the bot seriously misunderstands, it will take bad doubles and recube continuously. This ramps up the cube and you can win a huge amount, compensating you for all the games where you have been beaten by the bot.

In practice, these players seek massive backgames. Gnubg on 0-ply is susceptible to this technique.

1. Interesting! I hadn't realized that, and thought doubling max'd out at 64. Thanks for the tip.