You are here: Home > Interviews > Interview with Miguel Ballicora 

Interview with Miguel Ballicora 

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

http://sites.google.com/site/gaviotachessengine/ (Gaviota webpage)
http://sites.google.com/site/gaviotachessengine/Home/endgame-tablebases-1
(Gaviota tablebases)

Arena using Gaviota Tablebases

by:

Michael Diosi (Arena Webmaster)

  • Ask for permission
  • Publish the whole interview
  • Add a link to the Arena-webpage

 

 

 

Introduction:

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 rec.games.chess and rec.games.chess.computer 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:

  • - License: Gaviota TBs probing code have a very liberal MIT license (anybody could use them with almost no restrictions).
  • - Smaller indexing memory (~10 MB vs. ~20MB). Not critical now, it will become an issue with 6 pieces
  • - More flexible compression options: Some have smaller memory requirement (6.5 GiB), some faster decompression times (may become the option of choice when Solid state disks become more popular). I believe this flexibility that the Gaviota approach offers mayl be important in the future.
  • - Better cache system, which works like "bitbases on the fly". It is like having a cache with 4x more efficiency (in terms of memory). This leads to higher hit rates.
  • - The Gaviota interface allows different ways to probe: "Soft", which only gets info from cache and does not go to HD (very fast), and "hard", which is the traditional way. First, it probes the cache, and later, the drive.
  • The engine can probe soft much more aggressively (I do it everywhere except quiescence node). The traditional way has to be limited to places far from the leaves.
  • - Also available are WDL (win-draw-loss) probes. They are useful when the only thing it matters is whether the game is win, draw or loss, and not how may plies are needed to checkmate. This increases the cache efficiency 4x (works like bitbases as mentioned above).
  • - Flexibility for the future. It is possible that real bitbase files could be plugged in the future rather than building them on the fly. The engine will not have to change its code, and it will only notice, perhaps, an improve in efficiency

  •  

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.

 

Powered by CMSimple_XH | Template by CMSimple_XH | (X)html | css | Login