As I described in a previous blog post, I finally released Tarrasch V3 on November 25th. Through some mechanism that remains a mystery to me, people noticed and download frequency went up immediately. Around a thousand downloads in the first day, over five thousand in total now after twelve days or so.
In the days following the release I developed a weird kind of anxiety I haven’t experienced with Tarrasch before. No doubt this was due to the release being the culmination of an awful lot of work. Tarrasch V3 is a tiny insignificant thing in the world – but for me it’s something of a big deal and if it turned out that I’d released prematurely and made some hideously embarrassing error it would have been bitterly disappointing. For several days I couldn’t bear to even run my own program – I was too worried it would just crash hopelessly in some trivial way due to an obvious use case I’d somehow neglected.
Happily I got over than after a few days, and started poking around and even stretching my program a little again. The dreaded deluge of angry emails I was imagining didn’t materialise, and instead I got a trickle :- (not a deluge unfortunately), of nice feedback instead.
The title of this post is “Tarrasch V3 Released Successfully” and basically this means that Tarrasch V3 has finally replaced Tarrasch V2, and as far as I can tell the transition has been a smooth one.
This is not to say that there are no problems – but I think the ones that have come to my attention so far at least are of the kind that you can reasonably expect. I will issue a .01 update in due course and life will go on. At this point here are the issues I feel I need to fix fairly promptly;
- At the end of a big database create or append operation, writing out a large number of discarded duplicate games to the discarded duplicates .pgn takes a long time and this delay is not predicted or acknowledged by the progress indicator (the user might wrongly perceive that the program has crashed).
- If there are more tabs than can be comfortably accommodated – the most recent tabs aren’t selectable until older tabs are deleted to make room.
- If the vertical resolution is less than 766 pixels, the option engine dialog doesn’t let the user change engines.
- I think I was wrong to move the position heading (“Position after 1.e4” etc) from the frame to the board pane by default. On all but very large screens it takes too much room.
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.
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.
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!
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).
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.
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.
Experienced Tarrasch watchers will notice right away some big improvements.
- 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.
- 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.
- 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.