Volume 24, N°2

published
1.0

Backgammon tools in J

1: Bearoff expected rolls

by Howard A. Peelle (hapeelle@educ.umass.edu)

J programs are presented as analytical tools for expert backgammon [1]. Part 1 here develops a program to compute the number of rolls expected to bear off all pieces in a player’s inner board (with no contact).

Backgammon board

The inner board is represented as a list of six integers. For example, 0 0 0 2 3 4 represents 0 pieces on the 1, 2, and 3 points, 2 on the 4-point, 3 on the 5, and 4 on the 6.

Assign a few utility names for readability:

ELSE =: `
WHEN =: @.

Rollsis defined for an inner board input, as in: Rolls 0 0 0 2 3 4. It is the master program and calls Bearoff or else returns a default result of 0 when all pieces are off the board:

Rolls =: Bearoff ELSE 0: WHEN AllOff

Subprograms are:

AllOff =: All@(Board = 0:)
  Board =: ]
  All =: *./

Bearoff is 1 plus the average of expected values for all 36 rolls:

Bearoff =: 1: + Average@AllRolls
  Average =: +/ % #

AllRolls computes the best expected value among all possible moves for each roll of dice – six doubles and two copies of the minimum of 15 pairs of singles rolls, as follows:

AllRolls =: Doubles , 2: # Min@Singles
doubles =: > 1 1 ; 2 2 ; 3 3 ; 4 4 ; 5 5 ; 6 6
singles =: > 1 2 ; 1 3 ; 1 4 ; 1 5 ; 1 6 ; 2 3;2 4;2 5;2 6;3 4;
                                       3 5 ; 3 6 ; 4 5 ; 4 6 ; 5 6
singles =: singles ,: |."1 singles
  Doubles =: doubles Best@AllMoves"1 Board
  Singles =: singles Best@AllMoves"1 Board

Best calls Rolls co-recursively to get expected numbers of rolls for each board and returns the minimum – effectively finding the best move:

Best =: Min@:(Rolls"1)
  Min =: <./

AllMoves generates alternative moves with the first die, then generates moves for each with the last die, or else moves four times repeatedly when the dice are doubles:

AllMoves =: (Last Moves First Moves Board) ELSE (First Moves^:4 Board)
                                           WHEN (First=Last)
  First =: {.@Dice
  Last =: {:@Dice
  Dice =: [

Moves produces a table of legal moves for each board given or else 0 0 0 0 0 0 as a default when all pieces are already off. LegalMoves calls Move and Possibles which calls FromTo to identify indices of each possible move from and to points:

  EACH =: &.>
Moves =: ;@(LegalMoves EACH <"1)
  LegalMoves =: (Possibles Move"1 Board) ELSE Board WHEN AllOff
    Possibles =: FromTo Where FromTo OK"1 Board
      FromTo =: On ,. On-First
      Where =: #~
        On =: Points Where Board > 0:
      OK =: Off +. Inside +. Highest
        Inside =: Last > 0:
        Off =: Last = 0:
        Highest =: First = Max@On
          Max =: <./

Move adds 1 to the point to move to and subtracts 1 from the point to move from:

Move =: Board + To - From
  From =: Points e. First
  To =: Points e. Last
  Points =: 1: + i.@6:

Although these programs generalize easily to the full 24-point backgammon board, they are intended only as prototypes – not for practical use. (See Appendix for an efficient program.)

Rolls may be used to compute the number of expected rolls for any number of pieces on any points in the inner board. For example:

   Rolls 0 0 0 1 1 1
2.48642

So, it takes about two and a half rolls to bear off these pieces on the 4, 5, and 6 points.

Beware: Since multiple recursion is extremely inefficient here, input boards with more than a few pieces will be impractically time-consuming. Accordingly, Rolls should be re-defined to look up expected values from a database produced by the script in the Appendix below.

Problem

As a simple illustrative problem, compare the well-known end-game cases of bearing off one piece on the 1 point and one on the 6 point vs. one piece on the 2 and 5 points. Since

   Rolls 1 0 0 0 0 1
1.58642
   Rolls 0 1 0 0 1 0
1.47531

the latter is better.

Now consider using Rolls to decide the best move for a roll of 6 1 in the position 0 2 2 2 0 4. (Problem 487 in [2].)

Answer: Play 6-Off, 6-5 (not 6-Off, 2-1) since

   Rolls 0 2 2 2 1 2
5.30267
   Rolls 1 1 2 2 0 3
5.40427

Acknowledgements

Thanks to the Vector reviewer for testing these programs and for helpful suggestions.

Special thanks to friend and colleague UMass Computer Science Professor Paul Utgoff for years of enjoyment and sparkling discussions of backgammon and programming.

References

For an introduction to backgammon, see http://en.wikipedia.org/wiki/Backgammon
Bill Robertie, 501 Essential Backgammon Problems, Cardoza Publishing, New York, 2000
For on-line backgammon gaming, see www.GammonVillage.com

Appendix

Script for backgammon bearoff (with no contact) to build list of all 54264 ncodes and corresponding list of ns using base-16 coding for all inner boards (6 points):

Build =: verb define                            NB. Build (6)
boards =. (6#16) #: i.16^6
boards =. boards Where (+/"1 boards) <: 15      NB. select real boards
ncodes =: 16 #."1 boards                        NB. base-16 codes
ns =: (#ncodes) $ 0                             NB. Initialize
N"1 boards                                      NB. Update all ns
)
N =: verb define                                NB. N (6 integers)
code =. 16 #. y
index =. ncodes i. code
n =. index { ns
if. n=0 do. n =. Rolls y
             ns =: n index} ns                  NB. Update n in ns
end.          n
)
  ELSE =: `
  WHEN =: @.

Rolls =: Bearoff ELSE 0: WHEN AllOff
  AllOff =: All@(Board = 0:)
    Board =: ]
    All =: *./
  Bearoff =: 1: + Average@AllRolls
    Average =: +/ % #
    AllRolls =: Doubles , 2: # Min@Singles
doubles =: > 1 1 ; 2 2 ; 3 3 ; 4 4 ; 5 5 ; 6 6
singles =: > 1 2;1 3;1 4;1 5;1 6;2 3;2 4;2 5;2 6;3 4;3 5;3 6;4 5;
                                                           4 6;5 6
singles =: singles ,: |."1 singles
  Doubles =: doubles"_ BestN@AllMoves"1 Board
  Singles =: singles"_ BestN@AllMoves"1 Board

BestN =: Min@:(N"1)                      NB. calls N co-recursively
  Min =: <./
AllMoves =: (Last Moves First Moves Board) ELSE
                           (First Moves^:4 Board) WHEN (First=Last)
  First =: {.@Dice
  Last =: {:@Dice
  Dice =: [
  EACH =: &.>
Moves =: Unique@;@(LegalMoves EACH <"1)
  Unique =: ~. ELSE ,: WHEN (#@$ < 2:)
  LegalMoves =: (Possibles Move"1 Board) ELSE Board WHEN AllOff
    Possibles =: FromTo Where FromTo OK"1 Board
      FromTo =: On ,. On-First
      Where =: #~
        On =: Points Where Board > 0:
      OK =: Off +. Inside +. Highest
        Inside =: Last > 0:
        Off =: Last = 0:
        Highest =: First = Max@On
          Max =: >./
    Move =: Board + To1 - From1
      From1 =: Points e. First
      To1 =: Points e. Last
      Points =: 1: + i.@6:
Build 6                      NB. 43 minutes on Octiplex PC running J6.01
NB. Now #ns is 54264
NB. Next run bgn.ijs

Script bgn.ijs re-defines program N to compute expected number of rolls efficiently using ncodes and ns .

load 'jfiles'
jcreate 'bgns'
ncodes jappend 'bgns'
ns jappend 'bgns'
N =: verb define                         NB. N (inner board)
code =. 16 #. 6 {. y
index =. ncodes i. code
n =. index { ns
)
NB. Now use N for fast look up
NB. Example: N 0 0 0 0 0 1 is 1.25
NB. Example: N 0 0 0 2 3 4 is 6.56681