Programming

Forum Archive : Programming

 
Ideas for improving computer play

From:   David Montgomery
Address:   monty@cs.umd.edu
Date:   16 February 1994
Subject:   Computer BG Move Evaluation (long)
Forum:   rec.games.backgammon
Google:   2julu3$7dk@twix.cs.umd.edu

I'm interested in hearing other people's ideas on how to
improve both the level of play and the speed of computer
bg programs.  As a starting point for discussion, let me
list four things that I think humans do well in playing
backgammon, and which might therefore be profitable to emulate
in a program.

----------------------------

POSITIONAL INSIGHT
Human players rely a lot on high-level features that they
have learned through experience or read about in books
(or on the net, or from software).

I would say that the majority of backgammon programs have
focused on this aspect: developing high level features
which reflect the kinds of things humans think about.
Tesauro's work shows that these features can be quite
valuable even if you have a neural network which is capable
of learning its own 'features.'  It just makes things a lot
easier for a learning system if you give it useful hints.
If you don't have a learning system, then you really must
have hand-coded features.

Since so much work has been done in this area, it's less
interesting to me, but of course there is the possibility
that there are features out there which are easy to
calculate, extremely useful, which no one has thought of
(or at least implemented).

The types of features that I have found most useful, in
approximate order of importance, are:

shots/blot danger
racing equity/pip count
point making rolls
priming strength
other dynamic features (e.g. rolls that escape)

My personal experience is that the exact nature of these
features is that crucial (e.g., for priming strength you
can count points and gaps, or you can determine the
exact number of rolls to jump the checkers over the
prime, or you could measure it any of a number of other
ways).

Another manifestation of human positional insight is the
way humans classify positions: holding games, blitzes,
backgames, etc.  This too has been used in computer
programs, although to a lesser degree (e.g. having one
routine play all contact positions, another all races).
I think Championship Backgammon used this approach quite
a bit.  The main problem is deciding just how to partition
the space.  I think this approach is useful, but less
important than the features.

------------------------------

The other comments I have relate more to how quickly
people (or a program) play, rather than the level of
play.  But the two are related, because you can
generally improve your play by thinking longer, and
if you can somehow think faster, then you can think
about more in the same amount of time.

Also, since a prime reason for the existence of
computer bg programs is to do rollouts, the faster
we can make 'em, the better.  I want to have a
world class program on my PC which rolls out (at
its highest level of play) an opening position
5000 times in an hour.  Better yet, in 5 minutes!

------------------------------

AUTOMATIC MOVE ELIMINATION
Humans generally only consider a handful of moves - often
only one out of dozens.  As has been discussed here lately,
computers typically look at every move, which may number in
the hundreds.

I mentioned one simple way to reduce the number of moves:
don't consider any play which leaves you with 2+ fewer
home board points when you have doubles and you're not
bearing off.  That's my conservative version.  You could
make it more aggressive, potentially eliminating more
correct moves.

Do other people have ideas for eliminating moves?
One idea I toyed with, but haven't implemented, is to
say that when you can hit in your opponent's board, and
you don't have any blots in your own board, and some
other conditions, then consider no play which doesn't hit.

These examples seem convoluted, but the fact is its
difficult to come up with things which only very, very
rarely prune away the best move.  Its nice to prune
bad moves, but its much much more important not to
prune good moves.

I think that one of the reasons humans do this so well
is because they have a plan, or at least goals.  They
pull checkers into their own outer board because they
have a goal of making the 5 point, not just because
it evaluates higher ('looks better').  So when they
roll the number that makes the point, they don't have
to think about all the other plays -- just check no
higher ranking goal is possible -- and then make the
move.  I don't know of any goal-directed backgammon
programs, but it seems like a very useful idea.

------------------------------

GRADED EVALUATION
The moves that humans do consider, they typically do
not consider in an all-or-nothing fashion.  They might
look at five candidates for a while, then decide one of
them looks the weakest, throw it out, and think more
about the other four.  And so on.  Until they end up with
two moves they can't decide between, the other player
opponent clears his or her throat, and they arbitrarily
pick the wrong one :-).

This idea has been used in a limited way by bg programs.
For example, TD-Gammon evaluates all the legal moves and
selects a few as candidates for further evaluation.
These it does a one-ply lookahead evaluation on.
(Please correct me, Gerry, if this has changed.)

My feeling is a much more graded evaluation is both
reasonable and desirable (although a pain to
implement).  For example, one might have a lightning
quick evaluation of all positions with a linear evaluator
of just a few (well, < 50) features, bringing about
a first reduction.  Then the full evaluator (with
perhaps some additional, more complex features) would
be applied.  If the situation is still unclear, one
could look ahead one, and then two ply, if the
program is fast enough.   This is the approach that
I hope to implement, because I want my program to
be both good (requiring a lot of evaluation of
candidate moves) and very fast, for rollouts.
Has anyone else worked on this kind of thing?

------------------------------


THEMATIC MOVE ELIMINATION
An approach often described in the backgammon
literature is the following:  after having come
up with a list of initial candidate moves, group
them thematically, and choose the best among each
theme.  Then select from these winning candidates.
The idea is that candidates which are thematically
similar can be compared more accurately, and so
its relatively easy to pick the best move for
each theme.  One still has to select the final
move, but at least one has reduced the problem
size.  Also, one hopes that any error in selecting
the best candidate for each theme will be
small relative to the potential error of getting
the theme wrong.

Although difficult to implement, I believe this
approach could pay big dividends for computer bg
players (programs) as well.  Grouping moves
thematically is non-trivial, but the basic idea is obvious:
group moves that hit, that make an inner board point,
that make a blocking point, that make an advanced anchor,
that escape, and so on.

------------------------------

I would be very grateful to hear anyone else's
ideas on improving computer bg, or commenting
on what I've written here.  Thanks!

David
 
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