Winboard Forum

Hi all,

these days I tried to implement a sort of null move pruning. I got it working, but the results have been nearly not to be noticed. Some examples has been slightly slower some others slightly faster. But the quality of move answers themself seemed somehow to be decreased.

It is looking like Smirf's own intelligence feed back recursing facilities would not harmonize with the idea of nullmove pruning. Instead Smirf's generic approach seems to be at least as effective as the nullmove idea, because there not any significant improvement could be reached by using that.

In which scenarios nullmove pruning might be effective? What are the conditions concerning the to be optimized selection tree? Are there any other pruning methods, where nullmove pruning nevertheless would add some performance?

Reinhard.

Hi Reinhard,
I am not sure if I understand you correctly because your english is not very good(my first language is not english but in most cases I understand other people better).

I guess that you mean to chess positions in the word examples but I am not sure what you mean by slightly faster or slightly slower.

Did you use positions when there is a best known move and compared time to find the correct move?

What you mean by the quality of answers?

Do you mean that you tested it in games and found that it plays weaker moves?

Uri

Usually, you will see at least one or two more plies of depth with no real loss of quality (except in zugzwang, which is not too hard to detect). (Maybe 100 Elo better)

So I suspect you already have a method that reduces depth for positions that look less interesting.

Is that correct?

Hi Dann and Uri,

Dann: So I suspect you already have a method that reduces depth for positions that look less interesting

indeed, that is where the name Smirf comes from. http://www.chessbox.de/Compu/schachsmirf_e.html

Uri: your english is not very good

Well, it try to explain myself in English but not always I am successfull with that, sorry.

There is a private test suite, which is put into an evaluating routine for every possible move from that position. The experience has been, that the performance then was nearly the same. And - as you already have prosumed - I have got the impression doing test games for the result to produce slightly weaker moves.

Not at all there could be noticed by me an effect of reaching some plies more in depth. So I concluded, that both approaches are concurring and not supplying each other. Therefore I asked for the conditions and demands concering the to be optimized search tree, which (besides of avoiding zugzwang positions) probably have to be fullfilled to make the nullmove heuristic work.

After those frustrating experiments I have deleted that small Nullmove chapter from Smirf's tree search and decided to follow alone that genuine approach.

Reinhard.

Reinhard Scharnagl wrote:Hi Dann and Uri,

Dann: So I suspect you already have a method that reduces depth for positions that look less interesting

indeed, that is where the name Smirf comes from. http://www.chessbox.de/Compu/schachsmirf_e.html

Uri: your english is not very good

Well, it try to explain myself in English but not always I am successfull with that, sorry.

There is a private test suite, which is put into an evaluating routine for every possible move from that position.

Hi Reinhard,again I am not sure if I undertstand you correctly.
The problem is not words that I do not understand but some structure that I am not used to read.

I will try to explain your words in english that is more easy to understand for me.

If I understand correctly You say:
"there is a function that evaluates every legal move in every poisition in a test suite and give a score for it that is based on search."

Note that most programs including movei have only exact score for the best move.
I do not claim that this strategy is optimal(you may want to know exact scores for all moves for decisions about extensions or pruning) but it is clear that you need at least to care not to waste too much time on illogical moves.

The experience has been, that the performance then was nearly the same. And - as you already have prosumed - I have got the impression doing test games for the result to produce slightly weaker moves.

Not at all there could be noticed by me an effect of reaching some plies more in depth.

I am surprised to read it
If I understand correctly you claim that you do not search deeper when you add null move pruning.

It seems illogical because you should be able to search deeper when you add pruning even if it is wrong pruning.

So I concluded, that both approaches are concurring and not supplying each other. Therefore I asked for the conditions and demands concering the to be optimized search tree, which (besides of avoiding zugzwang positions) probably have to be fullfilled to make the nullmove heuristic work.

After those frustrating experiments I have deleted that small Nullmove chapter from Smirf's tree search and decided to follow alone that genuine approach.

Reinhard.

My experience is that null move usually works well in the middle game without special conditions.

Uri

Probably, he already reduces depth in some other way for the same positions.

Null move is an arbitrary boundary to reduce depth (that is, if a move appears equal to a loss of tempo or worse, search less deeply). He already has some pruning algorithms that reduce depth. So, he may have already reduced the depth by a similar amount. In that case, null move may not change the shape of the tree very much at all.

Hi Uri,

Note that most programs including movei have only exact score for the best move

that might be true for the final tree search routine. But I was talking from a testing routine, which is evaluating each move of a test position exactly, because that evaluating finally should work for good and bad moves.

If I understand correctly you claim that you do not search deeper when you add null move pruning

That is correct. I tried two versions: one cutting one extra ply, the other cutting two extra plies. But the targeted pruning effect could not be seen.

It seems illogical because you should be able to search deeper when you add pruning even if it is wrong pruning.

The logically explanation for this effect (so I conclude) is that there are nearly no prunings left for be cut off by the Nullmove heuristic. Or in other words: the genuine Smirf approach already has produced a very well pruned tree.

My experience is that null move usually works well in the middle game without special conditions.

There have been a lot of different testing positions in that testing suite.

Reinhard.

Reinhard Scharnagl wrote:I tried two versions: one cutting one extra ply, the other cutting two extra plies. But the targeted pruning effect could not be seen.

How does that reduction work? When null moving is "successful" you should prune the entire subtree.

Reinhard Scharnagl wrote:The logically explanation for this effect (so I conclude) is that there are nearly no prunings left for be cut off by the Nullmove heuristic. Or in other words: the genuine Smirf approach already has produced a very well pruned tree.

That's possible, but doesn't sound too likely. However, my experience is this: all components in a chess engine interact tightly with each other, and changes in one component might affect the others, especially bug fixes of course but not only those. So during the development of Kiwi it often happened that things that didn't work started to work after some time because of advancements in other areas. Null move pruning was like that, except that it immediately provided benefits to me, even in the most rudimentary form. Maybe you'll try again in a week and it starts working...

Hi Alessandro,

How does that reduction work?

here is the deactivated Nullmove pruning chapter whithin my code, but it has been written mostly in German language.

Code: Select all

/*
  // Null Move pruning
  if (  !GetPlySchach() && anz > 3
     && beta > -MATTWERT && beta < MATTWERT
     ) {
    TZug zg;
    zg.FullMove = 0;
    DoMove(zg);
    // bleibt der Gegner unter der beta-Schwelle?
    value = -Bewerte(-beta, 1-beta, tiefe-2);
    ReMove();
    // ggf. Pruning
    if (value >= beta) {
      // Remis-Wert nicht ?ndern
      if (value)
        value = beta;
      pL->E.minVal = value;
      goto _EndeAktiv;
    }
  }
*/


I have tested it with tiefe-2 and tiefe-3. I am very sure to have it implemented right. But it seems as if the search tree already would be in good shape. So there is nearly nothing left to be pruned here.

Reinhard.

Hi Reinhard,

I guess that Bewerte is a recursive function.

I guess that you have in your code somewhere before the code you posted:
int Bewerte(alpha,beta, tiefe)

In that case you tested only null move with R=1 or R=2

I use usually R=3 and it means in your case that I use tiefe-4 if I understand you correctly.

R is the number of plies of reductions relative to other moves.
After other moves I use tiefe-1 so if I want R=3 then I need after null move to use tiefe-4

Uri

Hi Reinhard,
aside from relatively small differences one thing that I see different from my implementation is a (missing) check to avoid consecutive null moves, which if performed will behave very badly... maybe it's performed by GetPlySchach() although from the sound of it I'm guessing that's the "side not in check" stuff...

same for me

I also do not allow 2 null moves in a row
More conditions are also not allowing null move pruning when the opponent has a small number of legal moves because there may be zugzwang and not allowing null move pruning in pawn endgames.

Uri

Hi Alessandro and Uri,

Alessandro: check to avoid consecutive null moves

a) because of that chapter is nearly pruning nothing, that estimations might be obsolete that moment for Smirf;
b) theoretically this limitation sounds necessary, but as I have thought it over there are only very microscopical chances that both sides would be such weak that consecutivly pruning could do any harm. But of course other programmers might be much more experienced with that matter than me.

Uri: In that case you tested only null move with R=1 or R=2

that is correct. But I already have had problems to accept the idea of R=2 (which seems to be right, looking at the decreased quality of answer moves). Thus I have not tried R=3 (and for other reasons, e.g. it would cause conflicts with my quiescence search).

Reinhard.

Hi Reinhard,

I don't think you have to avoid doing two nullmoves in a row.
I get better results allowing that, and by induction, if it works a ply N it
should also work at ply N-R.

Instead I think Uri is right, your reduction factor is simply too small.
Try at least R=2 and R=3 and even R=4 should be experimented with, at R=1, which you seem to be using, the nullmove tree gets too big.
Using a large R is what makes nullmove cheap and therefore worth while, but the larger the R the more risk there is. I think the optimal setting is hard to find without experimentation.

Nullmove will in some cases delay tactics for a few plies, but even in those cases it is often matched by the increased search depth.
Checks in qsearch can help to undo some of this blindness.
Zugzwangs are not so easy to detect, unfortunately. At least not without losing some strength in other areas.

BTW, are you going to play at CCT7?

-S.

Hi Sune,

Try at least R=2 and R=3 and even R=4

well, I will check that out, but I think it will do not change much on the missing pruning effect. Overmore it conflicts with my personal pruning philosopy. Without to unhide yet too much from Smirf's genuine method I can tell you, that the resulting cuts would be comparable to R=1 prunings. Zugzwang situations obviously seems not to be influencing negative that method.

BTW, are you going to play at CCT7?

Whatever a tournament this would be, actually I am more focussed in improving Smirf than in participating tournaments. That is caused by following circumstances:
a) Smirf's 8x8 and 10x8 variants ideas still are unsupported by Winboard and UCI, so what to do as Smirf has no own opening libraries;
b) Smirf's strength actually is only small below The Baron 1.40 in Chess960;
c) Smirf's evaluation routine has to be rewritten without changing its idea, because the first ad hoc realisation is still very slow and could be enhanced by an estimated factor of three and above.

Reinhard.

Sune Fischer wrote:Hi Reinhard,

I don't think you have to avoid doing two nullmoves in a row.
I get better results allowing that, and by induction, if it works a ply N it
should also work at ply N-R.

2 null moves in a row cause repetition of a previous position and it seems not logical to analyze position that you already visited again.

I know that internal iterative deepening is about doing it but if you want to use internal iterative deepening you can do it without allowing 2 null moves in a row.

Uri

Hi Uri,

only one thing could be true: a) Nullmove prunings always would leave the search tree in a good shape, b) special constellations (e.g. two Nullmoves following each other) could do harm to that idea. This moment I regard Nullmove prunings somehow to be dangerous.

Additionally to come back to that problem: within a tree evaluation I always evaluate position repetitions as zero (but not writing them back into the cache).

Reinhard.

Hi Reinhard,same for me but if I allow 2 null move in a row I am not going to detect the repetition.

The problem is that I may look only 4 plies backward or more than it to detect repetition because I know that repetition cannot happen after 2 plies.


Here is part of the source code that I have to deal with repetition problems in functions that detect also other draws(fiftyvalue is defined to be 100).

I have seperate function to decide if the game finished(only 3 ply repetition is a draw) and this is the reason that this function can return different value based on the ply of the repetition but I think now that it is probably useless and it is better if I have a seperate function for 3 ply repetition and do this function faster by telling it to give me only 1 in case of draw and 0 in case of not draw.



if (fifty<=3)
return 0;
if (fifty>=fiftyvalue)
return 1;

backward=4;
while ((backward<=fifty)&&(zobkey[hply-backward]!=zobkey[hply]))
backward+=2;
if (backward<=fifty)
return hply-backward+1;
else return 0;

Hi Uri,

The problem is that I may look only 4 plies backward or more than it to detect repetition because I know that repetition cannot happen after 2 plies.

that seems to be a very bad technic. I am not looking back along the game line. After deciding to expand a node, it will be locked within its cache entry and unlocked when done. If I will have to decide, whether a node has to be expanded, I will see when it might be locked already. That is the moment to answer with a zero evaluation.

(Oh bad, again I have given away another secret of mine ...)

Concerning Nullmove repetition: it would be very unlikely that for both sides it would be best to include a zero evaluation into the PV.

Reinhard.

Reinhard Scharnagl wrote:I am not looking back along the game line. After deciding to expand a node, it will be locked within its cache entry and unlocked when done. If I will have to decide, whether a node has to be expanded, I will see when it might be locked already. That is the moment to answer with a zero evaluation.

Hi Reinhard. If I understand correctly, you use the hash table to detect repetitions. I know some people do it that way, but some of us tried and rejected the idea. I rejected it because of hash collisions. But maybe you have a secret technique to deal with hash collisions...