Nullmove vs classic selective search

[Rebel]

The last months I have been working on my old "static selective search" system, found improvements (tuning basically) and now it outperforms (full) nullmove so convincingly (61%) I would like to bring it under your attention. I think that for those who like a REAL challenge there must be some good elo improvement as a reward for perseverance.

In short, the search is split into 2 parts

1. Nullmove part
2. Static selective search part.

Typically a 10 ply search (for the middle game) is split into 3 plies nullmove and 7 plies selective search, a 12 ply search 4 plies nullmove and 8 plies selective search, etc. The system is now fully parameter driven for easy tuning. Setting all the values to its maximum will result in a normal modern nullmove searcher.

The nullmove part is used to as a safety net to catch the most important failures of the selective search. Static selective search is risky business but it can be done, I think that especially Richard Lang has proven that by 10 (or so) consecutive world titles.

The static selective search decides either to search the current node at full depth, make a reduction or even prune merciless. The system works independently of futility pruning and LMR, they happily coexist.

I already described the inner workings in 2004 and although much of the stuff has been changed the basic principles still stand as a rock and are explained, I just don't know if I have explained it well enough.

Take a deep breath first.

http://www.top-5000.nl/authors/rebel/ch ... #SELECTIVE SEARCH

[diep]

The last months I have been working on my old "static selective search" system, found improvements (tuning basically) and now it outperforms (full) nullmove so convincingly (61%) I would like to bring it under your attention. I think that for those who like a REAL challenge there must be some good elo improvement as a reward for perseverance.

In short, the search is split into 2 parts

1. Nullmove part
2. Static selective search part.

Typically a 10 ply search (for the middle game) is split into 3 plies nullmove and 7 plies selective search, a 12 ply search 4 plies nullmove and 8 plies selective search, etc. The system is now fully parameter driven for easy tuning. Setting all the values to its maximum will result in a normal modern nullmove searcher.

The nullmove part is used to as a safety net to catch the most important failures of the selective search. Static selective search is risky business but it can be done, I think that especially Richard Lang has proven that by 10 (or so) consecutive world titles.

The static selective search decides either to search the current node at full depth, make a reduction or even prune merciless. The system works independently of futility pruning and LMR, they happily coexist.

I already described the inner workings in 2004 and although much of the stuff has been changed the basic principles still stand as a rock and are explained, I just don't know if I have explained it well enough.

Take a deep breath first.

http://www.top-5000.nl/authors/rebel/ch ... #SELECTIVE SEARCH

You said you described the inner workings in 2004, yet i disagree with you.

What you emailed me some 7 years before that, around 1997, then you sure had the tables described and algorithm, yet that algorithm was not in 2004 at your homepage. The excuse was that Tiger was using it if i remember.

You do however an excellent attempt now to describe it at your current homepage. My compliments for that!

Scoring 61% with an improved version is very good of course Ed. What i wonder about is which search depths you reach with it now and which selective search depths you use for that in Rebels SEE part.

Basically your concept is to search deeper lines that you predict with whatever method *somewhere* in the tree, to extend inside the s_depth.

At depth 14, you basically search 6 plies nominal and forward prune the remaining 8 ply depthleft.

From 15 ply and onwards the s_depth increases 1 ply each iteration, so your search methods branching factor starts losing it from LMR + nullmove + forward pruning from then on.

We can mathematically prove this quite easily, as basically each added iteration depth is a full ply addition to your s_depth and the selective depth no longer grows.

A much better table from mathematical viewpoint is when the s_depth is exactly 50% from i_depth.

So that means:

{ 0,1,1,2,2,3,3,4,4,5,5 ... }

A problem with the table you use now is that if you're at say 25 ply search depth, not an uncommon depth nowadays, that basically the first 17 plies a few single extensions or captures will extend the full 8 plies selective.

Odds for this is quite high, so basically your selective concept starts malfunctioning above 15 plies.

So your system cannot function in modern chessprograms that want to reach the top.

In Blitz and bullet i'm sure it can do ok SINGLE CORE, maybe at an iphone or something.

We still skipped the problem of the hashtable so far, yet that's irrelevant if a the table you give cannot work for todays search depths.

Let's not forget however that your system prunes far more than nullmove and todays forward pruning concepts the first few plies of search. A big achievement back then.

The aggregated extension of s_depth throughout the entire s_depth however voids the advantages for todays search.

Vincent

[Rebel]

Odds for this is quite high, so basically your selective concept starts malfunctioning above 15 plies.

Realize (as already said) a lot of things changed, its frame still stands.

These tables were recently replaced with a more intelligent approach via a new parameter, to be released next week.

[nullmove MIDG = 35]
[nullmove END0 = 40]
[nullmove END1 = 50]
[nullmove END2 = 60]

So at depth 15 it will use (15*35)/100=5 plies nullmove instead of 7, at D=16 and D=17 still 5 plies instead of 8 and 9. But you are right, what worked back then (2003 was my last and still top-5) isn't good today, see its current place at the rating lists

So your system cannot function in modern chessprograms that want to reach the top.

Are you kidding? I have no intention. CC is just a nice time passing for the time being and as long as it lasts. To be competitive again I first must convert my 32-bit ASM back to C in order to profit from 64 bit, rewrite mailbox to bit-board. I am 62, no thank you.

The aggregated extension of s_depth throughout the entire s_depth however voids the advantages for todays search.

Don't be too harsh. There is 20 years of work in the system. And I would not post if there was not such an extreme difference between full nullmove vs the static selective search.

[diep]

Odds for this is quite high, so basically your selective concept starts malfunctioning above 15 plies.

Realize (as already said) a lot of things changed, its frame still stands.

These tables were recently replaced with a more intelligent approach via a new parameter, to be released next week.

[nullmove MIDG = 35]
[nullmove END0 = 40]
[nullmove END1 = 50]
[nullmove END2 = 60]

So at depth 15 it will use (15*35)/100=5 plies nullmove instead of 7, at D=16 and D=17 still 5 plies instead of 8 and 9. But you are right, what worked back then (2003 was my last and still top-5) isn't good today, see its current place at the rating lists

So your system cannot function in modern chessprograms that want to reach the top.

Are you kidding? I have no intention. CC is just a nice time passing for the time being and as long as it lasts. To be competitive again I first must convert my 32-bit ASM back to C in order to profit from 64 bit, rewrite mailbox to bit-board. I am 62, no thank you.

The aggregated extension of s_depth throughout the entire s_depth however voids the advantages for todays search.

Don't be too harsh. There is 20 years of work in the system. And I would not post if there was not such an extreme difference between full nullmove vs the static selective search.

See it positive. It was a great invention for when you needed it.
That's what i wrote.

That's how you were succesful.

If you were active now, you'd invent another thing. See it like this

As for todays search depths, you posted the algorithm 8 years too late i'd say.

Maybe it's interesting to some traders though. They need huge pruning.
To avoid bugs like Knight Capital had wasting 440 million dollar

Maybe a monte carlo random search bug that didn't detect the error
Note i wouldn't be surprised if some civil servant over here had trusted them with big cash from the 800 billion euro cash the pension funds here have

They would not invest a penny in a small company in Netherlands, yet they throw with billions in USA as if it is paper money.

In that sense you can truely say you invented a tactical framework you needed when you needed it.

Computerchess nowadays is more about positional search depth.

Your framework doesn't search positional very deep if you would mathematically fix it for todays search depths.

Basically you'd search deeper the mainline and tactical shots.

The advantage of todays systems where hashtable works so well for (and cannot be missed) is they also search positional deeper.

I don't think assembler has become slower. It still is very fast to do things in 32 bits assembler. 64 bits is slower effectively than 32 bits at modern processors. Just the dudes over here had good examples how to do it in 64 bits - they have no clue how to be fast in 8 + 32 bits, and the cut'n paste average programmers that computerchess sees too much today, they just know how to cut'n paste... ...being creative is not the thing they excel at, in contradiction to what you did do back then.

Even then i feel the real victory of rebel was its evaluation function, not so much the spaghetticoding for search.

That said your algorithm to use 2 search depths and use the entire fullwidth search to extend tactical lines (and mainline i assume) up to the depth limited i-depth, that's a real algorithm that will not be forgotten and which was a winner algorithm when you needed it.

You shouldn't spoil all that though by lying about when you publicly posted it. You didn't post it in 2004. You posted it later obviously

In 2004 you posted the s_depth table basically.

As for modern search depths - it's not clear to me which search depth a much improved diep version needs to knock all the fruit/rybka clones from the board.

That's a very interesting question.

I do need a search though that can scale parallel as well. To have thing sscale parallel your hashtable has to function real well and the search frame work has to have a good branching factor. Also it has to search me positional deeper, not just tactical.

If we would modify your s_depth table to something like:

[0,1,1,1,2,2,3,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15... etc]

Then one would still be able to prune more than with nullmove and reductoins type LMR.

The problem is that your sdepth basically is the positional depth of the program and extensions of the s_depth can extend this depth.

The positional depth of what you call nullmoving programs, is over double that of the above s_depth table.

Of course tactical you'd kick butt.

Yet only single core of course and with malfunctioning hashtable.

So it has a few very fundamental flaws. Yet this was a big advantage back then of course, when tactics really mattered...

In an experiment i did do with your search frame work, it was tactical +500 elo or something, easilly seeing tactics 3 ply deeper for Diep than the nullmoving version of Diep. That's ancient times though...

Let's keep it like that.

[lucasart]

The last months I have been working on my old "static selective search" system, found improvements (tuning basically) and now it outperforms (full) nullmove so convincingly (61%) I would like to bring it under your attention. I think that for those who like a REAL challenge there must be some good elo improvement as a reward for perseverance.

In short, the search is split into 2 parts

1. Nullmove part
2. Static selective search part.

Typically a 10 ply search (for the middle game) is split into 3 plies nullmove and 7 plies selective search, a 12 ply search 4 plies nullmove and 8 plies selective search, etc. The system is now fully parameter driven for easy tuning. Setting all the values to its maximum will result in a normal modern nullmove searcher.

The nullmove part is used to as a safety net to catch the most important failures of the selective search. Static selective search is risky business but it can be done, I think that especially Richard Lang has proven that by 10 (or so) consecutive world titles.

The static selective search decides either to search the current node at full depth, make a reduction or even prune merciless. The system works independently of futility pruning and LMR, they happily coexist.

I already described the inner workings in 2004 and although much of the stuff has been changed the basic principles still stand as a rock and are explained, I just don't know if I have explained it well enough.

Take a deep breath first.

http://www.top-5000.nl/authors/rebel/ch ... #SELECTIVE SEARCH

So if I understand correctly, you do
(1) null move if depth <= threshold
(2) static pruning is depth > threshold
I am very skeptical about (2). What kind of null move implementation score 39% against this ? There are many subtile ways of doing null move, and many ways of getting it wrong. Maybe your null move benchmark that got beaten 61% wasn't quite right. How do you do null move: what preconditions ? what reduction ?

[ZirconiumX]

Ed's implementation of Nullmove is what he calls 'Static Nullmove Reductions'

From what I can work out he does his nullmove (at every move in the search) and if it fails high, he reduces. What depth he reduces I cannot remember. And since this is done at every move in the search, all that is left is tactically, and positionally good moves.

However, this ruins his TT because the search hasn't looked at all the moves, and may have missed something.

ProDeo is easily more selective than Houdini, it is just his move generator is slow. It is a 32 bit mailbox, not the 64 bit bitboards you are used to. But if PD ever got bitboards, then you are dust, Lucas.

Matthew:out

[Richard Allbert]

Have you read the link Ed provided, before posting that?

I understand it as follows: First x ply do null move as normal, as in most other programs. Avoid if alpha < score + margin. Also similar to other programs.

Remaining ply implement Selective Search according to the rules outlined.

What you do need is evaluation every node, and a lot of info from it - hanging pieces, king threats etc, and these clearly need to be accurately defined.

Code: Select all

  if (own_king_was_in_check_before_make_move) return TRUE; // search node with full depth
  if (move_does_check_the_opponent_king) return TRUE;      // search node with full depth
  if (move_is_winning_capture) return TRUE;                // search node with full depth
  if &#40;ALPHA < SCORE + THREAT + MARGIN&#41; return TRUE;        // search node with full depth
  if &#40;white_pawn_moves_to_rank6_or_7&#41; return TRUE;         // search node with full depth
  if &#40;black_pawn_moves_to_rank3_or_2&#41; return TRUE;         // search node with full depth
  if &#40;move_threatens_opponent_king&#41; return TRUE;           // search node with full depth
  else&#58; return FALSE;                                      // prune complete subtree

As for Bitboard being such a speed up on 64bit processor.... for me it made no difference vs mailbox on an i3.

Someone who knows more than I do recently wrote to me that it's processor dependent also, and not simply "BB is faster on 64bit".

[Uri Blass]

Ed's implementation of Nullmove is what he calls 'Static Nullmove Reductions'

From what I can work out he does his nullmove (at every move in the search) and if it fails high, he reduces. What depth he reduces I cannot remember. And since this is done at every move in the search, all that is left is tactically, and positionally good moves.

However, this ruins his TT because the search hasn't looked at all the moves, and may have missed something.

ProDeo is easily more selective than Houdini, it is just his move generator is slow. It is a 32 bit mailbox, not the 64 bit bitboards you are used to. But if PD ever got bitboards, then you are dust, Lucas.

Matthew:out

I am sure that the difference between prodeo and houdini is not only speed.

Prodeo maybe can be twice faster by better code but not 10 times faster and being twice faster certainly does not give more than 100 elo.

I do not see prodeo as 100 elo weaker than houdini in the rating list
and it is clearly more than 200 elo weaker than houdini.

[ZirconiumX]

Have you read the link Ed provided, before posting that?

Yup. I seem to remember the term from a thread somewhere - I cannot find it based on a quick search.

I understand it as follows: First x ply do null move as normal, as in most other programs. Avoid if alpha < score + margin. Also similar to other programs.

I understand it to be: he does Selective Search, but uses a nullmove value to confirm it.

Remaining ply implement Selective Search according to the rules outlined.

Yes.

What you do need is evaluation every node, and a lot of info from it - hanging pieces, king threats etc, and these clearly need to be accurately defined.

Oh ProDeo easily has all that.

Code: Select all

  if (own_king_was_in_check_before_make_move) return TRUE; // search node with full depth
  if (move_does_check_the_opponent_king) return TRUE;      // search node with full depth
  if (move_is_winning_capture) return TRUE;                // search node with full depth
  if &#40;ALPHA < SCORE + THREAT + MARGIN&#41; return TRUE;        // search node with full depth
  if &#40;white_pawn_moves_to_rank6_or_7&#41; return TRUE;         // search node with full depth
  if &#40;black_pawn_moves_to_rank3_or_2&#41; return TRUE;         // search node with full depth
  if &#40;move_threatens_opponent_king&#41; return TRUE;           // search node with full depth
  else&#58; return FALSE;                                      // prune complete subtree

As for Bitboard being such a speed up on 64bit processor.... for me it made no difference vs mailbox on an i3.

For me, bitboard is a huge improvement on a 32bit big-endian PPC machine.

Someone who knows more than I do recently wrote to me that it's processor dependent also, and not simply "BB is faster on 64bit".

Yes - I'd agree with that

Matthew:out

[ZirconiumX]

Ed's implementation of Nullmove is what he calls 'Static Nullmove Reductions'

From what I can work out he does his nullmove (at every move in the search) and if it fails high, he reduces. What depth he reduces I cannot remember. And since this is done at every move in the search, all that is left is tactically, and positionally good moves.

However, this ruins his TT because the search hasn't looked at all the moves, and may have missed something.

ProDeo is easily more selective than Houdini, it is just his move generator is slow. It is a 32 bit mailbox, not the 64 bit bitboards you are used to. But if PD ever got bitboards, then you are dust, Lucas.

Matthew:out

I am sure that the difference between prodeo and houdini is not only speed.

Prodeo maybe can be twice faster by better code but not 10 times faster and being twice faster certainly does not give more than 100 elo.

I do not see prodeo as 100 elo weaker than houdini in the rating list
and it is clearly more than 200 elo weaker than houdini.

Uri, I was on about selectivity, not speed. ProDeo will never be hugely fast due to doing a full evaluation every node, but tactically, a selective searcher is hard to beat.

Matthew:out