Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Couple of chess programming questions

Author: Vincent Diepeveen

Date: 09:07:37 09/10/02

Go up one level in this thread


On September 10, 2002 at 09:26:14, Eli Liang wrote:

>A couple of chess programming questions:
>
>(1) Are there any uses for ProbCut and/or Multi-ProbCut in chess positions where
>the variance of leaf-nodes is low?  What about the use of Warren Smith's BPIP or
>Russell&Wefald's meta-greedy algorithms in chess?  Any wins?

Not for DIEP, and for my draughtsprogram (where it was invented for)
it didn't work either. But look, the engine diep and the draughtsprogram
are much better than the dude who invented it. For some kids game
checkers which you can play near perfect, so getting to EGTB
or other won positions there is perhaps more important, than
a form of search which is better for an evaluation function.

>(2) Is it practical to use partial-order bounding as an improvement over
>conventional static evaluation?

I am not sure what you mean here. What is partial-order bounding
in this respect. You mean anything related to a quicker evaluation
than a full conventional static evaluation?

>(3) Reading Aske Plaat's search & re-search paper, it really seems like mtd(f)
>is something of a magic bullet.  But I note it seems that more programs don't
>use it than do (for example Crafty).  What is wrong with mtd(f) which Plaat
>doesn't say?

There is nothing wrong with it. However a softwareprogram must have certain
conditions to let it work well (in hardware other issues play a role)
  a) it must be a static evaluation with a small granularity;
     if pawn=32 it will work great, if pawn=1000 like in DIEP it won't
     work at all, other things aren't interesting then.

  b) fluctuations of mainline is a big problem for MTD. In short
     it prefers positions where the evaluation is completely flat
     and every iteration the same score.

So the main problem is real simple. If we just assume b then obviously
it works if a certain move is initially clearly best. You can quickly
skip plies then.

My question then is: if you already know a certain move is clearly best,
who needs to look deeper such positions anyway?

Of course for testsets this is a great feature. But for positions which
decide the outcome of important games at world champs, there the engine
doubts and doubts and doubts, and it's not hard to understand then that
there is pretty much fluctuation of the scores and mainlines and MTD
will look poor then.

But basically there are circumstances possible where MTD works great.
Of course this is not nice said, and definitely not meant as bad as
it looks, but in general: the more stupid an engine is the better MTD
works.

>(4) What are the current thoughts concerning bitboards/rotated-bitboards versus
>conventional 0x88 or other algorithms?  Just looking at open source chess
>programs, it doesn't seem that the chess programming community has come to a
>consensus on relative performance... or have you?

Without exception vaste majority of commercial engines and strong
amateur engines are non-bitboards. That says *something*.

DIEP is not 0x88 but basically 0x88 is working great in assembly whereas
other solutions like optimized gnuchess 4.0 concepts (not to
confuse with later gnuchess versions 5.0 which are raped to
bad bitboards).

Obviously bitboards do not work at 32 bits processors very fast. However
no one ever did effort in open source to either optimize 0x88 or gnuchess4.0
datastructures, so the alternative is to program something yourself.

Most programmers suck ass in programming for speed, so cut'n pasting crafty's
datastructure is an easy option then and they all post it's working
'great' for them too.

But some hard data on the MMX unit of the 32 bits processors
  a) the P3 has 2 decoders
  b) the P4 has only 1

In short normal instructions go 3 times faster on the P4, and a potential
but theoretic not possible 4 times faster. IN the future it will perhaps.

Which means that executing 64 bits code is no big fun on todays processors.

>(5) What is currently thought to be the best algorithm for autofitting the
>static evaluation function parameters? DT's least-squares approach seems
>simplest, but it seems as if a dozen other things have been tried too.  Is there
>any best-of-breed approach here?

autotuning parameters is something you only must do if you suck terrible
in chess, like not knowing the en passant rule very well.

they wlil tune of course some patterns you made with values opposite
signed from what you wished it is. Only very bad chess players will
be capable of making patterns that have the wrong sign, or bugs
in your thing.

>(6) Has anyone found any real "practical" benefits to fractional-ply extensions?

extensive tests i did with anything with fractinal ply extensions
and i have also tried pruning in that way, as well as others.

But the current diep version isn't using it at all.

Either an extension is GOOD and need to be extended by 1 ply,
or something SUCKS ass and doesn't need to get extended.

The idea of removing the badness of a sucking extension by not extending
it a full ply is fooling yourself IMHO.

I do not believe in fractional plydepth or extensions at all.

Many use it though.

>(7) Dennis Breuker has a paper comparing 5 different transposition table
>replacement schemes.  Has any else been able to validate his results that
>replacement should be based on the number of nodes searched and not search
>depth?

Well this was a good work of dennis, regrettably he only tried it till
8 ply depth searches, which is a bit pathetic. Nevertheless his conclusions
were ok and that's that more works. So despite pathetic testing from Dennis,
and minimal testing info, it is a good idea to do more probes. Yet it
was not a new idea at all. I already used 4 probes before he did the test.

I use 8 probes in my hashtable. Of course sequential probes, not anymore
at completley different locations.

In general a good usage of the hashtable in combination with recursive
nullmove R=3 is the big progress of todays software from search depth
seen. Of course the big progress in playing strength is more than that.
it's basically a better evaluation and better book which results in
the weakest link being pretty strong now.

Best regards,
Vincent



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