How much are bitbases worth?

[Tord Romstad]

I am not motivated to program this. In the first place the end-game never occurs. It would have infinitely more practical importance to know that KBK and KNK are not won, and Joker doesn't know that either.

In my experience KBN vs K isn't that rare. I don't have any good guesstimate of its frequency, but it happens often enough that I remember having seen it many times.

I agree that knowing that KBK and KNK are drawn has a far bigger practical importance, of course.

But the long-term goal is to have Joker solve its end-games by retrograde analysis as soon as they get to a stage where this is possible in the remaining time. And end-games like KBNK will satisfy this criterion even in blitz. (It takes less than 2 sec to build the tablebase). Having it play per tablebase from the point where there is KBPPKBPP will automatically avoid trading down to KBK from a won position. So why bother with temporary ad-hoc solutions?

In principle I agree, but to me, 2 seconds would be far too slow. I can't afford to let my engine's search suddenly halt for 2 seconds in a blitz game. Even if I could push it down to 0.1 seconds, it would be too much for generation on demand.

Tord

[hgm]

The original point was that for the 4-men end-games which are difficult to win, the bitbases are no help at all. KQKR is always won if you don't give away the Queen, and KBNK is always won if you don't give away a piece (or stalemate ). Engines usually don't need a bitbase to tell them if they give away a piece, they will avoid it anyway.

[hgm]

In principle I agree, but to me, 2 seconds would be far too slow. I can't afford to let my engine's search suddenly halt for 2 seconds in a blitz game. Even if I could push it down to 0.1 seconds, it would be too much for generation on demand.

Why is that? Every move after the EGTB is generated will be instantaneous. So if you have more than 2 sec left on the clock, what else would you want to do with the time you saved?

[Harald Johnsen]

Endgames with 5 pieces don't occur often, and when they do, the ordinary endgame knowledge in my program is usually sufficient to evaluate them correctly. Of course such endgames sometimes occur in the search even if they are never seen on the board, but I still can't believe they give anything close to 50 Elo points in self-play, unless the engine has hardly any endgame knowledge at all.

Tord

The bitbase or egtb are supposed to replaced the evaluation in the search, what we see on the board is irrelevant. So the knowledge that you code is never enought if you don't have all the rules coded.
A KB vs K never happens *because* we know it's a draw. That does not mean that this endgame does not happens a zillion times in the search.
Statistics about endgames of master game are useless here, we don't know what are the statistics for random games (ie tree search).

But, back to the topic, I don't think that adding bitbase support is a lot of work; if you use scorpio bitbases it's done in less than an hour.

HJ.

[Tord Romstad]

In principle I agree, but to me, 2 seconds would be far too slow. I can't afford to let my engine's search suddenly halt for 2 seconds in a blitz game. Even if I could push it down to 0.1 seconds, it would be too much for generation on demand.

Why is that? Every move after the EGTB is generated will be instantaneous.

No, of course it wouldn't! The endgame would first appear somewhere inside the search tree, almost certainly at some completely irrelevant node. The two seconds would be completely wasted. Moreover, this would probably happen many times in the endgame, because there are so many other 4-piece endgames which appear somewhere in the search tree, and for which I would need to stop and generate a bitbase to evaluate.

Tord

[Tord Romstad]

Endgames with 5 pieces don't occur often, and when they do, the ordinary endgame knowledge in my program is usually sufficient to evaluate them correctly. Of course such endgames sometimes occur in the search even if they are never seen on the board, but I still can't believe they give anything close to 50 Elo points in self-play, unless the engine has hardly any endgame knowledge at all.

The bitbase or egtb are supposed to replaced the evaluation in the search, what we see on the board is irrelevant. So the knowledge that you code is never enought if you don't have all the rules coded.

I'm aware of that, of course. What I meant is that my evaluation function is generally precise enough to guess whether most 4- or 5-piece endgames are won or drawn. There are exceptions, of course, but they are sufficiently rare that I am confident it doesn't cost me anywhere close to 50 Elo points in self-play matches.

But, back to the topic, I don't think that adding bitbase support is a lot of work; if you use scorpio bitbases it's done in less than an hour.

That's not an option: I don't use code I didn't write myself.

Tord

[Tord Romstad]

The original point was that for the 4-men end-games which are difficult to win, the bitbases are no help at all. KQKR is always won if you don't give away the Queen, and KBNK is always won if you don't give away a piece (or stalemate ). Engines usually don't need a bitbase to tell them if they give away a piece, they will avoid it anyway.

This is true for most 4-men endgames, but not all of them. For instance, KR vs KP, KR vs KN and KP vs KP are far from easy to get 100% right without a bitbase. I think my program does KR vs KP and KR vs KN quite well (but not perfectly), but in KP vs KP it relies completely on the search.

Tord

[hgm]

This is true for most 4-men endgames, but not all of them. For instance, KR vs KP, KR vs KN and KP vs KP are far from easy to get 100% right without a bitbase. I think my program does KR vs KP and KR vs KN quite well (but not perfectly), but in KP vs KP it relies completely on the search.

KP vs KP might indeed be a problem, if you don't extend Pawn endings enough in the search.

[hgm]

A KB vs K never happens *because* we know it's a draw.

Well, Joker has no inkling of this, and so it can occur if Joker plays, and 'gains' the opponent's Bishop against its last 2 Pawns in KBPPKB.

But even then it occurs very infrequently, so I am not losing a minute of sleep about it.

[Don]

I've started thinking about adding 4-piece and 5-piece bitbases to my program, but I hesitate a little because it seems to be an awful lot of work, especially for something that doesn't scale down to handheld devices.

Therefore, before I start: Has there been any experiments investigating how much you gain by using the complete 4-piece and 5-piece bitbases on modern hardware?

Tord

Hi Tord,

I'll give you my sense of this, which is just an opinion of course and should be taken as such (no flames please

My sense of this is that there is not that much benefit except to one of them in particular, the RP vs R database. I would say 90% of the benefit of 5 piece databases comes from this single database.

There are small databases that are important but they are easily contained in a small amount of memory. KPk is probably the most important of these. I built my own kpk in the late 80's and still use it and I assume most programs have this one. Also, someone devised a set of rules to score this perfectly.

In 1986 I got into an argument with a world famous chess programmer about the importance of KPK and this programmer believed that it wasn't needed because a simple rule of king opposition combined with keeping the king in front enables a win. Although it's true that you can play this ending correctly with a couple of trivial rules, the much bigger issue is KNOWING whether it's a win or not.

Stuff like BN vs K are not important, they are always wins and all your program needs to know is to drive the king to corner of the bishop, although if your program doesn't know that, it can flounder and lose the win.

The problem with 5 piece databases are that despite herculean efforts, they do impact the speed of your program. I have no doubt that if you could have them all in your program and they were FREE, you would probably increase the ELO by 20-30 or something modest like that, but since they are not free they probably degrade the performance by at least that much or more.

It may very well be the case that with modern programs these databases become much more important (and thus my guesses could be off.) I believe that at really high ELO levels you need to have some knowledge that is more commensurate with your ability - for instance it's not very important whether a raw beginner understands how to win with RP vs P when he hangs pieces all the time, but it's very important for a master to understand this. So that concept may be valid here.

To help answer that question, what do the very top guys do in tournaments? Does Rybka use these databases in tournaments and if so does he use them in the tree search, or only to play the ending correctly once he reaches it?