Search with bitbase

[Daniel Shawul]

I have spent quite some time with how to make progress with bitbases alone. Here is a summary. For further info, look into scorpio source code.

a) First you have to convet the WDL score into something that differentiates b/n won positions. I do this in egbbprobe.dll. Eg. 4 men are a 1000 points better than 5 men, higher material difference is better than lower, passed pawn ranks etc... In short I have a lot of heuristics and these combined with the rest had made it almost a perfect solver without tbs.

b) Integrate PLY into the score. This is like we do it for mates but the ply is multiplied by a factor so say 40 * PLY. So shorter wins are preferred.

c) Do not probe bitbases within the first 2/3 * search_depth. Without this you will not be able to make progress when the position is already a 5 men. This applies whether in normal or qsearch.

d) Captures , promotions and pawn moves (those that zero 50-move counter) allow probing anywhere even in the 2/3 zone. We are definately making progress here.

e) ... Not necessary for making progress, but I also filter root moves based on bitbase score to make move rapidly when there is one move left.

Maybe some others that I forget. Anyway here is the code for probing bitbases in scorpio. The code for scoring the position is too long so I recommend you look in egbbprobe.cpp if you are interested

Code: Select all

bool SEARCHER::bitbase_cutoff() {

#ifdef EGBB
	/*
	. Cutoff tree only if we think "progress" is being made
	. after captures
	. after pawn moves
	. or just after a certain ply (probe_depth) 
	*/
	if( egbb_is_loaded
		&& all_man_c <= 5
		&& &#40;ply >= probe_depth
		|| is_cap_prom&#40;&#40;pstack - 1&#41;->current_move&#41;
		|| PIECE&#40;m_piece&#40;&#40;pstack - 1&#41;->current_move&#41;) == pawn
		)
		) &#123;
			/*
			Probe bitbases at leafs ,only if they are loaded in RAM
			*/
			register int score;
			if&#40;&#40;ply <= probe_depth 
				|| &#40;egbb_load_type >= 1 && all_man_c <= 4&#41;
				|| egbb_load_type == 3&#41;
				&& probe_bitbases&#40;score&#41;
				) &#123;

					egbb_probes++;

					/*prefer wins near root*/
					if&#40;score > 0&#41;
						score -= WIN_PLY * &#40;ply + 1&#41;;
					else if&#40;score < 0&#41;
						score += WIN_PLY * &#40;ply + 1&#41;;

					pstack->best_score = score;

					return true;
			&#125;
	&#125;
#endif
	/*
	. no cutoff
	*/
	return false;
&#125;

[zamar]

E.g. KBNK is always won if there is no shallow tactical loss of one of your pieces (bare K forking B & N).

This is not entirely correct (or at least it's not easy to detect when there is a tactical loss). It took me many hours to test & write correct rules for KBNK endgame. Just one example of a tricky special case:

[D]8/K7/8/8/8/4k2B/6N1/8 b - - 0 1

[phhnguyen]

Thank you for your reply.

I have spent quite some time with how to make progress with bitbases alone. Here is a summary. For further info, look into scorpio source code.

I have known Scorpio and its bitbase for long time (I have read almost all posts about bitbases on this forum, including Scorpio). But still delay looking into its code, just to keep my mind fresh. Definitely I will study it later. Thank for publishing it.

a) First you have to convet the WDL score into something that differentiates b/n won positions. I do this in egbbprobe.dll. Eg. 4 men are a 1000 points better than 5 men, higher material difference is better than lower, passed pawn ranks etc...

Very good idea and details. Just hope that mine will be simpler because for first try, I will keep all 4 men as normal (full DTM values - not bitbase) so my search can stop right at 4 men and I can delay implementing a such complicated score system.

In short I have a lot of heuristics and these combined with the rest had made it almost a perfect solver without tbs.

Amazing, do you mean you don't need any endgame file at all?

b) Integrate PLY into the score. This is like we do it for mates but the ply is multiplied by a factor so say 40 * PLY. So shorter wins are preferred.

Good point!

c) Do not probe bitbases within the first 2/3 * search_depth. Without this you will not be able to make progress when the position is already a 5 men. This applies whether in normal or qsearch.

Very helpful idea. My first attempts of searching have just crashed because of too many probes.

d) Captures , promotions and pawn moves (those that zero 50-move counter) allow probing anywhere even in the 2/3 zone. We are definately making progress here.

e) ... Not necessary for making progress, but I also filter root moves based on bitbase score to make move rapidly when there is one move left.

Not very clear at this point. Do you mean you will make that move if it is the best?

How about if at root, you have some winning moves, some draws, and some losses? Probe and search only few winning moves still save a lot of time, right?

Maybe some others that I forget. Anyway here is the code for probing bitbases in scorpio. The code for scoring the position is too long so I recommend you look in egbbprobe.cpp if you are interested

Code: Select all

bool SEARCHER::bitbase_cutoff() {

#ifdef EGBB
	/*
	. Cutoff tree only if we think "progress" is being made
	. after captures
	. after pawn moves
	. or just after a certain ply (probe_depth) 
	*/
	if( egbb_is_loaded
		&& all_man_c <= 5
		&& &#40;ply >= probe_depth
		|| is_cap_prom&#40;&#40;pstack - 1&#41;->current_move&#41;
		|| PIECE&#40;m_piece&#40;&#40;pstack - 1&#41;->current_move&#41;) == pawn
		)
		) &#123;
			/*
			Probe bitbases at leafs ,only if they are loaded in RAM
			*/
			register int score;
			if&#40;&#40;ply <= probe_depth 
				|| &#40;egbb_load_type >= 1 && all_man_c <= 4&#41;
				|| egbb_load_type == 3&#41;
				&& probe_bitbases&#40;score&#41;
				) &#123;

					egbb_probes++;

					/*prefer wins near root*/
					if&#40;score > 0&#41;
						score -= WIN_PLY * &#40;ply + 1&#41;;
					else if&#40;score < 0&#41;
						score += WIN_PLY * &#40;ply + 1&#41;;

					pstack->best_score = score;

					return true;
			&#125;
	&#125;
#endif
	/*
	. no cutoff
	*/
	return false;
&#125;

Thanks again for your ideas and code!

[phhnguyen]

E.g. KBNK is always won if there is no shallow tactical loss of one of your pieces (bare K forking B & N).

This is not entirely correct (or at least it's not easy to detect when there is a tactical loss). It took me many hours to test & write correct rules for KBNK endgame. Just one example of a tricky special case:

[D]8/K7/8/8/8/4k2B/6N1/8 b - - 0 1

You are right, that is a draw. But I think H.G.Muller means that you can still detect that draw by searching few plies only (shallow).

According to my data, even strong side (KBN) in turn, there still 0.5% of all legal positions (6886 of 1391681) are draw. Over 6 thousand postions (just for 1 of 8 symmetries) white can not win.

[phhnguyen]

I have been on the step of implement normal search for probing bitbase (before that, I use a simple search which mainly looks into endgames for values).

Just have another considering / confuse: implementations of qs and evaluation functions. For the task of retrieving mate scores (full DTM) from bitbase EGTB, normal qs and eval functions seem be useless (because we don't need evaluate any position and qs cannot return not exact values).

Perhaps I will probe at leafs for returning values instead of qs/eval.

Any idea? Thanks.

Re-edit:
Oops, just see the code Daniel Shawul posted above. He probes at leafs. Very clear to me now. Sorry for redundant post

[Daniel Shawul]

Hi,

Amazing, do you mean you don't need any endgame file at all?

You still need the bitbases to tell you if the position is a WDL. Some people try to do it based on rules only but I am not a fan of that.

Very helpful idea. My first attempts of searching have just crashed because of too many probes.

A simple idea that worked for me at first was to never probe bitbases in main search. Just probe them only at leaf nodes (& qsearch). Later I added rules to probe in main search as well when we are obviously making progress.

Not very clear at this point. Do you mean you will make that move if it is the best?

How about if at root, you have some winning moves, some draws, and some losses? Probe and search only few winning moves still save a lot of time, right?

This is not necessary for making progress so it is better to forget about it here. But the idea is similar to 'easy move' used by many engines. If one move is much better than the rest do it immediately. If the position is in 5 men already do a one ply search and check if there is one outstanding move.

I have been on the step of implement normal search for probing bitbase (before that, I use a simple search which mainly looks into endgames for values).

Just have another considering / confuse: implementations of qs and evaluation functions. For the task of retrieving mate scores (full DTM) from bitbase EGTB, normal qs and eval functions seem be useless (because we don't need evaluate any position and qs cannot return not exact values).

Perhaps I will probe at leaves for returning values instead of qs/eval.

Any idea? Thanks.

I probe bitbases in search before any evaluation is done. If it is in bitbases no evaluation is called. The best thing to try right now is to do bitbase probes at _leaf_ nodes only. I am sure that will work fine for making progress.

[phhnguyen]

I am still working on my search function for bitbases but facing a big problem of heavy explosion.

At this moment, my search function is closed to a normal alpha-beta search (it uses hashtable, null move, pv, but there are not qs nor evaluation functions). All necessary endgames (bitbases for 5 men, full DTM for 4 men) are loaded into memory so they can be probed in high frequency. The search function is mainly used for 5 men only and it stops searching immediately at any branch down to 4 men due to full DTM 4 men.

I have tried few things such as probing at leaves only or 2/3 depths, and/or sorting move order by few ways such as hash move - captures - rest; hash move - winnings (based on probes) - draws - losings... but problem is still remaining. For example, for KRNKB, the search can reach easily depths 10-12 in reasonable time, but then too slow to go deeper and I don't think it can reach to depth 50 which needed for that endgame even in hours.

Still working but would like to know if anyone has experiences or any trick, technique?

Thanks for any help.

[kbhearn]

To reach depth 50 with alpha beta you're going to need massive amounts of pruning, an amount that's probably not attainable with just a WDL table for a generally won endgame. Perhaps a better option would be to just generate the single 5 man in memory on the fly from the 4 men tables. For tables with pawns you can restrict the pawns to their initial files as only progress captures can move them to another file in which case you've made it to a 4 man that you have an exact score for.

The other option would be to make your WDL table more generally useful with DTC information (such as C<20, C<35, C<50, not won as your 4 states for the bits (since the side trying for the win is generally obvious and the other side accidentally winning is generally findable as a quick tactic like 'stronger side just dropped their Q'). To convert this into a 100% accurate DTM search is still a chore, but perhaps actually manageable (perhaps not).

[Daniel Shawul]

For example, for KRNKB, the search can reach easily depths 10-12 in reasonable time, but then too slow to go deeper and I don't think it can reach to depth 50 which needed for that endgame even in hours.

I think you misunderstood the need for searching. It is not to resolve the endgame position by searching it to the end. 10-12 plies is more than enough to make progress. Here is what you need to do. For a WDL score, lets say you assign +5000,0,-5000 scores respectively, then at the leafs add your eval() to this score to help it make progress. Since you have hashtable, null move and all other stuff, you would need to adjust this score by the ply like we do mate scores. So before adding that and other stuff, it is better to test that simple idea first by turning off hashtable,null move etc..

[phhnguyen]

To reach depth 50 with alpha beta you're going to need massive amounts of pruning, an amount that's probably not attainable with just a WDL table for a generally won endgame.

Thank you. Now I feel confident with my current work (not doing something too silly).

Bitbase and WDL information seems be not magic for finding mates. I think using WDL may be much worse than using rules (even it is not easy to write rules) when searching because we can easily to add more information than only WDL to rules.

Perhaps, I will try to find another solution instead of insisting to search until mates - it is clearly hopeless for some endgames which DTM may be over 120.

Perhaps a better option would be to just generate the single 5 man in memory on the fly from the 4 men tables. For tables with pawns you can restrict the pawns to their initial files as only progress captures can move them to another file in which case you've made it to a 4 man that you have an exact score for.

Very interesting idea. However, from my experience, generating a 5 men endgame may take houses if not days (download them should be faster than generating them). Thus it is a big practical problem.

The other option would be to make your WDL table more generally useful with DTC information (such as C<20, C<35, C<50, not won as your 4 states for the bits (since the side trying for the win is generally obvious and the other side accidentally winning is generally findable as a quick tactic like 'stronger side just dropped their Q'). To convert this into a 100% accurate DTM search is still a chore, but perhaps actually manageable (perhaps not).

I think we may save for some endgames but not all if using DTC instead of DTM. The problem is still serious.