Welcome back - or so I hope - for yet another exciting installment of the grand, illustrious and ultimately pointless epic of “What have I wasted my freetime on in recent years”. This time around, I shall tell you about the royal game, i.e. chess, or rather of my humble attempts at contributing to its rich ecosystem of non-human players.

I will begin by explaining what I am talking about, briefly¹ recap the fascinating history of computer chess and in the course of that highlight the importance of game playing for showcasing, popularizing and driving machine intelligence research as well as its public perception. I shall further elaborate on my personal connection and love for the game and detail why - even in the face of a recent uptake of machine learning based techniques far more successful than my puny attempts could ever hope to be - an old-school, classical approach can still be a valuable investment of time and energy.
Afterwards, once my poor readers have slogged through this somewhat unnecessary prelude², I will get just a little more technical and provide a high level explanation of the general structure underlying many chess playing programs, culminating in a walkthrough of code implementing the UCI protocol used to communicate with GUIs and other programs pitting different human and non-human connoisseurs of the game against one another.
As a loyal and faithful reader you will, of course, have realized that this is quite similar in nature to my initial game boy emulation article, in that most of this post is focused on motivations, history and providing an overview, with only a very brief fragment of code at the end. Unlike that time, however, I do not restrict myself to publishing only selected snippets within an article but have already released the complete code for a working engine into the wild. All of this sounds like kind of a huge undertaking, so before I lose your valuable attention, let’s dive right in.

What is an engine anyway? - A brief history

Imagination

Reality

Dominance

Why?

Introducing …

How?

Overview

UCI

Outlook

What is an engine anyway? - A brief history

I will, from this point on, begin throwing a bit of jargon around, which might cause a minor amount of confusion. As confusion could lead to stress and nervous tension, which are now serious problems in all parts of the galaxy, I will attempt to not exacerbate this situation further by revealing at least some terminology in advance.

Contrary to popular opinion and willfully ignoring some popular applications of the word “engine”, I am not talking about cars, as those have rather little to do with chess and programming. Yes, they might be tangentially related, as self-driving cars are somewhat in vogue right now and also a topic of machine intelligence, but this connection is almost as tenuous as my interest in automobiles.³

In case the term is new to you, dear reader, allow me to clarify: When we use the phrase “chess engine” we quite simply refer to any program that is capable of playing a game of chess. You somehow feed it a representation of a given game state and it chooses a move it deems wise. That is all there is to it. Seems trivial, right?

Imagination

The idea of and desire for a program fulfilling this specification is indeed so blindingly obvious that it predates even the computers that could run it. In what is slowly but surely becoming sort of a theme in my articles - and not entirely unintentionally so - the basic concepts we rely on are, of course, based on work the great Alan Turing and others did somewhen in the 1940s.

Actually, the history here goes back significantly further, centuries even if you allow for various ‘fake’ chess playing automaton regularly displayed to amaze, entertain and dazzle nobility as well as the general public, the most famous of which likely being the Mechanical Turk.

The Mechanical Turk

This elaborate ‘machine’ was originally constructed by Wolfgang von Kempelen in 1770, toured throughout Europe, playing various illustrious celebrities in the process, was bought by Johann Nepomuk Mälzel in 1805, who exhibited it for another 33 years in even more areas - now including the United States, Canada and Cuba - only to eventually be lost to a fire in 1854.

Even so it turned out to be an elaborate hoax that managed to hide a skilled human operator within the devices seemingly complex interior, its mere existence and more than 60 year long reign during which it captivated the imagination of many an intellectual is quite telling. Consider, for a moment, the sentiment expressed by the great Penn Jillette in this short clip when discussing a scene from the movie The Prestige:

[…]There is a sense that movies never get, where everything being done in a magic show has to be in some way plausible. […] If a trick is so perfect that there is only one way to do it, well than that is the way you did it.

When you attend a magic show, you obviously know you will be fooled. Magicians happen to be the most honest liars you could possibly encounter, so they usually tell you upfront, directly or by implication, that what you will observe uses no supernatural powers, no divine intervention or other impossibilities, only lies, deception and trickery. If they do their job well, than despite your best efforts to see through it, regardless of your unwillingness, your disbelief is suspended. For a brief moment, in spite of all your knowledge and better judgment, you are left utterly dumbfounded, stunned, forced to question the very nature of your reality.⁴ Nonetheless, if the effect presented is too outlandish, too extreme, it dulls the wonder. Disappearing some huge public monument, to me, holds far less magnificence than an apparently simple card trick.

This rings even more true if you are trying to sell something as not a trick⁵, which goes to show that automatically playing a game of chess must have, at the time, seemed fantastical, absolutely wondrous and almost entirely impossible. Almost. There was this tiny sliver of hope. What if it were actually possible? What if Mälzels Machine were in fact just that, a machine? What other feats of mechanical wonder would be possible? How much farther can technologies boundary be stretched?

It is precisely this atmosphere which is evident in the opening paragraphs of a famous essay written by the illustrious Edgar Allen Poe and treating the subject matter of the Turk. He describes the automaton as “an object of intense curiosity, to all persons who think”, some of which pronounced it “the most astonishing of the inventions of mankind” and compared it with the “calculating machine of Mr. Babbage” - described with clear reverence - claiming even it would be “altogether beneath it”, were it real.⁶ He then proceeds to meticulously describe, analyze and dissect observations of the machines exhibitions and presumed workings to outline an argument for why he believed it to be an illusion and purported to reveal how said illusion was achieved.

Now, I absolutely adore Poes prose and whilst one could claim that especially The Masque of the Red Death was rather clairvoyant and bears eerie similarities to current events, not everything in this particular article has aged quite as well. Most of it is well reasoned and shows careful deliberation, yet a number of competing explanations are deemed obviously absurd, not meriting even a refutation, whilst the prospect of the machine being a true automaton, acting without human intervention and trickery, was deemed preposterous on the assumption that it was not playing perfectly enough. On the other hand, he asserted that the ability to play chess is in some way fundamentally different from computation, thereby both over- and severely underestimating technologies potential.

A pure and perfect fully autonomous chess machine was eventually constructed in 1912, almost a century after Poes essay. El Ajedrecista did not play an arbitrary game from beginning to end, but restricted to one specific ending - two kings and one rook - it invariably managed to checkmate its opponent. Just a few decades later, with the advent of general purpose computing, development accelerated significantly and complete - so not necessarily good - games played automatically were no longer constrained to mere fantasy. Effort from this point on, however, shifted more to the programs and algorithms used rather than mechanical contraptions controlled by it. Nonetheless, even in this regard, we have have come a long way. Some of the brilliant products one could buy today⁷ certainly would have exceed even the vivid imagination of a brilliant writer like Poe, seeming so far beyond comprehension to be indistinguishable from real magic.

The topic of early hoaxes and machines - as you can see - is rather extensive and cannot possibly be done justice in so small and puny a blogpost. There are some glaring omissions and much more fascinating details to be researched. Several books can and have been dedicated to the subject and some more could clearly be written, but are quite certainly out of scope for this article.⁸ Which is why we return, once again, to Turing.

Reality

In the early days, at a time when the field of computer science itself was still in its infancy and physical computers were playing catch up with the brilliant minds of their creators, B. V. Bowden set out to publish a small volume detailing the history, present and likely future of digital computers. Addressed at a general audience, Faster than thought collected very accessible contributions by many eminent scientists of the era and is, even today, well worth a read in its entirety.

What I would like to draw your specific attention to right now, however, is a fascinating article submitted by Turing. Not only did this rather short read break new ground by introducing a contender for the very first chess program, the explanations it contains are among the most lucid and illuminating I could find on the topic of game playing, with many of the concepts and ideas still relevant and in use today. In addition, this seminal paper can serve - not entirely unlike Poes treatise on the Turk above - as a wonderful lens by which to glean the perception of and attitude towards computing in those days, as I’d claim all writing, even technical and explanatory one, in some way reflects the society in which it is produced.

For instance, I mentioned earlier that with the rise of electronic computers effort shifted from machines to programs and a quick perusal of the paper will yield a concise explanation of why this might have been the case. After outlining the questions it seeks to answer, it contains this small gem justifying the approach taken:

“could one make a machine to…” might equally well be replaced by “could one programme an electronic computer to…”

This alone serving as ample justification illustrates just how far public understanding had progressed. No longer was a game playing machine considered altogether above a mere calculator. On the contrary, it seemed almost self-evident that if it could be built at all, it could be expressed as a calculation. Computers were slowly starting to be recognized as the very epitome of machine.

To drive home this observation and emphasize the grand promise it held, please allow me to quickly point out two special questions listed at the papers beginning:

Could one make a machine which would answer questions put to it, in such a way that it would not be possible to distinguish its answers from that of a man?

Could one make a machine which would have feelings like you and I do?

Whilst Turing concedes these might not be directly related to the problem at hand - that of chess playing - he claims they are nonetheless connected and likely to be at the tip of the readers tongue.⁹ In this particular work - as well as in this post - such intriguing questions are merely raised, pondered very briefly and then brushed aside, as the author proceeds to prove the central claim: That a machine could be made to play a game of chess.

He does so by first describing clear, deterministic steps such a machine should take and then, lacking a computer capable of actually executing such a program, promptly does it himself.¹⁰ The human imitating the hypothetical program later dubbed TuroChamp might have lost to a simple fork, but to my eyes, this does not make the achievement any less monumental. If there was even the shadow of a doubt left about the possibility, this game was more than sufficient to eradicate it. The stage was set for real engines to be created.

Turing himself later attempted to translate his descriptions into a working program, ambitions which were unfortunately left unfinished. As his life was tragically cut short by a society too cruel and backwards to deserve him, it was left for others to pick up the mantle and continue the work. The list of those who did reads almost like a who’s who of eminent computer science pioneers: Claude Shannon, the man who introduced the term bit, provided us with an estimate of the games complexity and a useful classification of search algorithms. John McCarthy, inventor of Lisp and garbage collection, proposed Alpha-Beta Pruning. Donald Knuth, who really should not need an introduction among my readership, analyzed it in detail and in so doing formulated the notion of the different node types. Ken Thompson, well known for C, Go, Awk and myriad other miracles, contributed to Belle and was involved in the creation of the first endgame tablebase.

This was but a small selection and I glossed over many a contribution, but you get the idea. What was fiction turned into solid theory, which turned into reality. Eventually, in 2012, even Turings original paper machine was finally constructed as a real, functional computer program and managed to play what was described as a passable game against the great Garry Kasparov, which it lost in 16 moves.¹¹ That story might, for most of my readers, evoke some memories, as the name Kasparov is of course also inextricably linked with yet another famous and fateful human vs computer match…

Dominance

With playing a game of chess now not only a possibility but a reality, the discussion shifted again, to whether a program could play chess better than a human could. Not just any human so, it had to be the best of the best.

You see, the battle for most of us was already lost very early on. Nonetheless, when we hear a prominent AI critic first mocked chess computers for losing to a 10 year old, only to subsequently lose to a machine in the 60s, it might be an amusing story, but it doesn’t really impress us much. After all, it is just the failure of one man and he - like most of us - was merely an amateur. As long as somewhere out there, there existed at least a single human being who could still reliably best the machines most of the time, we felt safe in our superiority. If one of us is better, we all could be. Humanity still reigns supreme.

It is fitting then, that when in 1997 IBM organized a much publicized match of its custom built Deep Blue chess computer against Garry Kasparov, then incumbent world champion and seen by many to this day as the greatest chess player ever, Newsweek magazine not only ran a piece on it but sported a cover adequately expressing the weight placed on one solitary humans shoulders:

"The Brain's Last Stand"

Printed in the lead-up to what was to become a historic event, Kasparov was quoted as stating “This is much bigger than a world-championship match”. And indeed it was. The rather meager 500 seats available to watch live were sold out and millions throughout the world actively followed the games on IBMs website.¹² This match was special. It was not just one man and he was the very opposite of an amateur. This man had not lost even a single match in his entire career. If the machine could beat him, it could beat everybody. He was humankinds champion. The brains last stand. And he lost.

Much has been written and said in the immediate aftermath of the event, mostly downplaying or elevating the scope of the achievement, revelling in either its significance or lack thereof. The match itself was riddled with controversy as the clash of business interests, a spirit of scientific inquiry and the chess players competitive personality gave rise to a battle fought almost as much away from the board as on it. When early on the machine did not play perfectly enough and decided on a move - later assumed to be caused by a simple bug - that seemed almost too human, Kasparov began to suspect foul play and grandmaster intervention, an accusation he hinted at in thinly veiled comments during a press conference. Coupled with the companies generally adversarial treatment of the world champion, like uncomfortable conditions in the playing hall, not providing any games to study his opponent and their inability to convincingly refute his accusations by providing logs, Kasparov grew enraged and convinced his opponents goal was to crush him, not by superior chess playing, but by any means necessary. Atypically for him, the grandmaster never quite managed to regain his composure.

So once victory came, it was not glorious. The triumphant team was not only booed but instructed to not smile, lest such reckless gloating could hurt stock prices. The machine was quickly dismantled and a rematch request denied. The grand winner proved to be not computer science, but IBM, whose value skyrocketed, whilst the consensus soon seemed to be that it wasn’t Deep Blue who won the match, it was Kasparov who lost it.

If one were to look for a pivotal point, there are a number of other candidates of arguably equal or maybe even greater technical importance, even so they were much less advertised outside of specialist communities: The first Deep Blue match, one year prior, contained the first game won by a chess computer against a reigning world champion, paving the way for the rematch and defeat in 1997. In 1998, a match was held between Viswanathan Anand, then world number two and later world champion, and the commercially available chess engine Rebel running on consumer grade, not specially built, hardware and was won by the machine. In 2002, Vladimir Kramnik, the man who eventually dethroned Kasparov, sparred with Deep Fritz in an event dubbed Brains in Bahrain and despite being given several advantages only managed to score a draw.

Nevertheless, to the general public, this one fateful encounter in 1997 marked the end of an era, the public culmination of more than half a century of research, the last time any human could realistically hope to beat the best of the machines. The end of our dominance and the beginning of theirs.¹³

After the match, Kasparov continued to dominate the human chess world for a while, eventually retired into politics and became a fervent advocate for cooperating with machine intelligence to maximize both of our potential.
IBM, meanwhile has moved on to other ventures, but still sees the value of game playing for advertising progress. Not only has their Watson system defeated humans at Jeopardy!, another system of theirs participated in a competitive debate.
Chess engines since have inexorably marched on and exploded in strength. When Kasparov, in more recent interviews, points out that modern engines would laugh at the moves made by both him and Deep Blue and smartphones could easily crush IBMs monster, it is not only true but also not only a statement about the progress in hardware.

Why?

More could be said, but there is work to do and your time is valuable, which is why I shall end my history lesson at this point. I believe it is evident that at all times, since the very inception of computer science and even long before that, game playing was stretching and redefining what was considered possible with mere machines.

Which is all very interesting, yet why should I - or worse, even you dear reader - bother to replicate the brilliant work of others? This story is beautiful, but it clearly sounds as if it had already ended? Why push for yet another unnecessary and unsatisfying sequel? Haven’t we had enough of those lately?

The short answer is - as with pretty much all topics covered on this lovely blog of mine - because it is interesting, fun and educational. I really cannot stress this enough, so at the risk of repeating myself, allow me to stoop down to the level of argument from authority:
With big companies, like IBM and Google, there are obviously economic interests and publicity at play, but that is not sufficient to explain the motivation of all the above mentioned outstanding individuals to spend time and energy on a problem which is ultimately no more than a pleasurable pastime. Apparently, an interest in game playing programs is - at least superficially - linked with an interest and excellence in computer science. What better method is there, than imitation, to truly grasp what it is that feels so fascinating, what drew in all those brilliant people to lay the foundations I and myriad others can now build on? ¹⁴ There are giants on whose shoulders I stand, yet I fail to see as far as they did. I would love to change that.

“Well ok then”, I hear you concur, “but why chess? Why not Go? Why not Shogi?¹⁵ Why not Arimaa?”. The reason here is twofold.

On one hand is obviously my personal love for chess. It already captivated me when I was taught to play the game by my stepfather in my early teens, but ever since me and a bunch of good friends¹⁶ managed to survive a particularly boring and tedious stretch of school by continuously playing behind our “teachers” backs it irreversibly managed to occupy a very special place in my heart.

On the other hand, the story is far from over. There is the occasional, rare sequel that turns out to improve upon the original. After it turned the world of Go upside down with AlphaGo 4 years ago, DeepMind continued to crush its own creation with yet another devastating innovation, which it promptly applied to chess to defeat the strongest engine to date. Leela, the open source descendant of this experiment, continued to push chess engine development into less established and more innovative directions. Just a little more than a month ago, Stockfish(and various other top engines) absorbed NNUE, an evaluation technique originally developed for shogi to gain a never before seen jump in playing strength. Computer chess today is more vibrant and fast moving than ever before.

“Alright”, you concede, “but do you think me a fool?! I looked - as any diligent reader should - at the code you linked and it does not apply any of the wondrous things you mentioned. There is no NNUE! There is no MCTS! Not a single neural network in sight, nothing special, just plain old alpha-beta and hand crafted evaluation functions! Justify yourself!”

Ok, you got me. I admit, I am not quite there yet. Even so I admire the progress made, I just can’t bring myself to like the methods used. Machine learning in general and neural networks in particular are far more useful than they have any right to be. Unfortunately, you can’t argue with results and GPT-3 has clearly taught us that quantity has a quality all its own. Nevertheless, the fields unnaturally successful approach of beating quality with quantity, processing power and energy just doesn’t ring right with me.

With four parameters I can fit an elephant, and with five I can make him wiggle his trunk.. And with a few million we can win at chess, but what have we learned?¹⁷

Classic, hand crafted evaluation functions can explain themselves. Many parameters are, of course, found by automated tuning and it is hard or impossible to see why any particular one is right or wrong. Nonetheless, by inspecting how they turn out, I can learn something and gain understanding previously not available to me. By inspecting which weight is given to which feature of a given position, I myself should ideally be able to improve.

Neural network powered engines, on the other hand, are much closer to a real black box and it is often impossible to understand the solutions they provide. No useful information can be gleaned from their output except the obvious: which move was chosen and how likely a specific outcome is believed to be. It is nice to know that the answer is 42, but without really knowing which questions we asked the only ones to really profit are pundits proclaiming to know what they cannot.

As such, at least for now, I shall keep my Pokemon Syndrome - wanting to be the very best - in check, stubbornly refuse to bow to the overwhelming power of the networks and try to see how far I can get without them. I am fully aware that my behavior is unnecessarily and unjustifiably prideful, whilst my understanding of what I am criticizing remains severely lacking. Yet, this is supposed to be fun and educational, so I shall do it my way, all shortcomings included.

Introducing …

And so we - once again - arrive at a point in an article where I perform a sudden and abrupt turn and the tone switches from one of calm, dispassionate objectivity to overtly emotional and sentimental. You see, when introducing this topic I mentioned in passing and comically warped the slightly worn Newton quote about standing on the shoulders of giants. Well, here is one giant unlike any other on whose shoulders I stood, leaned and sat:

Engine Logo

You are looking at a picture of my father¹⁸, now 61 years of age. Or he would have been, had he not died suddenly and tragically slightly more than one year ago. There is so much more I have to thank him for than I could adequately express here and unfortunately more than I managed to express in his lifetime. Without his upbringing, his influence, I would not have developed the necessary patience, perseverance and confidence to complete and publish a work like this. As such I would like to dedicate the release to his memory. I have long struggled with naming my engine - we all know the adage about the two really hard problems in computer science: cache misses, naming and off by one errors - and for far too long a time my working title was the beautifully arrogant, self-centered and simplistic ‘philchess’. Now, if it were punny, I could accept that, it would be a good thing. Madchess is a brilliant name, I love it and Erik Madsen deserves all the credit he can get for his helpful and wonderful blog. But with my name, this just doesn’t work. Hence, I have now decided to baptize my engine paulchen332, reusing the online handle my father adopted eons ago. Allow me to introduce you:

Engine Logo

It might just be a tiny pawn now, but its aim is to be the very best, it just got serious - as you can see by the turned cap - and it needs just one small step to become the strongest there is.¹⁹ You can pay it a visit by heading over to github ;-).²⁰

How?

If you have read from the very beginning, dear reader, and managed to stay with me up to here, I would like to thank you for your incredible patience, commend your study of history and express my eternal gratitude. If you have not and simply skipped to here, I am most grateful for your interest in my work, glad you could join us and urge you to read on, as I finally begin to explain just how a chess playing program actually works.²¹

In my glorious introduction, I pointed out structural similarities this article shares with my first one about gameboy emulation. The parallels do not stop at simply being structural so. Just like the work on my emulator, in the grand scheme of things, this is all rather insignificant and hardly innovative. What I have done and what I will write about is not exactly new. Others have done great jobs and I have not fundamentally reinvented the wheel. My implementations are, however, my own. I have put considerable thought into every detail, I have adjusted known algorithms to serve my own needs and I try my very best at providing the most accessible explanations possible. I hope and believe my perspectives and approach will be enlightening and of use to all of you, if only in part.

Overview

On a very, very high level, I have already specified the requirements our program has to fulfill at the beginning of our history section. Allow me to reiterate this most complicated of descriptions with some much needed visual aid:

Game State -> Engine -> Best Move

That is really all there is to it. The details responsible for how we get there, however, might be a little more involved. Despite the wonderful illustration above, the task before us might still seem ever so slightly daunting and even you, my most lovely and intelligent readers, might be stumped as to where to start.

The problems already begin with the apparently simple input and output this construction demands, which I have left woefully underspecified. What exactly constitutes what I described as the “game state”? How is it conveyed? What does it mean for a move to be “the best”?

Answers to those questions are not exactly trivial and deserve at least one article each²², but they can guide us. To help us get going at all, we can even simplify a little. For reasons I shall elaborate on in one of those future articles, which move is best cannot necessarily be determined with certainty in most positions. As such, if we were content with playing very, very badly, with the occasional brilliancy interspersed, simply choosing one move at random is perfectly sufficient.

This might seem significantly easier, yet when thinking about it for a few moments, we encounter another issue to be solved:

A nonsensical move

It is impossible to move from a1 to a3 here, as the piece on a1 is neither a rook nor a queen, but a bishop. Not all moves are possible at all times.

Further, not all moves which seem possible at a glance are necessarily legal:

An illegal move

Capturing with the pawn on h4 in this position would expose our king, which could subsequently be viciously slaughtered by a member of the clergy, something the rules do not allow.

There are multiple other intricacies and subtleties involved, mostly with castling and en passant. Which leaves us with the following conclusion: In order to determine which move we should play, we must first know which moves we could play.

This interesting problem, of determining legal moves for a given position, is called - unsurprisingly - move generation and is one of the most frequently employed parts inside a chess program. As such, it turns out to be a major target for optimization.²³

The reason it has to be used so often is that we rarely look at a single position in isolation. It proves much more helpful to examine multiple potential future positions, and to reach any of those a chain of legal moves has to be followed. This process, determining which continuations to observe and from that drawing conclusions about which lines are most promising to pursue, is what we refer to - in grand tradition of obvious names - as the Search.

Search itself does, however, suffer from one major flaw. We should not - and cannot - follow every possible sequence of moves to its ultimate conclusion. At some point, we have to decide to terminate the search and guess how good or bad the thus chosen final position looks for either player. Occasionally, this is downright trivial:

Overwhelming advantage

Whilst there is no immediate mate to be seen, without even trying to find one most humans will, at but a cursory glance, recognize which side is winning here. Most other positions are ever so slightly more subtle so, which is why the quality of such static evaluation plays a large role in determining an engines playing strength.

In order to execute all of those operations, we have to somehow keep a representation of our chessboard in memory and operate on it. This board representation should be carefully chosen to allow the most common operations to be executed as efficiently as possible.

And with that, we shall conclude our high level overview. I do hope this listing of major building blocks has proven somewhat illuminating and I managed to convey a general idea of how the parts interact. The post you are currently reading will, however, not explore them further, as I have thus far neglected one minor issue of paramount importance: how do we get our state to the engine and how does it report its move back?

UCI

If all we desired were the minimal viable interface, it would be perfectly sufficient to simply input some arbitrary form of from-square/to-square pair on standard input and output the same. Unfortunately for us, most non professional humans are not particularly adept at or in favor of blind chess and manually keeping track on a real board is certainly more tedious than strictly necessary. As such, the majority of our users would be significantly more satisfied if we managed to place some form of graphical representation resembling a physical board in front of them and allowed them to act on it.

Such a thing is certainly both possible and interesting. Implementing a beautiful and intuitive user interface poses fascinating challenges which can only help us grow as developers, yet those challenges are very different and quite far removed from the one we are actually attempting to solve. We could easily end up being too distracted to get the core parts into working order any time soon.

Furthermore, lovely pictures being the only way to interact with our program would render playing other machines annoyingly difficult. Interfaces created for humans are often notoriously hard for machines to process and vice versa, so tying our code too closely to one particular participant will necessarily inconvenience the other.²⁴

Luckily for us, others recognized this way before I even started considering writing an engine of my own and have taken measures to solve it. You see, dear reader, I have not been completely upfront with you earlier. Or at least, I have simplified a little, as it is not entirely accurate to refer to just any chess playing program as an engine. If it had a built in GUI, it would be more than that. The reason we use the term engine is because the thus described program might be central and drive the machine, but is usually not used on its own. To take full advantage of it, we do not execute it directly but in conjunction with a third party program, like the wonderful and incredibly useful Cutechess, which can invoke one or multiple engines in the background and mediate between them and us pesky humans.

To avoid duplicated and repetitive effort, it proved beneficial for most programs to agree on how exactly to talk to the outside world. This way complete decoupling is achieved and anyone can write a user interface that can talk to any engine following the protocol. Conversely, all an engine author has to do is implement the protocol and users are free to chose their favorite GUI to play against it. There are two popular such communication protocols to choose from, CECP and UCI.

For reasons which are not entirely rational and shall as such remain unmentioned, I decided on UCI. The exact details for all supported commands are specified here and I shall not bore you by repeating each and every one of them. Instead, I’ll just explain how it works in the most general terms and illustrate with some hopefully well chosen examples how I went about integrating the processing of UCI commands in my code. If you are interested in more, you can always check out the complete source code.

To begin examining how the protocol works, let’s have a quick look at a typical session:

As you can see, all communication is done via standard input and output of text commands, one line each. Communication is initiated by a simple “uci” and terminated with the intuitive “quit”. Other commands might have a varying number of optional arguments attached. An interesting property with large implications on possible implementations can be observed in the second call to go. During processing, before the search is completed and a result returned, another command - “stop” - is entered, causing the search to terminate prematurely. To put it in the words of the official documentation: “the engine must always be able to process input from stdin, even while thinking”.

Before continuing, I would like to offer a word of advice to my dear readers: The details which follow cannot be explained generically, so I shall assume some familarity with the C++ programming language and, lacking that, following my explanations might be neither easy nor valuable. If, at any point, you feel overwhelmed, feel free to skip to the end.

Brief intermissions aside, postponing the problem of parallelism for a moment and assuming we had an engine class with appropriate member functions, connecting those to a command line interface becomes downright trivial:

template <typename ENGINE_T, typename IO_T, typename ...ARGS_T>
void run_cli(IO_T io, ARGS_T&&... args)
{
	ENGINE_T engine{io, std::forward<ARGS_T>(args)...};
	
	using namespace std::string_view_literals;
	using command_handler_t=std::add_pointer_t<void(ENGINE_T&, std::istringstream&)>;
	
	constexpr auto command_map=ptl::make_fixed_flatmap<std::string_view, command_handler_t>(
	{
		{ "uci"sv,			detail::call_helper_v<&ENGINE_T::uci> },
		{ "debug"sv,		detail::call_helper_v<&ENGINE_T::debug> },
		{ "isready"sv,		detail::call_helper_v<&ENGINE_T::isready> },
		{ "setoption"sv,	detail::call_helper_v<&ENGINE_T::setoption> },
		{ "register"sv,		detail::call_helper_v<&ENGINE_T::do_register> },
		{ "ucinewgame"sv,	detail::call_helper_v<&ENGINE_T::ucinewgame> },
		{ "position"sv,		detail::call_helper_v<&ENGINE_T::position> },
		{ "go"sv,			detail::call_helper_v<&ENGINE_T::go> },
		{ "stop"sv,			detail::call_helper_v<&ENGINE_T::stop> },
		{ "ponderhit"sv,	detail::call_helper_v<&ENGINE_T::ponderhit> },
	});
	
	std::string line, cmd;
	for(;;)
	{
		line=io.input();
		std::istringstream stream(line);
		stream>>cmd;
		
		if(cmd=="quit"sv)
			break;
		
		if(auto it=command_map.find(cmd); it!=command_map.end())
			it->second(engine,stream);
		else
			io.error("Unknown command '",cmd,"' ;_;");
	}
}

To the uninitiated, it might look like there is a lot going on here, but it is really not. About half of the code is only concerned with constructing an object of the engine class with the passed arguments and defining a simple map providing one function pointer for each command. Afterwards it simply loops, repeatedly reading one line of input and decomposing it into its first word and the rest. The stringstream conveniently skips over any leading and trailing whitespace, which is another requirement of the UCI protocol. A quit command ends our processing, any other one is searched for in the map. If found, the relevant function pointer is invoked, passing the engine object and the stringstream containing the rest of the line. I’d claim the most interesting parts are those very function pointers and how we get them, so let’s examine that in some more detail.

They are apparently some sort of variable template named detail::call_helper_v instantiated with a member function pointer.²⁵ Here it is:

template <auto>
class call_helper;

template <typename C, typename R, typename... ARG_T, R(C::*memfun)(ARG_T...)>
class call_helper<memfun>
{
	public:
	static void call(C& handler, std::istringstream& data)
	{
		call_impl(handler, data, std::index_sequence_for<ARG_T...>{});
	}
	
	private:
	template <std::size_t ...IDX>
	static void call_impl(C& handler, std::istringstream& data, std::index_sequence<IDX...>)
	{
		std::tuple<std::decay_t<ARG_T>...> args;
		((data>>std::get<IDX>(args)),...);
		
		(handler.*memfun)(std::move(std::get<IDX>(args))...);
	}
};

template <auto v>
constexpr auto call_helper_v = call_helper<v>::call;

Now this might be a bit harder to swallow for casual C++ users, but please bear with me for a little longer. To get this out of the way first, what the code actually accomplishes is simple: it extracts arguments of the appropriate type from the stringstream (which holds the rest of the input line) and calls the dedicated member function. So our goal here is for a member function like void gun(int a, const float&b) to be invocable with the command line “gun 42 3.14” and do the right thing. With this preamble, allow me to describe how the code above manages to accomplish just that.

The variable template call_helper_v at the end would not be necessary and exists just as a convenience to save us from repeatedly typing ::call at the site of usage, whilst the real work is done by the class template declaration above. It expects a non-type template parameter of arbitrary allowed type, but is only specialized for member function pointers. The purpose of this somewhat convoluted construction is to get at the argument types expected by said member function, which are now available as the parameter pack ARG_T. So if we had a simple class like this:

struct fun
{
	void gun(int a, const float& b); 
};

and instantiated the template as

call_helper<&fun::gun>;

C would equal fun (our class), R would be void (our return type) and ARG_T would be <int,const float&> (the argument types). This allows us to define a std::tuple capable of holding variables for storing all argument values, regardless of which combination the member function expects. In the running example, args would be a std::tuple<int,float>. Notice that I dropped the const qualifier and reference, a job done in the code by std::decay. Our function might expect a reference, but this reference must have something to refer to, which is the tuple element we store.

Now that we have our variables - one for each function argument - we utilize the normal, potentially overloaded, operator» to extract values from our input line into those variables. So the code we would want our template to generate ought to look something like this:

data>>first_argument;
data>>second_argument;
//...

As the variables are stored as members of a std::tuple, we have to utilize std::get to use them:

data>>std::get<0>(tuple);
data>>std::get<1>(tuple);
//...

This looks, to the untrained eye, suspiciously close to the most basic use case of a simplistic for loop. And indeed it would be, if “0” and “1” above were function arguments, not non-type template parameters. As it stands, the following code we would like to write will unfortunately fail to compile:

for(std::size_t i=0;i<sizeof...(ARG_T);++i)
	data>>std::get<i>(tuple);

Lacking a constexpr variation of for, we have to resort to more functional methods to achieve the same result. This is why the private function template with a std::index_sequence argument is needed. std::index_sequence_for<int,const float&> will yield a std::index_sequence<0,1>, and passing this as a parameter to the call_impl will deduce <0,1> as the IDX pack, exactly the values our for loop would have iterated over. With this pack we can, at compile time, employ a fold expression to generate the calls to std::get we so desired:

((data>>std::get<IDX>(args)),...);

We then employ the same “trick” to generate an argument list for the function call and our work is done. Slightly more complicated arguments, like chess positions as FEN strings or similar are cleanly delegated to dedicated types and overloads for stream extraction.

Which leaves only two problems we shall now try to solve in tandem: one of tight coupling and the one of parallelism already mentioned above: Preferably we would like to have most of our engine code isolated from all this protocol madness. Maybe one day I will realize the errors of my ways, see the light and convert to CECP? If so, do I really want to change huge parts of my code? Maybe one day, in a bout of utter madness, I will suddenly decide that it could be a cute idea to replicate Turochamp for modern GUIs? If so, would I really want to duplicate all the UCI specific member functions which are rather tedious and independent?²⁶ Furthermore, the core engine code does not only have to be isolated structurally but also in execution, as it must run concurrently with command processing.

How do we solve this, you ask? With yet another level of indirection of course! We wrap our engine in another class providing the required interface²⁷ and safely executing engine functionality in a dedicated thread. Here is the declaration:

template <typename ENGINE_T, typename IO_T>
class wrapper
{
	public:
	template <typename... ARGS>
	wrapper(IO_T io, ARGS&& ...args);
	
	~wrapper();
	
	void uci();
	
	void debug(debug_setting setting);
	
	//[...] one function for each UCI command 
		
	private:
	IO_T io_;
	pcl::monitor<ENGINE_T> engine_;
		
	std::thread worker_thd_;
	std::atomic<bool> should_stop_;
	pcl::locked_queue<std::function<bool()>> task_queue_;
};

I omitted most UCI functions for the sake of brevity, but the general idea should be reasonably easy to grasp. This wrapper template requires an engine type and a type to handle input/output and stores an instance of each of these as a member variable. The engine is stored in a monitor, which simply pairs it with a std::mutex and ensures it can only be accessed when a lock is held. Further, it holds a thread responsible for doing all the real work, hence its name, and a simple thread safe queue to communicate with that thread. should_stop_ is passed to the engines search function to potentially notify it of interruption.

The worker thread itself is incredibly simple:

worker_thd_{[this]()
{
	for(;;)
	{
		auto fun=task_queue_.wait_and_pop();
		if(!fun())
			break;
	}
}},

It simply loops, waits until it can pull something from the queue, executes whatever function it finds there and quits the loop and thread if this function call returns false.²⁸ The queue is filled when certain UCI commands are triggered, for instance:

template <typename ENGINE_T, typename IO_T>
void wrapper<ENGINE_T, IO_T>::position(board_position pos)
{
	should_stop_=true;
	task_queue_.push([this,pos=::std::move(pos)]()
	{
		engine_([&](ENGINE_T& engine)
		{
			engine.setup(pos.fen);
			for(const auto& m:pos.moves)
				engine.do_move(m);
		});
		return true;
	});
}

Other commands are entirely independent and do not even interact with the worker thread:

template <typename ENGINE_T, typename IO_T>
void wrapper<ENGINE_T, IO_T>::isready()
{
	io_.output("readyok");
}

As always, check out the source code for all details and feel free to ask for clarifications or teach me the inevitable shortcomings of my design.

Outlook

Once again, allow me to quickly recap what we have done:

I have taken you on a whirlwind tour of history to explain how we got to having the great abundance of amazingly strong chess playing programs we have today. In so doing I hopefully managed to wet your appetite to start working on your own engine or at the very least care tangentially about mine. To help you along in that journey, I have published my code and begun the process of explaining it, first at a high level, then in some detail for a selected small but essential part. More details will follow in subsequent articles. With my next post in this series, I plan to cover board representations and the trade-offs involved.

As usual, I tried to mention and acknowledge as many sources of inspiration and motivation as I possibly could, but there is little doubt in my mind that I missed some. If so, you can trust it was ineptitude, not ill intent. I am a firm believer in Hanlon’s razor and like to apply it to myself as well as others. If there is any particular sin of omission you, dear reader, feel I have committed, pray tell me in the comments below and I will try to amend this post.

If you wish to leave constructive feedback, any other thoughts or even praises for me and your fellow readers to find, I am happy to accept those, too. If you feel strongly about anything I wrote and would like to educate me on how irresponsibly uneducated I am, I welcome your insults and threats of violence. The opposite of love is not hate, but indifference. As such, I am delighted about any and all interaction and am looking forward to responses of any kind ;-)

whom am I kidding at this point, really? ↩
or simply skipped it. If you are not interested in my random ruminations and just want to get down to details, you can jump ahead to “How?”, it does not really depend on what came before. ↩
for which I might even harbor a certain disdain. Hardly noticeable in my writing… ↩
Hell, there is even an entire show based on the premise of concealing and guessing the methods used and I freaking love it. The child like joy and occasionally anger Penn&Teller display when fooled is almost as fascinating to watch as the dedication, ingenuity and creativity of the presenting magicians themselves. ↩
the moral implications of doing so might warrant another, longer and more thorough discussion. I belief it’s pretty reprehensible so. ↩
Judging by the release date of the article, I assume this must have referred to the Difference Engine, not the more general Analytical Engine which is considered to be one of the first Turing Complete designs. ↩
and which I would love to own. ↩
The influence all of this had on fiction is quite fascinating. Moxon’s Master, for instance, contains descriptions which seem clearly inspired by the Turk and might be the first depiction of a robot in english language literature. ↩
In case you are wondering: The first is answered in the affirmative, whilst the second is deemed unknowable. Just read the paper ;-) ↩
Somewhat ironically, he technically failed at this sort-of reverse Turing Test by introducing some miscalculations. ↩
It was also reconstructed by yours truly, just for this post and the fun of it xD. Interestingly, my version produces the same amount of deviations as the chessbase one, but different ones, so I guess I might have misunderstood something fundamental. I do, however, believe part of their analysis is wrong, as at one point they mention “The black pawn on e5 has disappeared, and with it the bonus for the two rows it had advanced (+0.4 for White).”, whereas Turings paper only mentioned “each white piece […] and the black king”. I therefore believe the position of black pawns was not taken into account for computing the position-play value. I am also not entirely sure their interpretation of Turings quiescence search is accurate. They write “captures had to be followed up at least to the point where no further capture was immediately possible”, but the paper machine has a notion of standing pat. The value of a position was supposed to be the greatest of “the positions obtained by considerable moves” or “the position itself evaluated as if a dead position”. ↩
IBM itself writes of more than three billion impressions ↩
This fascinating story is, of course, as all the other parts of this historical overview, far too interesting and extensive to be covered exhaustively in so small a post. As such, I would like to invite my dear readers to dig deeper. To give you some hints as to where you could start, I’d like to point out, that there is a documentary featuring Kasparov himself which rather obviously hints at the suspicions of foul play. I also recently watched a much more nuanced, detailed and fair treatment of the whole affair on Youtube. And here is a fairly recent interview with one member of the Deep Blue team. Oh, and once you are done with all that, I warmly recommend this conversation between Kasparov and Demis Hassabis of AlphaGo fame. In general, the story of AlphaGo shares some truly striking parallels and some notable differences which are well worth investigating. ↩
Additionally, Turing, in his paper cited above, claimed that the better a program, “the more ingenious perhaps the designer”. Being indirectly praised by the father of computer science himself should earn at least some minor bragging rights, wouldn’t you agree? ↩
I have, in fact, started and abandoned writing a shogi program a really long time ago. I am a little sad that plan never really came to fruition, so I might try again someday. ↩
All of whom are by now far better players than I could hope to be. ↩
Here is the obligatory xkcd comic making my point. ↩
The hand on his shoulder and the hair on the side are mine, in case you are wondering. ↩
This brilliant logo was graciously provided by the wonderful Jana Ochse. ↩
You might, upon perusing the source code, realize that a large part of the evaluation function consists of huge, arbitrary looking tables with numbers lacking any explanation. Those have, of course, been arrived by automatic tuning, but the code responsible for this optimization (as well as a huge number of tests) is not included in the published repository yet. The reason is trivial, as this code suffers one major flaw: It is embarrassingly ugly. I shall eventually publish it, in conjunction with articles explaining its working, once I found the time to clean it up a little. ↩
So, if you wish to do me a favor, dear friend, I would be much obliged if you could quickly jump up just one section. ↩
which they will get ;-) ↩
Interestingly, move generation was glossed over completely in the Turing paper. I presume this was because it is so well defined a problem to seem trivial in theory. Legal moves follow directly from the games rules, which are unambiguous and almost boring. In practice, however, this is one of the much harder things to get completely right. Even Deep Blue seems to have had some bugs in that regard. ↩
Most of the difficulties with self driving cars stem from this. If we had specially built roads and no signs desiged for the human eye, I dare say it wouldn’t even pose much of a challenge. ↩
The most astute of you might have realized, that one of those is not like the other. All but one of the member functions are named exactly like to command they represent. register had to deviate from that rule, as it is a keyword. ↩
Oh wait, that already happened… ↩
Which is basically the facade pattern. ↩
In retrospect, I have to admit this is a little unclear. The interpretation of boolean return values is not always obvious and it might be better to return some simple enum class value and check for something like task_queue::end_processing. ↩

The Royal Game

Contents