question about SEE

[asanjuan]

This is my first post in this forum, so dont' be cruel with me...
I have a -maybe quite simple- doubt about SEE.
I have always refused to implement a SEE routine. (you can say i'm lazy)
In my engine, I use some kind of SEE at "one-level", only recognizing if a move is a good capture or not. This is the pseudo-code:

Code: Select all

if captured_piece is undefended then return TRUE  
else if  val&#40;attacking_piece&#41; < val&#40;piece_captured&#41; then return TRUE 
else //houston, we have a problem 
if val&#40;attacking_piece&#41; > val&#40;piece_captured&#41; 
   && val&#40;attacking_piece&#41;  <= 
   val&#40;piece_captured&#41; + val&#40;minimum_defender&#41; then return true //because i want to search on this move

else return False 

and depending of what is returning this function i update the "expected" material gain or loss for that move (from a table with MVV-LVA values). At the end i look for the moves with an expected material win >0.
I also use this routine for move ordering in the main search.
This is working very well in my tests, but I see some kind of node explosion when searching at depths over 10 and so on.

I believe that changing my simple routine to a more sophisticated SEE could improve this node explosion, but i'm not sure. So here is my question:
¿has anybody proven that SEE _WILL FOR SURE_ reduce the amount of nodes visited?

[tpetzke]

I have no mathematical proof. Just experienced that the more accurate you are in your decisions the lesser nodes you search. But usually getting more accurate slows you down (nps drops) so it is a trade off.

You should include capture moves with a material gain of 0 in your QS and make sure you use that standing_pat correctly. Most QS searches should not go very deep.

Thomas...

[hgm]

Looks pretty much like what I do. Except that moves of the final catagory, although they are searched, are postponed until after captures that are obviously good or equal.

Note that whether you will havea search explosion or not does not so much depend on which moves you search, but on the order you search them. Sorting in MVV order remains crucial.

[Sven]

Hi Alberto,

your pseudo code looks ok for me, apart from the comment by Thomas that equal captures are not covered yet. But that last part would not be a plausible explanation for a "search explosion" since in qsearch you would even skip more moves (the effect in main search being not clear for me without knowing more about your move ordering in general).

You have mentioned that you use your SEE function also for move ordering in main search. That might be part of the problem, depending on your possible other move ordering criteria (MVV-LVA would be preferred IMO).

To isolate the real source of the problem I would test which of these four variants causes search explosions and which does not:

a) main search + qsearch with SEE (your current state)
b) only main search with SEE (i.e. no skipping of bad captures)
c) only qsearch with SEE
d) no SEE (supposedly your previous state)

Maybe you get a hint that way.

EDIT: to answer your last question, using SEE to skip bad captures in qsearch almost certainly reduces the tree size, but in case of using SEE for ordering in main search the answer is clearly "it depends".

Sven

[mike_bike_kite]

¿has anybody proven that SEE _WILL FOR SURE_ reduce the amount of nodes visited?

I'm very new on the forum and very new to chess programming but I get the following figures with my little engine:

Code: Select all

Type    #Nodes    Time  Nps   Score
min       3724k   92.0  40k   104
ab         135k    3.5  39k   104
see         17k    0.5  33k   104

The minmax search on level depth 4 had to seach 3.7m nodes. Using alpha beta reduced this to 135k. Ordering all the moves on each level reduced this again to 17k. The end score and suggested move for each method is the same in each case but the time to do each search was dramatically different. Your program is dramatically faster than mine but the gain should be similar.

I'll repeat that I'm a bit new to all this so I might be making mistakes.

[hgm]

Just to make sure how your numbers relate to the original question: when you get the 135k nodes for alpha-beta, is that completely without sorting of any kind? Most people that do not use SEE would still use MVV/LVA sorting. And they might even go beyond that, and use refinements to MVV/LVA for the HxL captures like the one mentioned here. So the question was really how much a full-blown SEE would help you beyond very advanced (but non-SEE) sorting.

[mike_bike_kite]

Min max and alpha beta were without any sorting. Sorting is used at every level in the last run. The sorting I use is by defender and attacker values, whether the square is defended by a pawn and whether the square is near the centre.

[asanjuan]

Thanks for your comments.
I didn't realized that there were so many contributors, and that you can answer so fast!
I'll try with the condition material_gain >=0, implement a SEE routine and also revising move ordering.
This can take me some days, but I promise to keep you updated.
Thankyou again.

[asanjuan]

I promised to keep you updated, so here it is:
SEE was not the problem. My experiments showed that using SEE is better than MVV/LVA in quiescence, having the same results, but lesser nodes.
I solved my problem with node explosion changing a simple "return beta". In my zero-window search i was returning "max_value", and this was the cause for non necessary re-searches in the principal variation. When i changed "return max_value" to "return beta", the problem went away.
So the conclusion is:
- in PVS, use fail-hard inside de null-window search.

[hgm]

Sounds more like there is something wrong with your PVS implementation. Whether you return beta or a value that is much higher, in the caller this will both be a fail low (alpha or much lower). And a fail low should never trigger a re-search.