How Ken Regan’s method works

14. Oktober 2022 asdfjkljerry1 Kommentar

Disclaimer: This is my understanding on how his approach works based on this talk given to FIDE. If you spot mistakes or have additional information, feel free to comment below. He has several papers published on the topic of cheat detection, which I do not consider here.

There is a lot of talk about the Hans Nieman case, but I found surprisingly few info and explanations on how cheat detection actually works. Recently, Super GM Fabiano Caruana criticized Ken Regan’s „algorithm“ as creating too many false negatives. IM Kostya Kavutskiy described Ken Regans method as „I don’t understand how they [statistical models] work but it involves math“. In fact, the way that cheat detection is characterized as an „algorithm“ already hints that there is a false impression how things actually work. While describing this as an algorithm is technically not wrong, the idea that there is an algorithm that runs on some games at the end outputs „cheater“ or „not a cheater“ is too simplistic.

Rather, this is all about anomaly detection. You compute statistics for games, and then these statistics have to be interpreted. And for certain thresholds this can be done more or less automatically, but depending on the results, things might get fuzzy.

I will here provide a short introduction on how Ken Regan’s cheat detection actually works. Note that this is based on his (public) slides – however they are dated 2013 and I am sure he has updated and refined his approach since then. Nevertheless I think looking at the ideas he presented there is worthwhile, as it provides a good introduction into the topic, and the general idea is probably going to be the same for current methods.

In general we need to define metrics for cheat detection and compute these metrics w.r.t. a number of games. Ideally, these metrics are able to distinguish games where cheating occurred from those where players played without any assistance.

Let’s first have a look what metrics he uses. In his slides, Ken Regan mentions:

move-matching (MM%)
average error per move (AE), scaled in units of PEPs
equal-top matching (TM%), usually 34% higher than MM%

There are no definitions given in the slides. However we can make an educated guess about what is meant.

Move matching probably refers just to comparing moves from a game with the corresponding top engine move in that position.

Average error per move (AE) refers probably to comparing the evaluation of a played move with the top engine move, computing its difference in e.g. centipawns, summing these differences up for all moves of a game and dividing it by the number of moves played. This is limited however to positions with PEPs, which is defined as “Pawns in equal positions, i.e. we want to rule out very unequal positions. Say if you are +4.4, and you play a move that is just +4.1, then this is something we might want to rule out – it might technically be an error, but practically just converting to a winning position or simplifying to convert the win.

Equal top matching probably refers to move matching but not just for the top engine move but rather for the first few top moves of the engine within a defined interval.

Let’s consider an example with AE. Suppose we have a huge database of games, and filter that database w.r.t. to a certain engine range, i.e. top players with an ELO of 2700+. We create a range of AE values and for each AE value count how often one specific value occurred. For example:

an AE of 0.0 occurred in 1 game
an AE of 0.1 occurred in 11 games
an AE of … occurred in … games
an AE of 1.5 occurred in 1253 games
an AE of 3.0 occurred in 10 games
an AE of 3.1 occurred in 0 games

These numbers are of course completely made up. If we plot these data we will get a bell curve which is going to look like this.

We can assume that these numbers follow a normal distribution. There are two reasons for this. The unscientific one is that if you have no clue how your data is distributed and there is no specific reason to consider something else, the normal distribution is always a good guess 🙂 The scientific one involves the central limit theorem which I will not delve into here.

The Measurement

So how are we going to use this metric to distinguish between cheating and non-cheating games?

The crucial values that characterize a normal distribution are the mean µ and the standard deviation σ. We do not know the precise values, but we can estimate them if we have a large collection of games. Suppose there are 100 games of (non-cheating) players, then we compute the means µ as:

And the standard deviation as

Given µ and σ we can plot the underlying normal distribution.

Note that by having µ and σ, we can think of AE as a real-valued random variable and for each real valued AE we can get a value on how probable the occurrence of this AE is. What is interesting here is that we can give a visual interpretation for various sums of probabilities. In particular there is the famous 68–95–99.7 rule.

For example the purple area covers 68 percent of all possible values. The purple and red area cover 95 percent of all possible values. And take additionally the yellow area, 99.7 percent of all values are covered.

Where do these three values come from? As you can see the areas are split in a way that we move left and right from the mean. And the amount that we move left and right is just a multiple of the standard deviation:

the left and right line of the purple area is -1*σ and +1*σ
further to the red area we have -2*σ and +2*σ
and at the yellow borders we are at -3*σ and +3*σ

In other words, suppose we encounter a game where we get an AE value that is very far from the mean, i.e. close to 3σ away from the mean. This means that this is outside of the 0.997 fraction of values; and if we convert this into probabilities, it means it’s a chance of 1 in 370 (cf. the probability table here.

If we step 4σ away from the mean, it’s already 1 in 15787 and so on.

This is precisely where need interpretation on how likely such an „odd“ performance actually is. In his slides, Ken Regan uses the number of games played measured in weeks of TWIC and gives some estimates for multiples of the standard deviation that should raise eyebrows.

Note that we here think in multiples of the standard deviation. We could also convert the observed AE_Game_? of the game in a standardized value by dividing the difference from the mean by the standard deviation:

This is known as the z-score, and we can use z-scores to look for suspicious games and compare z-scores for games.

Multiple Games

We can however go one step further. Suppose we have not just a single game, but say 64 games that we want to take a look at. We can ask the question: Say we would randomly select 64 played games (randomly sample 64 games), what kind of result would we expect to obtain? And then, how do these 64 games, say suspicious games from a tournament from one player compare to such a random selection of games?

We can use z-testing to check if there is something fishy. For that we need to treat the 64 games as random samples, and random samples can be characterized by a sampling distribution.

The mean of the sample distribution is given by

and the standard deviation of the sample distribution (also known as the standard error) is given by

Consider a small example. Suppose that from our large database we have determined \mu = 50 (centipawns) witha standard deviation of 16 centipawns. We now have a sample of 64 games with µ’ = 40.

Then

Note that for just one example as in the case above, we have squareroot(1) = 1, i.e. σ‘ = σ.

We obtain a z-score

Again, you need to interpret this number. There are z-tables which give the probabilities for z-scores. Here we can conclude that it is highly unlikely. If you sample 64 games – which is quite a high number, it is just very very unlikely that we end up so far away from the mean (of the original distribution). In practice however it is unlikely that we get such obvious indicators. Nevertheless it would be very interesting to compute a few statistics for say, the games of Igor Rausis.

Next let’s consider some questions that are asked a lot:

instead of thinking through all this math’ stuff and statistics, can you not simply start up Chessbase, click some buttons for which you have no clue what they actually do and for which the manual says „this correlation isn’t a sign of computer cheating“, publicly post that on youtube and not get completely roasted for doing so? Apparently, the answer is yes.
What if you cheat in a smart way, in that you use the engine only a few times in a game? If you do that often, then your AE mean will change (even if slightly) and eventually show in the stats
What if you cheat in a smart way, in that you use the engine only a few times in a game, but then afterwards play some slightly incorrect moves such that your AE values do not change? Then the metric will not detect it and it will not show up in the statistics. Note that this is why neither Ken Regan nor chessdotcom nor anyone else can ever be fully transparent about the metrics and techniques that they actually apply – you can tune your cheating in such a way that statistics will show nothing. Note however that one the cheater’s end it is also not easy to manipulate that way, as you have to make sure that several metrics will stay within normal parameters.

Last if we have more data, it will become more difficult to cheat. For example instead of computing AE, one could think of measures like:

average error per move, but only for those moves where the player just returned from tab switches in the browser (where a cheating player presumably looked at an engine vs an honest player, who might just have adjusted the volume of music playing in another browser tab).
average error per move, but only for those moves where the player has XX minutes/seconds on the clock.
Here we assume that the error rate significantly increases for an honest player under pressure, where for a cheating player these are exactly the crucial moments where he cheats

There are other ways as well. For example we could try to construct a neural network that tries to identify “crucial” positions in a game, namely precisely those positions that are difficult to navigate in for a human player. If we then measure the average error for moves played in such positions, this metric might be better in distinguishing cheaters from honest players.

You can read more about neural networks in my free book about Neural Networks for Chess.

As you can see, statistics cannot provide perfect proof, but are fuzzy. For some cases it’s crystal clear, i.e. if we see a performance with a good metric – such an average error per move – that is as likely as winning the lottery. But in other cases it’s not that simple.

More importantly it is important to understand the result. If statistical methods indicate oddities, then this does give a strong indication of cheating indeed. But if statistical methods do not show any irregularities, this does not mean that someone did not cheat. It just means that the statistics do not support any evidence of cheating. That’s something very different, but is often confused in practice.

Last, if we want scientists like Ken Regan to develop better methods and metrics then FIDE should change two things:

collect and provide more data for tournament games, especially time information and
provide a research grant such that a few PhD’s can conduct research on chess cheat detection

I am sure that there are several research directions which are unexplored yet.

Ken Regan’s cheat detection is probably faulty

26. September 2022 asdfjkljerryHinterlasse einen Kommentar

The title is a tongue-in-cheek slab at a statistician. But probably true, though.

There has been a lot of discussion lately w.r.t. to chess overt-the-board (OTB) and online cheating. And there is this video by Ken Regan, FIDE’s semi-official cheat expert where he analyzes Hans Niemann’s games and comes to the conclusion that no cheating occured.

And then there is the C-Squared podcast by top chess player Fabiano Caruana where Fabian questions the soundness (or rather sensitivity) of Ken Regan’s methods, because Fabiano witnessed a very odd game where he was sure that cheating was going on, but the player was cleared due to Ken Regan’s method.

Ken Regan is a well known professor, and international master in chess, and active researcher in complexity theory. His methods are sound, and this post is by no means intended to question his expertise or integrity.

According to his slides his main approach is to use Z-Scores; in particular several selected tests, namely move-matching, average error per move and equal-top matching. He does not precisely define what he means by that in the referenced slides, and it’s also unclear if he uses (secretly) other measures as well. But it does not matter here.

The point that I want to make: Ken Regan as a one-man-show will probably not be able to keep up with sophisticated cheating.

First there is not enough manpower and tooling. Anomaly detection is a really broad field. Using Z-Scores is a valid approach, but there is plently of research and other methods as well. The question is of course which methods work well for chess, and which don’t. And there will never be a lot of published open research on this, because keeping the methods and tools confidential is vital for e.g. chess.com as a business, and even for open-source platforms such as lichess – if you know the underlying method, you could probably cheat in a way to avoid being detected.

I’d argue that in order to kick-start well-done anti-cheating you would need at least one or two mathematicians who do research into statistics, two computer scientists who program the tooling and do data analysis, and a bunch of skilled chess players who help with interpreting the results.

Tooling is really vital here. Just brainstorming here: We know Maia was trained to predict human moves w.r.t. certain rating groups. I.e., given a position, what would a 1500 play in this position? (You can read more about Maia in my book about neural networks for chess). Could you do the same for grandmasters? How about incorporating timing information, i.e. given that a Grandmaster has XX minutes on the clock, what are the most likely moves he/she would play in this position? Could you train a network for that?

Such an approach might help to detect cheaters, but it also might be complete nonsense. It’s probably worth a try though, but it requires training a very complex network over days or weeks, implementing the training pipeline, collecting and encoding positions, feeding it in the network, hyperparameter optimization and so on. And there is probably a broad range of other ideas that you could try, which alll take a lot of time and effort.

It is absurd to believe Ken Regan could do this alone in his spare time besides being a full university professor.

And then the second thing is data. He himself writes in his talk notes:

„Online chess servers use specialized tests on greater information, such as exact time per move, „telltales“, particular engine profiles..“

In order to tune any kind of detection method and choose suitable parameters, you need lots of data. As mentiond, timing information are probably very valuable, as e.g. decisions change under time pressure. Then there are a few (OTB) games out there where we know for sure that cheating happened. However to validate any kind of method, or even to use machine or deep learning to distinguish games where cheating occured from those where this was not the case, such game data is crucial. I wonder what Ken uses, but I guess it essentialy boils down to ChessBase and TWIC.

On the other hand we can imagine that an online chess site such as chess.com or lichess.org have precisely these things available: Teams of computer scientists and mathematicians who focus specifically on cheating, as well as an incredible amount of game data; including crucial meta-information. And that’s not only timing information, but other things as well, such as browser-information; e.g. „How often did the tab with the website lose focus?“, which might make the analysis more precise. It’s likely that chess.com is more professional here than lichess, as it’s not just done voluntarily but chess.com is able to hire and pay experts to focus on all that for an extended period of time.

All in all this makes it very likely that Fabiano Caruana hypothesis that Ken Regan’s current approach to cheat detection has a very low sensitivity, is correct. Or in other words that it does not work properly.

Improved and Simplified USB Chessboard

31. März 20219. April 2021 asdfjkljerry8 Kommentare

After finishing the electronic chess board, I was not fully satisfied with the result. There are several issues:

a comparatively high price due to the cost of the reed switches and magnets
the overall look and finish – looks quite primitive
neodym magnets are dangerous – they are really strong. If you eat two of them, you probably will need surgery. Now I don’t eat magnets, but I have two children in the house, who love to do stupid things…

The main issues is however that the board emulates just a USB keyboard and is not a full chess computer. This means there is only communication in one direction, i.e. from the keyboard to the computer/smartphone/tablet.

So if you accidentally knock over some pieces, it’s actually difficult to get the computer and board in sync again. After all, how to recognize programmatically, if a piece is placed (corrected), or if this is the start/end of a new move? The only option to resolve this is to either add more buttons, a touchscreen or some other way a user can interact with the board. All this is cumbersome from the perspective of man-machine interaction.

Another point is that the program code is quite complicated, too. For example when playing with white, we don’t want the keyboard to submit moves from black, so we have to keep track whose turn it is. Again, when accordantly knocking over pieces, this gets out of sync. Same for castling – is this just a standard rook move, or the rook move after castling (and should thus not be submitted to the computer).

After re-thinking all this, I stumbled upon Berger’s Sish Board. This is based on tactile switches. The advantages are here:

it’s quite cheap to assemble. No need to buy expensive reed switches and magnets. Tactile switches are much cheaper
comparatively easy to build, few tools are required for the woodworking part

The main advantage however is man-machine interaction. Knocking a piece over? Just place it on the right field without pressing the tactile switch. Castling? Just press the tactile switches for the king, and place the rook without pressing the switches. Program code gets very simple: Just check the switches, and if one is activated, send the field information as an ascii string, i.e. "e2". Done.

Estimating the overall cost:

Arduino Leonardo or ProMicro. I reused my clone from the old board – 9 Euro
Tactile Switches. Bought bulk from Amazon. The type I used was 6x6x6mm. They require some force to be pressed, so that we don’t accidentally activate them when moving pieces around. A 100 switches were 5 Euro incl. shipping.
A vinyl chess board, with a field size of 47mm – I didn’t want the board to be too large. 10 Euro incl. shipping.
Copper Wire. This is just 0.80 Euro + shipping. I won’t count the shipping, since I had to order several supplies anyway.
To glue everything together, I used construction adhesive. The stuff that you use to glue baseboards to a wall. This is especially important to securely glue the tactile switches to the wooden panel. I didn’t buy this at amazon but at a local discount store, so 5 Euro.
The wood. This is difficult to estimate. Due to the Corona-induced overall lockdown in Germany, hardware stores were closed, and I could not shop around easily. So I used left-overs from the first board construction. I estimate the overall cost at around 20 Euro, if you’d buy from scratch.
a USB cable. approx 5 Euro, but I had a spare one around (and who doesn’t?)
chess pieces can be re-used from another existing set, so I don’t count them.

That’s a total cost of around 55 Euro, and beats any off-the-shelf chess computer on the market today.

As for the assembly: I pretty much followed Berger’s approach, so I won’t go into details but just notice a few differences:

didn’t use plastic spacers between the wood panel and the board. The tactile switches I used were half the heigth of his ones, so even without spacers the vinyl board was pretty even. In the end I cut leftovers of the wooden panel into small pieces, and glued them inbetween the switches.
didn’t use a USB port, but instead have a USB cable hanging out of the board. This is not very elegant, but I could not find a sturdy USB port that could be easily mounted. Will probably add one in the future
Currently not painted. Right now I am indecisive wether I will paint this, put oil on the wood, or leave it as is.
again I did not use a Teensy board, but an Arduino Pro Micro clone. A Leonardo would work as well. My source code is freely available here, but there is really not much to it.

Here are few pictures as well as a video that shows how to play with Aart Bik’s excellent Chess for Android.

Video@Youtube

Going Commercial: Fat Jerry

25. Februar 2021 asdfjkljerryHinterlasse einen Kommentar

I’ve complained a lot about all the work that goes into building open source software. So I thought a lot about how I can improve the situation, and decided to go commercial and make a living out of writing chess engines.

In particular I discovered a completely revolutionary neural network technique from Japan, dubbed NNUE. The original research paper was written in Japanese, so I decided to write a translation, available here.

You might have heard that the latest Stockfish 13 engine is based on that. I’ve discovered that the existing Stockfish engine can be modified in a way that significantly increases performance. Amongst several deep changes I made are

I’ve changed the UCI id to „Fat Jerry“
I’ve change the author name to myself
I’ve changed some engine parameters

I am targeting a retail price of approximately 42.42 Euro. Really that’s a steal compared to competitors, which charge more than double!

Stay tuned.

The Arduino-based Electronic Chess Board (ArdEBoard), Part 2

10. Februar 202110. Februar 2021 asdfjkljerry6 Kommentare

As mentioned, I am neither experience with woodworking, nor do I have the tools. I thus thought about the simplest and cheapest construction method.

Inspired by Berger’s Bluetooth Construction I opted for a foldable chess set. They’re quite cheap, have a thin board surface so that the reed switches are not too far away from the pieces, and also aren’t too big and fit well on my desk. I would remove the hinge, mount the reed sensor below the board surface, and screw everything on top of a piece of plywood (or rather medium-density fibreboard, i.e. MDF). I also wanted to use screws and avoid hot glue whenever possible. I just don’t believe in hot glue.

I ordered the following parts:

The cheapest chess set I could find. Due to Queens Gambit, it’s actually quite difficult right now to find chess sets in the first place. I ordered the cheapest foldable set possible, expected nothing in terms of quality. And I was not disappointed. Amazon, 25 Euro
An Arduino Pro Micro Clone with an ATmega32U4 (you need an ATmega32U4, not an ATMega328P. Only the ATmega32U4 is able to act as a USB-HID, i.e. emulate a USB keyboard). I really like what the Arduino guys are doing and usually buy original, but since I tried to challenge the 100 Euro mark (cf. last post), this time it was a clone. Also some jumper wires. Amazon, all in all 13 Euro.
40 First4magnets F307-20 10mm diameter, 1mm thick N42 neodym-magnets. Amazon, 15 Euro
A KY-012 active piezzo buzzer. I wanted some audio feedback, when pieces are place or the board is configured by lifting up pieces. Amazon, 5 Euro
70 reed contacts PRK-2,5×16, Pollin, 20 Euro
Shipping from Pollin, 6 Euro
70 diods 1N4448, Pollin, 1 Euro
copper wire, 10m, Pollin, 1 Euro
2 thin (3mm) MDF plywood sheets, Pollin, 3 Euro
1 large 5mm MDF plywood sheet, OBI, 14 Euro
A can of black spray paint (more on that later), 6,50 Euro
2m squared timber (more on that later), 5 Euro

All in all we’re at around 115 Euro. That’s slightly more than I wanted, but still. We’re less than half of what a DGT smartboards costs. If I had known what problems would arise, I would have not bought a board but just wooden chess pieces. These are available for as low as 13 Euro, e.g. here and would still look way better than the ones that shipped with this foldable board. This would save another 10 Euro.

A sketch of the construction is here:

First I deconstructed the foldable chess set.

I sawed the supporting wood into small pieces.

Then I could break out this supporting block piecee by piee without damaging the board itself.

Now we end up with two halfs of a chess board.

To create the bottom plate and the one that would hold the reed switches and all electronics, I had to make rectangle precise cuts without an electric saw. I used a workbench and adjusted it so that the middle of the workbench adjusted with the drawn line. The workbench then steers the saw so that I would cut a straight line. This worked suprisingly well.

The bottom plate attached to the chessboard.

The pieces came with some odd fabric glued to the bottom. When scraping it off, I noticed that the pices were slightly bent inwards.

Let’s imagine this is a knight. The pieces are really of very low quality.

Since the pieces were bent inwards, I could directly glue the magnets to them with some cyanoacrylate adhesive. After that, some felt to cover everything.

Some experiments on where to put the reed switches. For my setup with a square size of 42mm, I found that from the lower left corner of a field to the start of the glass bulb, there should be precisely 1 cm. I would recommend slightly larger magnet to have some more flexibilty when placing the pieces, but it works.

Some more measurements.

Finally I had to 64*3 holes. What fun! I also placed some spacers on top, so that the chess board would not damage the glass bulbs of the reed switches. The spacers are orginally intended for furniture, so that the furniture does not scratch wooden floor. They work well, but again: The distance from the reed switches and the magnets should not be too far!

Soldering and wiring everything, bottom view.

Top view, after soldering everything.

The wiring is pretty straight forward, once you understand the idea. Simply connect rows 1 to 8 each to a PIN of the Arduino. These have to be configured as OUT pins and set to high (1), e.g. pinMode(RANK_5, OUTPUT);

Next the columns also go to 8 PINS of the Arduino. These are set as input with pull-up enabled (e.g. pinMode(FILE_A, INPUT_PULLUP);

For each row:

set the row to LOW (0). Then loop over all columns and get the output. If the output is LOW, we have piece there. If it’s HIGH, we have no piece.

In the picture above, row 7 was set to low. If the reed switch is closed, there is a connection between column G and row 7.

Mounting the Arduino certainly wins no price for beauty.

So I mounted everything and was ready to go. The project already had cost me several evenings, and I was pretty exhaustd. Then I noticed two very big problems.

First I placed the chess pieces on the board without making sure the glue was dry. Some glue was oozing through the felt on the board, and destroyed the paint on the board.

The next thing is that I only now noticed, that the chessbaord was very bent. It either came like that from the factory, or I guess that removing the supporting wood resulted in that bending. This however would result in that in the middle of the board, the magnets were too far away from the reed switches. Also during programming, the Arduino hung up and had to be reset. However with the Pro Micro, that’s a very fiddly thing.

I got really frustrated at this point, and wanted to throw everything in the trashbin.

I could now follow two path: </p>

buy more material, i.e. another chessboard, or borrow tools from friends to re-build a fitting high quality one from scratch.
or improvise to rescue the project

In the end I improvised. I bought some squared timber and used the rest of the plywood to construct some kind of wooden cotntainer. I also used masking tape on the plywood to create a chessboard pattern, and spray-painted everything

That’s the final board assembled.

Here and here are two videos of me playing chess on the board. I used a prototype version of my chess GUI Jerry which supports entering moves via keyboard. No sound output yet.

The source code of the Arduino that controls the chessboard is of course open source, and available here. It currently supports castling, i.e. won’t submit the second rook move to the GUI. It currently dos not support sliding the pieces, but in practice that’s no real usability issue. Adding that should be simply though, just some small delay until a piece is identified as having moved.

Conclusion

I have mixed feelings about the result. It certainly is nicer that a flimsy plastic chess computer. On the other hand, I look in awe when people create nice looking chess boards on their own, such as Pewatronic Grandmaster (I’ve only seen it from pictures, but it looks really great. And it also seems to be a one man show, which proves that it is indeed possible to create a high quality board on your own).

However the price difference to a DGT Smartboard is really not that far. So unless you have fun doing such projects, I recommend buying one of these…

The Arduino-based Electronic Chess Board (ArdEBoard), Part 1

8. Februar 202110. Februar 2021 asdfjkljerryHinterlasse einen Kommentar

I was always fascinated by physical chess computers. These were physical units resembling a chess set with dedicated CPUs and programs. They were very popular throughout the 80’s and 90’s but of course got out of fashion when computing power increased, and off-the-shelf PCs outperformed these dedicated CPUs.

Nowadays there remains a very small market for such dedicated units, which can be grouped into three categories:

Electronic/Sensory Chess Boards: These use either reed-switches in the board and magnetic chess pieces to track the movement of the pieces. Another options is to put small coils with different resonance frequencies in the pieces and then detect their presence. The advantage of the latter approach is that by using different coils, one can distinguish between the different piece types. This makes setting up an arbitrary position very easy. The information about the position resp. a move is then sent to a PC via USB or bluetooth. Such boards are primarily intended to record tournament games and also immediately provide the information of the current state of the game and the moves for broadcasting, thereby decreasing the work load of the tournament organizers. But of course they can also be used to play a game of chess against a computer, i.e. by connecting it to a mobile phone or a PC with a dedicated chess program.
Plastic chess computers. These are dedicated units including a chess program. Moves are enterd by physically pressing the source square and then the destination square. A pressure sensor recognizes this and the move is sent to the internal engine. The computer’s move is then shown via some small LC-Display.
Wooden chess computers. These are also dedicated units, usually of very high quality. They act similar to sensory boards, i.e. have coils or reed-switches, but often also small LEDs on each square, so that the computer’s reply is indicated not only via a small display, but also by highlighting the squares via the LED.

What models are out on the market as of 2021?

The absolute market leader for electronic boards is DGT. All professional tournaments use DGT boards. They come in two varieties: Fully wooden ones, ranging from about 500 Euro up to 1000 Euro, and a simplified plastic version for approx. 250 Euro. The latter is quite a deal breaker, as it provides full piece recognition with a high quality (although it’s plastic) build. There is also an Italian company Certabo which makes nice wooden units. The advantage there is that their boards include small LEDs on each square, which make them slightly better suited for computer play.
There are few plastic chess computers. Actually there are only two makers that I know of: Lexibook and Millenium. The Lexibook one’s however seem to be very weak and of poor build quality. Same goes for the plastic models from Millenium. The only reasonable and strong computers here are the Chess Genius and the Chess Genius Pro. They retail for a whopping 100 Euro and 150 Euro resp. The high-quality unit from DGT, the Centaur retails at approx. 350 Euro. As far as I know it does not feature piece recognition though.
Last there are wooden chess computers. The entry level is the Millenium "The King Performance" for approx. 350 Euro. Even though it’s a wooden unit, it does not feature piece recognition. It also does not have reed switches or some other sensory method, but rather a pressure detector, i.e. you have to press down the source and destination square to enter a move. Higher priced is the Chess Genius Exclusive. Then there are really beautiful enthusiast units, from Pewatronic at approx 1800 Euro and the DGT Revelation II at around 2800 Euro. Certabo also offers dedicated chess computer units that connect to their boards. Now, they do really look beautfiul, but the price range really does make it something for enthusiasts only.

So to sum up: The cheapest entry into the world of chess computers is the plastic Chess Genius for approx 100 Euro. The next best thing is the DGT Smartboard for approx 250 Euro.

Now, the plastic Chess Genius doesn’t look very promising. It looks as if the sensor board is so stiff, that you have to press with the fingers on the board in order to exercise enough pressure. The board size is very small, and the display is almost unrecognizable.

So I’ve put myself on a challenge: Can I build my own sensor board for around 100 Euro? I took my inspiration from Berger’s Solus Chess. There, he took an existing chess board, integrated a reed sensor matrix, attached magnets to the pieces, and wired everything up with an embedded system that acts as a USB keyboard.

Now there are two major issues that I identified:

The price range. On his website, Berger reported that he spent around 213 Euro. Even though this unit included a Bluetooth connection, which I omit here, the price remains a challenge. This is due to the cost of the chess set in the first place, but also the cost of the reed switches.
The wooden construction. You can see on Berger’s page, that he apparently is skilled with wood-working and has the necessary tools. I have a hand-saw and an electric cordless screwdriver, and that’s it. In particular I do not have a circular table saw, which from my experience, I simply required to make precise cuts. I could buy these tools, but this would exceed the 100 Euro cost-limit by far. Also I currently don’t have the space to store such things.
The electronic construction, i.e. the soldering, and the programming of the embedded system. For me, this is the easy part.
The general lockdown. When I started this project over Christmas, Germany was (and still is) in complete lockdown. That means all home depots are closed. You can pre-order and collect, and then there is Amazon, but all that is very cumbersome. For wood, you need to feel and check before buying. Also I often get better construction ideas when I see the available products.

So let’s go.

Rough Ride

8. November 20208. November 2020 asdfjkljerryHinterlasse einen Kommentar

The last blog entry was about optimizing a C++ based PGN parser. There are only two people that I know of who have the computer-science knowledge to really understand my suffering.

One is a colleague of mine. So after writing this up, I went to his office room and shared my pain. Accidently, he already read my blog entry.

Now, I was expecting something along the lines of „Wow, writing your own C++ allocator – that’s absolutely awesome, great“.

But after telling him the whole story, he was more like „Wow. That’s messed up. Why do you do this to yourself in your freetime?“

I reached out to person number 2 via Facebook. His reply was: „Friends don’t let friends write C++“.

And these endless hours of debugging and not making any progress really made me think. Together with the blo series about a challenge optimizing a dictionary app as presented by Raymond Chen (see previous blog entry).

During the pandemic, I save approx. 1.5h per day of commuting time due to working from home. I decided to invest this time in a little experiment: Rewrite the whole chess-logic and PGN parser in Java and compare the result.

While porting, I found several bugs in the C++ code. Compared to that, the Java code was a breeze to write. Full stack traces, easier debugging, better tooling (IntelliJ, build systems like Maven etc.)… programming was fun again.

And while I was at it, I also ported the GUI using JavaFX. And the result is Jerry 4.0.0. Version 4.0 is a complete rewrite in Java. Windows binaries are here, and for Linux there is also a Snap. It has 99% percent of the old features of the C++ version, plus, given a chess position and millionbase, it requires approx. 10 minutes to search for it. Not great, but acceptable.

There is sometimes reluctance against Java based programs on the desktop, which I’d like to address:

Java doesn’t look „native“: However few programs nowadays look native. In fact „native“ often looks outdated, and especially on Windows with different frameworks like WinForms (based on GDI) and WPF (based on DirectX) and UWP it’s not clear what „native“ actually means. JavaFX together with JMetro provides a fresh and modern look on both Windows and Linux.
A JDK or JRE is required as a separate download, which is annoying for users: Java 14 has japckage which allows to simplify application distribution both for users and developers by creating native application packages. On Windows you download a typical installer, and I doubt that users would even notice it’s a Java program if I wouldn’t mention it here.
Java applications are slow to start: So are any complex GUI applications. My benchmarks indicate that in fact the JavaFX rewrite of Jerry is faster to start than the old Qt version. Plus, it’s way easier to add a startup screen to a Java program (thus indicating progress to a user) than with Qt – from my experience
Java + the JRE creates a hughe overhead in terms of program size: JerryFX including all libs is approx 200 MB unpacked. The old C++ version was approx 125 MB unpacked. With todays broadband speeds and common storage sizes, this is more than acceptable. Note that even a complete native version in C++ for Windows would likely require Visual C++ Redistributable which is in the order of 20 MB.

In other words: Nowadays, Java provides a desktop experience that easily matches native and other cross-platform solutions.

Thus all in all, I am really happy with the result. The current version is a really good foundation to finally add all those features which I have envisoned, while having a high amount of productivity. I usually code late at night after a long and exhausting day of work, and coding in Java especially frees my mind from thinking about memory allocation all the time.

Towards fast PGN Parsing

29. Februar 20201. März 2020 asdfjkljerryc++, chess, parsing, PGN, Qt1 Kommentar

PGN is the de-facto standard for chess games, especially when it comes to interoperability. Unfortunately, PGN is somewhat misdesigned. Apparently, it’s not just me who thinks so. PGN is designed to make it easy for humans to read PGN files, and edit or write them manually with a text editor. At a cost, namely that it’s difficult to parse it with computers.

The odd thing here is that PGN files are rarely created manually, almost everyone uses a chess program to enter or edit moves, and then save the game afterwards. That’s the basic mis-design.

The main difficulty in parsing PGN files – aside from a lot of ambiguities – is SAN notation, i.e. the source-field of a move is missing. For a human it’s easy to spot the source-field, but for a computer it means that the program has to know the chess-rules to figure out which move is executed (there are shortcuts, as described below).

Nevertheless, PGN is here to stay, and so my goal is to quickly parse huge PGN files in order to be able to search for arbitrary positions. Even though Jerry is not primarily database program, such basic functionality should be present.

Jerry 3.0.1	120593
New Parser, compute only pseudo-legal moves	28791
above plus -O3 optimization turned on	24000
above plus pool allocation for nodes	16000
above plus piece lists	14016
above plus no pseudo-legal move generation if only once piece	11842
above plus no QString uci as class member of Move	7352

PGN parse speed (KingBaseLite2016-03-E60-E99.pgn)

When I originally implemented PGN parsing, I took a look at python-chess – really excellent, easy to read code. However not optimized. The algorithm was like this:

read each line in the PGN file
split the line into tokens (like a move token, annotations, comments etc.)
for each move token
    extract the target file and piece type (and row/line disambiguity markers)
    generate all legal moves in a position
    find the unique move among all legal moves of that piece type and
    target file

I benchmarked this by reading each game from a subset of the KingBaseLite database and constructing the full underlying game tree for each game. That’s the first line in the table above. Incredibly slow. Can we do faster?

Initially I tried to reuse an exising fast parser from other open-source projects, but realized after some time that this would essentially result in a complete rewrite of Jerry, due to very different underlying data-structures and game representations. Realizing cost me approx. three month, so this was quire annyoing. In the end, I decided to optimize the existing implementation.

So why is the above version slow? I split the line into tokens using QRegularExpression matches. After tokenizing a line, I again made heavy use of QRegularExpressions to get the target file. It’s likely faster to manually create a parser by checking character substrings in a line and then continue accordingly.

Another point is that we don’t need all legal moves. First note that for pawns, we can directly determine the source-field of a pawn move (e.g. for e5, the pawn has to be on e4, for e4 it has to be either on e3 or if e3 is empty then it’s on e2 etc. So we can concentrate on piece moves.

Suppose that we can already uniquely identify a piece move by just computing the pseudo-legal moves. Then either it’s that move, or the PGN is incorrect. In either way, it makes sense to just execute the move, it’s our best bet. The next version (line 2) was thus:

manually parse each line and check for move tokens
for each move token
    if it's a pawn move, directly create a move by considering the target 
    square of the pawn
    if it's a piece move, then create all pseudo-legal moves, taking into
    account the piece type and the target square.
    if we uniquely find one move among the pseudo-legal moves, execute it, 
    otherwise generate all legals moves. If we still can't identify the move,
    abort

An improvement of factor 4, but still: Can we do faster?

A simple speedup is to turn on compiler optimization (O3), cf. line 3 in the table. Ok, but can we do faster?

In the implementation of Jerry, a game is a tree-structure, where each node represents the current board position, the move leading to it, comments. Children of the node are the main line as well as other variations. When readin each game I had a loop:

while(hasNextGame()) { 
    Game *g = PgnReader.read();
    // do something with the game, e.g. search for a position
    delete g;
}

and the PgnReader would of course always create a new game with Game *g = new Game() and then add nodes to it while parsing. New is malloc in C++, and that’s costly. Thus I considered a custom allocator. There are fancy ways of doing, but since this is here limited to only nodes, a quick and dirty approach was to create a FreeList of nodes and initially create a decent number of nodes (thus reserving memory once at program startup). Then whenever a node is needed, it is taken from the FreeList. Instead of calling delete after reading the game, the nodes are put back on the FreeList and re-used. I call this pool-allication, even though it’s not a reall pool-allocator.

This again almost halfed the time required. But – can we do faster?

Jerry internally uses a mailbox-structure (i.e. a 120 array) to represent a board. (Pseudo)legal move generation for a particular piece-type is then as follows. Suppose we are looking for all white knight moves:

for each of the 64 squares (a subset of the 120 array):
    if the square is not empty, and the square contains a white knight: 
        create all (pseudo)legal moves for that knight

Another approach is to use piece-lists in a addition to this board array. This is then simplified to:

get the piece-list for white knights
for each entry in that list: create all legal-moves

The penalty here is then whenever a move is applied, in addition to updating the board-array we also have to update the piece-lists. However if we implement the piece lists carefully as arrays with fixed size (i.e. no new, and thus no malloc) and carefully update only the piece that moved when applying a move to the board, this gave another small improvement (line 5).

Another small optimization is that with piece-lists it’s easy to check if there is only a single piece (i.e. a single white knight) in the position. If so, then we can even skip pseudo-legal move generation. Either the PGN is correct and it’s this only white knight that is moving to the target square, or the PGN contains an illgal move and then it’s still better to just continue compared to just aborting to read the PGN altogether.

That’s the version in line 6. Ok, but can we do faster?

Well after a lot of performance analysis with valgrind/massif, it turns out there was a hidden malloc all the way along. I should have spotted this earlier, but this is tricky. Jerry relies heavily on Qt datastructures, and especially on QStrings, which simpify handling encodings (such as UTF8) a lot. My datastructure for representing a move was basically like this:

class Move
{

public:

    uint8_t from;
    uint8_t to;
    uint8_t promotion_piece;
    QString uci_string;
...
}

Move generation is then similar to this:

QVector<Move> pseudo_legals;
for ....
    pseudo_legals.append(Move(...))

But QString has implicit sharing, and that means it’s content is stored on the heap. So each Move creation, even if it’s seemingly on the stack, has a hidden malloc, when the uci_string is created as a class member!!!

Same thing with a QMap that I used to store a transposition table as part of the game-board class.

After removing the uci_string from the Move class (we can create uci_strings on the-fly when required, that’s no real slow-down as uci-strings are only required for engine-interaction), we arrive at the last version (line 7). And I am out of ideas.

There are other small optimizations that I applied along the version, e.g. using QString::fromLatin1( ), better code-flow etc., but all in all, I am out of ideas.

Let’s see, how we compare. The test is to take millionbase, and, depending on the functionality of each program/library, either just load each game from the PGN, or search for a particular position. The current implementation isn’t optimal, and likely will never beat Scid, but it’s sufficient to work with it in practice, I guess.

Scid	0:50
Fritz 17	4:02
Jerry, optimized	4:12
ChessX	> 30:00
chesslib (Java)	> 30:00

PGN parse speed (millionbase-2.22.pgn)

Still, lot’s of clean-up and edge-cases w.r.t. the PGN format to consider, but we’re getting there.

All in all, this profiling and optimzation took quite some time and ressources.

I recently read an excellent series of blog posts. This is a good entry point. Basically Raymond Chen (the „Mr. Windows“ Raymond Chen) created a small Chinese dictionary application in C++. Rico Mariani did a quick port to C#. It turned out that the quick port was significantly faster than the C++ version. Raymond Chen had to do some heavy optimizations (including writing a custom allocator), rewriting and profiling to get a faster version. A good overview is here.

This looked very similar to my problem, and so I often get envious when looking at managed code, i.e. languages like C# and Java. On the other hand, there there is either no decent cross-platform GUI toolkit (C#) or quite problematic deployment (JavaFX). This is why I added chesslib in the above comparision. This seems to be clean-looking straight-forward but non-optimized code. Just for comparision and to self-assure me that writing Jerry in C++ was the right decision.

Or was it? 😉

Previously on… Building Jerry

25. März 201925. März 2019 asdfjkljerry1 Kommentar

It’s been quite some time after the last blog entry. What happened inbetween? Significant changes in my private life prevented me from focusing solely on developing.

But aside from that, the development of Jerry never really stopped. In fact I spent quite some time on adding database functionality. I even wrote a complete spec on how to store chess games in a straight-forward binary format. Implementation took quite some time, testing, debugging and effort.

In the end I was very short before releasing a new version, but testing revealed a serious flaw: Importing large PGN files took extraordinary time to parse and convert into the internal format. The time required was simply unacceptable. Which made me realise that before going into any direction w.r.t. databases, this PGN parsing part first requires some significant overhaul.

There was another issue, namley that inventing yet another binary format for chess databases is a bad idea. On the open source front, Scid (.si4) is the de-facto standard when it comes to chess databases. The other one is of course Chessbase (.cbh, .cbv), which is unfortunately proprietary and not openly documented. There has been some reverse-engineering work done, but this is of course very informal. Hence I’ll aim for .si4 compatibility, first.

While Scid is open source, there is no well written spec, so everything has to be inferred from the source code itself – this is quite tedious. Currently I am working on writing down something akin to a specification of the Scid file format. Progress is slow, as specifically the encoding of chess moves is tricky.

What other things are new?

The current version of Jerry (3.1.0) has some serious „under-the-hood“ work done. Especially when it comes to writing proper, encapsulated modern C++, i.e. things like Return-Value-Optimization, fixing several memory leaks etc. I have to admit though that code written in the evening after a long day of work simply has not the same quality as production code.
Thanks to the nice folks at Debian, Jerry is now available in Debian Sid (unstable).
The Apple MacOS port is abandoned. Jerry can still be compiled on OS X, but I simply don’t have the hardware available and can’t afford the hefty prices right now. Plus Apple makes it harder and harder to acquire compilers for OS X, i.e. even if not technically required, there is essentially another $99 per year to join the Apple developer program.

Version 3.2.0. is currently in the pipes. New features include the ability to handle large PGN files (large, as in Millionbase – large), as well as a new GUI that features a ribbons instead of menus. Yes, ribbons (I personally just prefer them). The homepage has a screenshot.

Version 3.2.0 is feature complete, and I am just testing for a few more weeks to make sure no showstopper bugs are present. Stay stuned!

Foxy Openings 97

3. Oktober 2016 asdfjkljerryHinterlasse einen Kommentar

Queens Gambit Accepted by IM Andrew Martin.

A small in-between post: I was recently looking at Queens Gambit Accepted. There is a foxy DVD (nowadays downoadable video) available. However this is just video, and the games are not available as a pgn download anywhere.

The 15 games (PGN file format) can be downloaded here. I also included a text-file with index, i.e. giving an overview of the variations and the offset (minutes:seconds) on which each game starts.

Few points concerning the material itself: The games are sometimes pretty obscure, but from strong players (2200+), so that’s okay. The video itself does not show player names, so I had to infer from IM Martins English pronunciation of foreign players and events the actual games… all in all it took me one afternoon to find all of them.

Personally I do not take much from the commentary of IM Martin, the video and analysis seems very rushed and superficial. Moreover I do not think that strategic motives are explained well enough for intermediate players, such as myself. Instead you’ll hear a lot of statements in the style of „… and it gives black a good position“. He also shows and analyzes games during the middle- until the endgame, imho just to kill time. I bet that doing DVD series and videos is usually paid very low for authors, and so is often the quality.

Nevertheless the selection of games and selection of variations is really sound and easy to play. So you could probably just look at the games and analyze them directly. On the other hand, the video is approx $9, so that’s not that much either…