COMPUTER CHESS: statistics
Deniz Yuret
am particularly interested in the efficacy of heuristics related to search
(move ordering, selectivity, extensions, etc.) It would be nice if we had a
source that gave us some idea about the qualitative properties of chess trees.
Some useful statistics on typical middle game positions might be:
1. number of nodes generated at each ply,
2. histogram of the static evaluation for each ply
(or for the children of a node) and
3. how it changes with further iterations,
4. the frequency with which typical move ordering heuristics "hit" and "miss"
5. the frequency with which quiescence search provides useful information that
cannot be computed easily statically.
etc. etc.
I guess the standard way is to write your program first, and then tweak the
parameters to optimize. But it seems like knowing these things ahead of time
might save a lot of effort in the design process.
I want to ask two questions:
> Does anyone know of any studies for data of this sort?
> Do you have further suggestions of "statistics" that would be useful to know
for the design of a chess program?
I won't be lazy, and actually collect these kinds of statistics if none are
available. So if there is something you have always wondered about chess
trees, now is the time to ask...
best,
deniz
--
Deniz Yuret
MIT Artificial Intelligence Laboratory tel: (617) 253-6247
545 Technology Square, Room: NE43-815 fax: (617) 253-5060
Cambridge, MA 02139, USA e-mail: de...@ai.mit.edu
Deniz Yuret
MIT Artificial Intelligence Laboratory tel: (617) 253-6247
545 Technology Square, Room: NE43-815 fax: (617) 253-5060
Cambridge, MA 02139, USA e-mail: de...@ai.mit.edu
Robert Hyatt
Deniz Yuret <de...@great-grain.ai.mit.edu> wrote:
>One is faced with a lot of heuristic decisions when writing a chess program. I
>am particularly interested in the efficacy of heuristics related to search
>(move ordering, selectivity, extensions, etc.) It would be nice if we had a
>source that gave us some idea about the qualitative properties of chess trees.
>Some useful statistics on typical middle game positions might be:
>1. number of nodes generated at each ply,
I agree that this would be useful. However, since we all tend to "go our
own way" with search extensions, it is *hard* to compare a to b. To further
complicate things, the special-purpose hardware guys have to give up some
things to be able to build the hardware, as a result the trees they grow are
usually quite a bit larger than a corresponding "software only" tree anyway.
>2. histogram of the static evaluation for each ply
> (or for the children of a node) and
>3. how it changes with further iterations,
I have seen a couple of small studies here. the point of interest was how
often does a program change it's mind by going one ply deeper. The tongue
in cheek conclusion: "just enough to make it worthwhile.."
>4. the frequency with which typical move ordering heuristics "hit" and "miss"
position dependent which makes it hard to compare. some positions (notably
tactical ones) are handled quite well by programs with heuristics that tend
to try checks, captures, etc. as well as extend these lines deeper. Others
can cause an algorithm to perform poorly as every additional ply of search
exposes new things about the position that make the old move/ordering info
nearly worthless...
>5. the frequency with which quiescence search provides useful information that
> cannot be computed easily statically.
all the time. captures are simply *hard* to statically evaluate since there is
so much "dynamic" information to handle: what's pinned, what's overloaded,
what's defending against mate, etc. That's why we all do the quiescence
search (and why it's called "quiescence search").. give the evaluator a
"quite" position to evaluate where it doesn't have to (hopefully) worry about
hanging pieces, threats, pins, etc...
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170