Computer chess and the 50‐move rule

An essay

Computer chess

I bought my first chess computer in 1979. It was a Chess Challenger 7 and it cost me £95, which is about £500 (US$850) at today’s prices. Its playing strength was around Elo 1000, not much above beginner standard. It was the size, shape and weight of a tray of chocolates and about as fragile. Now in 2014 you can get chess software free on the Internet that, when run on an ordinary personal computer, can defeat most master players under tournament conditions. Computer chess has come of age.

In modern computer chess there is a division of duties between two separate pieces of software: the clever bit and the pretty bit. The clever bit is the chess engine: you can’t see it, but it works behind the scenes analysing positions and recommending moves. The pretty bit is the chess GUI (graphical user interface), which displays the position and the moves and takes moves from the user. Whenever the user asks the computer for a move, the chess GUI communicates with the chess engine through a standard protocol, and plays the move that the chess engine recommends. Chess GUIs and strong chess engines are both available free on the Internet.

Chess engines have come of age, but in one respect they are still like juniors. They don’t like endings. The techniques they employ, like tree searching and position evaluation, don’t work so well in endings. To play an ending well you need to formulate a plan, and attempts to create chess engines that formulate plans have not been very successful.

So wouldn’t it be splendid if a chess engine could consult a library that told it with certainty the best move to play in every conceivable endgame position with at most, say, 7 pieces?

Well, nowadays it can. The library is called a tablebase. A 5‐piece tablebase, for example, catalogues all positions with 5 pieces, including the two kings and including any pawns. Tablebases for 3, 4, 5 and 6 pieces can be downloaded free on the Internet. Their size increases rapidly with the number of pieces. The Syzygy 5‐piece tablebase occupies 1 gigabyte of hard disc space, the 6‐piece tablebase 149 gigabytes. The new Lomonosov 7‐piece tablebase occupies 140 terabytes: it is stored on large servers and may be consulted online for a reasonable paid subscription. Of course many endings have more than 7 pieces, but a chess engine playing an ending with more than 7 pieces needs to evaluate positions that may arise after further captures, and in doing so it may make valuable use of its tablebases for 7 pieces and fewer.

To play an ending well you need to formulate a plan, or consult a tablebase.

Metrics

With access to a tablebase, it is easier to draw a drawn position than to win a won position. To draw a drawn position it is sufficient that you always play a move that keeps the position drawn. But to win a won position it is not sufficient that you always play a move that keeps the position won. You must make progress; you must be able to reach successive goals culminating in checkmate. For this purpose, when you look up a won position in a tablebase it will return to you a number representing how far you are from some goal. Then if you have a won position and you have, say, 10 legal moves in that position, you can feed to the tablebase each of the 10 prospective positions in turn and choose the one that is closest to the goal.

Different tablebases may employ different goals, and different measures of how far you are from the goal. That is, different tablebases may employ different metrics.

DTM

The simplest metric is called DTM: depth‐to‐mate, or distance‐to‐mate. The distance‐to‐mate may be expressed in moves, counting each White move and each Black move as half a move, or it may be expressed in ply, counting each White move and each Black move as one ply. So 7 moves is 14 ply. The earliest tablebases used the DTM metric. Popular tablebases today that use the DTM metric include the Nalimov and Gaviota tablebases.

If you are not familiar with game theory, then it may not be clear to you what it means to say that a given position is, say, 7 moves from mate. Surely the distance to mate depends on how the players play? Yes indeed, but we mean 7 moves from mate if both players play the best moves. Then what do we mean by the best move? Well, we mean the move that optimises the distance to mate: minimises it if you are the attacker, maximises it if you are the defender. Is there not a circularity there? As I have expressed things so far, yes there is. But the circularity can be resolved. Chess is a two‐person zero‐sum game of perfect information. It is zero‐sum because when either player wins the other player loses. Perfect information means that both players know the full state of the game at all times, unlike card games where you can’t see your opponent’s hand. In these circumstances game theory tells us that in a won position there is a well‐defined distance‐to‐mate, called the minimax distance. The attacker can reach mate in at most that distance, whatever the defender does; and the defender can defer mate for at least that distance, whatever the attacker does. When we use the term distance‐to‐mate and do not qualify it, we mean the minimax distance.

The following position, which we will revisit several times, can be used to illustrate DTM.

Endings of this class, with two knights against a pawn, known as the two‐knights endgame, are notoriously difficult for humans to play unaided. Two knights on their own cannot force a win because of stalemate threats. Two knights against a pawn, however, may be able to force a win. The idea is to blockade the pawn with one knight, corner the defending king with your king and the other knight, and finally bring the blockading knight into the game to give checkmate with both knights. As soon as the blockading knight moves, the pawn can move, depriving the defender of his stalemate resource.

DTM tablebases report that in the above position White can win and the distance‐to‐mate is 74½ moves, or 149 ply. That is to say, White can force mate on his 75th move, and not earlier. If you are interested, you can use the navigation buttons in Diagram 1 to see DTM‐optimal play. Do not try to understand the play in detail: indeed in the early part of the sequence it is well nigh impossible to do so. The play includes a move, 28 Nf4, that, for me, is the most beautiful move I have ever seen in the whole of chess. Clicking the button labelled + takes you on a lightning tour of the play lasting about a minute.

The 50‐move rule

The world governing body for chess is the World Chess Federation, known by its French acronym FIDE. One of the FIDE rules is the 50‐move rule, which says (in effect, and ignoring procedural niceties) that if the last 50 moves made by both players do not include any capture, pawn move or checkmate, then either player may claim a draw. The purpose of the 50‐move rule is to prevent games from continuing indefinitely, and to prevent a player from winning by merely tiring his opponent out. The DTM metric takes no account of the 50‐move rule.

The 50‐move rule is ancient, dating back at least to Ruy López in 1561. Until the 20th Century it was conventional wisdom that any position winnable without the 50‐move rule was winnable with it, so that the 50‐move rule was thought to be a purely practical matter with no theoretical implications. In the early 20th Century the chess theorist Alexey Troitsky found exceptions, including the two‐knights endgame, as well as the endgame of rook and bishop against rook. For a while FIDE tried to keep track, extending the 50‐move limit for known exceptions. With the advent of computers, it became clear that the fount of such exceptions is practically bottomless, and FIDE gave up trying to cater for them, returning to the simple 50‐move rule for all positions.

We can posit a move counter, with the following properties: it is initialised to 0 at the beginning of the game; it is reset to 0 by every capture, by every pawn move and by checkmate; it increments by 1 ply with every move by either player not of those three types; and it triggers the opportunity to claim a draw if it ever reaches 100 ply.

The position in Diagram 1 was presented with no history and no mention of its movecount. By convention in those circumstances we take its movecount to be 0. We could say that there was no previous play (personally I dislike that interpretation, as it is inconsistent with the Laws of Chess) or we can suppose that Black’s most recent move leading up to the position was a capture or a pawn move (in my view a much better interpretation).

We have seen that the distance‐to‐mate in Diagram 1 is 74½ moves, and you will have noticed that 74½ moves is greater than 50 moves. It could have been worse: there are positions with two knights against a pawn whose distance‐to‐mate is as high as 114½ moves, and there is a position with queen and pawn against rook bishop and knight whose distance‐to‐mate is 548½ moves.

So does that mean that the position in Diagram 1 is drawn? No it doesn’t, for there is the small matter of the pawn moves, which reset the move counter to 0. It might seem like a good idea to inspect the DTM‐optimal play from Diagram 1 and note when the pawn moves actually take place. If you do that, you find that they take place as shown on Timeline 1:

Timeline 1: Pawn moves in DTM‐optimal play from Diagram 1

The pawn moves are nicely spread out. The move counter reaches 43½ moves and no farther. All that matters to us is that it never reaches 50 moves. Black has no opportunity to claim a draw.

So that’s all right then: the position in Diagram 1 is won? We can’t draw that conclusion! Black was playing to maximise the distance to mate. No one can force him to do that. He may seek instead to increase the distance between the pawn moves, even if that means reducing the distance to mate. If White is playing DTM‐optimal moves and Black is clever, then indeed Black can do that. You can follow the moves on the game viewer from Diagram 2:

The pawn moves are shown in Timeline 2.

Timeline 2: Pawn moves from Diagram 2

The pawn moves are no longer so evenly spread out. The move counter reaches 50 moves: indeed, 64½ moves. Black can claim a draw.

So that means that the position in Diagram 1 is drawn, then? Not so fast! White need not stand idly by while Black manipulates the distance between the pawn moves. Two can play at that game. While Black plays to maximise the distance between the pawn moves, White can play to minimise it, even if that means increasing the distance to mate.

But how does White work out what moves to play? By now it may be dawning on you that we need a new metric.

DTZ50

In fact the position in Diagram 1 is a win for White, as we will shortly discover. And yet we have seen that, because of the 50‐move rule, DTM‐optimal play by White can fail to win it. In short, the DTM metric does not cope with the 50‐move rule.

A more recent metric designed to cope with the 50‐move rule is DTZ50. The letters DTZ stand for “depth to zeroing” or “distance to zeroing” and the 50 alludes to the 50‐move rule. “Zeroing” refers to the zeroing of the move counter by a capture, pawn move or checkmate. The popular Syzygy tablebase employs DTZ50.

The DTZ50 metric does not use checkmate as its goal. Instead it uses the intermediate goal of reaching a won position that occurs immediately after the move counter has been zeroed by a capture, pawn move or checkmate. When you look up a won position in a DTZ50 tablebase it will tell you the minimax distance to such zeroing. Here, “won position” means won taking account of the 50‐move rule. The minimax distance that the tablebase returns will obviously be at most 100 ply.

In the play shown with Diagram 2, White was playing DTM‐optimal moves, whereas Black was playing DTZ50‐optimal moves, which is how Black was able to extend the gap between the pawn moves.

In theory, the DTZ50 metric fully solves the problem of playing a perfect ending with an appropriate number of pieces under the 50‐move rule. It plays a perfect ending in the sense that it will always win a won game and always at least draw a drawn game. It always wins a won game because it will always reach the next zeroing of the move counter while keeping the position won, and reaching checkmate can only involve a finite number of such zeroings: any given pawn can only move 6 times, and any given piece can only be captured once.

In the position in Diagram 1, the value of the DTZ50 metric is exactly 100 ply, which is why I chose that position. So we can finally say that the position is won. If you are interested you can follow the DTZ50‐optimal play on the game viewer from Diagram 3:

The pawn moves are shown on Timeline 3.

Timeline 3: Pawn moves in DTZ50‐optimal play from Diagram 3

DTZ50 may be perfect in theory, but it suffers from a laughable practical quirk. Look at Diagram 4 below.

Even a beginner will find 1. Kb6 Kb8 2. Qd8#. The position after 1. Kb6 has a depth‐to‐zeroing of 2 ply. But the DTZ50‐optimal move is the comical 1. Qd8+. After that move, the position has a depth‐to‐zeroing of only 1 ply and is still won: 1...Kxd8 is forced and White can mate on move 85. And before you can scream, “No modern chess engine would be so stupid!” I can tell you that I have Houdini 4, among the strongest chess engines on the planet, and I use it with the Syzygy DTZ50 tablebase that its documentation recommends, and it does play 1. Qd8+ in that position.

In one sense that is not so stupid. DTZ50, like DTM, is a movecount‐independent metric. When a DTM or DTZ50 tablebase considers a position, it doesn’t know the movecount of the position and it doesn’t care. If the movecount in Diagram 4 happens to be 98 ply – because White has been playing aimless moves for the last half hour – then 1 Qd8+, or perhaps it should now be called 50 Qd8+, is the only winning move. But that is not an adequate excuse. The tablebase doesn’t know that the movecount is 0, but the chess engine does. Before recommending the DTZ50‐optimal move in a position with a low movecount, the chess engine really ought to do a little homespun analysis to check for any obvious improvements.

DTM50 – a new metric

It is an ideal worthy of any chess player, human or machine, to win a won game in as few moves as possible. What we really want, then, is a DTM50 metric: distance‐to‐mate, taking account of the 50‐move rule. DTM50 tablebases are currently being constructed. They are much more complex than DTM and DTZ50 tablebases, because the DTM50 metric is movecount‐dependent. We saw why with Diagram 4: if the movecount is 97 ply or less the distance‐to‐mate is 3 ply, but if the movecount is 98 ply the distance‐to‐mate is 169 ply, while if the movecount is 99 ply or more the position is drawn. With so much extra information to store, a DTM50 tablebase will necessarily be considerably larger than existing DTM or DTZ50 tablebases.

If you are interested you can follow DTM50‐optimal play on the game viewer from Diagram 5. Many thanks to Galen Huntington, one of the authors of the new DTM50 tablebases, for kindly checking and correcting the play.

The pawn moves take place as shown on Timeline 5.

Timeline 5: Pawn moves in DTM50‐optimal play from Diagram 5

Is the 50‐move rule a Good Thing?

The 50‐move rule tends to be unpopular among computer chess buffs. I can see their point: there is a certain charm in a 7‐piece position with a distance‐to‐mate of 548½ moves, and it is a bit of a dampener to be told that it is invalid because of the 50‐move rule. Computer chess theorists tend to regard chess without the 50‐move rule as “pure”, and the 50‐move rule as a contamination to be rid of. Some are optimists: they look forward to a day when FIDE will abolish the 50‐move rule. Some are in denial: “Who uses FIDE rules anyway?” (The whole world except the USA, that’s who.)

The irony is that the 50‐move rule is counterproductive. We have seen that without the 50‐move rule White can mate from Diagram 1 in 75 moves, and that with the 50‐move rule it takes 90 moves. It is to be expected that it will take longer with the 50‐move rule, because there is more drawn territory that White has to avoid. Far from its purpose of shortening games, with best play the 50‐move rule lengthens them.

Practical, over‐the‐board chess between human opponents will continue to need the 50‐move rule or something like it. Otherwise, what is to be the result of a game that reaches Position 1? The result should depend on the skill of the players. It would be unfair on Black to award a win to White if White has no idea of how to win; and it would be unfair on White to award a draw to Black if White is one of the few players in the world capable of winning against any defence; and it would be preposterous to allow the game to go on indefinitely. The current paradigm of allowing White a chance to make progress, and awarding a draw if he cannot, seems the only fair solution.

So it seems that there will continue to be two chesses: the parent game, human chess, with its 50‐move rule; and its offspring, computer‐aided endgame theory, without the 50‐move rule. The offspring, the computer version, has flown the nest. It has come of age.