Programming

Forum Archive : Programming

 
BKG 9.8 vs. Villa

From:   Raccoon
Address:   racgammon@yahoo.com
Date:   3 August 2006
Subject:   Backgammon champions and computers in 1979
Forum:   rec.games.backgammon
Google:   1154666209.460074.268390@m79g2000cwm.googlegroups.com

"The first strong computer opponent was BKG 9.8. It was programmed by
Hans Berliner in the late 1970s on a PDP-10 as an experiment in
evaluating board positions. Early versions of BKG played badly even
against poor players, but Berliner noticed that the critical mistakes
the program made were always at phase changes. He applied basic
principles of fuzzy logic to smooth out the transition between phase
changes, and by July 1979, BKG 9.8 was ready to play against then
current world champion Luigi Villa. It won the match, 7-1, becoming the
first computer program to defeat a world champion in any game, although
this was mostly a matter of luck, as the computer happened to get
better dice rolls than its opponent in that match." --Wikipedia

7 point match

 Game 1
 Villa : 0                       Gammonoid : 0
  1) 61: 13/7 8/7                44: 24/20 24/20 13/9 13/9
  2) 42: 13/9 6/4

Better is 42: 24/20 6/4

  2)                             44: 20/16* 20/16 6/2 6/2

Better is 44: 20/16*(2) 9/5(2)

  3) 61: 25/24 24/18              Doubles => 2
  4)  Takes                      42: 8/4 6/4

How about 42: 13/7*?

  5) 43: 8/4 8/5                 52: 16/11 9/7*
  6) 41: 25/24 13/9*             54: 25/20* 20/16*
  7) 53: 25/20 25/22             21: 7/5* 5/4
  8) 33: 25/22 7/4 6/3 6/3       51: 16/11 9/8
  9) 32: 13/10 24/22             22: 13/11 11/9 11/9 11/9
 10) 62: 22/20 20/14             62: 8/2 13/11*

Better is 62: 13/7 9/7

 11) 51: 25/20 13/12*            66:
 12) 33: 12/9 10/7 9/6 6/3       11: 25/24 24/23 6/5* 6/5
 13) 55:                         31: 23/20 11/10
 14) 43: 25/22 22/18             66: 20/14 14/8 10/4 8/2
 15) 53: 18/13 13/10             64: 8/2 8/4
 16) 51: 10/5 7/6                32: 9/6 6/4
 17) 42: 6/2 7/5                 62: 4/2
 18) 54: 24/19 19/15

Better is 54" 22/13

 18)                             31: 4/1* 2/1
 19) 55:                         66:
 20) 53: 25/22 15/10             42: 9/5 9/7
 21) 65: 22/16 16/11             62: 7/5 5/0
 22) 11: 10/9 9/8 8/7 7/6        21: 2/0 1/0
 23) 61: 11/5 3/2                64: 5/0 4/0
 24) 21: 4/2 2/1                 65: 5/0 5/0
 25) 55: 22/17 17/12 12/7 7/2    62: 4/0 2/0
 26) 43: 22/18 18/15             32: 4/1 2/0
 27) 22: 15/13 13/11 11/9 9/7    21: 2/0 1/0
                                  Wins 2 points

 Game 2
 Villa : 0                       Gammonoid : 2
  1) 63: 24/18 18/15

Most players today would play 63: 24/18 13/10

  1)                             63: 24/18 13/10*
  2) 52: 25/20 20/18             11: 8/7* 8/7 6/5 6/5
  3) 54: 25/21 6/1*               Doubles => 2

No double ...

  4)  Drops                       Wins 1 point

Easy take!

 Game 3
 Villa : 0                       Gammonoid : 3
  1) 52: 13/8 13/11              41: 13/9 6/5
  2) 63: 11/5 8/5                44: 13/9 9/5 8/4 8/4
  3) 54: 13/8 8/4                64: 8/2 6/2
  4) 21: 6/4 6/5                 54: 13/8 13/9

Better is 54: 13/8 9/5

  5) 41: 8/4 13/12*              63: 25/22 8/2

Better is 63: bar/16

  6)  Doubles => 2                Takes
  7) 51: 8/3* 4/3                66:
  8) 63: 8/2 5/2                 66:
  9) 64: 24/18 18/14             66:
 10) 61: 24/18 18/17             66:
 11) 41: 17/13 12/11             66:
 12) 22: 14/12 13/11 13/11 11/9  66:
 13) 21: 11/9 9/8                66:
 14) 32: 8/5 12/10               66:
 15) 52: 10/5 6/4                66:
 16) 53: 11/6 9/6                66:
 17) 66: 6/0 6/0 6/0 6/0         62: 25/19 19/17
 18) 52: 5/0 5/3                 61: 17/11 11/10
 19) 64: 5/0 4/0                 31: 10/7 7/6
 20) 61: 5/0 3/2                 62: 24/18 18/16

Villa's next roll is the super antijoker 43, but that's not the only
reason 62: 24/16 is not right!

 21) 43: 4/0 4/1*                41: 25/24* 16/12
 22) 41: 25/24                   63: 9/3 6/3
 23) 53:                         31: 12/9 2/1*
 24) 66:                         55: 24/19 19/14 14/9 6/1
 25) 66:                         21: 9/7 9/8
 26) 66:                         44: 9/5 8/4 7/3 4/0
 27) 66:                         53: 5/0 3/0
 28) 66:                         66: 6/0 6/0 5/0 5/0
 29) 62: 25/19 19/17             41: 4/0 1/0

Double/pass already.

 30) 21: 17/15 15/14              Doubles => 4
 31)  Drops                       Wins 2 points

 Game 4
 Villa : 0                       Gammonoid : 5
  1) 54: 13/8 13/9               42: 8/4 6/4
  2) 52: 9/4 6/4                 42: 13/9 13/11
  3) 44: 24/20 24/20 20/16* 20/16 21: 25/23 6/5
  4)  Doubles => 2                Drops
      Wins 1 point

A well-played game! In the next and final game, Gammonoid's moves 5, 18
12 and 19 are particularly stinky.

 Game 5
 Villa : 1                       Gammonoid : 5
  1)                             21: 13/11 6/5
  2) 21: 13/11 24/23             61: 11/5 6/5
  3) 64: 13/7 11/7               21: 6/4 5/4
  4) 61: 13/7 23/22              32: 8/5 5/3*
  5) 31: 25/22* 24/23            42: 25/23 13/9
  6) 62: 22/16* 16/14            53: 25/20 23/20
  7) 51: 23/18 14/13             63: 13/7* 13/10
  8) 43: 25/22 22/18*            55: 25/20 20/15 8/3 8/3
  9) 63: 18/12* 13/10*           32: 25/22 25/23
 10) 41: 13/9 10/9               32: 23/20 24/22
 11) 42: 8/4 6/4                 61: 20/14 14/13*
 12) 62: 25/23 13/7              51: 13/8 3/2*
 13)  Doubles => 2                Takes
 14) 32: 25/22* 6/4              42: 25/23 10/6
 15) 21: 4/2* 2/1*               53: 25/20 25/22
 16) 42: 22/18 18/16             55: 20/15 15/10 10/5 8/3
 17) 31: 7/4 16/15               43: 6/2 5/2
 18) 41: 15/11 11/10             42: 5/1 5/3
 19) 21: 4/2 2/1                 22: 22/20 22/20 22/20 3/1
 20) 41: 10/6 7/6                55: 20/15 20/15 15/10 15/10
 21) 53: 9/4 9/6                 33: 10/7 10/7 7/4 7/4
 22) 51: 8/3 8/7                 32: 20/17 17/15
 23) 53: 7/2 6/3                 53: 20/15 20/17
 24) 33: 7/4 7/4 3/0 3/0         66: 17/11 15/9 15/9 11/5
 25) 51: 6/1 1/0                 64: 9/3 9/5
 26) 51: 6/1 1/0                 64: 6/0 4/0
 27) 51: 6/1 1/0                 42: 4/0 2/0
 28) 62: 6/0 2/0                 41: 4/0 1/0
 29) 54: 6/2 4/0                 41: 4/0 1/0
 30) 11: 2/1 1/0 1/0 1/0         62: 6/0 2/0
 31) 61: 4/0 4/3                 21: 2/0 5/4
 32) 31: 4/1 1/0                 55: 5/0 4/0 3/0 3/0
                                  Wins 2 points and the match

Gammonoid knew that backgammon is a race!

Adam Tansley  writes:

Thanks Raccoon.  And here's what a modern day bot thinks of all that
(gnubg 2-ply analysis):


Chequerplay statistics
                               Villa                   Gammonoid
Total moves                      91                      90
Unforced moves                   78                      73
Unmarked moves                    0                       0
Moves marked good                87                      75
Moves marked doubtful             2                       6
Moves marked bad                  1                       4
Moves marked very bad             1                       5
Error rate (total)               -0.617 (-7.332%)        -2.433 (-22.671%)
Error rate (per move)            -7.9 (-0.094%)         -33.3 (-0.311%)
Chequerplay rating              Expert                  Beginner

Luck statistics
                               Villa                   Gammonoid
Rolls marked very lucky           0                       3
Rolls marked lucky                2                       5
Rolls unmarked                   86                      81
Rolls marked unlucky              3                       1
Rolls marked very unlucky         0                       0
Luck rate (total)                +0.025 (-8.596%)        +4.438 (+54.568%)
Luck rate (per move)             +0.3 (-0.094%)         +49.3 (+0.606%)
Luck rating                     None                    Good dice, man!

Cube statistics
                               Villa                   Gammonoid
Total cube decisions             50                      52
Close or actual cube decisions   21                       8
Doubles                           3                       3
Takes                             1                       2
Passes                            2                       1
Missed doubles (below CP)         3 (-0.048 (-0.351%))    0
Missed doubles (above CP)         0                       1 (-0.038
                                                             (-0.505%))
Wrong doubles (below DP)          0                       1 (-0.151
                                                             (-1.006%))
Wrong doubles (above TG)          0                       0
Wrong takes                       0                       0
Wrong passes                      1 (-0.674 (-4.504%))    0
Error rate (total)               -0.723 (-4.855%)        -0.189 (-1.511%)
Error rate (per cube decision)  -34.4 (-0.231%)         -23.6 (-0.189%)
Cube decision rating            Beginner                Casual player

Overall statistics
                               Villa                   Gammonoid
Error rate (total)               -1.340 (-12.187%)       -2.622 (-24.182%)
Error rate (per decision)       -13.5 (-0.123%)         -32.4 (-0.299%)
Equiv. Snowie error rate         -7.4                   -14.5
Overall rating                  Intermediate            Beginner
Actual result                   -50.00%                 +50.00%
Luck adjusted result            +13.16%                 -13.16%
Luck based FIBS rating diff.   +177.04
Error based abs. FIBS rating   1924.4                  1616.6
Chequerplay errors rating loss   98.5                   414.8
Cube errors rating loss          27.1                    18.6


Worth noting that although Gammonoid got very lucky, and Villa had by
far the better checker play, Gammonoid actually did better with the
cube, according to gnubg.

tansley
 
Did you find the information in this article useful?          

Do you have any comments you'd like to add?     

 

Programming

Adjusting to a weaker opponent  (Brian Sheppard, July 1997) 
Anticomputer positions  (Bill Taylor+, June 1998) 
BKG 9.8 vs. Villa  (Raccoon+, Aug 2006) 
BKG 9.8 vs. Villa  (Andreas Schneider, June 1992) 
BKG beats world champion  (Marty Storer, Sept 1991) 
Backgames  (David Montgomery+, June 1998)  [Long message]
Blockading feature  (Sam Pottle+, Feb 1999)  [Long message]
Board encoding for neural network  (Brian Sheppard, Feb 1997) 
Bot weaknesses  (Douglas Zare, Mar 2003) 
Building and training a neural-net player  (Brian Sheppard, Aug 1998) 
How to count plies?  (Chuck Bower+, Jan 2004)  [GammOnLine forum]
How to count plies?  (tanglebear+, Mar 2003) 
Ideas for improving computer play  (David Montgomery, Feb 1994) 
Ideas on computer players  (Brian Sheppard, Feb 1997) 
Introduction  (Gareth McCaughan, Oct 1994) 
Measuring Difficulty  (John Robson+, Feb 2005)  [GammOnLine forum]
Methods of encoding positions  (Gary Wong, Jan 2001) 
N-ply algorithm  (eXtreme Gammon, Jan 2011) 
Neural net questions  (Brian Sheppard, Mar 1999) 
Pruning the list of moves  (David Montgomery+, Feb 1994) 
Search in Trees with Chance Nodes  (Thomas Hauk, Feb 2004) 
Source code  (Gary Wong, Dec 1999) 
TD-Gammon vs. Robertie  (David Escoffery, June 1992) 
Training for different gammon values  (Gerry Tesauro, Feb 1996) 
Training neural nets  (Walter Trice, Nov 2000) 
Variance reduction in races  (David Montgomery+, Dec 1998)  [Long message]
Variance reduction of rollouts  (Michael J. Zehr+, Aug 1998)  [Long message]
Variance reduction of rollouts  (Jim Williams, June 1997) 
What is a "neural net"?  (Gary Wong, Oct 1998) 
Writing a backgammon program  (Gary Wong, Jan 1999) 

[GammOnLine forum]  From GammOnLine       [Long message]  Long message       [Recommended reading]  Recommended reading       [Recent addition]  Recent addition
 

  Book Suggestions
Books
Cheating
Chouettes
Computer Dice
Cube Handling
Cube Handling in Races
Equipment
Etiquette
Extreme Gammon
Fun and frustration
GNU Backgammon
History
Jellyfish
Learning
Luck versus Skill
Magazines & E-zines
Match Archives
Match Equities
Match Play
Match Play at 2-away/2-away
Miscellaneous
Opening Rolls
Pip Counting
Play Sites
Probability and Statistics
Programming
Propositions
Puzzles
Ratings
Rollouts
Rules
Rulings
Snowie
Software
Source Code
Strategy--Backgames
Strategy--Bearing Off
Strategy--Checker play
Terminology
Theory
Tournaments
Uncategorized
Variations

 

Return to:  Backgammon Galore : Forum Archive Main Page