Skip to content

Tarrasch Database Implementation

December 7, 2016

This is by way of a small digression. It won’t be of interest to most readers but might be of interest to programmers. It can be considered as a follow up to my earlier Chess Move Compression post where I outline the compact and efficient move representation used by the Tarrasch V3 database code.

In the comments to an earlier post, reader Umij asked this question; I would really love to hear the technical reasons you abandoned the SQLite approach for an in-memory database. Was it just the required database space? Or did performance break down when dealt with millions of games? Was some chess functionality (e.g. specific searches, opening trees etc.) impossible to implement in a fast manner using SQL?

I (eventually) answered in-place, but it might be worth breaking the answer out as an independent blog post. Basically answering Umij’s question serves to explain how Tarrasch’s database is implemented. The rest of this post is the text of my answer.

I think I can explain this best by starting with the current in-memory solution, then introducing the old SQLite solution. The in-memory solution is essentially a big vector of games. Each game is represented as a C++ string. I am misusing the concept of a string really, for a start the string is binary data and not textual in any way. If this bothers you think of a game as a vector of bytes rather than a string. Also, in software engineering, encoding a bunch of fields in a single string is actually a classic anti-pattern (i.e. mistake). But it does have advantages (e.g. one allocation per game) and as Reti said rules of thumb are glasses for the short-sighted. To mix metaphors sometimes you have to break a few eggs to make an omelette. The first part of the string efficiently encodes the game meta data (players, event, site, date. result, elo information etc.). The remainder of the string is a one byte per move representation of the game moves using the performant yet compact encoding system I described earlier in a big blog post.

An important refinement is that for storage and copying I actually exclusively manipulate pointers to games rather than games themselves. I use C++11 shared pointers to do this efficiently with automatic memory management. This means that I can efficiently assemble multiple subsets of the entire database (for the clipboard for example, or the results of a database search) without wasting additional memory for multiple copies of games.

I implement all the database features by brute-force search through all games move by move. I put a lot of effort into the design of my move encoding and the implementation and optimisation of the move by move search. But it’s fair to say I was amazed at how quickly I can scan through a million (or 2 or 3) games this way. It’s a tribute to the brilliant engineers who put together the extraordinary CPUs we have today. A key trick is that I can end a game search early when I find that a home square pawn (eg a White pawn on a2) in the target position moves or is captured in the game I am scanning. In other words, if there is a White pawn on e2 in the position I am searching for, and in the game I am scanning White plays e2-e4, then obviously I am not going to reach the target position in this game and I can stop scanning. Similarly I can end early when the piece type counts and pawn counts I track indicate the game I am scanning can never reach the position I am targeting. A refinement is that I handle games with no promotions (95% of games statistically) with a faster version of the scan algorithm. In the faster version, if say there are two white rooks in the target position, then if during the game scan the white rook count goes from 2 to 1 (due to a capture of a white rook) I can end early because with no promotions I know there is no possibility the white rook count will increase later in the game.

When I used SQL the equivalent to the big vector of games was a “games” table. The rows of the table were games, the columns were gamed_id (the primary key – basically just an incrementing row index) plus White, Black, Event etc. and finally Moves which was a string using my one byte per move scheme.

With this table SQL would let me find, sort and present games reasonably effectively. But of course any kind of position searching required something extra. The solution I used was a second table, a “positions” table. Each row of the positions table was a position and a game_id. Actually I used a hash of the position (instead of the entire position) – for space efficiency. Positions which occurred in multiple games generated multiple rows (same position, but different game_id). So the total number of rows was much greater than the total number of positions that occurred in the entire database. Obviously that’s a lot of rows! As I got this working I found that building this table got intolerably slow with larger databases. So I refined the idea; I used 4096 individual position tables. Each position would automatically be associated with one of the 4096 tables according to its hash. I think database programmers call this “sharding”. The position hash is basically a number generated by XORing together all squares of the board using pseudo random constants for each square – each square has 13 possible pseudo random constants (64×13 constants altogether). For each square you select a pseudo random constant corresponding to the piece on the square (13 possibilities; 6 white, 6 black, empty). It’s faster than you’d think because there’s a trick that lets you incrementally recalculate the hash move by move without a total recalculation.

The scheme I settled on was to use a 44 bit hash. The underlying hash calculation was 64 bit and the top 20 bits were discarded (a shame but the way these things work you basically do a 8, 16, 32, 64 or 128 bit calculation then discard excess bits if you have them – it’s impossible or at least offers no benefit to do the calculation at any intermediate size). Of the 44 bits, 12 selected one of the 4096 tables and the position hash values in each row of the table were the remaining 32 bits. It was necessary to account for hash collisions – two completely different positions will occasionally generate an identical 44 bit hash. To find the games where any target position occurred, calculate the hash for the position, select one of the 4096 position tables (directly from 12 bits of the hash), and then ask SQL to find all the rows in that table with the remaining 32 bit position hash code. Each row has a game_id which lets you access a complete game from the games table. It was necessary to scan through the game to make sure the position was really in the game and not the result of a hash collision.

If this is all clear to you you are doing very well! From now on I’ll dial down the details somewhat and things should be easier to follow.

The biggest advantage of this SQL approach was that it was very good at quickly finding unique or at least rarely encountered positions – the kind of positions that occur well after opening theory ends. Soon after getting all this working I remember getting a postcard from Iceland with a stamp with an interesting looking chess position on it. I thought that the Icelanders know their chess, this wouldn’t be a random or meaningless position. Sure enough, it turned out that it was the final position in the game Olafsson-Fischer, Portoroz Interzonal 1958. A win for Iceland’s favourite son against the most famous chessplayer in history (later also a naturalised Icelander of course). The cool thing about this was that the search delivered the result instantly. Press the search button – boom – there’s Olafsson-Fischer. I distinctly remember the burst of adrenaline I got from performing this experiment and getting a perfect result immediately. Unfortunately this is more of an edge case than the kind of thing you normally want your database to do. A much more normal situation is to put in a standard position from opening theory, to find out how good players handle the position. Often in that case there might be thousands of games to deal with. If the position is (say) the position after 1.d4 d5 2.c4 e6 you might have 100,000 games (admittedly an extreme case). To do the things you want to do, like tabulate stats for all the options (3.Nc3, 3.Nf3 etc.) you need to read all 100,000 games. This tended to be unbearably slow.

By way of contrast, the in-memory approach might take a few seconds to locate Olafsson-Fischer Portoroz 1958. But it finds all the 1.d4 d5 2.c4 e6 games in a trice because there are so many pieces on the board (all 32 of them, so any capture means you can immediately abort a game scan), and especially since there are 12 pawns still on their home squares (so any of those moving [or being captured] immediately aborts a game scan). And tabulating the stats is child’s play too, since all these games are in memory. So in effect the in-memory approach is biased towards good performance in things that matter and worse performance for things that don’t. The SQL approach is the other way around.

As if all this wasn’t enough, there were other compelling reasons to switch to the in-memory scheme. To make the SQL position searches fast I had to add “indexes”. This bulked out the already large database files even more, and dramatically slowed building the databases. The 4.5 million game database I was using for development worked reasonably well for most things. But it was an overnight job creating it. And it was 12 Gigabytes! It was way larger than the equivalent .pgn (you really want that ratio turned on its head), basically an unruly monster too big to ever be distributed. By contrast the 2.5 million game millionbase file on my website is 238 Megabytes (so 55% of the games in 2% of the space). And it can be created in a few minutes. But wait there’s even more! Once I had transitioned over to the in-memory approach I started thinking about other types of searches, not just simple position searches. It was a straightforward process to extend the in-memory searches to find various types of patterns and material balances. I am very proud of these features, and no SQL constructs I can think of would be remotely relevant or useful to such searches.

In summary, switching from my original SQLite database model to a simple binary format with in-memory searching was an absolute no-brainer, at least with the benefit of 20/20 hindsight. However I absolutely don’t discount the possibility that a more experienced and capable SQL developer could think of dramatic improvements to the model I was using. I concede I don’t know how Chessbase searches work – they have a very practical solution with compact databases, reasonable creation times, reasonable search speed and (I think) a disk based rather than memory based model. All power to them, I don’t know how to do that.

I think my in-memory approach has a decent future. Computers aren’t coming out with less RAM, and with my compact 100 bytes per game (approx) scheme I can at least in theory accommodate 10 million games in a gig of memory. As I wrote somewhere else, Chrome can eat a gig of memory doing a little web browsing. I’ve noticed that Windows 10 is smart enough to transparently (to user and programmer) swap the memory used by the database out to disk if it’s not accessed for a while. I haven’t exhausted the tricks I can use to speed the search. Most simply I can throw extra threads at the problem – at the moment I just use one core. And also I can anticipate that the user is likely to drill down further when he or she does a search – so I could (again using multi-threading) search just-in-case in the background and have the drill-down results ready instantaneously. At the moment the only multi-threading I use is to do an initial database load into memory in the background.

Advertisements

Release Anxiety

November 25, 2016

Last night I finally went ahead and released Tarrasch V3. This after a week of each day considering going ahead, then changing my mind. Yesterday I decided it was not a matter of life and death, I can and almost certainly will release further versions, nobody wants to see an endless series of Beta versions without a real release, so time to go ahead.

Ideally a major release should follow a period of intense testing on a stable release candidate. That’s not what happened here. My release candidate (see previous blog post) included lots of changes itself. Then yesterday I found (and fixed) the most alarming Tarrasch bug I’ve seen in quite a while. It turns out that the “Append to Database” feature was flawed, throughout the Beta program. The bug shows up right away if you try to append a big .pgn to a small database. In the much more typical case of appending a small .pgn to a big database usually there will be no problem, but occasionally you will silently exceed a hidden threshold and the result will be bogus player names, sites and events in the newly appended games. My best guess is that the great majority of Beta users will not have triggered this problem, and I did have a clear “use with caution” warning (at least until the release candidate a few days ago – unwisely I dispensed with the warning for that one). But still. I need to carefully analyse the whole thing and add some information to my website about it. Basically I am pretty sure my recommendation will be not to use any database you’ve maintained with the append feature during the Beta program. I am sorry.

Thinking about the bug, worrying about the bug, is heightening a rather alarming feeling of anxiety I have about the release. Is this an inevitable part of exposing yourself to the world in this way? Here’s my work, go ahead and use it. But it’s computer software so it may, probably does have bugs. Potentially embarrassing and serious ones. That are going to make me look bad, really bad.

I suppose the rational thing to do would be to continue and intensify testing. On an absolutely stable target this time, Tarrasch V3.00a, as released to the world. But believe it or not I can’t stand to even look at it. It just makes me feel nervous. I think I am going to have a day or two off instead.

Tarrasch V3 Release Candidate Released

November 20, 2016

Today I nearly finished Tarrasch V3. After many years of work! However in the end I decided I was too tired, and had made too many changes, and I didn’t want to rush such an important milestone and risk botching it.

So instead I released the final version Beta version. The plan is that this is a release candidate – in other words the final version will follow in a few days with (preferably) no changes. You can download the final Beta and try it out from my website triplehappy.com. It goes without saying that I will be very grateful to anyone who does this and reports on their experience, good or bad.

Actually having said all that I am going to make one more change – I am going to eliminate the “in-between” name TarraschDb and use Tarrasch instead. So when I finally pull the trigger on Tarrasch V3 (hopefully in the next few days), the new release will overwrite Tarrasch V2, not Tarrasch V3 Beta. This is a unification process designed to eliminate confusion – there will (soon) be only one latest version of Tarrasch. Of course I will make Tarrasch V2 available to anyone who wants it for some reason.

Here are the enhancements in the lastest Beta, from my Github release notes. There are some significant enhancements to the user experience in this list;

  • All chess boards larger (use space more efficiently) with configurable colours and move highlighting
  • All chess graphics has improved anti-aliasing for crisper borders
  • Number of custom UCI parameters increased from four to six
  • Added open recent files (mru) functionality
  • Menu shortcuts and help strings finally work according to Windows standard (after many years of not noticing a problem : )
  • Paste into edit window will (finally) parse and use .pgn tags if present.
  • Much more complete and effective Ratings filters for database creation
  • Now works on Windows XP
  • Can capture engine output when playing against engine (this was an unnoticed bug in Tarrasch V2)
  • Lag N moves training feature was broken in previous release, now fixed
  • Fixed major bug whereby Undo/Takeback did not play nicely with “force immediate move” and/or fixed period mode. This was an unnoticed bug in Tarrasch V2.
  • Update default engine to Stockfish 8
  • Ticking clocks are now red
  • “Reply to …” prompts are now red
  • Tabs can now be closed with mouse
  • Many small bug fixes

I think these all add up to a much more refined experience. I personally now enjoy using Tarrasch more than ever before. Everything flows nicely, it’s easy to get things done without fighting the program, and (very importantly) with the anti-aliasing improvements and the highlighted squares the graphics are more professional looking and very satisfying to use.

In case it’s not obvious I am feeling pretty good about Tarrasch V3 right now!

Once More into the Breach

October 12, 2016

I have been putting a lot of hours into Tarrasch, and for once most of those hours have been in testing (and fixing problems revealed by testing) rather than answering the siren call of enhancements and new features. The result is not only a new Nightly build, but a new Beta build as well (until the next Nightly build these builds are exactly the same thing). I am pretty confident about this build actually – it “feels” solid. I suspect this build could well be the most robust version of Tarrasch I’ve ever put out – I’ve certainly tried harder to find problems in corner and edge cases than I ever did with Tarrasch V2. I am almost tempted to retire Tarrasch V2 now.

But this is all based on a feeling, the objective truth is that this version is brand new and a significant delta on previous versions (literally dozens of refinements) so it’s more sensible to stick with the plan, to put in more testing, get more feedback, get more solid miles behind me.

My thanks to Claude Tamplenizza, from Australia for doing some systematic testing for me. He gets a credit on the Help > Credits page in this release.

There aren’t a million visible enhancements to see but I do urge keen users to switch to the new version because the many many bug fixes are definitely worth the price of admission – this is definitely more solid than previous Tarrasch V3 versions. A few enhancements you might notice;

  • You can now modify the board colo[u]rs (no doubt there are people who preferred the old Greyscale scheme – they will be happy).
  • That reminds me that I now try and detect whether you’re in a “color” country or a “colour” country and adapt my spelling accordingly. Little details count I think.
  • The board colo[u]rs make it into the preview chess board. But not (yet) the setup chess board.
  • I’ve improved the new chess graphics anti-aliasing (basically anti-jaggies) somewhat. It’s a subtle but worthwhile graphics enhancement.
  • If you use the database facility to explore an existing game, a “>” character appears in the database move statistics window to guide you through the game. Hard to describe but very obvious and useful in the right circumstances.
  • I’ve added a button to make it easy to make new tabs.
  • You can [once again] click on player names and clock times to make changes (I temporarily lost this facility with the new look).
  • If you are adding games to a tournament file, Tarrasch will now try and help you out by auto-filling the rating fields (for repeat players). Next step – support picking the players from a list! (no I haven’t done that – but I hear the siren call).

A Day in the Life of a Windows Developer

October 2, 2016

Yesterday I hunted down and eventually overcame an infuriating problem with the Visual Studio toolchain I am using to build Tarrasch. The problem was a bogus “This project is out of date do you want to build it?” message every time I started the Visual Studio debugger. The message is bogus because it appeared every time, even immediately after a successful rebuild. Experienced (perhaps that should be “jaded”) Visual Studio developers are likely familiar with this problem. It is possible to simply ignore the message, but that gets old quickly and besides, it is rather antithetical to typical programmer mentality.

The details of this problem vary but the basic pattern is a standard one, I know it has happened to me before. There is plenty of help to be found on the Internet, although it turns out that most of that help is misleading if you are using Visual Studio 2015.  Older versions of Visual Studio would require a tricky hack (involving weird xml config files) to make Visual Studio more verbose so that it would explain its build decisions. Bitter experience (from yesterday) tells me that the tricky hack doesn’t work any more, although the good news is that there is now a much simpler solution;

Tools-> Options-> Project and Environment-> Build and Run-> change verbosity

Woo hoo. In my case, acquiescing to the build request always resulted in sqlite3.c being recompiled. So I cranked up the build verbosity and studied the masses of diagnostic information that now accompanied the build, including an explanation for the apparently unnecessary sqlite3.c recompile. It turned out that sqlite3.c is dependent on an obscure Windows building block called C:\Windows\System32\tzres.dll. Presumably this is a time zone related component of some sort, which is ironic since I am pretty sure my problem only popped up as a side effect to my edge case time zone (I live in New Zealand, in the extreme GMT+12 timezone, in the future compared to most everyone else). But I am getting ahead of myself.

I tried to figure out why Visual Studio connects sqlite3.c to tzres.dll, but couldn’t see any suspicious includes and ultimately gave up the chase on that front. Surely I could fix the problem irrespective? Very much to the point was the fact that I had woken up to an overnight automatic upgrade to Windows 10 Anniversary edition. Apparently that update had mysteriously changed the timestamp of tzres.dll to a date in the future (!). This meant that sqlite3.c would always be “out of date” (i.e. need to compile), until we reached that future date. Fortunately it was only one day in the future, so as it happens the problem would have sorted itself out simply by waiting for a day. My best guess is that something about my extreme timezone, which usually has me one day in advance of most of the computing world (especially in the middle of the night) confused Windows Update.

I mistakenly decided to force the issue (rather than just living with it for the rest of the day) by tweaking the timestamp of the disorderly tzres.dll. The plot thickens, Windows 10 fought back, resisting all my attempts to revert the timestamp to something more sensible!  Windows knows best, if it says we’re in the future, we must be in the future! My backup work-around was to instead change the timestamp of sqlite3.obj to the future date too (should I be thankful that Windows didn’t somehow work out what I was doing and stop me ?: ), so that Visual Studio doesn’t always want to compile sqlite3.c. Unfortunately Visual Studio still thinks TarraschDb.exe is out of date (because it’s now behind sqlite3.obj) so it still wants to do an unnecessary link. So I only saved the unnecessary compile.

In retrospect it would have been better to have saved the hours I spent investigating the problem – given that the problem was going to solve itself after a day or two anyway. That doesn’t happen often though, and I suppose it’s nice to have at least a partially solved mystery.

I decided to write the whole thing up here, it might help someone else if something similar crops up and they have good google fu.

 

Dramatic Progress

September 20, 2016

I must confess that once again I have veered off the course I have previously worked out and gone off piste. In theory what I should have been doing recently was simply polishing and refining whilst avoiding major changes. That was the quickest path to finally finishing Tarrasch V3 and retiring Tarrasch V2.

This is what I’ve actually been doing.

tarrasch-nightly-screenshot

Experienced Tarrasch watchers will notice right away some big improvements.

  1. The board uses an attractive colour scheme, inspired by the improved Tarrasch Icon I recently introduced. I’ve finally yielded to pressure and added algebraic coordinates as well.
  2. The program finally uses all the space available efficiently and effectively. The user can resize the three panel layout to their heart’s content, and very importantly the board resizes appropriately to suit.
  3. Since the beginning I have had a group of big buttons to make it easy for new users to find a few key features (eg start a game with the engine, or setup a position etc.). I think it has always been good from a usability perspective, but there’s no doubt it’s a little quirky. I’ve greatly improved the concept and eliminated the quirkiness with a two tab bottom panel – my buttons are now “Suggestions” and that is the default tab – it has more room available so the suggestions are more descriptive and informative (sorry they aren’t shown in the screenshot). The other tab is the more mainstream “Engine Analysis” and selecting that tab is now available as the simplest and most intuitive way to start the kibitzer. It’s a simple and obvious improvement inspired by the fact that the engine output and the suggestions were always fighting for the same space. Now I’ve (finally) realised the right thing to do about that and it’s a change that makes me very happy.

You can download and start using this refreshed Tarrasch immediately at the project homepage http://www.triplehappy.com. Look for the “Nightly” build on the downloads page. I will probably update the Tarrasch V3 Beta build very soon to this newer version. In truth I am now finding it hard to look at older versions of Tarrasch V3 (and Tarrasch V2) without experiencing something akin to physical pain.

So it’s more important than ever for me to get on with the remaining refinements and finish this thing. The goal is to have one version of Tarrasch, with the new look, all the new features, and greater finish quality and solidity than ever before. My Github process is now mature and refined as well, and any developer can quickly start working with the Tarrasch code with none of my old compiler warnings and wxWidgets headaches. I’ve made some progress on platform portability and so Mac and Linux versions are on the horizon as well. Soon Tarrasch will be both a superb practical chess program and a good development platform for future enhancement.

What are the remaining refinements I speak of? I still have a few user interface improvements to make – now I have improved board graphics I want to migrate them to the position setup and game preview windows. And of course the user should be able to edit the colours and optionally have highlight colours to identify the most recent move. But most importantly I need to pay real attention to the workflow options within the program. I need to make sure games, tabs and files work together seamlessly irrespective of the order that the user does things. I’ve somehow managed to get this far without really putting that aspect of the program under the microscope and properly tightening it down – I urgently need to identify all the corner cases and do the hard yards needed to make sure they are all rock solid.

Digging up the Roads

August 14, 2016

Yesterday I added another Tarrasch download opportunity to the downloads page on triplehappy.com. I chose to call the new “release” Nightly as opposed to replacing the existing Beta. I am definitely risking confusion through too many options here, but as always it’s all about trade-offs.

Basically I have made a lot of changes under the surface, and these expose enough benefits to end users that I want to make the new version available. But I am not quite ready to replace the existing beta, because I haven’t put in enough miles with the new changes to have sufficient confidence. However I will be using the newer Nightly build myself and I would really appreciate it if others try it out and give me feedback.

What are the nature of the recent changes? Most importantly I have finally bitten the bullet and upgraded wxWidgets, the massive GUI library that Tarrasch is built on. For more years than I want to count I have been using the same wxWidgets installation and fearing making any changes in that area. At some stage this has to stop, wxWidgets has had years and years of attention to goodness knows how many details and it is silly to turn your back on these essentially “free” improvements.

I am really pleased that I finally decided to take a fresh look at wxWidgets and install and integrate the latest version. I had become scared to touch anything in the wxWidgets arena. This caused some very tangible problems. Most importantly perhaps it meant a distinctly suboptimal experience for software developers who were tempted to work with the Tarrasch source code via Github. The wxWidgets dependency was woven into Tarrasch in a way that reflected the way I set up an old version of wxWidgets on my machine, many years ago, way before I ever open sourced my code. In retrospect I am rather ashamed of the previous state of my tarrasch-chess-gui Github repository. I have now cleaned all that stuff up. A Windows C++ developer can now expect to be successfully rebuilding Tarrasch (with zero warnings – not hundreds of warnings!) about 10 minutes after deciding to take a look – even if he or she had no experience with wxWidgets. I should really have done this years ago.

One nice little refinement that has come out of this exercise is that I could finally do something about the Tarrasch icon. Previously I had managed to completely lose control of how the icon was baked into Tarrasch. This was really embarrassing actually, I had resorted to literally purging the standard installed wxWidgets icon and replacing it with my (poor – and also not scalable) T shaped icon. I couldn’t build any wxWidgets application without the T icon even if I wanted too! If I remember correctly the reason for this was a weird feature of Windows that still affects me now on Windows 10. Windows caches icons, it doesn’t reload icons each time it needs one. But for me at least (I am being conservative here – maybe I have some obscure registry setting wrong) the cache doesn’t get refreshed when the file changes. So rebuilding a program with a new icon apparently has no effect!

I didn’t understand the problem years ago when I first encountered it, and overreacted basically purging all traces of the standard wxWidgets icon from my system in an effort to make the T icon show up. It’s funny, there is an old programmers’ joke that says something like “There are only two difficult problems in software development – good naming, invalidating out of date cache entries, and off by one errors”. I would have thought in this case Microsoft could actually just invalidate the cache entry whenever a file’s modification date changes but maybe that’s too simple for some reason.

Anyway, now I understand the problem better I have taken control back, and can put whatever icon I want into any .exe. (The fact that the icon doesn’t appear to change [at least immediately] no longer causes me to doubt my sanity).  I have taken the basic idea of a T shaped section of the chess board and made a nicer, resizable icon using the motif of a fianchettoed bishop which is a real T shaped formation. If you install the Nightly build you might not see the new icon of course! If that’s the case, please google for “Rebuild the Windows icon cache” or similar.

This post is getting too long. I will restrict myself to making one more point. Another tangible benefit for end users of the wxWidgets upgrade has been that one longstanding Tarrasch problem has been eliminated or at the very least greatly attenuated. Keen users might have noticed that adding a lot of variations and/or comments to a game progressively slows down the responsiveness of the Tarrasch editor. This becomes a very real problem for me in my role as an amateur chess journalist. I am going to be using the Nightly release for this reason alone.