movegen needed
Keith Wear
backgammon tree. I was wondering if there is a good move generator that is
available which is fairly independent from the rest of the program. I would
like to just give it the position of the pieces, the roll of the dice, and
the person to play.
Any pointers would be appreciated.
Keith Wear
David Montgomery
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