Current issue

Vol.26 No.4

Vol.26 No.4

Volumes

© 1984-2017
British APL Association
All rights reserved.

Archive articles posted online on request: ask the archivist.

archive/26/1

Volume 26, No.1

  • Submitted
  • 1.0

Backgammon tools in J

4: Ace-point Bearoffs

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

J programs are presented as analytical tools for expert backgammon to compute the probability of winning a two-sided bearoff with stacks of pieces on both ace points, to generate binary probability trees, and to solve a related problem.

Utility programs:

    ELSE =: `
    WHEN =: @.
    X =: [
    O =: ]

The probability of the first player (X) winning is 1 minus the probability for the second player (O) -- which is the sum of probabilities for rolling double dice and single dice -- or else the default 1 when there are no pieces left:

Ace =: (1: - Double + Single) ELSE 1: WHEN (X<1:)

The probability of double dice is 1%6 times the result of Ace for the second player (now first, due to switching turns) with the same number of pieces to bear off and four less for the first player (now second). The probability of single dice is similar, but two less:

    Double =: (1:%6:) * O Ace X-4:
    Single =: (5:%6:) * O Ace X-2:

An alternative definition:

Ace =: (1: - Double + Single)~ ELSE 1: WHEN (<1:)

    Double =: (1:%6:) * (Ace (-4:))
    Single =: (5:%6:) * (Ace (-2:))

For example, the winning probability for the first player with 8 pieces vs. 6 pieces is:

    8 Ace 6
0.301055

Here is a table of such probabilities for all odd-numbered stacks:

    5.2 ": 1 3 5 7 9 11 13 15 Ace"0/ 1 3 5 7 9 11 13 15
    1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
    0.17 0.86 1.00 1.00 1.00 1.00 1.00 1.00
    0.00 0.25 0.79 0.98 1.00 1.00 1.00 1.00
    0.00 0.02 0.30 0.75 0.96 1.00 1.00 1.00
    0.00 0.00 0.05 0.33 0.72 0.93 0.99 1.00
    0.00 0.00 0.00 0.08 0.35 0.70 0.91 0.99
    0.00 0.00 0.00 0.01 0.10 0.36 0.68 0.90
    0.00 0.00 0.00 0.00 0.02 0.12 0.37 0.67

Results for even numbers one larger (Ace"0/~ +:>:i.8) are the same. These results can be confirmed by program Pwin in [3] using probability distributions. For example, 8 0 0 0 0 0 Pwin 6 0 0 0 0 0 is 0.301055.

Now generalize these programs to generate a binary tree for any input probability P (and its complement) to a given level L:

    P =: [
    L =: ]

BTree =: (Left,Right) ELSE 1: WHEN (L<1:)

    Left  =:   P * P BTree L-1:
    Right =: -.@P * P BTree L-1:

This can be used to generate probabilities for n-roll bearoffs. For example, to bear off 3 pairs of pieces:

    1r6 BTree 3
1r216 5r216 5r216 25r216 5r216 25r216 25r216 125r216

The sum of any p BTREE n is 1, and the previous level p BTREE n-1 can be reconstructed by _2 +/\ p BTree n. The whole tree is:

    1r6 BTree"0 i.4
    1     0     0      0     0      0      0       0
  1r6   5r6     0      0     0      0      0       0
 1r36  5r36  5r36  25r36     0      0      0       0
1r216 5r216 5r216 25r216 5r216 25r216 25r216 125r216

Problem

Here is a related conundrum to solve: Given a stack of pieces on the ace-point, what is the probability of bearing off the final pieces with a doubles on the last roll? [This problem was posed by Walter Trice, well-known backgammon author and world-class player.] See end of article for answer.

It is easy to modify BTree to produce an asymmetric binary tree by truncating a branch:

BTreeA =: (LeftA , RightA) ELSE 1: WHEN (L<1:)

    LeftA =: P * P BTreeA L-2:
    RightA =: -.@P * (P BTreeA L-1:) ELSE 0: WHEN (L<2:)

Use it to explore the problem:

   +/ 1r6 BTreeA 8       or       +/ (1%6) BTreeA 8
479891r1679616                 0.285715

Or, use a variant of Ace (above):

DoubleOffAce =: (D + S) ELSE 1: WHEN (<1:)

    D =: (1:%6:) * DoubleOffAce@(-4:)

    S =: (5:%6:) * DoubleOffAce@(-2:) ELSE 0: WHEN (<3:)

For instance, DoubleOffAce 15 is 0.285715.

Answer

The probability of bearing off a stack on the ace-point with doubles is 2%7.
+/"1 (1r6 BTreeA)"0 i.10 shows oscillating convergence, or DoubleOffAce"0 i.20 (in pairs).

References

  1. Peelle, Howard A. “Backgammon Tools in J (Part 1) Bearoff Expected Rolls”, Vector, Vol. 24, No. 2&3
  2. Peelle, Howard A. “Backgammon Tools in J (Part 2) Wastage”, Vector, Vol. 24, No. 4
  3. Peelle, Howard A. “Backgammon Tools in J (Part 3) Two-sided Bearoff Probabilities”, Vector, Vol. 25, No. 4

 

script began 12:17:35
caching off
debug mode off
cache time 3600 sec
indmtime not found in cache
cached index is fresh
recompiling index.xml
index compiled in 0.3068 secs
read index
read issues/index.xml
identified 26 volumes, 101 issues
array (
  'id' => '10501070',
)
regenerated static HTML
article source is 'XHTML'
completed in 0.3353 secs