Computer Chess Club Archives


Search

Terms

Messages

Subject: Selecting among book moves

Author: Steven J. Edwards

Date: 08:14:27 06/19/98


Fellow programmers:

Inexpensive disk drives and easily acquired game databases have made opening
book position library construction a much easier process than it was only a few
years ago.  In the early days of CC competition, having a 5,000 move book was
impressive; now we are regularly talking about constructing books from hundreds
of thuousands of games.

But have we made an advance in how moves are selected from the book?
Specifically, what is the best method for selecting a move from the various
alternatives stored for a given position?

Currently, I use a very simple method.  I only store moves played by the winning
side; each move has a reference count (number of wins).  At lookup time, all the
moves for a posiiton are scanned and the sum of the counts is calculated.  Then,
a uniformly distributed psuedorandom number is picked so that the probability of
a move being selected is directly proportional to its count relative to the sum
of the counts.

This technique completely ignores draws and losses.  But how to use that extra
information?  Given a position and a set of books moves for that position with
each book move having (win/lose/draw) counts, what is the algorithm for
selection?

Another problem is that opening theory changes over time.  A very popular move
in the first decade of this century may not be so good in the last decade.
Perhaps along with usage counts, each move should also have a time distribution.
 For example, the Date tag values of scanned input games that feature that move
could be used to generate mean and standard deviation data.  At selection time,
more recent moves could be selected over earlier moves.  But again, what would
be the best way to do this?

-- Steven (sje@mv.mv.com)



This page took 0.01 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.