Tag Archives: Chess

An Introduction to Shogi

ANNOUNCEMENT:  There will be a special event at my workplace, the MRC/CSO Social and Public Health Sciences Unit, running at 5PM on 7 February 2020.  Dr Shuzo Sakata of the University of Strathclyde, Shogi player and teacher, will be showing us all how to play Shogi!  Sets will be provided — please RSVP to me directly if you plan to come, to ensure we have enough sets.  

What is Shogi?

Shogi is the Japanese form of Chess, the ‘royal game’, in which two players vie to be the first to checkmate their opponent’s King — meaning their King is unable to escape capture on the next move.  Many centuries ago, when the ancient ancestor of Chess called Chaturanga was developed in India, the game spread across Asia and Europe, spawning new variations in every region that embraced the game.  Shogi is first recorded in the Heisei Era in ancient Japan — around the 11th century — where it rapidly developed into its own, unique take on the royal game.

shogi-set-cropped

My traditional Shogi set — a Shin-Kaya board, with hand-carved pieces made from Japanese maple, with the kanji (Japanese characters) carved in the Minase calligraphy style in lacquer

How is Shogi different from Chess?

Shogi does share the same goals as Chess — checkmating the enemy King — and shares some of the same pieces.  However, many of the fundamentals are quite different:

  • The Board: a Shogi board is a 9×9 playing area of 81 squares, compared to the 64 squares of the chessboard.  The board is not chequered either.
  • The Pieces: Chess has six types of pieces: Pawns, Knights, Bishops, Rooks, Queens, and Kings.  Shogi has ten: Pawns, Knights, Silver Generals, Gold Generals, Lances, Rooks, Bishops, Dragons (Promoted Rooks), Horses (Promoted Bishops), and Kings.  Some of the shared pieces move differently, too: Knights make the same L-shaped jump but only forward; and Pawns move and capture only directly forward.
  • Promoting Pieces: In Chess, pawns that reach the enemy’s back rank can promote to become a Knight, Bishop, Rook, or Queen.  In Shogi, any piece that reaches the enemy camp (the three rows where their pieces begin the game) can promote.  A promoted piece flips over, and the other side of the piece indicates their promoted form.  Promoted Bishops (Horses) and promoted Rooks (Dragons) are the most powerful pieces in the game.

Shogi’s Ingenious Addition: Drops

There’s one major rule change that was added to Shogi in the 16th century and has come to define the game ever since: drops.

In Shogi, when a piece is captured, it is truly captured — it becomes the property of the capturing player.  The capturer places the piece on a small side-board called a komadai (piece stand) and holds it in reserve.  At any point from then on, they may forgo a normal move and instead drop a captured piece to any empty square on the board!  

However, an important point to remember: promoted pieces, when captured, are demoted.  Any dropped piece must be moved into the promotion zone again to be promoted.  Two other key exceptions: Pawns cannot be dropped so that you have more than one of your pawns on a single vertical line; and pieces cannot be dropped in a space where they have no legal moves.

Drops make Shogi play and feel very different from Western Chess.  Since captured pieces come back to life throughout the game, the number of pieces on the board stays roughly the same throughout — there are no endgame situations with near-empty boards, as in Chess.  The constant back-and-forth of captures and drops makes a Shogi game dynamic, aggressive and fierce — attacks are frequent, and giving up the initiative to play defensively is risky.

Thanks to drops, Shogi is also much more decisive than Chess — less than 2% of professional Shogi games end in a draw, a staggering difference from the ~60% draw rate of professional chess!

Is Shogi hard to learn?

Not really!  The biggest obstacle for most new players is learning the pieces — as you can see in the photo of my Shogi set above, all Shogi pieces are the same shape and colour, and the two players’ armies are distinguished by the pieces’ orientation (aim pointy bits at the enemy!).  The different pieces have their names written on them in Japanese kanji characters, which are not so easy to learn for people who don’t speak Japanese.

However, the best way to learn is to simply dive in — after a game or two, the kanji fade away and are easy enough to recognise.  I find it helps beginners to forget they are letters — this tends to prime us to try to divine their meaning, which makes them more intimidating.

Instead, just think of them the same way as you think of the shapes of Western Chess pieces — both are abstract shapes, and neither really relates to what the piece does or how it moves.  The kanji are effectively just symbols, just like the odd shapes of Chess pieces.  Also, you only really need to recognise the top characters on each piece — that’s enough to distinguish all the pieces from each other.

Other than that, it’s just a bigger version of Chess!  The steepest part of the learning curve after that is getting comfortable with the powerful impact of drops — this is especially strange for seasoned Chess players, who will be accustomed to captured pieces playing no further role in the game.  But again, given a few games, you’ll soon start to see the exciting, combative play allowed by the drop rule, and you’ll be chucking Gold Generals at your opponent like a pro.

How the Shogi Pieces Move:

Here’s a quick reference to the moves of the Shogi pieces:

evans-shogi-move

As you can see, the King, Rook and Bishop move the same as in Chess.  The Knight moves the same as in Chess too, but can only jump forward.  The Pawn moves forward and captures forward — no diagonal capturing like in Chess.  The Gold General moves one space in any direction except diagonally backward, while the Silver General can move one space diagonally in any direction or one space directly forward.

The promoted pieces are easy to remember — all promoted pieces move the same as the Gold General, with the exception of the Horse and Dragon.  The Horse moves like a Bishop, but can also choose to move one square orthogonally; the Dragon moves like a Rook but can also move one square diagonally in any direction.

You might notice that the Shogi pieces have a general forward bias in their movement patterns, and most are short-range movers.  This works very well with the drop rule — the combination of forward movement and drops favours attacking play, and the short-range movements prevent the game from becoming too chaotic, as it might be with powerful pieces appearing wherever they like on the board.

The flip side to this is that you can very rarely have a condition called entering Kings, where both players’ Kings have moved into each others’ promotion zones.  This makes it very difficult for anyone to win, as most of the pieces attack forward rather than backward.  This is one of the very rare ways you can have a draw in Shogi.  In practice this rarely happens, especially between beginners, who normally dive heedlessly into battle and neglect King safety entirely!

Note that the Horse provides a good reason for the Shogi board to not be chequered.  In Chess your Bishops are confined forever to half of the board — either the black diagonals or the white ones.  The Horse however can spend a move to shift from one set of diagonals to the other, so it’s less useful to have the chequers to indicate where the Bishops go — once promoted they can go anywhere.

Shogi: A whole family of amazing games

One of the things I love about Shogi is that, in a sense, it’s part of a whole game system rather than a single game.

To unpack that a little bit — you may be aware that there are many hundreds of Chess variants out there, variations on the game with different boards, pieces and rules.  Shogi has these too, but unlike in Chess, many of the Shogi variants are hundreds of years old, and were refined over the centuries into fantastic games in their own right!  Shogi variants are well-designed, well-balanced, and offer just as much intrigue and fascination as the traditional form of the game.

In fact, before the introduction of the drop rule made the modern game dominant, there used to be three variants of Shogi that were commonly played: Sho Shogi, or ‘Small Shogi’, which added drops later and become modern Shogi; Chu Shogi, or ‘Middle Shogi’, a much bigger game played on a 12×12 board of 144 squares; and Dai Shogi, or ‘Large Shogi’, played on an even bigger 15×15 board of 225 squares.  Shogi used to come in Small/Medium/Large sizes!  Alongside these main variations, there were numerous other variants of Shogi developed over the centuries, some of which I’ll describe below.

Today, besides Sho Shogi only Chu Shogi maintains a small presence — the Chu Shogi Renmei in Japan is the official governing body, and holds regular tournaments.  This is unfortunate, really, as the Shogi variants are quite unique — particularly the larger variants, which are far larger than any commonly-played Chess variants, and offer hugely creative pieces and styles of play.

Thankfully, the efforts of one George Hodges in the late 20th century led to the revival of these ancient forms of Chess, and remarkably he even manufactured affordable sets for most of the large variants.  Sadly George left us a few years ago, but his wife carries on that business, and she remains the only source on the planet for physical sets of most of the Shogi variants.  I of course have bought several of them myself 🙂

Without further ado, here’s a brief intro to a few of the more spectacular Shogi variants — several of which I will bring with me to the Shogi event in a few weeks time!

Chu Shogi

Chu Shogi is a spectacular game.   Those lucky few who have played it frequently class it as one of the finest Chess games ever invented — and I thoroughly agree.

The game is not super accessible at first — the board is much larger than in Shogi (144 squares vs 81), and there are far more pieces on the board (46 pieces per player, compared to 20 each in Shogi).  All told, you’ll have to remember 28 different piece movements instead of 10 like in Shogi!  But the rewards are very much worth it.

I should say that the larger Shogi variants do not use the drop rule — otherwise the games would go on far too long!  Instead captured pieces are lost permanently, as in Chess.

Despite the large board and huge armies, Chu Shogi maintains a pretty swift pace.  Each player starts with powerful pieces on the board from the beginning — including multiple Dragons and Horses, and the Free King which moves as a Queen in Chess.  Interesting to note here that the Queen in Chess was invented three centuries later — Chu was an extremely innovative game for the time.

The most powerful piece, and the piece that defines Chu Shogi, is the Lion.  The Lion effectively moves twice in one turn — it can make two consecutive King moves in any direction, with all that implies: it can capture twice; capture once and return to its starting square, appearing to capture without moving; or it can move once then return to its starting point, effectively passing its turn.  All of these abilities are staggeringly powerful for different reasons.  The Lion is so important and so engaging that the Chu community wisely added some rules to prevent players trading them off early in the game — it’s a bit complicated, but essentially you can’t sacrifice your Lion for your opponent to recapture unless you captured a sufficiently powerful enemy piece in the process.

Notably, Chu Shogi includes a piece called a Drunk Elephant, which moves like a King except it can’t move directly backward.  This piece promotes to Crown Prince, which is a second King — and both Kings and Princes must be captured to win the game!  Because of this, Chu and the other large variants with Drunk Elephants (most of them) don’t actually have a checkmate rule — any royal pieces must be actually captured to win the game.  This allows you to sacrifice a Prince or King for tactical reasons — although honestly that’s rarely advisable!

At any rate, it’s a fabulous game, definitely worth your time if you’ve ever enjoyed a game of Shogi or Chess.  It’s also the root of many of the larger Shogi games, meaning if you can play Chu it’s easier to jump up to the larger games afterward.

chu-shogi-set

My Chu Shogi set, in the initial position.  Board purchased from Aoyama Gobanten in Tokyo, pieces from Angela/George Hodges in the UK.  The powerhouse Lion is two squares above the King, if you’re wondering.

chu-shogi-end

The end of a Chu Shogi game — White wins after 288 moves (!), fittingly enough with a Lion checkmate.  Check out the huge piles of dead pieces on the side of the board!

Dai Shogi

Dai Shogi, big brother to Chu, is much bigger than its sibling but not that much more complicated to learn.  Essentially, take Chu, add eight more piece types with fairly easy-to-remember short-range moves, all of which promote to Gold General, and you have Dai!

Some criticise Dai as being too slow or not exciting enough, given that it’s essentially a scaled-up version of Chu with more pieces and a bigger board.  But I strongly disagree — the larger board significantly expands the options available to players, the larger armies make the game more forgiving given the lower importance of material losses, and the powerhouse Lion is less dominating on the larger playing area.  The game is indeed slower, but it’s also strategic, intriguing, and a great introduction to the larger Shogi variants given it’s easy to pick up once you know Chu.

dai dai vs shogi comparison

A comparison of Dai Shogi (left) vs modern Shogi (right) — turns out that Large Shogi is, in fact, large

dai-shogi-aftermath-568moves copy

A Dai Shogi game I won online — after a mere 568 moves.  Note my opponent threw a ‘spite check’ at me when he knew he was done for — even if I didn’t have checkmate on my next move, my Cat Sword (cool piece name) would’ve instantly recaptured his attacker anyway.

Tenjiku Shogi

Tenjiku Shogi — sometimes translated as ‘Exotic Shogi’ — is one of the most unique and dynamic games of Chess ever devised.  The game is played on a massive 16×16 board (256 squares), and each player starts with 78 pieces in their army — and yet, the pieces are so powerful that the game can be over in less moves than a game of regular Shogi!

Like Chu Shogi is defined by the Lion, Tenjiku is defined by the Fire Demon.  Each player starts with two of these.  The Fire Demon can move as far as it wants in six directions — already extremely powerful by Shogi standards.  But on top of that, it burns everything it touches!

In other words, the Fire Demon instantly kills any piece adjacent to it when it finishes moving, meaning it can capture up to eight pieces in one move.  Not only that, but if the opponent isn’t thinking and moves a piece next to it on his turn, that piece is also instantly captured — and that doesn’t count as your turn!

On top of that, your army also contains a Lion, two pieces called Water Buffaloes that promote to Fire Demons, and a number of range-capturing Generals — these are pieces that can jump over any number of enemy pieces in order to make a capture.  The upshot of all this is that, right from the opening, Tenjiku is a dynamic and dangerous game — attacks start immediately, and your huge 78-piece army starts dwindling very quickly.  No other Chess variant plays like this, and it’s an absolute blast.

tsa tenjiku1

A Tenjiku Shogi set from Angela/George Hodges — the top player’s pieces have been flipped to show off their promoted sides.  Of course I also own one of these sets.

 

Dai Dai Shogi

Dai Dai Shogi — or, literally translated, ‘Big Big Shogi’ — definitely fits its name.  The game is played on a 17×17 board of 289 squares, with each player leading an army of 96 pieces!  The starting setup, unlike most Shogi variants, is highly asymmetric — amongst the 96 pieces in your army, there are 64 different types of pieces, so many of your army are unique single pieces.  All told, you need to remember 68 different piece moves — again unlike most variants, only 20 pieces promote in this game, and most of those to Gold General.

Dai Dai is quite a fascinating game, with a style of play all its own.  This is the first large Shogi game to introduce promotion by capture — pieces promote as soon as they capture any enemy piece, and don’t have to wait until they reach the promotion zone.  This creates some intriguing tactical decisions, as some pieces effectively demote, becoming much weaker when they make a capture — so you’d better make that capture count!

This is particularly true in the case of the powerful hook-moving pieces introduced in this game: the Tengu, or long-nosed goblin, that can make two consecutive Bishop moves at right angles to each other; and the aptly-named Hook Mover, which makes two consecutive Rook moves at right angles to each other.  If that doesn’t sound so amazing, consider that a Hook-Mover on an empty board can reach any square in one move — hard to keep your King safe from that!  But, both these pieces demote on capture, so they’re effectively one-shot nuclear weapons — use them wisely.

Dai Dai Shogi is well worth a try if you’re interested in a unique twist on Shogi — the asymmetric setup, huge piece variety and powerful hook-movers make for a surprisingly aggressive game, considering the size of the board.

dai dai vs shogi comparison

Big Big Shogi indeed!  Board and pieces from Angela/George Hodges once again.

 

Maka Dai Dai Shogi

Maka Dai Dai Shogi is yet another step up in size from Tenjiku, played on a 19×19 board of 361 squares, with each player starting with an army of 96 pieces.  The name is a bit interesting — ‘Dai’ means big or large, as we know, and ‘Maka’ is a word derived from Sanskrit that means something like ‘Superior’.  So ‘Maka Dai Dai Shogi’ means basically ‘Superior Large Large Shogi’, or less awkwardly, ‘Superior Ultra-Large Shogi’.  I would argue this is pretty accurate — it’s definitely ultra-large, and has a number of superior qualities.

One of the standout qualities of Shogi as compared to Chess is that most of the pieces can promote, and the large variants for the most part carry on this tradition.  Maka Dai Dai, however, takes it to the next level, and allows the King himself to promote!  A promoted King becomes an Emperor, the most powerful piece to exist in any variant of Chess: the Emperor can instantly teleport to any unprotected square on the board, including squares occupied by enemy pieces.  In other words, the Emperor can instantly go anywhere and capture anything, so long as that square isn’t directly threatened with recapture by an enemy piece.

Alongside this, in Maka Dai Dai promotions occur by capture, as in Dai Dai Shogi.  This helps to speed up the pace of the game, as on such a large board reaching the promotion zone would take forever.  Promotion-by-capture also makes attacking the enemy King a risky proposition — if you mess it up, the King might capture an attacking piece, thereby immediately becoming an Emperor, which is both extremely powerful and desperately hard to checkmate!

“If you come at the King, you best not miss.”

–Omar Little

Maka Dai Dai, like most of the large Shogi variants, was invented by Buddhist monks — after all they have lots of time on their hands.  This is more apparent in Maka Dai Dai than the other variants, as it includes pieces drawn from Buddhist mythology that behave in unusual ways.  The Deva and Dark Spirit, for example, promote to Buddhist Spirit and Teaching King respectively — and any piece that captures them becomes a Buddhist Spirit or Teaching King, so these immortal creatures effectively never leave the board.

Substantial research has been done on this game by Professor Tomoyuki Takami, who states that Heian-Era sources suggest that Maka Dai Dai was actually one of the earliest forms of Shogi to exist.  He says that the pieces of the game are inspired by Chinese astrology and traditional masked dances and festivals of the early Heian era, and that in the early days the game was played as a form of ritual rather than entertainment.  Over the centuries, the game was reduced down to smaller forms, like Dai Dai Shogi, Dai Shogi and Chu Shogi, once they discovered that this ritual game was actually quite fun to play, but pretty long….

How long, you ask?  Well, George Hodges once compared the lengths of various versions of Shogi — this is the number of total moves in an average game for each variant:

  • Chess: 80
  • Shogi: 110
  • Dai Shogi: 400
  • Dai Dai Shogi: 800
  • Maka Dai Dai Shogi: 1100
  • Tai Shogi: 2000

Wow, that’s long.  If you start up a game of Maka Dai Dai Shogi, make sure you have the weekend free 🙂  I should say that I, of course, own a physical set for this game and would happily play it with anyone who asks.  The board is too big for my table, however, so we’d have to find a place big enough!

tsa maka set1

A Maka Dai Dai set by Angela/George Hodges — promoted pieces on top.

maka dai dai emperor

The Mighty Emperor

 

Tai Shogi

OK, now this is getting ridiculous — Tai Shogi, or ‘Supreme Shogi’, is a spectacularly huge game played on a 25×25 board of 625 squares, invented in the 15th century by Buddhist monks (of course).  Each player marches into battle with an army of 177 pieces each, and in order to play you need to remember 99 distinct piece movements.

I’ve never personally played this, but remarkably, you can actually buy a set of this from Angela Hodges here in the UK.  The board is more than a metre square!  Even experienced players take upwards of two hours to set up the pieces in their initial position.  As you can see below, each players’ starting ranks are absolutely chock full of pieces — in fact the opening phase is a bit like a sliding-block puzzle as you try to free up lines for your pieces to get into the action.

Notably, there are actually no Kings on the board — each player starts with an Emperor in play (!), and a Crown Prince that moves like a King.  Both must be captured to win the game.  Many of the other pieces have strong promotions, which occur by capture as in Dai Dai and Maka Dai Dai rather than by entering the promotion zone — so carelessly leaving pieces out to be gobbled up can rapidly turn the game against you!

Those who’ve played Tai say it’s an extremely challenging game, because it’s very hard to formulate any kind of sensible whole-board strategy in a game this large.  As a result the game plays more like a wargame, with intensely tactical local skirmishes of great complexity breaking out across the board.  Meanwhile, the everpresent Emperors make each move feel consequential — leave anything hanging and you may give the Emperor a chance to start some carnage.  Given how old this game is, the creativity of all this is astounding — it’s kind of like an ancient version of Warhammer or something.

I don’t yet own this game but certainly plan to at some point — consider this a standing challenge to all!  Once I get a set for this, I’m happy to give it a go with anyone who’s interested.

tai shogi vs shogi comparison

Regular Shogi just looks tiny compared to Tai Shogi!  Without a doubt you could play an entire Shogi tournament in the time it takes to play one game of Tai Shogi.

 

Taikyoku Shogi

Unbelievably, Tai Shogi is not the biggest Chess game to ever exist.  It used to be, until some documents were uncovered in 1997 with rules for a 16th-century Shogi variant called Taikyoku Shogi, or ‘Ultimate Shogi’.

This preposterous game is played on a 36×36 board of 1,296 squares.  Each player has an army of 402 pieces, and to play you must remember 253 distinct movement patterns.  Each side starts with a King and Crown Prince on the board, and a Drunk Elephant who can promote to Crown Prince — meaning you may have to capture three royal pieces to eventually win.

Unlike the other huge variants, in Tai Shogi promotion is once again by entering the enemy camp rather than by capture.  Each army contains a huge variety of pieces with whimsical names like the Running Bear, Vermillion Sparrow, Violent Ox, Enchanted Badger, and — my favourite — the Vertical Puppy.  If I ever play this game somehow, I’m going to devote my entire strategy toward devising a way to checkmate my opponent using the Vertical Puppy.

Amazingly, a real-life wooden set for Taikyoku Shogi was carved and used for a special segment on the Japanese variety show Fountain of Trivia back in 2004.  Two Shogi pros faced off in a game of Taikyoku Shogi, using a little reference book to help them remember how the pieces moved.  The game lasted 32 hours and 41 minutes, and ended in checkmate for the first player after 3,805 moves!

There’s a clip of the match on YouTube, unfortunately the quality isn’t great but the whole segment is there: https://www.youtube.com/watch?v=_c0Y26iTPSM

At the end of the match, the winning player says ‘I don’t want to do that again’; the loser says something hard to translate, but it’s kind of like ‘I have no regrets’, conveying the impression he doesn’t mind losing something so bizarre, and is mostly glad it’s over.

taikyoku-real1

A fanmade version of Taikyoku Shogi — quite impressive!

Where do I go from here?

Well, as you can see, Shogi offers a whole world of interesting games.  I wrote far too much here, and yet still didn’t cover anywhere near all the variants — there’s a number of smaller ones too, but I just love the big monster games.  If you fancy trying a variant of Shogi, and want to pick just one, I’d recommend Chu Shogi — it’s monstrous without being ponderous, and the Lion is such a creative and beautifully-balanced addition to the game.  Leaving aside my nerdy fascination with all things Shogi, it’s a genuinely delightful game.

Your best bet of course is to play modern Shogi — in my opinion it’s the finest version of Chess by quite some distance, and can easily support a lifetime of play and study.  There are numerous places these days to play online, like 81dojo  which is free, in English and supports several variants as well.  Obviously modern Shogi has by far the largest playing community of any version of Shogi, and rightfully so — it strikes a balance between complexity and simplicity that’s hard to beat.

For a taste of Shogi, come on down to our Shogi event next month and get acquainted with the modern game!  I’m sure you’ll enjoy it, even if just as a peek into a corner of Japanese culture most of us never see.  For those of you who really take a fancy to the game, you’re welcome to join Shuzo and myself in our soon-to-be-launched Shogi club, which will meet regularly in Glasgow to play Shogi and learn about the game.

And, if you’re a weirdo like me who can easily spend all day playing games, join me for a game of Chu, Dai, Tenjiku or Maka Dai Dai Shogi!  Just make sure you free up your schedule first 🙂

 

 

Tagged , , , , , , , , ,

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 Syzygy-Tables.info; 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:

KPPvsKP TBs 2

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:

KBBvsKQ TBs

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:

KNNvsKP TBs

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 , ,

(Re-)Learning C Via Computer Chess

In recent months I haven’t had much time to do a lot of programming, what with the demands of my work. One thing I’d been meaning to do, whether it factors into my research directly or not, was to re-acquaint myself with the C programming language. I used it way back in the day, but then as time went on I fell in love with Python, which despite being ridiculously slow in comparison, is extremely fun to use. But the fact remains that it’s very useful to be able to write compact, speedy code from time to time, either for writing simulations for work or for passion projects.

So, I decided to find myself just such a passion project to rediscover the joy of programming in C, and given that I’ve been playing and studying a hell of a lot of chess and shogi in my spare time of late, I decided to learn how to program a fast and relatively powerful chess engine in C. A traditional chess engine uses brute force to search a very large number of possible moves on its turn, evaluating each one in turn until it chooses what it thinks is the best move for the situation. Given how much computing power is available these days, even a half-decent smartphone can now play chess at a level greater than any human, including Grandmaster-level professionals.

In order to do this I followed a great series of videos on YouTube called ‘Programming a Chess Engine in C’, which is 95 videos long (!), but covers a ton of stuff, helping you build a fully-functional chess engine in C which uses the standard techniques in chess programming — alpha-beta search with null-move pruning and some other optimisations. The engine is capable of playing a game of chess via text commands with the user, or by communicating with graphical chess software using the UCI or WinBoard/CECP protocols to let you play a game with mouse control and lovely graphics for the pieces.

After watching all that and feeling my way around C again, I’ve now produced a chess engine of my own, which I’ve named SpaceDog, in honour of my dog who is from space.  At the moment it’s basically the same as the VICE engine which comes from the videos above, but has a few small additions in the evaluation function to make it a little stronger (hopefully), as well as a few quality-of-life improvements here and there.  It works great, and plays a mean game of chess already — which perhaps isn’t surprising since it searches and evaluates about 3.5 million chess positions per second!  In comparison a master-level human player might evaluate perhaps 3 or 4 positions per second.

Here’s a screenshot of SpaceDog playing in text mode:

Screen Shot 2018-10-14 at 03.23.34As you can see, it prints out a nice little text-based board for you (white pieces are capital letters, black pieces are lowercase).  Moves are entered in long algebraic notation — so to move white’s queen at the bottom of the board to the square above white’s king, you’d enter d1e2.  SpaceDog also prints out its search results and position evaluations on each move, so here you can see at the bottom that it searched nine moves ahead (depth:9) and spent 2.9 seconds evaluating 11.9 million moves before choosing the move e7e4 (taking my pawn with its queen) based on what it thinks of the resulting position and its future prospects.

Every searched position is evaluated quite simply, with a score calculated on the basis of material balance, the position of the pieces, and things like whether there are isolated pawns and other key features.  Right now I’m adding some additional evaluation terms that better capture how the relative value of certain pieces, and their ideal placement on the board, changes as you proceed from the opening to the endgame.  Hopefully this will make SpaceDog a bit more shrewd at finding checkmate!

The engine can also use opening books — these are files generated by processing millions of opening moves from many hundreds of thousands of professional chess games, choosing a repertoire of openings based on what moves proved to be most successful.  This means SpaceDog essentially has a huge file of opening moves already catalogued in the book, with an enormous selection of replies and counter-replies for all the best possible responses from the opponent.  These moves then don’t need to be searched, meaning that SpaceDog saves tons of time for searching much deeper in difficult middlegame and endgame positions.

At this point SpaceDog probably plays well enough to beat anyone I know, but would likely still lose to players above Master level.  That would probably change at fast time controls — i.e., quick game setups like blitz (5 or 10 minute time limit for each player) or bullet (1 minute each!).  At these time controls, humans simply can’t make much use out of our superior long-term strategic planning abilities, so even SpaceDog’s rudimentary but tactically sound play should be tough to beat when us human meat-bags are sweating over the clock and feeling the pressure.

Anyway, it’s been a lot of fun so I plan to keep it going!  Next steps are to continue to enhance the evaluation function to better account for things like keeping the king safe and setting up outposts for bishops and knights.  I’ll also work on some more technical enhancements like multi-PV search (searching multiple lines of play on multiple CPU cores simultaneously) and adding support for endgame tablebases to allow SpaceDog to achieve perfect endgame play.

Most importantly though, I want to add a mode so SpaceDog can play Crazyhouse and Chessgi, variants of chess in which captured pieces become yours and can be dropped back onto the board as part of your army.  This is a feature taken directly from shogi which is a game I also love, so I’m looking forward to implementing these.  Eventually I may try to build on that foundation and add a shogi mode as well.

‘What’s the point of all this?’ you’re probably asking at this point — after all, SpaceDog will never be as good as current strongest engine Stockfish, and plenty of other engines play Crazyhouse and lots of other variants besides (such as this version of the mighty Stockfish).  There are even innovative neural-network-based engines coming out now like LCZero that are challenging for the throne of toughest computer opponent.  But nevertheless writing SpaceDog has been satisfying and fun, and it’s given me another way to learn more about chess and enjoy the game from a different angle.  I’d also forgotten how satisfying coding in C can be — the final SpaceDog program takes up only 74KB (!), yet it effortlessly plays chess better than I can.

Anyway, I thought I’d post this up just on the off chance anyone else might get something out of learning a bit about chess programming.  I highly recommend the tutorial videos I linked above from Bluefever Software — they’re really easy to follow and provide excellent explanations of the key concepts you’ll need to know to write a chess engine.

Someday I’ll post up the code for SpaceDog too, once I add a few more additional features in!

Tagged , , ,