Winboard Forum

Hi,

during Paderborn (just before the last round) I discovered a big problem in Quarks book compiling code which leads to wrong statistics in the book.

Therefor I would recommand to download the following book of Quark:

http://www.quarkchess.de/quark/quarkbook.zip

Attention: 17 MB

You must also adjust the quark.qbt.

book quark.bk1

This book will work fine with the v2.35 and should do better then the old ones. (The bug exists since version v1.76, so right after CCT4 - so it's a really old bug)

If anybody is interested he can contact me by eMail to get the v2.55 which is more or less the Paderborn version but without the book compiling bug.

Currently I work on a new version with history pruning, but right now I am not really sure if it is worth the effort. Quark gets usually 1 or more plys deeper with it, but seems to be also 1 or more plys more stupid... Results are so far very unclear, it seems to do a bit better in blitz but I am not really sure about long games. Seems that I have removed my old tactically a bit unsound pruning with another unsound pruning system. But there are still enough screws to play with. Besides that I still work on the eval, but that is another very time consuming and complicate thing.
Since v2.55 I have introduced bitbases and recognizers -> those which eMail me about the v2.55 will get an explanation how to create them. They really seem to help a bit in endgames - not by a big margin, but at least measureable... So the v2.55 finds two solutions more then the v2.35 in the PET and most of them faster then the v2.35...

Greets, Thomas

P.S.: Yes, Paderborn was a disaster for Quark -> I do not know if it would have scored really better without the book bug, but at least it could fight then longer, because getting out of book in bad positions does not really help...

Thomas Mayer wrote:Currently I work on a new version with history pruning, but right now I am not really sure if it is worth the effort. Quark gets usually 1 or more plys deeper with it, but seems to be also 1 or more plys more stupid...

Hi Thomas,
in the past few weeks I have experimented a lot with history pruning and have been really disappointed by the result I got in play. However, at some point I decided to turn off null move and things changed a lot. That version, which used a far from optimal pruning, scored 48% against the normal program (with null move and all). For comparison, no version with history *and* nullmove scored more than 42% in that experiment. Although my program could very well be a pathological case, I also remember that in a old post Reinhard said that nullmove wasn't working well for him, so it seems possible that having more than one pruning algorithm in the tree can lead to trouble and must be tuned carefully.

Hi Alessandro,

Alessandro Scotti wrote:

Thomas Mayer wrote:Currently I work on a new version with history pruning, but right now I am not really sure if it is worth the effort. Quark gets usually 1 or more plys deeper with it, but seems to be also 1 or more plys more stupid...

in the past few weeks I have experimented a lot with history pruning and have been really disappointed by the result I got in play. However, at some point I decided to turn off null move and things changed a lot. That version, which used a far from optimal pruning, scored 48% against the normal program (with null move and all). For comparison, no version with history *and* nullmove scored more than 42% in that experiment. Although my program could very well be a pathological case, I also remember that in a old post Reinhard said that nullmove wasn't working well for him, so it seems possible that having more than one pruning algorithm in the tree can lead to trouble and must be tuned carefully.

well, I have severall things in mind which I want to try: e.g. my results were better when I only try history pruning when nullmove was also allowed in the position. Of course I don't do history pruning when I extend the position. Like nullmove I might add a variable so that two history prunings in a row are not allowed. I also stop history pruning 3 plys before the leaves... a friend of mine told me that since he does the same thing with nullmove his results got way better...
Also I have not tried other history schemes, so far I rely still on the old table [from][to] -> maybe that makes also a difference.
In the endgame it seems to be problematic with history pruning -> therefor I try it currently with reducing just a half ply instead of a full one... Of course there is much more possible to test... Anyway, history pruning seems to harm some positional things - And it is interesting enough to work on it, I simply like the idea and it's simpleness...

Besides, without nullmove I think it is doing more or less something similar then the nullmove but without the Zugzwang problem...

Greets, Thomas

Hi Alessandro,

before I started programming my Smirf I have thought a lot of pruning in abstract. Each pruning strategy e. g. has an estimated error potential to cut away the best move sequence. So iterating pruning at several plys will have a specific depth, where with a probability of more than 50% only nonsense will be investigated because the best sequence will mostly not be followed until there.

So it is to obey not to add the bad chances by combining pruning ideas. And (what has been Smirf's approach) it should be attempted to decrease the bad chances at cascaded prunings by lowering the chances of skipping the best move sequence.

Because I have noticed that combining my pruning method with nullmove pruning would neither be more effective nor shrink the chances of bad cuts, I erased any nullmove pruning and noticed moreover to have better chances to include best move sequences.

This moment I am still satisfied with my pruning results - may be because an estimated strength of actually 2400+ Elo for the still unready Smirf beta is quite encouraging. Today my problems with that program are located in errornous using of cached values and related difficulties.

When I hopefully will have managed later to clean Smirf from current problems, it of course will happen, that I will have different attempts to combine other pruning ideas again, maybe also nullmove related ideas will have a second chance. We will see ...

Regards, Reinhard.

Can someone explain history pruning to me?

--Jon

jdart wrote:Can someone explain history pruning to me?

--Jon

<my limited understanding>

If a move has a low history score, decrease the depth to which you will search it. Of course you won't prune checks etc. And you will only do this if the move is not a hashtable/killer move etc, and maybe other safeguards. Fruit 2.0 has some code for this, If you're interested.

One detail which is maybe important: I remember from Fruit code that when a history heuristic based move is tried, and it does not fail high, then the score for that history move is decreased.
</my limited understanding>

Hi Jon

jdart wrote:Can someone explain history pruning to me?

here is just a part of Quarks code:

Code: Select all

#if HISTORYPRUNING
            // History Pruning
            if ((Stellung.ZugPhase>10) && (DistanzAB>(3*MOVELENGTH-1)) /* && ((NullMove) || (SWert<Alpha)) */
               && (!Extend) && (!Stellung.MoveChecks) /* && (BesterWert>-31000) */
               && (History[Stellung.Zug & 4095]<BestHistory[Tiefe]) && (!Stellung.InHV)) {
               Extend=Endspiel[!Farbe] ? -MOVELENGTH/2:-MOVELENGTH;
            }
#endif


I explain the used variables here:

Stellung.Zugphase is the movephase of the nextmove function -> e.g. phase one is the Hash move etc. Phase 10 are the first 3 silent moves. Phase 11 are all other silent moves.
DistanzAB is the distance to the leave.
MOVELENGTH is the length of one move (I use fractal depth)
Nullmove is just boolean and if true, nullmove is allowed in that position
SWert is the evaluation in the position
Alpha does not need an explanation, I think...
Extend stores the extensions in that position.
Stellung.MoveChecks indicated wether the move checks.
BesterWert is the so far found best value in the current position.
History[] is the history table
Stellung.Zug is the current move -> Quark has a 16 bit move, first 6 bits for the from field, next 6 bits for the to field and last 4 bits for the new piece...
BestHistory[] stores half of the best value for any move found in the history table
Tiefe is simply the depth -> as you can see my code is full of german and english variables - I have the feeling that it depends wether my last eMail was in english or in german which language I use...
Stellung.InHV indicates wether the node is still a PV node (PV = Hauptvariante in german)
Endspiel[colour] indicates wether the colour is in endgame or not

So the idea is simple: you only reduce depth for silent moves if their History value is beyond a certain value compared to the move with the highest History score in that node... (Currently I use half of the best score, but you can also try one third or whatever)

Also you must keep care of your history table so that the value do not get to high - therefor I have a MaxHistoryScore which stores the biggest value found in the tree. After every move I check if it is higher then 65000. If yes, I just shift right every value in the history table by 12 bits. (Of course this is also a field to experiment with)

As you can see from the /* and */ this all is still in the experimental phase and some more work is to do here... So far the results are not so well against other opponents (but too less games). Against itself it is slightly above 50%...

Greets, Thomas