Transposition table based pruning idea

[jd1]

Hi all,

Merry Christmas!

I was wondering if anyone has tried a scheme like the following in a fail-soft environment:

If:
- trans_depth == depth -1, not in pv, and trans_score is far below alpha or far above beta (with the correct bound of course), then return trans_value instead of searching the position.

While this seems fairly sound as long as the margin is large enough, that by itself is obviously not sufficient as it would simply cause the engine to skip alternate depths when searching these lines which are far from the alpha/beta window.

So, to avoid this problem, if trans_depth == depth -2 (i.e. the next ply):
- we search the position at depth-1 while deactivating the tt-based pruning
- if the result of the search is unexpected (i.e. cut node doesn't cut or all node produces a beta cutoff), then we note the best move from the depth-1 search for move ordering and then search to full depth. Otherwise, we return the depth-1 score.

This way we also avoid searching the full depth unless absolutely necessary.

I'm getting a promising +8 elo in self-play after 6000 games (more games needed of course), so I was wondering if anyone has tried something like this? Or are there any potential problems?

Psuedo-code:

Code: Select all

if (SearchCurrent[ThreadId]->trans_pruning){ // this is a flag to enable/disable the pruning scheme
    if (trans_depth+1 == depth){

	trans_value = value_from_trans(trans_value,height);			

	if (&#40;TRANS_IS_LOWER&#40;trans_flags&#41; && trans_value >= beta + margin&#41; || &#40;TRANS_IS_UPPER&#40;trans_flags&#41; && trans_value <= alpha - margin&#41;) 
		return trans_value;
   &#125; else if &#40;trans_depth+2 == depth&#41;&#123;

	trans_value = value_from_trans&#40;trans_value,height&#41;;
                     
         // if last time we returned early from trans &#40;HACK&#58; alpha & beta may have changed&#41;
	if (&#40;TRANS_IS_LOWER&#40;trans_flags&#41; && trans_value >= beta + margin&#41; || &#40;TRANS_IS_UPPER&#40;trans_flags&#41; && trans_value <= alpha - margin&#41;) &#123; // 
							
		// we do a new search at depth-1
		SearchCurrent&#91;ThreadId&#93;->trans_pruning = false;
		value = full_search&#40;board,alpha,beta,depth-1,height,new_pv,node_type,false,ThreadId&#41;; 
		SearchCurrent&#91;ThreadId&#93;->trans_pruning = true;
				                    
		// if the search returns the expected value / cutoff, we return its value. if not, go on to full depth search
		if &#40;node_type == NodeCut && value >= beta&#41;
		    return value;
		if &#40;node_type == NodeAll && value <= alpha&#41;
		    return value; 
				       					
		// use info from previous depth-1 search	
		trans_move = new_pv&#91;0&#93;;
	  &#125; 
   &#125;
&#125;

[jd1]

Sorry, the code formatting seems to be broken ... but hope it's still understandable. Thanks!

[mjlef]

I have tried this idea in my old program NOW (and a bit in Komodo), but by itself, never found it gaining elo. But NOW did use the hash entry to "correct" the static eval (lower bounds pushing the score up and upper bounds pushing it down, depending on the score). So this does help out static null pruning by giving it a more accurate score, since the score is based on a search and not just the static eval. If you are not already doing that, you might give it a try.

[jd1]

I have tried this idea in my old program NOW (and a bit in Komodo), but by itself, never found it gaining elo. But NOW did use the hash entry to "correct" the static eval (lower bounds pushing the score up and upper bounds pushing it down, depending on the score). So this does help out static null pruning by giving it a more accurate score, since the score is based on a search and not just the static eval. If you are not already doing that, you might give it a try.

Hi Mark,

Thanks a lot for the reply and suggestions.

The idea in the OP is definitely worth elo in Toga II, one can easily verify by turning off the option ("Hash Pruning") and testing. I ended up with +7 elo after 16000 games. But it's probably one of those things that only works for some engines.

I'm testing your suggestion right now, in theory it should definitely work - it was a bit of an oversight not to do it ... but we'll see whether it actually works in terms of Elo or not

Best,
Jerry

[AndrewGrant]

I've just started about a dozen or so tests for variants of this idea.

I do not track all/cut at the moment, so half the tests have that added. The other half use the ttBound as the all/cut. Ill note that proper tracking of cut/all reduces my node counts more so than using the ttBound as all/cut. I suspect ttbound as all/cut is unfounded.

Testing margins of [16, 32, 64, 128, 256] (Pawn is ~84 in Ethereal).


What kinds of margins and other changes have tested, if any?

Was grabbing to new 'ttMove' from the PV something you tested, or something you added because it makes sense, quite frankly. I ask because perhaps this serves as a form of better IID in your / my case.

Should have some results in the evening.

[jd1]

I've just started about a dozen or so tests for variants of this idea.

I do not track all/cut at the moment, so half the tests have that added. The other half use the ttBound as the all/cut. Ill note that proper tracking of cut/all reduces my node counts more so than using the ttBound as all/cut. I suspect ttbound as all/cut is unfounded.

Testing margins of [16, 32, 64, 128, 256] (Pawn is ~84 in Ethereal).


What kinds of margins and other changes have tested, if any?

Was grabbing to new 'ttMove' from the PV something you tested, or something you added because it makes sense, quite frankly. I ask because perhaps this serves as a form of better IID in your / my case.

Should have some results in the evening.

I tried margins of [25, 50, 75, 100, 150, 200] and 100 tested the best (pawn is about 80 in Toga II). I did not spend a lot of time tuning the margin though.

I use the ttMove from the new pv because it makes sense, but I did also test without it -> no Elo gain at all.

In terms of other tests, I tried (all failed, although 2 & 3 were very close):
1) Pruning at trans_depth == depth-2 with a higher margin.
2) Also using exact TT entries for pruning. In theory this ought to work but I couldn't make it gain Elo.
3) Simply returning the value of the depth-1 search instead of going on to a full depth search.
4) BTW I have also tried this idea in Fruit reloaded but I couldn't get it to work there.

[AndrewGrant]

I use the ttMove from the new pv because it makes sense, but I did also test without it -> no Elo gain at all.

Are you saying that removing this made the patch as a whole non elo gaining. Or are you saying that by your idea with the ttMove is just as good as your idea without the ttMove?

If it is the first, I'de say this is a form of IID that gains elo. If it is the second,I'll keep trying.

All my runs failed, best was -3 ELO on an SPRT test. I'm going to try without the exact bounds now.

[jd1]

I use the ttMove from the new pv because it makes sense, but I did also test without it -> no Elo gain at all.

Are you saying that removing this made the patch as a whole non elo gaining. Or are you saying that by your idea with the ttMove is just as good as your idea without the ttMove?

If it is the first, I'de say this is a form of IID that gains elo. If it is the second,I'll keep trying.

All my runs failed, best was -3 ELO on an SPRT test. I'm going to try without the exact bounds now.

Hi Andrew, sorry for the confusion -> without the using the ttMove from the new pv the patch as a whole did not gain Elo.

So yes, you have a good point that this may actually be a form of IID.

I also note that in general Ethereal returns the conservative value when pruning, e.g. static null / null move returns beta on a cutoff, razoring returns alpha if depth > 1, etc., whereas Toga II (and Stockfish) will return the value from the null move search as long as it's not a mate, and return the value of the quiescent search in razoring, etc. This becomes more important when tt based pruning is used, and my gut feeling is that this may be why the idea won't work in Ethereal.

[AndrewGrant]

Ill give the 'accurate' scores from early pruning a try.

Up until 48 hours ago, I did what you and what SF did -- return the true value by Null/Prob/ect. Found 7-8 elo by not doing it.

https://github.com/AndyGrant/Ethereal/c ... feead273c5

[jd1]

Ill give the 'accurate' scores from early pruning a try.

Up until 48 hours ago, I did what you and what SF did -- return the true value by Null/Prob/ect. Found 7-8 elo by not doing it.

https://github.com/AndyGrant/Ethereal/c ... feead273c5

That's a very interesting (and convincing) test result, thanks. I'm going to try doing what you do.

I personally doubt the idea in the original post, even if it works with 'accurate' values in Ethereal, would be worth as much as that.