// This program attempts to compute the equities for hypestgammon,
// a highly simplified version of backgammon proposed by Murat on
// the USENET newsgroup rec.games.backgammon in January 2020.
//
// Hypestgammon is played on a standard backgammon board, but each
// player has only one checker, which starts on the 24pt, and there
// is only one (six-sided) die instead of two. There is a doubling
// cube. To decide who plays first, they play rock-paper-scissors.
// The rock-paper-scissors winner is not allowed to double before
// rolling the die for the first time. Other rules are as in
// ordinary backgammon.
//
// Note that checker play is deterministic, so the only interesting
// decisions are cube decisions.
//
// Note also that gammons don't really make sense because a gammon
// is the same as a single win. However, backgammons do make sense.
// In this program, the value of a backgammon is a parameter that
// can be set with a #define
//
// The program attempts to compute equities with a simple iterative
// algorithm. The points of the board are numbered 1 to 24 as usual
// (from the perspective of the player on roll) but in addition:
// - the 0pt plays the role of the bearoff tray for me,
// and the role of the bar for my opponent;
// - the 25pt plays the role of the bearoff tray for my opponent,
// and the role of the bar for me.
#include
#include
#define BOARDSIZE (24)
// The die value is taken to be the same as the size of the inner board
#define INNERBOARDSIZE (6)
// The value of a backgammon can be changed
#define BACKGAMMONVALUE (2)
// This function is the key step of the iterative algorithm.
// It updates the equities of the position where
// my checker is at position i and
// my opponent's checker is at position j
void update_equity(
double equity[BOARDSIZE+2][BOARDSIZE+2][3],
int coord1[BOARDSIZE+2][BOARDSIZE+2][INNERBOARDSIZE],
int coord2[BOARDSIZE+2][BOARDSIZE+2][INNERBOARDSIZE],
int i,
int j)
{
int c1, c2, die;
double dt, nd;
// Ignore if it's an illegal or terminal position
if ((i == 0) || (j == BOARDSIZE+1)) return;
if (i == j) return;
// If I have no cube access then the new estimate of my equity
// is the average of six previously estimated equities
// (one for each possible die roll).
// I get these equities by "playing" the roll, then flipping the board
// to view it from my opponent's perspective, then negating
// (because my equity is the negative of my opponent's equity)
dt = 0.0;
for (die=1; die<=INNERBOARDSIZE; die++) {
c1 = BOARDSIZE+1 - coord2[i][j][die-1]; // Flip the board
c2 = BOARDSIZE+1 - coord1[i][j][die-1];
dt -= equity[c1][c2][0];
}
dt = dt/INNERBOARDSIZE;
equity[i][j][2] = dt;
// If the cube is centered then I first compute an estimate of
// my "no double" equity by averaging six previously estimated equities
// (one for each possible die roll, assuming I don't double)
nd = 0.0;
for (die=1; die<=INNERBOARDSIZE; die++) {
c1 = BOARDSIZE+1 - coord2[i][j][die-1]; // Flip the board
c2 = BOARDSIZE+1 - coord1[i][j][die-1];
nd -= equity[c1][c2][1];
}
nd = nd/INNERBOARDSIZE;
// If my opponent has a pass then the new estimate of my equity is max(nd,1.0)
if (dt >= 1.0) { // My opponent would pass if doubled
equity[i][j][1] = (nd > 1.0) ? nd : 1.0; // No Jacoby rule
// If my opponent has a take then the new estimate of my equity is max(nd,dt)
} else { // My opponent would take if doubled
equity[i][j][1] = (nd > dt) ? nd : dt;
}
// A similar calculation applies if I own the cube,
// but I have to remember to multiply equities by 2
nd = 0.0;
for (die=1; die<=INNERBOARDSIZE; die++) {
c1 = BOARDSIZE+1 - coord2[i][j][die-1]; // Flip the board
c2 = BOARDSIZE+1 - coord1[i][j][die-1];
nd -= equity[c1][c2][2];
}
nd = nd/INNERBOARDSIZE;
if (dt >= 1.0) { // My opponent would pass if doubled
equity[i][j][0] = (nd > 2.0) ? nd : 2.0;
} else { // My opponent would take if doubled
equity[i][j][0] = (nd > 2.0*dt) ? nd : 2.0*dt;
}
}
int main()
{
// equity[i][j][k] is the equity of the position where
// my checker is at position i
// my opponent's checker is at position j
// the cube location is indicated by k:
// k == 0: I own the cube on 2
// k == 1: Cube is centered on 1
// k == 2: my opponent owns the cube on 2
double equity[BOARDSIZE+2][BOARDSIZE+2][3];
// The max die value is assumed to be INNERBOARDSIZE.
// coord1[i][j][k] is my checker's location
// after I move a die roll of k+1 from the position
// where my checker is at i and my opponent's checker is at j.
// Usually this is i-(k+1), but not necessarily if I'm bearing off.
int coord1[BOARDSIZE+2][BOARDSIZE+2][INNERBOARDSIZE];
// coord2[i][j][k] is my opponent's checker's location
// after I move a die roll of k+1 from the position
// where my checker is at i and my opponent's checker is at j.
// Usually this is just j, but if I hit my opponent then it's 0.
int coord2[BOARDSIZE+2][BOARDSIZE+2][INNERBOARDSIZE];
int i, j, k, n;
// Loop over all possible board positions
for (i=0; i<=BOARDSIZE+1; i++) for (j=0; j<=BOARDSIZE+1; j++) {
// My checker and my opponent's checker can't be at the same location
// unless one of us has borne off
if ((i == j) && (i != 0) && (i != BOARDSIZE+1)) continue;
// (Pre)compute coord1 and coord2
for (k=0; k= my current position then I bear off
} else if (i <= k+1) {
coord1[i][j][k] = 0;
coord2[i][j][k] = j;
// If i - j == k + 1 then I hit
} else if (i - j == k + 1) {
coord1[i][j][k] = j;
coord2[i][j][k] = 0;
// Otherwise I just move my die by k+1
} else {
coord1[i][j][k] = i - k - 1;
coord2[i][j][k] = j;
}
}
// Initialize equities.
// If I have won...
if (i == 0) {
// ...and it's a backgammon, then I score extra...
if (j <= INNERBOARDSIZE) {
equity[i][j][0] = 2.0*BACKGAMMONVALUE;
equity[i][j][1] = BACKGAMMONVALUE;
equity[i][j][2] = 2.0*BACKGAMMONVALUE;
// ...but otherwise it's just the cube value that matters.
} else {
equity[i][j][0] = 2.0;
equity[i][j][1] = 1.0;
equity[i][j][2] = 2.0;
}
// Similarly if I have lost.
} else if (j == BOARDSIZE + 1) {
if (i > BOARDSIZE - INNERBOARDSIZE) {
equity[i][j][0] = -2.0*BACKGAMMONVALUE;
equity[i][j][1] = -BACKGAMMONVALUE;
equity[i][j][2] = -2.0*BACKGAMMONVALUE;
} else {
equity[i][j][0] = -2.0;
equity[i][j][1] = -1.0;
equity[i][j][2] = -2.0;
}
// Otherwise, initialize equities to zero
} else {
for (k=0; k<3; k++) equity[i][j][k] = 0.0;
}
}
// Iterate!
for (n=0; n<10000; n++) {
for (i=0; i<=BOARDSIZE+1; i++) for (j=0; j<=BOARDSIZE+1; j++) {
update_equity(equity, coord1, coord2, i, j);
}
}
// Print results
printf("// Hypestgammon equities when backgammon value is %d\n", BACKGAMMONVALUE);
printf("//\n");
printf("// eq[24,2] = [0.544454, 0.116477, -0.184103] means\n");
printf("// that if my checker is on my 24pt and my opponent's\n");
printf("// is on my 2pt, then my equity, assuming I'm on roll, is:\n");
printf("// 0.544454 if I own the cube on 2\n");
printf("// 0.116477 if the cube is centered\n");
printf("// -0.184103 if my opponent owns the cube on 2\n");
printf("//\n");
printf("// The 0pt is the bearoff tray for me and the bar for my opponent.\n");
printf("// The 25pt is the bearoff tray for my opponent and the bar for me.\n");
printf("//\n");
for (i=0; i<=BOARDSIZE+1; i++) for (j=0; j<=BOARDSIZE+1; j++) {
if ((i == j) && (i != 0) && (i != BOARDSIZE+1)) continue;
if ((i == 0) && (j == BOARDSIZE+1)) continue;
printf("eq[%d,%d] \t= [", i, j);
for (k=0; k<3; k++) {
printf("\t%lf", equity[i][j][k]);
if (k<=1) printf(", ");
}
printf("\t]\n");
}
}