Saturday, October 29, 2011

Gaviota Endgame Tablebases

One thing I leaned in the past about coding endgame knowledge is, that when you think you have done it correctly - you only think that. Chances that you coded some big mistakes are really high.

One example is the endgame king and 2 bishop vs bishop. This is seen in theory as an easy to defend draw. So you might think when you encounter it on the board you just return a draw score instead of further search and eval. This is a big mistake because it will make the engine blind. There are a lot of positions in a KBBKB endgame that are not drawn.

Trivial ones are where the defender bishop can be captured right away, but also non trivial ones where the attacker is able to separate the defender king and bishop, pin the king to bishop and capture it later. To detect those not so few exceptions you need a rule set that tells you whether this position is a safe draw or not.

Missing a draw is not so bad, the engine just keeps searching until it finds a know draw. Announcing a draw in a position that is a forced win is fatal because the engine might play a stupid move (giving away its bishop) because of that.

So the rule set must be verified against a database that it only announces correct draws. In my former attempts with 4 man positions I built the required database my self by retro analyses from mate positions. But I have no algorithm that deals with 5 man positions yet and thought before inventing this wheel I have a look at the available data.

As I only need the information whether a positions is a draw and not the actual distance to mate information I thought that bitbases are enough. Here only a Win - Draw - Loss flag is returned. I found a bitbase set from Daniel Shawul, called the scorpio bitbases. Those come with a DLL that lets you probe the bitbase. Usage is pretty easy but unfortunately it does not work for me. After a few probes the program crashed with an exception caused by a function in the DLL. So I left those alone.

Next try where the Gaviota Tablebases from Miguel Ballicora. This is a bit more work to setup, because here the complete source is provided and because 4 different compression schemes are supported its quite a heap of files. I was not able to compile it with my wingw edition of gcc. It complained about a missing "resource.h" file. But in MSVC it worked, I was even able to compile a static library from it, so I don't have to include all those single files in my engine project.

I must say the design is pretty good, flexible and clear. Once you understood how they work it is easy to probe them. Well done Miguel !

So I will verify my rules now against the Gaviota Tablebases and whenever maybe in the future I decide to use table bases also for the actual search of the engine I'm sure I will use the Gaviota ones. Also of course most of the interface code to use them in my framework is now already written.