How much are bitbases worth?

[Tord Romstad]

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

[Dann Corbit]

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

I saw one experiment that showed +50 Elo (IIRC).

[hgm]

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?

[Dann Corbit]

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?

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.

[Dirt]

What bitbases could be responsible for such a large effect? f the 3+1, KBNK is the only one that Joker might bungle.

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.

[Tord Romstad]

What bitbases could be responsible for such a large effect? f the 3+1, KBNK is the only one that Joker might bungle.

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.

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:

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;
}

IIRC, a six ply search was sufficient to win against tablebase defence with this very simple evaluation. A six-ply search with so little material left is, of course, practically instant. Winning a game with less than five seconds left on the clock is easy.

Tord

[Tord Romstad]

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.

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.

Tord

[hgm]

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.

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

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?

[Dirt]

The difficulty of winning KBNK is a myth.

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? :-)

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.

[Tord Romstad]

The difficulty of winning KBNK is a myth.

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?

I'm almost certain I couldn't win it either.

What I meant is that it was an easy endgame to program.

Perhaps there are no theoretically won five piece bitbase positions that Glaurung couldn't win with only win/lose/draw information.

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.

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.

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.

Tord