move evaluators?
Bob Johnson x6152
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?
Is there a decent way to prune down the number of these evaluations?
Appologies to Gerry Tesauro, who may find my questions trivial.
----- Robert D. Johnson rjoh...@cvbnet.cv.com
Gerry Tesauro
Bob Johnson x6152 <rjoh...@cvbnet.CV.COM> wrote:
>
>If a computer rolls 1-1, how many possible plays might a computer need
>to evaluate before it decides its "best" play?
>
>Is there a decent way to prune down the number of these evaluations?
>
>Appologies to Gerry Tesauro, who may find my questions trivial.
Actually, I think this is a very interesting and non-trivial
question. 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 (tes...@watson.ibm.com)
David Montgomery
>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
Durf Freund
: 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.
Oh, how I wish that were true.
Durf
Justin Boyan
>If a computer rolls 1-1, how many possible plays might a computer need
>to evaluate before it decides its "best" play?
It seems to me that the maximum number of legal moves would indeed
occur on a roll of 1-1; perhaps on the following position, which has
*2210* distinct legal moves for X:
24 23 22 21 20 19 bar 18 17 16 15 14 13
/--v-----v-----v-----v-----v-----v---+-+---v-----v-----v-----v-----v-----v--\
= | <X> <X> <X> <X> | | <X> <X> <X> <X> |
= | | | |
= | | | |
= | | | |
= | | | |
= | | | |
= | | | |
| | | |
| [O] |
| | | |
| | | |
| | | |
| | | |
| | | |
| <X> <X> <X> | | <X> <X> <X> <X> |
\--^-----^-----^-----^-----^-----^---+-+---^-----^-----^-----^-----^-----^--/
0 1 2 3 4 5 6 7 8 9 10 11 12
I've never seen a position quite like this one come up in a game
situation, though, so Monty, your cap of 2000 legal moves per roll
seems sufficient!
-Justin
--
------------------------------------------------------------------------------
Justin...@cs.cmu.edu Comp Sci grad student, Carnegie Mellon