Category Archives: diversions

Chess Engine Update: Endgame Tablebases

In the background, while tons of work stuff has been happening, I’ve been continuing my mission to write a fully-featured computer chess engine in the C programming language.  My engine is named SpaceDog, in honour of my dog Laika, who is from space.

Work on SpaceDog has been proceeding well, with lots of additions to its evaluation function, convenience features like outputting fully-diagrammed logs of each game you play against it, outputting games in PGN format, etc.  Now I’m diving into adding more substantive features, in this case support for Syzygy endgame tablebases.

Endgames have always been a prominent feature of chess study, and over the centuries millions of players have stared uncomprehendingly at difficult endgame studies, mate-in-3 puzzles, and similar things.  For the improving player, endgame study is interesting but also very challenging, in that there are innumerable situations where a seemingly simple or natural move can lead to disaster, or conversely the failure to find a very specific and unintuitive move can lead to a missed win.

Naturally this is just as much of an issue for computer chess engines as it is for humans.  Many engines over the years have been programmed with specific rules for winning typical endgames like KPvsK (King and pawn versus a lone king) and some of the particularly long-winded and tedious ones like KRvsK (King and Rook versus King) or the dreaded KBNvsK (King, Bishop and Knight vs King — you get it now, abbreviations only from now on!).  Some of these endgames require remembering rules particular to each endgame, or even memorising long strings of winning moves in order to not mess up and give your opponent a stalemate.

Before we go any further, a quick reminder of the basic rules of ending a chess game:

  • Checkmate: opponent’s King is in check (attacked) and unable to escape to safety
  • Stalemate: opponent’s King is not in check, but your opponent has no legal moves, (remember it’s illegal to move into check)
  • Draw: declared when players repeat an identical board position 3 times in a row, OR when 50 moves have elapsed without a pawn move or capture taking place

These rules and the complicated nature of some endgames make things difficult for humans to succeed in their endgame play, and chess engines struggle too, even when looking ahead many more moves.  Let’s see, for example, how SpaceDog copes with the tricky KBNvsK ending:

KBNvsK no TBs 2

Here’s a snippet of SpaceDog’s attempt (before my recent additions) to play KBNvsK (the full PDF record is available here).  I actually stopped the engine after 26 moves as it was clearly making no progress!  If you check the full game log out, you’ll see that SpaceDog manoeuvres bravely, but is unable to work out the correct plan to trap the enemy King, even though it was looking ahead 25 moves at this point.  SpaceDog needed to trap the enemy King against the side or corner of the board to make it easier to deliver checkmate, but couldn’t coordinate its pieces correctly, and so the ending barrelled irretrievably toward a draw by the 50-move rule.

It’s worth saying that SpaceDog, even armed with only its core evaluation function and search, is more than capable of winning many endgames.  But even in those cases, it can make the occasional mistake that can allow a clever opponent to salvage a draw or stalemate, or can be simply inefficient and take longer than it should to mate the opponent.  Let’s take this KPPvsKP ending as an example:

KPPvsKP no TBs 2 This endgame looks simple, but the black King is in the way of White’s protected passed pawn on c4, so getting that pawn to promote and become a Queen requires some finesse.  SpaceDog manages this quite well without any additional help, mating the opponent in 24 moves.  However, with clever play it should be possible to checkmate Black quicker and with a greater material advantage.

And that clever play is what endgame tablebases are all about.  Endgame tablebases in chess came about thanks to Richard Bellman, who in 1965 proposed analysing chess endgames using retrograde analysis — starting from checkmate positions, and working backward from there to find the optimal moves to reach that position.  The end result of this would be a massive database containing every possible configuration of pieces on both sides of an endgame with small numbers of pieces, with complete information on how to reach the best possible ending from that position.  In 1977 computer science legend Ken Thompson used the first endgame tablebase in an engine against a human opponent, and from there chess engine programmers were off to the races.

Today thanks to widely available supercomputer power we have access to tablebases that enumerate all the optimal moves for both players from every possible endgame position containing seven or fewer total pieces.  This is a truly staggering number of positions — 423,836,835,667,331 to be exact!  Yes that’s 423 trillion positions.  There are 512 billion KRBNvsKBN endgames alone!  For every single one of these positions, we know: the game-theoretic value of the position (Win, Lose or Draw, or WDL for short); the distance-to-zero (moves before a pawn move or capture that zeroes out the 50-move drawing rule, or DTZ); and the distance-to-mate (number of moves for the winning side to mate, or DTM).  You can explore any and all of these positions and view the winning moves and various stats about endgames at; the front page also has handy links for downloading all the tablebases for yourself.

I should note that of course given the size of these databases, the actual files are very large.  The best available compression algorithm for full WDL and DTZ tables is Syzygy, which is what I’ve added to SpaceDog.  The 3, 4 and 5-piece endgames will take about 1GB of storage, but you’ll need 149GB for the 6-piece endgames, and a staggering 18.4TB for the 7-piece endgames!  To use them most efficiently, make sure the WDL tables are on very fast storage like a solid-state drive (SSD), as these are accessed by engines very frequently to guide the engines toward favourable endgame positions, whereas the DTZ tables are only accessed once the engine actually enters an endgame position and needs to know the best moves.

So, after a weekend of work, SpaceDog can now use the Syzygy endgame tablebases, and thus plays endgames perfectly.  This makes it far better for practicing endgame play, for learning difficult endgame and mating sequences, and for analysing games.  To see how dramatic the change is, let’s go back to that KBNvsK endgame from earlier, where SpaceDog stumbled about uselessly for 26 moves heading for a draw, despite having a massive advantage in material.  Once we add Syzygy tablebases, SpaceDog obliterates its opponent in only 7 moves:

KBNvsK TBs 2

Look at that lovely short move listing!  This time, SpaceDog uses all of its pieces in concert, confining the enemy King to the corner by occupying the short f1-h3 diagonal with its bishop.  Shortly afterward, we end up with an effectively and efficiently checkmated opponent:

KBNvsK TBs mate 2

Even when we revisit endgames that SpaceDog can win easily, the Syzygy tablebases provide significant improvements.  Going back to the KPPvsKP endgame from earlier, SpaceDog checkmates five moves faster:


SpaceDog not only wins faster, but it ends up with two queens instead of just one!  The opponent doesn’t stand a chance:

KPPvsKP TBs mate 2

Of course these are far from the most complicated endgames available.  SpaceDog can now win endgames that take potentially hundreds of moves, without making a single mistake.  The Syzygy tablebases are built with the 50-move rule in mind, so in some longer endgames you’ll see clever trickery as SpaceDog just manages to make or allow a pawn move or capture before the deadline, to reset the clock and deliver checkmate later on.  Take for example this KBBvsKQ endgame, in which SpaceDog achieves mate in 52 moves:


Here SpaceDog methodically manoeuvres the Queen to neutralise both of White’s bishops, until it captures one of those bishops at the last possible moment (the last half-move of move 50):

KBBvsKQ move 50

That gives SpaceDog the time to finally deliver forced checkmate two moves later:

KBBvsKQ mate

As you might imagine, remembering forced sequences of so many moves and using them with such impeccable timing is impossible even for the top Grandmasters — there are simply too many endgame possibilities to make rote memorisation worth the trouble.  Even if it were worth it, remembering sequences like that over the board under time pressure against live opponents would be a very tall order!

During my testing I found a particularly cruel example of this kind of brutal efficiency in this KNNvsKP endgame, where White delivers a tricky checkmate with two knights after 52 moves:


Note that the first move, Na2, immediately immobilises Black’s passed pawn, where it stays frozen until move 50, when White lets it run free.  ‘Yay!’ says Black, ‘I’m making a Queen!  I’m back in this!’

KNNvsKP move 50

Black does make a Queen, as it happens, but it’s ultimately pointless as they get checkmated immediately:

KNNvsKP mate

SpaceDog, that’s just harsh!

Anyway, these are just some fun examples from 5-piece endgames — there’s some amazing endgames in the 6- and 7-piece databases of course, with forced checkmate sequences lasting hundreds of moves, totally bizarre-looking moves that turn out to be the only path to win or draw, and intricate piece play that has done wonders for our understanding of endgames.  I highly recommend taking a look at some cool endgames using an engine, or just browsing them via the web interface linked above — you’re bound to find something fascinating.  Assuming you care about chess, obviously.

So what’s next for SpaceDog?  Well first, my Syzygy tablebase support is only half-finished — endgame play is now perfect, but I have yet to implement searching of the WDL tables during midgame play to guide SpaceDog toward the best possible endgame positions.  That’s a relatively straightforward addition and will take much less time than adding the DTZ support, thankfully!

After that, I’m aiming to beef up SpaceDog’s search, making it more efficient to allow searching to greater depths, and making it much faster by using multi-threading (multiple CPU cores).  At that point, SpaceDog will have all the main features of a modern alpha-beta chess engine, and will make a worthy opponent for its eventual successor: SpaceDogNeuro.

You can download the latest SpaceDog executables for Windows and MacOS (Linux forthcoming, when I remember) at the Github repository, by the way, but bear in mind it’s a messy hobby project, and a major work-in-progress with bugs lurking everywhere!  If I were you I’d wait for version 1.0.  In the meantime, for serious chess analysis, Stockfish is the superior choice (and it’s free and open-source too).

Tagged , ,

The Game of Go

I’ve been off work for a couple of weeks now, and rather than going on holiday I’ve mainly been trying to rest up after several months of really intense work.  As part of my attempted recuperation I’ve been playing a lot of the board game Go, a game I have a tremendous fondness for but go through long periods of slacking off when my brain is busy with work stuff.  I’ve been enjoying the opportunity to play more and thought that some of my friends and colleagues might enjoy the game too, so I decided to put together an intro to the game, alongside copious links to resources and ways to play online.  I hope this might spur some of you out there to give it a try.

Go is a board game that’s been around for a very long time, and is generally believed to be the oldest board game still being played today; Go was invented about 3000 years ago in ancient China.  The game is still immensely popular in Japan, China (where it is known as weiqi), and Korea (baduk), where professional play is well-established, and it boasts a  growing following in America and Europe as well.

I’ll start by giving you a very brief summary of the rules of the game, then link you to some resources that will help you get started.

Playing Go

Go is known as a game of great complexity and subtlety, but the actual rules are simple.  There are two players, White and Black, and each has 180 stones of the appropriate colour.  Black always goes first, which confers a slight advantage, so in compensation White receives a bonus (komi) of 6.5 points at the end of the game (under Japanese rules, it’s 7.5 under Chinese rules).

The players start with an empty board of 19×19 squares, like so:

empty go board

Notice that the board has nine marked star points which help players to orient themselves in this large playing space.

The players take it in turns to place a stone on an unoccupied point on the board.  Once placed, a stone never moves, although it can be removed when captured.  Stones are captured if all of the empty points surrounding them (their liberties) are occupied by stones of the opposing colour.  This GIF shows an interesting example, where Black keeps capturing White stones only to eventually have his entire group captured himself by cutting off his own stones’ liberties:

go capturing gif

Over time as stones are placed and some groups are captured or fortified, the players will sketch out and secure territory where their opponent cannot play without being captured.  At the end of the game, both players total up the amount of territory surrounded by their stones, add in the number of stones they’ve captured from their opponent, and compare the totals (plus the 6.5 points komi for White) — the player with the highest total of territory and prisoners wins the game.

Below is an animated gif showing an example of play: a complete record of the famous ‘Game of the Century’ between Go Seigen (Black) and Honinbo Shusai (White).  In this match players could adjourn to think at any time, so this game dragged on for three months!  White won by two points in the end and the game is celebrated for some brilliant moves and fierce fighting over territory.

seigen shusai gotc

You can download a huge archive of 48,000 historic Go games in SGF format here, or if you want to view records of professional games in a handy web applet you can check out

The Style of Play

From the simple rules of Go, very complex patterns of play emerge.  Unlike other prominent competitive board games like chess, in Go the board starts empty, and the number of available points to play a piece is very large (361 points on a Go board vs 64 squares on a chess board).  The sheer number of possible moves is so huge that players must rely on intuition, a solid grasp of fundamental principles of play, and keen awareness of their opponent’s movements to play well.

This reliance on intuition makes Go a surprisingly emotional game — pick up any book by a serious professional and you’ll see them speak with great passion about how various moves and games made them feel.  This in turn leads to some seriously intense contests — watch professional matches and you’ll see the players’ faces often contort with pain as they confront a powerful move by their opponent.

As a result of the complexity of the game, you’ll see Go players start their play in the corners and edges of the board — this is because it’s easier to make territory on the sides and corners, since you can use the edges as boundaries for your territory.  As the sides and corners are decided, players begin reaching toward the centre of the board, attempting to connect their strongest groups of stones together and grasp larger chunks of territory.

The beginning of a Go game is often overwhelming for new players, who struggle to figure out where to start placing stones on this massive empty board.  Generally the Black player will start play on the upper-right star point, which is considered polite to your opponent — it’s close to their end of the board and gives them a clear idea of where to start play.  This helps somewhat, but the opening is still the toughest part of the game for newcomers.

As a result, most experienced players recommend that new players start on a smaller board, either 9×9 or 13×13.  These are less intimidating to start with and get you into territory fights right away, giving you an immediate introduction to the moment-to-moment tactics of Go.  Just bear in mind that you should try to advance to the full 19×19 board as soon as you can, as it’s a very different game at that scale.  On the full board strategy becomes as important as tactics, and stones in distant corners have powerful implications elsewhere as patterns of territory shift and evolve over large swathes of the board.

Learning the Game

Learning Go is a long process, as the game requires an understanding of a lot of complex interactions between stones.  There’s also a bit of a language barrier, as many Go terms derive from Japanese and are difficult to translate, so most players just use the Japanese words.  As a result you’ll need to understand things like what it means when stones are in atari (stones that will be captured on the next move unless you do something to save them), or in seki (opposing groups of stones that can’t capture one another without endangering themselves).

Luckily there are some great introductory books I can recommend that will give you copious examples of these terms and many helpful and illustrative Go problems (tsumego) to test your skills.

For complete newbies I highly recommend Go: A Complete Introduction to the Game by Cho Chikun.  Cho Chikun is one of the greatest players alive today, being the only player in history to hold all four main Japanese titles at the same time.  His book is surprisingly short but very dense with helpful illustrations of key go concepts, and it rewards deep study and playing out the examples on a real or computerised board to experience each pattern for yourself.

From here you can check out the Elementary Go Series from Kiseido Publishing.  This series covers key concepts of the game in detail in each volume.  Many players recommend these books for players seeking to advance to intermediate levels of play.

When you’ve fully digested all this, you can try Lessons in the Fundamentals of Go by Toshiro Kageyama.  This book is thicker than the others and quite dense with content — expect getting through this to take weeks, not days.  But the concepts he explores are critical to good high-level play, and if you master them you’ll be well on your way to a thorough understanding of the game.

For online resources, I recommend studying the games of great masters, which you can easily find via the archives linked above and at places like  The LifeIn19x19 forum is a great place to get tips from other Western players, with many members happy to give guidance on your development as a player.  Finding good software is also key to learning the game, as this will be how you view and study the games of great players, or analyse your own games to examine your own strengths and weaknesses.


Go Software

This section will be relatively short, because in my view there’s really just one piece of software you really need to study Go, and that’s Sabaki.  Sabaki is free, open-source, and works perfectly on Windows, Mac and Linux.  It also nicely captures the austere aesthetics of the game, showing you a lovely 19×19 wooden board sat on a tatami mat and simple black and wide stones.  You can customise the look with themes as well, if you like.

A subtle touch that I really appreciate is that each stone is placed with a slight random touch, rather than precisely on the relevant point on the board, giving the whole thing a slightly more organic look as the game evolves.

Looks aside, Sabaki is a great piece of Go software, allowing you to view SGF files (the move-by-move records of Go games, as in the archives linked above), edit your own, and play against any AI Go engine that supports the GTP protocol (basically all of them).  In particular I recommend using Tencent’s PhoenixGo engine, which is very strong and comes with instructions on how to link it with Sabaki on Windows and Mac.

Here’s a screenshot, stolen from Sabaki’s GitHub page:

Sabaki screenshot

If you’re a more advanced user and want sophisticated analysis of your games from a strong AI, you can use Lizzie, which uses the Leela Zero engine to analyse your moves and show you what the engine recommends in each situation.  Download the latest version from the Releases page at the link, then follow the instructions in the Readme file to get started.  The results can be helpful, but bear in mind Leela Zero can only show us what she thinks, not explain why she thinks it, so still it’s better in my opinion to get input from human players and learn Go fundamentals rather than just ape the moves the computer engines recommend.

Here’s an example of Lizzie’s output, showing the user its recommended moves (the cyan-coloured one is Leela’s top recommendation):

lizzie screenshot


Go Equipment

Go equipment, much like the game itself, is steeped in centuries of history and tradition.  Japanese aesthetics in particular have had a profound influence on Go equipment.  Today most high-level players or keen amateurs in search of fine equipment will go to Japan to get it.

go set1

The finest Go boards are made from the Japanese Kaya tree, and makers prefer that the tree is between 700-1000 years old when the wood is harvested.  This combined with the fact that Kaya trees are protected in Japan means that true Kaya boards can be ludicrously expensive; free-standing boards with legs can rise well into the tens of thousands of pounds.  Normal people go for so-called ‘Shin Kaya’ boards, usually made of Alaskan spruce, which looks close enough to the right colour and feel for most people and can be had for £100 or so for a tabletop board of 3cm thickness.

go stones 2

The finest Go stones, meanwhile, come from a place called Hyuga in Miyazaki Prefecture in Japan.  The black stones are made of nachiguro slate stone, while the white stones are meticulously carved from clamshells, resulting in a beautiful shining surface striped with subtle lines.  The finer the stone, the thicker it is and the denser and thinner the lines are.  As with the Kaya boards, genuine Hyuga stones are incredibly rare and have price tags far beyond most mortals.  However, these days you can get clamshell and slate stones made from imported Mexican clams that are nearly as perfect as the real thing, and a good set of decent thickness will set you back about £200-300 rather than tens of thousands.

go bowls1

Finally you have the Go bowls, which hold each player’s stones.  Traditionally you place the bowls next to the board with the lid upside-down in front of it, and place any captured pieces in the upturned lid.  This is polite to your opponent, who needs to know how many pieces you’ve captured as that affects the game’s final score.  Go bowls again can cost ridiculous amounts for traditional Japanese wooden articles, but beautiful and functional bowls hand-carved from cherry and other woods needn’t set you back more than £150 or so.

The overall effect of a fine Go set should be a beautiful, smooth board with a soft yellow tone that perfectly compliments the black and white stones.  When you place a stone on the board, it should make a satisfying ‘click’ against the wood — in particular on the free-standing boards, which have a chunk hollowed out of the interior to ensure it makes a pleasing sound.

In total, if you purchase a nice table Go set from a prized Japanese maker like Kuroki Goishi-ten, expect to pay about £300-400 for the lot (plus shipping/Customs fees of course).  This is assuming a 3cm or 6cm Shin Kaya board, ‘Blue Label’ Mexican clamshell stones, and mid-level bowls of sakura wood or similar.  Various distributors do sell some of their products in Europe — check Masters of Games in the UK, or in Germany.  Both stores also offer budget sets with Korean glass stones that are more than fine for most people; a set with a nice Shin Kaya board, Korean glass stones and Go bowls made with European wood should cost no more than about £200.

One of my great regrets from my time in Japan is that despite my intense desire for one, I never purchased a fine Go set for myself.  They really are lovely.  As a consequence of not taking that leap, I have this masochistic ritual of checking Kuroki Goishi-ten’s sales every summer, finding myself unable to justify the ~£100 in shipping costs on top of the cost of the set, and end up torturing myself over it for weeks.  Someday I’ll take the plunge; in the meantime I do hope to get a Shin Kaya/glass stones set someday soon, and then eventually upgrade to proper clamshell stones.

Go vs Chess

For those of us in the West, the average person’s familiarity with abstract strategic board games often starts and ends with chess — even people who don’t play have probably heard of Garry Kasparov and Bobby Fischer.  Both chess and go are intellectually challenging and stimulating, but they differ in quite fundamental ways.  I’ll say up front that I enjoy both, and feel each one offers something the other doesn’t.

As described above, Go is simpler than chess as far as the rules go — stones are simply placed and never moved, and complex interactions between pieces arise from their configurations, not from the rules themselves.  Meanwhile, in chess each piece moves, different types of pieces move differently, and the goal of the game is to trap the opposing king, which again depends on intimate knowledge of the roles and movements of the different major and minor pieces.

For the chess player, Go can initially seem a bit incomprehensible.  Chess openings have been so thoroughly explored by humans and computers that many experienced players play the first 10-15 moves essentially from memory (depending on their choice of opening), while in Go this vast empty board makes the opening phase really perplexing.  Note that Go players also have opening patterns they study called joseki, but these aren’t overly necessary except at high levels of play, and in fact many pros discourage new players from studying them until they’re quite advanced in their play.

The smaller boards and armies of chess mean the game also turns much more on tactics than Go.  Chess does have lots of strategy to it of course, but on the whole it’s more likely that a single move can change the course of a chess game than a single move massively changes a Go game on that huge 19×19 board.  So, if you’re more interested in intricate tactics and moment-to-moment attacking play, chess may be more your game; whereas if you’re interested in sweeping strategic movements and more intuitionist play styles, Go may be for you.

Honestly though, I’d say just play both — each game is rewarding in its own way, and I suspect a strong tactical chess background will serve you well in Go, just as strong strategic instincts in Go should surely help your chess game.  I also recommend trying chess’ East Asian cousins Shogi, Xiangqi and Janggi.  Shogi (Japanese chess) allows captured pieces to re-enter the game on the capturing player’s side which creates an interesting dynamic feel.  Xiangqi (Chinese chess) has unique pieces and a larger board with territorial restrictions; Janggi (Korean chess) is very close to Xiangqi but with some rules differences that make it a very interesting variant.  In fact I may post about these games someday down the line, as all are very accessible now with free apps for online play, and both Shogi and Xiangqi have some excellent English-language resources available (less so Janggi).

Playing Go Online

Speaking of online play, Go is likewise more accessible than ever thanks to the efforts of an extremely dedicated global community of players.

There are a number of great free services that enable online play against opponents all over the world, 24/7/365.  A few of them specialise in real-time games, in which you and your opponent finish the game in one sitting, while others focus on correspondence games, where you take your time with each move and update the game on the server when you’ve chosen your move, and games take place at a leisurely pace over weeks or even months.

All of these services are free, by the way, though some offer subscriptions with extra benefits.

Real-Time Servers

IGS (The Internet Go Server) — By far the oldest of the bunch, the IGS has been around since 1992 (!).  It started in Japan and still has the largest Japanese player community; many professionals play here.  A nice software client, CGoban2, is available for all major operating systems, and there’s a good app as well for Android and iOS.

KGS — Popular with Westerners, KGS is well-known for being a chatty server where more experienced players will offer learning games for newbies and analyse your games to help you improve.  Has lost popularity somewhat in recent years and the Android app is apparently a bit unreliable, however.  I’ve heard some players recently recommending people shift to other servers, as they have difficulty finding good opponents here nowadays.

TygemBaduk — A Korean server but has an English-language website and client.  Quite popular and apparently a good place to face strong opposition, though the client only works on Windows and iPad so be aware of that.  The web client will work on any platform, though.

WBaduk — A very large Korean server, immensely popular.  Another great place to face strong opposition, but they’ve also got problems with accessibility — just a few days ago the English client disappeared off the Google Play Store (!).  Worth joining once you’re ready for strong opponents, but perhaps worth keeping on eye on things to see whether some changes to the service might be forthcoming.

Fox Weiqi — An absolutely massive Chinese server that’s becoming increasingly popular among Westerners due to having an English-language client and a polished Android app.  Do note however that you have to sideload the app onto your Android phone, presumably due to China not really being a fan of Google services.  Also the app is in Chinese only as far as I can tell.  I’m installing the app as I write this so we’ll see if I can manage to find what buttons to mash to play a game with someone!

Correspondence Servers

Online Go (OGS) — A fabulous place to play correspondence Go.  Uses a constantly-updated, modern web interface with responsive design — meaning it works perfectly and looks great regardless of whether you use it on desktop, laptop, phone or tablet.  At any given time there are tens of thousands of correspondence games going.  Real-time play is also supported, but most players do opt for correspondence games.

Dragon Go Server — A bit old-school design-wise, but has been around a long time.  I’ve never personally played here but my impression is the userbase is pretty loyal.  The web interface works fine for what it is, but definitely miles behind OGS.  For playing on Android you can use a free plugin for the Go app BW-Go.


Go Apps

AQGo — An Android app that lets you play against the super-strong neural-net go bot LeelaZero, which is a community attempt to replicate Google’s super-powerful AlphaZero go bot.  Needs to be sideloaded onto your phone.

Crazy Stone Deep Learning — A beautifully polished Go app that lets you play against a strong neural network opponent.  The Pro version is a bit pricey as apps go (£12.99), but it’s been worth it for me to have an ever-present strong opponent that will analyse my games in-depth.  Also available on Steam for a much higher price but also has a stronger rating (7-dan).

GridMaster Pro — A cheap, no-frills Go app that lets you play against a variety of Go engines, including Leela Zero.  A slight caveat here in that in my experience, sometimes Leela Zero will refuse to make a move until I forcibly shut and reopen the app, but your mileage may vary.  Leela and other engines can be downloaded directly through the app and installed instantly — check the app’s website for details.

TsumeGo Pro — An app for tsumego problems, Go puzzles that test your knowledge of key Go concepts.  Extremely useful for polishing your skills and furthering your understanding of the complexities of keeping groups of stones alive — or killing your opponents groups!  In-app purchases get you more problems to solve.

Pandanet IGS — The app for the Internet Go Server above.  Free and works really well in my experience.


Well, that’s quite enough for one day — I hope this info might prove useful to someone out there who’s curious about Go.  It’s a wonderful game and more accessible than ever, so if you’re interested in giving it a try, just pick your choice of app and get in there!

Tagged , , ,

Diversions: Fun with FRACTRAN

Recently I’ve been learning to use Mathematica, a piece of software I was curious about for a long time.  Luckily my university has a licence for all staff, so I snagged a key as soon as I learned this and have been mucking around with some serious stuff — namely it’s surprisingly good neural network features — and some less serious stuff to get my head around the Wolfram Language.

This weekend I’ve been messing around with FRACTRAN, a fascinating esoteric programming language and model of computation developed by John H Conway, who’s perhaps most famous amongst computer types for inventing the Game of Life cellular automaton.  FRACTRAN is a language in which programs consist entirely of lists of fractions, like so:

primeProg = {17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 
 1/17, 11/13, 13/11, 15/14, 15/2, 55/1};

Now that may seem nonsensical, but bear with me here.  FRACTRAN works with really simple rules; given a list of fractions and an initial input N:

  1. Find the first fraction F in the program listing which becomes an integer when multiplied by N, then replace N by N*F
  2. Repeat until N doesn’t produce any integers when multiplied by any fraction in the program, then halt.

Easy peasy!  So we can write a FRACTRAN interpreter in Mathematica quite easily.  This one outputs each stage of program execution in order to a list called outputFrac, to allow us to manipulate the results later if need be:

fracRunList[fracProg_, input_, steplimit_] := Module[{j, state},
 j = 0;
 state = input;
 outputFrac = {};
 While[j <= steplimit, newProg = state *fracProg;
 integerList = IntegerQ[#] & /@ newProg;
 intSpots = Position[integerList, True];
 AppendTo[outputFrac, state];
 If[Length[intSpots] == 0, Break[]];
 state = newProg[[intSpots[[1, 1]]]]; j++]];

So, when you call this function with fracRunList[{list of fractions}, N, timestep limit], it multiplies N through the list, checks that new list for integer values, appends that value to the list outputFrac, then starts again.  The function will halt either when it reaches the timestep limit you specified, or when no more integers result from multiplying N through the list.

When we run the program above — suspiciously called ‘primeProg’ — with an initial N=2 for 50 steps, we get this:

{2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 
132, 116, 308, 364, 68, 4, 30, 225, 12375, 10875, 28875, 25375, 
67375, 79625, 14875, 13650, 2550, 2340, 1980, 1740, 4620, 4060, 
10780, 12740, 2380, 2184, 408, 152, 92, 380, 230, 950, 575, 2375, 
9625, 11375, 2125, 1950, 1650, 1450, 3850, 4550, 850, 780, 660, 580, 
1540, 1820, 340, 312, 264, 232, 616, 728, 136, 8, 60}

That may look like nonsense, but note that scattered through that list of numbers we have 2, 4, and 8 — which are respectively 2^1, 2^2, and 2^3.  So what PrimeProg does is actually output all the prime numbers, in the form of prime exponents of 2!

We can see this easily if we run a simple filter on the list outputFrac after running the program for 50,000 steps:

findPrimes2[list_] :=
 Log[2, Select[list, IntegerQ[Log[2, #]] &]];

fracRunList[primeProg, 2, 50000]

Output: {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}

After 50,000 steps, our clever little list of fractions has produced the first 13 prime numbers!  Theoretically we can run this forever, and produce every prime number.  Although each one takes longer to come out than the last, unsurprisingly, so I don’t recommend it.

Another variation of the prime-finder program I found from the Esolang wiki is more efficient, using only 9 fractions to output prime exponents of 10.  We’ll test it out below, this time filtering the resulting output list for prime exponents of 10:

prime10Short = {3/11, 847/45, 143/6, 7/3, 10/91, 3/7, 36/325, 1/2, 

findPrimes10[list_] :=
 Log[10, Select[list, IntegerQ[Log[10, #]] &]];

fracRunList[prime10Short, 10, 50000]

Output: {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}

This prime-finder has managed to dig up 15 primes in 50,000 steps, rather than 13 like the original.

The really remarkable thing about FRACTRAN, though, is that it’s actually Turing-complete — it can in principle calculate anything calculable by any other programming language.  A simple example of a multiplication programme shows off how this works:

multiFrac = {455/33, 11/13, 1/11, 3/7, 11/2, 1/3};

fracRunList[multiFrac, 72, 50]

Output: {72, 396, 5460, 4620, 63700, 53900, 4900, 2100, 900, 4950, 68250, 
57750, 796250, 673750, 61250, 26250, 11250, 61875, 853125, 721875, 
9953125, 8421875, 765625, 328125, 140625, 46875, 15625}

What’s happened here is that we gave our FRACTRAN program a single number that actually represents our two input numbers — in this case 3 and 2 — as a product of prime numbers raised to appropriate powers — 2^3 * 3^2 = 8 * 9 = 72.  FRACTRAN then outputs the result as the power of a different prime — 15,625 = 5^6 = 5^(2 * 3).  A fairly roundabout way to get multiplication done, but it works!

What this shows is that it’s possible to have FRACTRAN programs operate on multiple inputs, so long as those inputs are encoded as products of prime powers.  In fact, we can assign specific primes to be our data registers and use carefully-constructed fractions to operate on those registers, and even construct complicated programs with loops!  As this StackOverflow answer shows, it turns out FRACTRAN is exactly equivalent to a Minsky Register Machine, which have been proven to be Turing-equivalent — hence confirming that FRACTRAN is actually a Turing-complete language.

As a consequence some intrepid folk have built some impressive constructs in FRACTRAN.  One of my favourites is a FRACTRAN interpreter which is itself written in FRACTRAN!  Using just 48 fractions, this program takes as input an encoded FRACTRAN program and initial state, and correctly interprets the program and outputs the result.  Here’s everything you need to try it:

fracInFrac = {5/19, 1558654261983398483185/122130132904968017083, 
 185/1822837804551761449, 4996917562403854655/41, 272365/67, 43/5, 
 43/71, 125173/47, 145915005923554298917151/952809757913927, 
 950886101246622507133/41426511213649, 160585150715989139597/13, 
 8752951/23, 17/43, 17/29, 6409/47, 5/17, 31/53, 17042839/7, 
 1829/41, 59/73, 331639/23, 4307/41, 89/59, 3713/31, 79/83, 
 268837/23, 31/79, 8633/7, 101/97, 68579/11, 9797/13, 9797/47, 
 35/101, 9167/13, 103/107, 1774381/47, 109/103, 109/113, 578899/23, 
 11227/13, 127/109, 127/131, 16637/47, 16637/11, 1114679/61, 2/127, 
 5/2, 3/37};

(* Encode a FRACTRAN program as a base-11 number for input into 
fracInFrac interpreter *)
base2 = 11;
pad2[f_] :=
 Block[{n = IntegerDigits[Numerator[f], base2 - 1],
 d = IntegerDigits[Denominator[f], base2 - 1], len},
 len = Max[Length[n], Length[d]]; n = PadLeft[n, len]; 
 d = PadLeft[d, len]; Flatten[{0, Riffle[n, d], base2 - 1}]];
digits2[progList_] := Join[Flatten[pad2 /@ progList], {base2 - 1}];
encode2[progList_] := FromDigits[Reverse[digits2[progList]], base2];

(* FracInFrac input state encoder function *)

fracInput[fracProg_, init_] := 5*7^init*67^(encode2[fracProg]);

In order to encode our FRACTRAN program into a format the interpreter can understand, we first need to encode the program as a single number.  In this case the encode2 function reverses the list of fractions in the program, then encodes the digits as base-10 numbers within a base-11 number.  Then we need to combine that with our initial state into a single number that we can pass to the interpreter.  We do this using the fracInput function, which gives us a ridiculous huge number that consists of 5 * 7^(initial state) * 67^(encoded program).  In fact, the resulting numbers are far too huge to print here as examples even for the simple adding program (which is just {3/2}!), and Mathematica can’t even cope with encoding larger programs and simply spits out an error.  Changing the encoding to use a smaller prime for the program is possible, but I leave that as an exercise for the reader.

Another intrepid StackOverflow commenter produced a FRACTRAN interpreter for FRACTRAN in 84 fractions, which has a slightly less ginormous program encoding:

fracInFrac3 = {197*103/(2^11*101), 101/103, 103*127/(2*101), 101/103, 
 109/101, 2*23/(197*109), 109/23, 29/109, 197*41*47/(31*59), 
 11^10*53/(127*197), 197/53, 37/197, 7^10*43/(11^10*37), 37/43, 
 59/(37*47), 59/47, 41*61/59, 31*67/(41*61), 61/67, 7*67/(127*61), 
 61/67, 101/71, 73/(127^9*29), 79/(127^2*73), 83/(127*73), 
 89/(2*29), 163/29, 127^11*89/79, 337/83, 2*59/89, 71/61, 
 7*173/(127*163), 163/173, 337*167/163, 347/(31*337), 337/347, 
 151/337, 1/71, 19*179/(3*7*193), 193/179, 157/(7*193), 17*181/193, 
 7*211/(19*181), 181/211, 193/181, 157/193, 223/(7*157), 157/223, 
 281*283/239, 3*257*269/(7*241), 241/269, 263/241, 7*271/(257*263), 
 263/271, 281/263, 241/(17*281), 1/281, 307/(7*283), 283/307, 
 293/283, 71*131/107, 193/(131*151), 227/(19*157), 71*311/227, 
 233/(151*167*311), 151*311/229, 7*317/(19*229), 229/317, 
 239*331/217, 71*313/157, 239*251/(151*167*313), 239*251/(151*313), 
 149/(251*293), 107/(293*331), 137/199, 
 2^100*13^100*353/(5^100*137), 2*13*353/(5*137), 137/353, 349/137, 
 107/349, 5^100*359/(13^100*149), 5*359/(13*149), 149/359, 199/149};

To encode the program, we reverse the order of the fractions in the program, put ’10’ between each numerator and denominator, and encode the whole list as a base-11 number:

(* Encode a FRACTRAN program in reversed base-11 digits *)

baseConvert[frac_] := 
 {Numerator[frac], 10, Denominator[frac], 10};
baseDigits[fracList_] := 
 Most[Flatten[Reverse[Join[baseConvert /@ fracList]]]];
baseEncode[fracCode_] := FromDigits[baseDigits[fracCode], 11];

(* Sample encoding: Simple adding program {3/2} *)
encodedAdder = baseEncode[addProg]

Output: 475

That seems manageable, right?  But then we have to encode the initial state 72, as well, and this program uses the format (3^(state) * 5^(encoded program) * 199)…

(* Complete encoded initial state for FRACTRAN interpreter *)
(* 3^initial_state*5^encoded_program*199 *)

encodeFracProgState[fracList_, init_] := (3^init)*(5^baseEncode[fracList])*199;

(* Sample complete encoding: Adder, initial state 72 *)

encodeFracProgState[addProg, 72]

Output: 4595528627302514457847822534456305637274485006848124607416562426715142

…Yikes.  Well, because I love you guys so much, I tested this out.  I ran the encoded program through the 84-fraction interpreter, and piped the output to a text file which rapidly blew up to 4.8MB of numbers.  The correct answer pops out after 6,030 lines of gibberish and looks like this:


Which is actually the expanded form of:

3^243 * 5^475 * 149

And you’ll note that 3^243, which is also 3^(3^(3+2)), giving us the answer to our original request to add 3 and 2, buried up in the second layer of exponents.  Whew!

Anyway, as you can see it’s easy to get lost in FRACTRAN despite its apparent simplicity.  It’s really interesting to play with, though, and it’s an odd moment when you realise that these simple lists of fractions are actually capable of some remarkable things.  The weekend is nearly over now and I have to prepare for actual work, but perhaps next weekend I’ll return to this and construct a compiler for FRACTRAN, making it possible to write programs in a higher-level language and squish them into FRACTRAN form.

Or I might start fooling around with different nerd stuff instead, who knows?












Tagged , , , ,