Interview with Miguel Ballicora 

Miguel Ballicora (Argentina) is the author of the Gaviota/Gaviota Tablebases, December 2010 (Gaviota webpage)
(Gaviota tablebases)

Arena using Gaviota Tablebases


Michael Diosi (Arena Webmaster)





The Arena chess GUI now supports the Gaviota Tablebases by Miguel Ballicora (Argentina). With this occasion we conducted an interview with the author of the Gaviota chess engine and the author of the Gaviota tablebases. For those interested in tablebases in general we suggest you read this article.

Interview with Miguel Ballicora (Gaviota/Gaviota Tablebases):

01. When did you start engine programming ?

Miguel Ballicora (Gaviota):
I started in the late 90’s. During the Kasparov - Deep Blue matches I was frequently checking the and fora, and began to read a bit about chess engine programming. That sparked my curiosity. At the same time, I wanted to learn C and move away from Pascal, which was the language I used for some of my scientific programs. Writing a bitboard move generator was my first attempt to learn the language. Once I did that, I realized that I was not so far from having a very simple engine, so I continued. By the year 2000 I released the first version of Gaviota.

02. What were your sources for the tablebase code?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
Sometime ago, a paragraph from the chapter “Squeezing space” from the book “Programming Pearls” by Jon Bentley sparked my interest in tablebases coding. There, it was explained how K. Thompson compacted his. The concept is not very complicated and reading about them in computer chess fora was enough to understand how to develop the code. When I was already writing the code, I read an article by Heinz and Nalimov to make sure I was not doing anything sillyr. I partially read the article and realised that the indexing was completely different. Nalimov’s indexing is much more clever and tried to squeeze every single byte of memory at the expense of making the code more complicated. I did not think it was the right approach for me at the time and I continued with a more simpler strategy. I think it paid off. At the end, the tablebases needed to be compressed anyway, and having a more regular arrangement of indexes may have helped the compression. Gaviota tablebases ended up occupying less memory than Nalimov’s despite it was never my original goal. Regarding the compression, there is available a lot of information on Internet as well as state-of-the-art open source code.

03. How are they generated ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
In several passes. In the first, all the positions that are mate, illegal, or stalemate are marked as such. In the second pass, each position is examined to see if after a move, it could reach a mate position, for instance. That position will be marked as mate in one. With a similar procedure, later passes will determine which positions are mate in two, three etc. Positions that can move only into losing positions, will be marked with the lesser evil. At the end, positions that could not reach a mate or be mated, will be marked as draw.

04. How do they differ from the Nalimov Tablebases ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
The information stored in disk for each position is basically similar. Both are “distance to mate”. In other words, each index contains information about how many moves are needed to mate the opponent or to be mated. Everything else, including how the indexes are arranged is different. Gaviota tablebases have the following advantages:

05. What problems did arise ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
It took a long while to code. Each type of endgame (i.e. a given combination of pieces) requires at least one dedicated function to convert a position into an index, and one to convert that index back into the original position. It took me some time too to make sure that everything was correct. For this purpose, I wrote several utilities to double check and confirm the values in the tables. Debugging was probably the most consuming task.

06. What was your motivation to create your own TBs ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
It was for fun and curiosity. I wanted to see whether my engine played better the endgame phase with TBs, and since I like to use my own code, I decided to go ahead and build them myself. In addition, I saw very little interest in developing anything related to TBs after Nalimov’s and I was really curious to see whether it could be improved. If I wanted to increase the strength of my engine, it was probably time not well spent, but I am not driven by ELO only. I learned a lot in the process, particularly about compression, which is something I could use for many other purposes beyond chess.

07. How far are the 6-men TBs ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
The only think I can say is that I certainly plan to build them. First, I need to optimize the generation of the 5-piece tablebases. I would like to have an algorithm that uses the least memory possible (even if it takes longer), so anybody could join to build the 6-piece tablebases in a “distributed” effort. Building the 5-piece files will serve as a pilot experiment to test that possible algorithm.

08. Can you please tell us about the web-server ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
I am not planning to have a web server, but I do plan to write a “TB engine” that may work as a server. That will work as very high level interface.

09. Any concrete plans for an open-source plug in ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
That would be the TB engine I mentioned above. Any graphical interface or other programs will be able to use that engine to extract TB information. In this way, those interfaces may not need to be recompiled if improvement are found (for instance, this engine could probe another computer, the internet, 6 piece files, etc).

10. Any plans for further developing the engine ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
Yes, so far I did a good progress with the evaluation, but the search is very primitive. I have not even attempted to introduce any of the most aggressive pruning techniques. For instance, I did not implemented LMR (Late move reductions) yet. Certainly, a lot of work remains to be done and little by little I will keep improving the engine.

11. What engines do support Gaviota TBs

Miguel Ballicora (Gaviota/Gaviota Tablebases):
The first engine to support them was Daydreamer by Aaron Becker. Later, Critter (Richard Vida) and Myrddin (John Merlino) were added to the list. At least four others supports them in unreleased versions or they will be supporting them soon. They are KnockOut, Olympus, Chiron, and GnuChess. In addition, There is available a non-official version of Stockfish that uses them with old code written by Joona Kilskii and ported to the newer versions by Peter C. I just found out today that Umko (Borko Boskovic) uses it and the next version of Houdini (Ronert Houdart) will support them too.

12. Are the TBs accessed during search if there are more than 5 pieces on the board ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
This is certainly up to the engine author, who could choose the best approach for its engine. In Gaviota, I probe during the search quite deeply.

13. What are the disadvanteges of BitBases vs. Tablebases ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
Bitbases occupied less memory because they contain less information than table bases, so in general it is possible to have them in RAM memory for a very fast access. This is certainly not possible or even convenient for tablebases today.

14. Can they be used together ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
Yes, in fact I believe that is the best combination and that is exactly what I am trying to do with Gaviota. I designed a common interface so the engine request information that most of the times is satisfied by bitbases (you only need to know whether you win, not how close you are to mate the opponent), but if you need, “behind the curtains” the interface will access the table bases. For now, the bitbases are generated on the fly and temporarily stored in a cache. In the future, the interface could access true bitbases. At this point, it is not clear to me whether this is actually needed.

15. Can GaviotaTablebases (BitBases) oversee a mate if it is very far away?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
Not if every leaf in the tree takes you to a position with 5 pieces or less. It is not possible to get into a loop in which the engine does not make progress towards mate. There is no reason for this to happen unless the engine has a bug in storing some of this information in the hash tables. But that is problem that could happen with or without table bases.

16. Do the Gaviota TBs consider en-passant and castling moves ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
For en-passant, the information is not stored on disk, but the probing code calculate it on the fly. This is done transparently, so the engine does not that the result is not stored. It looks it is. For castles, the information is not stored either and the same transparency exists. However, the probing code returns “position not found”. Since the probing code forces the engine to declare what castles are available, it forces the engine to be thorough and remove the possibility of a bug in which the engine probes the tablebases when castles are still available. There is a very famous engine who suffers from this type of bug when it probes Nalimov’s, for instance. The Gaviota approach is very practical and it could be safely used even with chess puzzles. If there is castle available, it may just take one more ply to be solved, but it will not give wrong results. In addition, since the interface requires that the engine sends the castle information, I may decide to include in the future an extra file only with positions with castle. Engines will not even need to change their code.

17. Can you estimate how large the 6 men TBs will be ?

Miguel Ballicora (Gaviota/Gaviota Tablebases):
This is difficult to know. Considering that one of the compression schemes I chose based on the LZMA algorithm (default scheme 4) is more efficient than the one present in Nalimov’s, it is very possible that the whole set could be just under 1 Tb. In fact, I stop investigating more alternative approaches for compressing the 5-piece tablebases better because It was not worth it. 6.5 Gb was good enough. However, it may be important to get an even better compression for the 6-piece tablebases.

We would like to thank Miguel for granting us this interview. We wish him a lot of success in the future.