Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: What is

Author: Don Dailey

Date: 11:20:58 05/08/98

Go up one level in this thread


On May 08, 1998 at 10:51:56, Ulrich Tuerke wrote:

>Hi Don,
>thanks for your good and clear presentation. I too think that
>pre-processing is still done in most of the current chess programs, -
>more or less.
>I am considering the possibility of a moderated pre-processing, i. e.
>apply the time-consuming pre-processing evaluation parts not at the root
>but to nodes at depth - say - the half of the aimed search depth. Thus,
>one would still have the main advantage, saving a lot of calculation
>time, because the number of pre-processed nodes would still be a
>microscopic fraction of the leaf nodes. But on the other hand, the
>preprocessed knowledge would be applied to nodes being far closer to the
>leaf nodes (in your examples "only" 30 ply instead of 60).
>Opinions ?
Of course!

I've been considering this type of approach for a  long time.  I think
it definitely has  merit.  It would  suffer from  hash table anomolies
but there are ways to deal with this, the primary one to simply ignore
them.

There are  a few issues to  be dealt with  but my feeling  is that you
might do well  with this scheme.  Scoring  might be a  little fuzzy at
times but  that  might   be ok.   Probably  the scheme   would   be to
pre-process at  every  level up to  MAX_DEPTH-n, where  n might be  at
least 3 or  4  ply.  Keep in  mind  that pre-processing  is incredibly
expensive even compared to fully  dynamic processing, so I suspect you
cannot get  very close to the leaf  nodes.  Of course  3 or 4 ply away
might be considered pretty close if you were doing 14 ply searches.

The way I  got this idea (which  I'm  not taking credit for)  actually
began when I was programming the ending Bishop and Knight vs King with
a pre-processor program of mine a few years ago.   This is a very good
exercise for someone wanting to understand some of the difficulties of
pre-processing.  I tested with a 3 ply  search, and tuned the thing up
to do  quite well.  But it turned  out to  not work  so  well at other
levels!  It turns  out that no matter what   table you use,  they will
tend to be  optimum for a  specific depth only.   It  was almost funny
because I kept figuring out which positions in the search were messing
it up  and  changed the tables  accordingly.  These  anticpations were
wrong though  at different  levels!   Finally though, I  extracted the
most general principles possible and  created a table that was  almost
static (not based as much on the placing of the pieces) and it did ok,
but not  as good as the depth  specific ones.  Some preprocessors will
suggest a move and for this ending that would work  well.  The idea is
to give a bonus to  the whole search  tree under some  root move.  For
example I might give a small bonus for playing  any move that's a pin.
This  makes the program  slightly in favor  of playing  a pin.  I call
these  "ply 1 incentives" but  there is probably  better terminolgy in
use.  This is also another example  of preprocessing.  See note at end
of my post.

But your  idea would  solve this and  a  host of other  problems.  You
could  make very good guesses   about configurations  if you knew  the
possible changes to a position were limited.  This would enable you to
be more aggressive about the knowledge you included.

Here is another   idea I had  which is  more dynamic  in nature.    It
occured to me  that you could  do a fairly  decent evaluation based on
pawn position only, the idea being  a separate set  of tables for each
pawn structure.  These could be built by the pawn structure hash table
mechanism most programs have.   Most pieces can  be judged well by the
pawn structure around them.

I did not persue  this idea because I  fear it may  still be too slow.
If my hash  table  hit  rate was say    95 percent, then 1/20 of   the
positions  would require  a preprocessing  step.   While this does not
seem like much, you have to consider  how expensive building the table
is.   It's pretty expensive,   especially if you want  sophistication.
But on top of that  you must recompute  the positional score each time
the pawn structure  changes, EVEN if the table  itself is ready to go.
This  should be  fairly fast  but not  trivial in   terms of execution
speed.  You have already  killed some of the  speed you were hoping to
gain.  Is the  idea  workable?  Maybe,  but I'm skeptical.   Also, the
pawn  structure is not the   only relavant factor  so other evaluation
would not doubt be  needed.  For instance you cannot  look at the pawn
structure and know  for sure that  you  are in an endgame.   You could
make assumptions though  based on the exact position  you had when you
built the tables.

Anyway the idea  is interesting and I sometimes  toy with  the idea of
trying it out, but it seems like a lot of  work for an experiment that
may not pay off.  It could well be that someone dedicated to making it
work might find imaginative solutions to some of the problems.

But your idea may be more sound.  It may very well be that some are
using it.  I've never heard of a specific example of it though.

- Don

*
I think an  old program  called "Tech"  used  the method of "ply 1  move
incentives." There  was no  evaluation at  all (the  way I remember it)
except for material value and a list of moves was prepared in order of
goodness from a pre-processor at the  root.  The program simply played
the first move it came to in the  move list that was  at least as good
tactical as any other.   I'll bet Bob Hyatt knows about this one.  I
had a nice dicussion once with the programmer when he was giving a talk
on hash table collisions in chess programs.






This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

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