Computer Chess Club Archives


Search

Terms

Messages

Subject: To skin a cat (was Re: NULL MOVE)

Author: Don Dailey

Date: 21:12:53 02/24/99

Go up one level in this thread


On February 24, 1999 at 19:16:27, Bruce Moreland wrote:

>
>On February 24, 1999 at 15:37:58, Don Dailey wrote:
>
>>My program is a mixture of static rules and null move.  I do null
>>move when I have significant depth remaining, but when I am near
>>end nodes I do a simple static attack analysis.  This has proven
>>to be a significant improvement to my chess program.  It is faster
>>than null move and slightly riskier, but the net affect is
>>a stronger chess program (for me.)   Even though it's probably
>>riskier, it does pick up things null move will miss although the
>>converse is also true.
>
>Can you describe this or give examples please?  I know that some people do this
>but I haven't the vaguest idea how it works.
>
>bruce

Ok, I'll describe it.  There is  nothing about it that is particularly
sophisticated, it's just another variation on a theme.

Essentially, it's a  lot like  a Static  Exchange  Evaluator but  with
simplifications.  What you are trying to measure  is of course whether
the side to move is likely to lose any material,  so you can take some
liberties that SEE might not take.

You only apply  this routine   (I'll  call it the  static  selectivity
tester) when a call to  eval is already above beta.   I do this anyway
when determining whether to do a  null move search.   But I think it's
more important to do it with  this tester.  Now  you must evaluate the
attack potential  of the enemy  or side NOT to  move.  The dumbest and
simplest test, which works pretty  well but is far  from optimum is to
consider the highest piece that is attacked  and take some fraction of
it's value.   Something like 2/3 is appropriate.   As an example, if a
queen is attacked, you are making the assumption that it will be lost,
but that you will recover 1/3 of it's value.

Before I  continue, I would  like to share a  little history of how we
came up with this idea.   One day me and  Larry Kaufman were lamenting
the appearance  of   new programs that    used  some kind   of unknown
selective search and  seemed to benefit from this.   We of  course did
not have  a clue about  how this was done.   We tried a lot  of stupid
stuff and of course none of  it worked very  well.  But Larry made the
observation that the queen was pretty good  at taking care of herself,
and that even when it was hopelessly attacked, you could almost always
get  a piece back for  it.  Generally this  involved simply taking the
piece that was attacking  the queen.  Since  the queen was the highest
valued  piece other than  the  king, he  asked   me, just for  fun, to
implement a rules that said IF you are  not in check, and your current
STATIC  score is 6 pawns  above beta, just prune   the move out of the
search.  I implemented it, we measured  a nice little speedup (nothing
huge)  and he tried a  bunch of problems, and   we solved every one of
them in the same  depth we normally would.  We  started to get excited
and then we run a bunch of self-test games.  Our new selective version
proved to be a modest but noticable improvement.  We were elated.  But
then I said to Larry, why not  look first to see  if the queen is even
attacked?  One thing led to  another and  we started implementing  all
kind of rules, noticing what was attacking and what was defending this
or  that.  Before long we  had a full  blown  selective search program
which became RexChess.  We didn't know what the other guys were doing,
but we had stumbled on  the right principle ourselves.  Looking  back,
it almost seems that we  were stupid not to  pick this up before,  but
this is  always  the  case  with  new discoveries.  They   seem almost
trivial once you have  the benefit of hindsight.   Of course the basic
principles were discovered   by others well  before  us,  but we  were
forced to figure them out on  our own since  no one would tell us what
they were doing.

So  most of these ideas evolved  from this work.   To continue on, the
next step is to do this test on the largest piece that is attacked and
work your  way down.  If you  determine that a  piece is attacked, you
take 2/3 of it's value and test this against  beta.  For instance if a
knight is attacked, consider it 2/3 of a knight etc.

There are  a few rules to determine  if something is attacked, You can
simply use SEE if you  have it, or  you can do something much simpler.
The  very  simplest, but of course   wasteful, is to consider anything
that is under direct attack as being lost.  We do this for up-attacks.
With down attacks we don't even consider  it an attack if the attacked
piece or pawn is defended by a pawn.  Otherwise  we look at the lowest
valued defender and do the  math.  We don't  play this out several ply
like a good SEE routine might do, we just assume the worst and play it
safe.  We don't bother to check to see if the defending pawn is pinned
either or anything this elaborate.  With equal attacks we simply count
attackers and  defenders and compare them (I  think.)  In some version
we didn't even  consider same piece attacks as  attacks because if his
knight is attacking your knight you can simply remove HIS knight since
it is your turn to move.  However we feel that this is a bit too risky
even though it gives you a nice speedup.

We also  have  some advanced pawn rules,  a  pawn on  the 7th,  if not
blocked  is considered a queen   attack.  In versions of our  programs
that do a lot of this kind of selectivity, we  have stuff for pawns on
the 6th  too.  Also we have some  simple but common mating themes, the
most useful one is that if a major piece is attacking a square next to
the king with some backup, we go full width.

There are a lot of refinements to this and we have tried them all.  It
ends up being 6 of one, half dozen of the other.  It's hard to improve
in any substantial way on this basic scheme.   You can play with speed
vs accuracy tradeoffs until you are blue in the  face.  The 2/3 number
I gave you  needs to be tuned.   We  use a value slightly  higher than
2/3, this should be  adjusted just so, there is  a point where  if you
use too small   a fraction you  will suddenly  start missing a  lot of
tactics.   We have also experimented   with having different fractions
for different  pieces, but have never demonstrated  any  real gain for
doing this.

All of this offends  my sense of precision  and beauty too, but I just
haven't found a way  to improve on  this scheme which is a hodge-podge
of assumptions and hacks.  The interesting  thing about this for us is
that null move selectivity  is clearly a big  win at deeper levels due
to it's  superior threat finding  ability, but near  leaf nodes of the
main search, this always ends  up being  better.   I really WISH  null
move "all the way" was best (for us) because  it's certainly a cleaner
way to do things.

You  might try using this with  Ferret just to see  what happens.  Run
your SEE routine  to get a  tactical score and   try using 2/3  of the
value returned  (on the 2 levels  just before the quies search instead
of null move)  just to see what  happens.  Probably you've  hacked and
tweaked your program to do whatever it does very well already and this
might not be an improvement for you, but then again, maybe it will be.

I  said before that this sometimes  picks up  things  a real null move
search might not.   This is  mainly  a side effect and   serendipitous
because my routine sometimes  makes a conservative assumption and goes
full width where a null+quies might not.

Rex was built on this whole idea, no null move at  all.  In its day it
was considered a very FAST program.   The earliest version of Socrates
that won the 1993 international championship was  my LAST program that
didn't use null move pruning and it also used this kind of selectivity
since we were not yet willing to try null move prunning.

I ported this program over to Unix and play with it occasionally and I
am   still  impressed with how  fast   it is, it  does   this  kind of
selectivity on the last 4 levels of the main search, like Rex does (or
maybe Rex does 3 ply of this, I'm not positive.)  I would love to make
the executable  of this program  public domain if it  were not for the
fact that I do not OWN it!  It beats  every public domain programs out
there pretty easily and it also beats  the current serial CilkChess on
a  32 bit machine.  It's still  a good program  even without null move
prunning.  I think null move prunning would improve it however.

I  think there are  probably  several  modern programs  that use  some
version of this  static based selectivity,  and Rebel is  one of them.
Rebel may not do it  anything like we did, but  it shows that there is
more than one way to skin a cat!

- Don



This page took 0.09 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.