Can we still deceive computers in chess?
Musings by Kiyoshi Takahashi
Despite the relatively good results of Kasparov against supercomputers (beat Deep Blue in 1996, lost to it in 1997, drew against Deep Junior and against X3D Fritz in 2003), people have somehow stopped believing humans can beat the machine at chess. There have however always been positions weakly understood by computer-based chess engines... at least until recently.
Basic endgame positions with few pieces
We call endgame the part of the game where only few pieces are still on the board. Some of the endgame positions are known to be drawn, especially when there are very few pieces left on the board. For example, everyone knows that if only the two kings are left, the position is drawn. The computer has no problems understanding this as the position is equal in material. If one player has just the king and his opponent has just a king and a knight, the position is also officially drawn as you cannot mate a king with just king and knight. The computer knows it as it is part of the rules.
The problem begins to appear with just one more piece, for example in a king versus a king, a bishop and an edge pawn positions. If the bishop is the so-called "bad bishop" (opposite color of the promoting square) and the defending king is well positioned, then the position is known by humans to be a draw. Why? Because the bishop is not helpful: you cannot check the king when he "waits" on the promoting square and checking the king on the next square will just make him go back to the promoting square. The only thing you may obtain is a stalemate, where the defending player has no legal move which is a draw. Computers used to have a hard time understanding it because they could not understand that no progress is being made – as long as they could move around keeping the same material advantage, they were happy).
Another type of position is called a "fortress". It is when one side has a disadvantage of material but manages to create a "safe" zone. For example, with king, pawn and rook against king and queen. The defending side will try to make the pawn protect the rook and the king protects the pawn. The attacking side cannot take the rook as it is protected by the pawn and cannot take the pawn as it is protected by the king.
How to make computers understand better those positions?
This typical problem has been solved with the so-called "endgame tablebases", which are the theoritical result and perfect play in every position when few pieces are left on the board. The tablebases used today contain every possible position with six or fewer pieces (including the two kings), i.e. you cannot trick the computer anymore in positions with few pieces. Not all programs have tablebases, but in man vs machine games they are generally used by the computer.
More pieces – blocked positions
Positions where tablebases cannot help (too many pieces left on the board) can be challenging for computers. Some of those positions are based on the fact that everything is "blocked" and no more progress can be made. Here is a very easy example:
Everything is blocked and having two extra rooks and an extra bishop does not help. Humans understand quite quickly that there is nothing to do here, but computers will happily play 50 useless moves before accepting this is a draw (after 50 moves without capture or pawn move is a draw).
You can try the following experiment: play ...Rb5 for black in the above position and see how long it take for different chess programs to recognise that they must not take the rook.
Another elementary position is based on the same idea, with fewer pawns:
The bishop is completely useless and as the black king cannot penetrate or attack white pawns the position is a draw. So this position is a draw – but check the evaluation of your chess engine.
So many blocked pawns are not even necessary. This following position is also a draw:
Black has much more pawns and they are not theoretically blocked, but if they move, they are immediately captured. Once again try out your engines in the above position. Actually, endgames with opposite color bishops are often drawn because those pieces cannot fight against each other.
Finally, there is another type of drawn game: the perpetual check. One player can check his opponent ad eternam. One example is the end of a wonderful study by Djaja.
The black player has a material advantage of the exchange and his/her pawn is more advanced. However, White can save the day by checking the opponent continuously with the rook (on the g-file). The black king has no shelters and cannot escape those checks.
Computers are beaten then, right?
No, still not. A new type of analysis called Monte Carlo is now making computers able to understand when a position is drawn because no more progress can be made. How? The chess engine will start multiple ultra fast games against itself and analyse the results of those games. If they are all draw (50 moves without piece capture or pawn move is a draw), the computer will understand the position is draw. Also, if for example, one move leads to only drawn positions while other moves lead to lost games, the computer will understand that it has to play this one move, even if it does not understand why (fortress? perpetual check? blocked position? does not matter as long as the result is there).
No more hope to trick the machine, then?
There are still complex middle games positions that are difficult to assess for both humans and computers, especially if they are not conventional (queen exchanged for three minor pieces, or rook versus four pawns). Also some sharp opening lines, where one sacrifices material for long lasting initiative or a better pawn structure. These may still be difficult to understand for computers.
Finally, we need to remember that:
computers were created, designed, programmed by humans. So, it is not entirely man vs machine, but more human (chess players) vs human (programmers)
computer improvements are also beneficial for humans. Strong players prepare their opening with the help of chess engines and everyone can analyze games (whether against another person or against a computer) or check some particular positions with chess programs
- since I was a kid I have heard: "the computer will soon be stronger than humans at chess, so the interest for chess will disappear". I never understood that. Machines can also move faster than us, so does that mean we have lost interest for the marathon, swimming (for speed), speed-skating? Yes, computers are now better than us at chess, but no, we have not lost interest in the game and will probably never do so – at least not because of the computer strength.
The Behting Study revisited
The subject of deceiving computers – or giving them the very few tasks left that they cannot solve – forces us to revisit a study we have been using for many years now. The story begins in 1983, when, as a rooky journalist, Frederic Friedel co-founded the first German computer chess magazine, Computerschach & Spiele. In the very first issue of the magazine he presented a study about which he wrote the following: "Why will computers beat world champion Anatoly Karpov" [ah, yes, Tolya ruled at the time] "before they will be able to solve the following study." And then he presented the famous "Behting Study".
K. K. Behting, Baltische Schachblätter 1908
White to play and draw
This, you must admit, is not a very complex position. Just two knights and a few pawns. But it goes beyond the horizon of most computers – and most human beings. Try to work it out. Normally we tend to ask our readers to solve puzzles and problems without seeking assistance from the electronic smarty-pants. In this case we explicitly ask you to analyse the position with the finest chess program and most powerful computers at your disposal. The best way to go about it is to play the white side and let the computer attack with the black pieces. Unless you find the one correct solution it will frustrate your every attempt to hold the position for white.
On the other hand you can let the chess program work on the diagram position, for many hours – or days if necessary. It is probably too much to expect it to find the correct first move with a 0.00 evaluation (indicating a draw). But it would be interesting to know if a computer can find the correct solution, even though it thinks that the position is still hopelessly lost for White.
So what is this mysterious, this legendary first move? Well, simply one of the deepest we have ever encountered in a chess study. It is also enchanting to note that revealing the solution would involve showing people the first three white moves and then briefly explain a logical point. After that you would immediately agree that the position is a dead draw, that indeed the solution is perfectly correct.
We cannot bring it over ourselves to reveal the solution just yet – and spoil the study for readers who have not seen it before. Here's the deal: we will publish the solution at the end of the week, giving everyone the opportunity to solve it themselves, with the full assistance of their computer brains. After that we will give the solution and ask you to check it one more time for cooks. Please do not send feedback on this study until the solution and the second part is published.