Backgammon Programming

Programming

Pruning the list of moves

From:   David Montgomery
Address:   monty@cs.umd.edu
Date:   9 February 1994
Subject:   Re: move evaluators?
Forum:   rec.games.backgammon
Google:   2jbvqr$e2q@twix.cs.umd.edu

> 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. David

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 (tesauro@watson.ibm.com)

Did you find the information in this article useful?

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