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
How much are bitbases worth?
Moderators: hgm, Rebel, chrisw
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: How much are bitbases worth?
I saw one experiment that showed +50 Elo (IIRC).Tord Romstad wrote: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
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How much are bitbases worth?
That seems a lot to me. It corresponds to a 7% better score, or 1 in 7 games where half a point was lost because of bungling a won or drawn position.
It must depend a lot on the level of the engines; Joker almost never gets into a 5-men position before the game is totally decided.
What bitbases could be responsible for such a large effect? f the 3+1, KBNK is the only one that Jker might bungle. But bitbases are no help there. With 2+2 it might bungle KQKR and KQKP, but also there bitbases are zero help.
Is it all due to KRPKR?
It must depend a lot on the level of the engines; Joker almost never gets into a 5-men position before the game is totally decided.
What bitbases could be responsible for such a large effect? f the 3+1, KBNK is the only one that Jker might bungle. But bitbases are no help there. With 2+2 it might bungle KQKR and KQKP, but also there bitbases are zero help.
Is it all due to KRPKR?
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: How much are bitbases worth?
I think it may be slanted because it was a test between engine verses engine+bitbase (If memory serves).hgm wrote:That seems a lot to me. It corresponds to a 7% better score, or 1 in 7 games where half a point was lost because of bungling a won or drawn position.
It must depend a lot on the level of the engines; Joker almost never gets into a 5-men position before the game is totally decided.
What bitbases could be responsible for such a large effect? f the 3+1, KBNK is the only one that Jker might bungle. But bitbases are no help there. With 2+2 it might bungle KQKR and KQKP, but also there bitbases are zero help.
Is it all due to KRPKR?
Since an engine is very evenly matched with itself, you are much more likely to get into endgames than against either a stronger or weaker opponent.
-
- Posts: 2851
- Joined: Wed Mar 08, 2006 10:01 pm
- Location: Irvine, CA, USA
Re: How much are bitbases worth?
And of course Joker could be induced by a bitbase to trade down from a position it could easily win by knowing that KBNK is a sure win. Bitbases seem to make much more sense when there are tablebases to back them up at root, even if it's only by the GUI. On their own the only sort of "safe" implantation would seem to be to store drawn/not-drawn information, and leave it to the engine to decide which side is better.hgm wrote:What bitbases could be responsible for such a large effect? f the 3+1, KBNK is the only one that Joker might bungle.
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: How much are bitbases worth?
The difficulty of winning KBNK is a myth. It is extremely easy for a computer program to mate with bishop and knight. All you need is a piece square table for driving the king to the right corner, and a very shallow search. Here is my entire KBN vs K evaluation function, with a few little irrelevant details removed in the interest of brevity:Dirt wrote:And of course Joker could be induced by a bitbase to trade down from a position it could easily win by knowing that KBNK is a sure win.hgm wrote:What bitbases could be responsible for such a large effect? f the 3+1, KBNK is the only one that Joker might bungle.
Code: Select all
const int DistanceBonus[8] = {0, 0, 100, 80, 60, 40, 20, 10};
const uint8_t KBNKMateTable[64] = {
200, 190, 180, 170, 160, 150, 140, 130,
190, 180, 170, 160, 150, 140, 130, 140,
180, 170, 155, 140, 140, 125, 140, 150,
170, 160, 140, 120, 110, 140, 150, 160,
160, 150, 140, 110, 120, 140, 160, 170,
150, 140, 125, 140, 140, 155, 170, 180,
140, 130, 140, 150, 160, 170, 180, 190,
130, 140, 150, 160, 170, 180, 190, 200
};
Value KBNKEvaluationFunction::apply(const Position &pos) {
Square winnerKSq = pos.king_square(strongerSide);
Square loserKSq = pos.king_square(weakerSide);
Square bishopSquare = pos.bishop_list(strongerSide, 0);
if(square_color(bishopSquare) == BLACK) {
winnerKSq = flop_square(winnerKSq);
loserKSq = flop_square(loserKSq);
}
Value result =
VALUE_KNOWN_WIN + DistanceBonus[square_distance(winnerKSq, loserKSq)] +
KBNKMateTable[loserKSq];
return (strongerSide == pos.side_to_move())? result : -result;
}
Tord
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: How much are bitbases worth?
50 Elo points sounds like way too much, even for self-play. I run self-play matches all the time. 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.Dann Corbit wrote:I think it may be slanted because it was a test between engine verses engine+bitbase (If memory serves).
Since an engine is very evenly matched with itself, you are much more likely to get into endgames than against either a stronger or weaker opponent.
Tord
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: How much are bitbases worth?
Sure, but Joker does not have such a piece square table. So it uses its normal one, which thinks all corners are equally bad, and thus has a 50% probability to latch onto the wrong corner. (And more if the opponent knows what he is doing.)Tord Romstad wrote:The difficulty of winning KBNK is a myth. It is extremely easy for a computer program to mate with bishop and knight. All you need is a piece square table for driving the king to the right corner, and a very shallow search.
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. 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?
-
- Posts: 2851
- Joined: Wed Mar 08, 2006 10:01 pm
- Location: Irvine, CA, USA
Re: How much are bitbases worth?
Not entirely. I'm almost certain I couldn't win it, and HGM has just told us Joker might not. Are you claiming he's wrong about that? :-)Tord Romstad wrote:The difficulty of winning KBNK is a myth.
Perhaps there are no theoretically won five piece bitbase positions that Glaurung couldn't win with only win/lose/draw information. In that case I see no down side to using bitbases, but If so I doubt that only having drawn/not-drawn would result in any missed wins either.
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: How much are bitbases worth?
I'm almost certain I couldn't win it either.Dirt wrote:Not entirely. I'm almost certain I couldn't win it, and HGM has just told us Joker might not. Are you claiming he's wrong about that?Tord Romstad wrote:The difficulty of winning KBNK is a myth.
What I meant is that it was an easy endgame to program.
I'm quite sure there must be some. Some of the KQP vs KQ and KQN vs KQ wins are phenomenally difficult. There are probably some KRP vs KR wins which are too hard, too. There is therefore little doubt that having tablebases in addition to bitbases would be better for my program than only bitbases, but in practice adding tablebase support would be a waste of time, because noone would ever download gigabytes of data just to make my program one or two Elo points stronger.Perhaps there are no theoretically won five piece bitbase positions that Glaurung couldn't win with only win/lose/draw information.
I think a drawn/not drawn bitbase would be just as good as a full bitbase in practice, but it doesn't really offer any advantages. I doubt that you would save a significant amount of space: In almost all the endgame families in 4 and 5-piece endgames, there are at most two frequently occuring results anyway. After compression, the full bitbase will have almost exactly the same size as the drawn/not drawn bitbase.In that case I see no down side to using bitbases, but If so I doubt that only having drawn/not-drawn would result in any missed win.
Tord