Search with bitbase

[phhnguyen]

Hi all,

I have been working on my own EGTB, focusing on 3-4-5 men only. Everything is OK except 5 men's size because I plan to use them for a chess utility (an endgame solver / dictionary) for IOS devices.

Thus I have converted 5 men endgame into bitbase (use 4 values / 2 bits per position) and immediately faced to problem of searching. My current simple search (without using hashtable nor alpha-beta search - it mainly looks into endgames for DTM values for given position) which works very well for normal/full values of DTM EGTB, becomes stuck / non-progress. Thus I have been working to improve it. The first task I will do is to convert the search back to normal alpha-beta search with hashtable so it can really do search.

For next step, I have been considering some different ways to help my search to progress:

1) All endgames are bitbase. The search will look into endgames for getting values as guide / direction / cut off whenever having a capture or Pawn push. Just worry about explosion of nodes and slowness of speed

2) 5 men endgames are bitbase, but 3-4 men ones are still normal / full values (normal 3-4 men size is acceptable). Search with board of 3-4 men should be simple. Search which starts with 5 men will look into engames whenever having a capture only. Because of capture, the board becomes 4 men and we can extract full values of DTM from 3-4 normal EGTB so search can stop immediely at that branch.

I (just) guess that (2) seems be faster and actually I may not really need to store 5 men bitbase endgames.

Any suggestion, idea or exprience? Any other problem should I consider?

Many thanks for any helps.

/Pham

[hgm]

It depends on your goal: do you really want to play the shortest path to mate, and announce its length, or do you just want to win?

For the latter you can stop searching the branch as soon as you capture even with pure bitbases. Just treat conversion to a won end-game as King capture, except that you give it a significantly smaller score. (E.g. if your mate score is 30,000, you could give a won 3-men 29,900, 4-men 29,800, 5-men 28,700.) This would make the engine go for the shortest path to a winning conversion (so play by DTC rather than DTM, basically). The fact that conversions are irreversible guarantees progress, so in the end you must reach the mate. Provided your search is deep enough to force a winning conversion, of course.

There are end-games for which bitbases are no help at all. E.g. KBNK is always won if there is no shallow tactical loss of one of your pieces (bare K forking B & N). If you have 2 bits per position, spending them to differentiate drawn, won within 10 moves, won within 20 moves and longer wins would be much more useful than WDL, as it would limit the depth of the search required to see progress to 10 moves.

[phhnguyen]

It depends on your goal: do you really want to play the shortest path to mate, and announce its length, or do you just want to win?

Thanks for your answer.

My current app will be kind of problem solver / endgame looker, thus win/loss values are not enough but it needs to extract full values of DTM.

For the latter you can stop searching the branch as soon as you capture even with pure bitbases. Just treat conversion to a won end-game as King capture, except that you give it a significantly smaller score. (E.g. if your mate score is 30,000, you could give a won 3-men 29,900, 4-men 29,800, 5-men 28,700.) This would make the engine go for the shortest path to a winning conversion (so play by DTC rather than DTM, basically). The fact that conversions are irreversible guarantees progress, so in the end you must reach the mate. Provided your search is deep enough to force a winning conversion, of course.

I see that problem, that why I have to convert my search function back to normal alpha-beta with hashtable to face to explosion problem.

Just worry about speed. Imagine, I want to return to user all postions of KBNK which mate in 33.

There are end-games for which bitbases are no help at all. E.g. KBNK is always won if there is no shallow tactical loss of one of your pieces (bare K forking B & N). If you have 2 bits per position, spending them to differentiate drawn, won within 10 moves, won within 20 moves and longer wins would be much more useful than WDL, as it would limit the depth of the search required to see progress to 10 moves.

I agree that a lot of endgames we can use search instead of using EGTB. However, speed/time is another problem: search only is hardly or takes too much time to answer some data queries such as showing all mate in n moves when search with EGTB seems be much faster.

BTW, using search for some but not all endgames, we still need to solve problem of bitbase search.

[hgm]

Well, bitbases are only helpful for guiding a search that has an evaluation good enough to find the progress by itself. They can then be used to cut off all branches that move into the sector with a game-theoretical result worse than that of the root. This is only helpful in end-games where there are a lot of non-obvious blunders possible. If the only non-winning positions are those where you give away a piece, (e.g. in KBNK), the search would be able to cut them off almost as efficiently by itself (e.g. because it knows KBK and KNK are hard draws).

I can imagine that 5-men bitbases could be helpful in an end-game like KRPKR, where win/draw is decided by the positioning of the pieces, and the evaluation of the search does not have any knowledge specific to this end-game (e.g. only PST and mobility).

[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.