KQKB and KQKN heuristic for bitbases?!

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply

KQKB and KQKN heuristic for bitbases?!

Post by jesper_nielsen » Tue May 01, 2007 7:33 am

Hi All!

Implementting endgame recognisors, ala DarkThought, i am currently working on adding bitbases for the 4-piece endgames to my engine Pupsi.

I have generated the "depth to mate" tables, and they appear to be working.

The next phase is to create a "won-draw" and "draw-lost" bitbases from the "depth to mate" tables.

My problem right now, is that my engine cannot force a win in the KQKB and the KQKN endgames using just the bitbases! :-(

The heuristic used is based upon "forcing the opponent king to the corner" and "keeping the kings close together" if won (or lost, if black to move);

Please see http://supertech.lcs.mit.edu/~heinz/dt/node33.html for details about recognisors.

So if white to move:
Lower bound if won.
Exact 0 if draw.

If black to move:
Upper bound if lost.
Exact 0 if draw.

This heuristic works splendidly for KBBK and KBNK (adjusted for the right corners).

What kind of heuristic is needed to force a win?

Should I look for the bug in the heuristic or in the way recognisors are used in the search?

What are your experiences with these endgame bitbases?

Thanks in advance!

Kind regards,

As i am writing this, I found a bug in my recognisor. If lost, the value returned was marked as a lower bound. So this entire post is a waste of time! :-(

But i won't throw it away. Doggone it! Instead i will change the question to this:

What heuristics are you using for your bitbase handling of simple endgames?

So far, it appears that driving the opponent king to a corner and keeping the kings close works great.

More kind regards,

User avatar
Posts: 22909
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller

Re: KQKB and KQKN heuristic for bitbases?!

Post by hgm » Tue May 01, 2007 11:54 am

Actually the bitbases do not offer you any information for these end-games that you would not get from a 3-ply search (+QS): the KQKB and KQKN end-games are generally won. SO the only thing you have to do is avoid giving the Queen away, and the longest way to do that is move to a position where Q and K can be simultaneously attacked by a N or a defended B, or with the B where Q and K are pinned on each other on a diagonal. That takes 3 ply (blunder + check + evasion + (QS) capture of Q).

So I guess any heuristic would work just as well as in a bit-base-free ordinary search.

Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: KQKB and KQKN heuristic for bitbases?!

Post by bob » Fri May 04, 2007 8:15 pm

For those kinds of endings, I don't think you even need 'em. KQKR is more difficult than either of those, and a simple "drive the king to the edge/corner and keep the kings close together is more than enough to force the win with kqkr. With kqkb or kqkn it is even easier...

Post Reply