Forum Archive :
Pruning the list of moves
> Under some conditions, I notice that a BG program may take far too
> long to make a move. I thought about this long ago, and came up with
> the following questions.
> If a computer rolls 1-1, how many possible plays might a computer need
> to evaluate before it decides its "best" play?
I don't have the numbers with me, but I believe it is possible for there
to be over 1000 moves. In practice, especially in contact positions,
there may be over 100 positions, but there usually aren't anywhere near
1000. Still, 150 positions is a lot to evaluate. I'm not 100% sure about
these numbers -- I calculated this stuff several years ago, and I don't
have the results handy. I know that when I'm generating a list of moves,
I leave room for 2000 moves, and I've never had any problems with this.
BTW, all the papers on computer backgammon mention that there are on
average around 20 ways to play a roll. Perhaps Berliner or Levy
measured this, I don't know. Has anyone else confirmed this, or
made any more detailed measurements? Its clear that there is a very
large variance, since many positions have only 1 'move' (e.g., fanning)
while others, like 1-1 in some situations, have *a lot* of possibilities.
> Is there a decent way to prune down the number of these evaluations?
The only work that I've heard of along these lines is (was) actually
implemented in Expert Backgammon. EB in many situations doesn't
look at moves which break up its inner board, since such plays are
so rarely correct. So EB is already pruning the space! You can
see the consequences of this pruning, sometimes. For example, EB
will sometimes leave a lot more shots than it needs to coming home
vs. a holding game, when it finally is forced to break a point. It
refuses to bust up its board, and gives an unnecessary double or
triple shot. This could be fixed (and may be, for all I know) by
looking again when the play selected is so ugly. This seems similar
to the way humans select 'ugly' moves -- at first you reject them
all, and then you go back and look for the least of several evils.
Or one could prune more conservatively, which is what I do in my
program, allowing the machine to consider breaking one home board
point but not two, and not pruning at all for non-doubles.
I would love to hear of any other ideas on pruning the search space,
especially without evaluation, which is what I understood you to
mean. A sensible way to prune the space besides this is to do
a little bit of evaluation, then select a few first level candidates,
evaluate these candidates further and prune further, and so on.
So all the moves get evaluated, but you don't think long about the
bad moves. TD-Gammon does something like this, because it first
evaluates all the moves without lookahead, and then generates a
weighted average of the continuations of the best candidate moves.
Gerry Tesauro writes:
The way all computer programs work (that I know of, anyway)
is to evaluate every possible legal play with an evaluation
function, and pick the highest scoring one. In some
positions, rolls of small doubles can produce several
hundred legal candidate plays. Evaluating all these plays
can be time-consuming if the evaluation function is slow.
This is rather different from what we humans do in that
kind of situation-- we focus only on the reasonable or
plausible candidates. The hundreds and hundreds of completely
hopeless plays never even enter our minds.
As a practical matter, you could solve this problem by
first using a "fast" evaluation function to prune the
number of candidates down to some manageable number, before
actually selecting the move with your "slow" function.
But to write a program with smart legal move generation,
that only thinks of reasonable candidates, is something
I don't know how to do. Has anyone else ever thought about
how to do this?
-- Gerry Tesauro (email@example.com)
- 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)
- Blockading feature (Sam Pottle+, Feb 1999)
- 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)
- 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)
- 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)
- Variance reduction of rollouts (Michael J. Zehr+, Aug 1998)
- 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)