This chess puzzle has become popular in the last few days:

enter image description here

But doesn't the white king just need to wander to where the cross is, then move the white pawn forward, then the black bishop takes it and it is a draw in 50 moves.

This question was posed by Roger Penrose who is a great and successful academic. Why it is interesting? Is it really true that computers can't solve it?

  • 14
    I think you definitely don't want to move that white pawn... – Sconibulus Mar 17 '17 at 17:05
  • Why not go two steps further to B8 to ensure the king can't move out of his cage while the pawn moves forward? – Ian MacDonald Mar 17 '17 at 17:19
  • @IanMacDonald I think you mean A8. The king would be in check in B8. – felipa Mar 17 '17 at 19:24
  • Would a computer playing White make a losing move, or would it simply make arbitrary harmless moves until the game ends up being drawn? If the latter, what's the problem? – supercat Mar 17 '17 at 19:28
  • Yeah, I guess, but the king would have to move through B8 to get to A8. – Ian MacDonald Mar 17 '17 at 19:36
up vote 26 down vote accepted

This has something to do with the way computers evaluate positions. They will first count the value of each side's pieces (usually: pawn = 1, knight/bishop = 3, rook = 5, queen = 9) and then some other things, like pawn structure and mobility (number of possible moves). Based on that, Black is much better in this position. Computers don't have a way to 'see' that Black can't liberate himself from the position without White's help, and because the bishops are limited to the dark squares, they can't mate White on their own, or capture the white pawns, liberating the other pieces.

A computer will just 'mindlessly' move the Black bishops around, and only when almost 50 moves have been made, conclude that there is no progress to be made and the game is a draw (because of the 50-move rule, which says that after 50 moves without captures and pawn moves, the game is a draw).

It is said that only if you remove two of the three bishops, some engines are able to see it's a draw. The position as shown is too hard for them; see these two ChessBase articles. The image below, from the article by Sagar Shah, shows that a modern engine thinks Black has an advantage of almost 25 pawns:

enter image description here

Oh, and by the way: the solution you mention actually gives the draw away. The c6 pawn is needed to keep the black king inside his cage. The actual solution is just to move your king along the white squares and nothing else.

  • Has anyone tested this with Stockfish for example? – felipa Mar 17 '17 at 19:06
  • 2
    Even if the computer thinks Black has an advantage, does it matter? Nobody ever won by resigning, and all White has to do to force a draw is never voluntarily move C7. That is literally White's only losing move (other than resignation) and Black has no way to force it. More interesting would be a position which allowed black to sacrifice a queen in a way that would resolve to an ending that would be winnable only after many moves but would prevent White from securing a draw. – supercat Mar 17 '17 at 20:18
  • 2
    I put the position into Stockfish on a reasonably fast PC. After running for about 8 minutes it's at ~5 billion nodes examined and depth 48 (it's been at depth 48 for several minutes now) and still reckoning the evaluation at about -28. – Gareth McCaughan Mar 17 '17 at 21:24
  • Does depth 48 mean 48 moves or 48 ply? – eyeballfrog Mar 17 '17 at 22:46
  • 2
    @supercat, capturing one of the black rooks would also be a losing move for white – ilkkachu Mar 19 '17 at 10:14

The problem is something of a red herring. If you implement a computer chess algorithm by (mostly) exhaustive search and piece-counting then it is possible that so many moves need to be made before the right set of moves is found that the computer will never find them; or take ages to find them; or draw first from lack of captures (as pointed out already). If you implement a computer algorithm to look for other things (e.g. test if the only effective opposing pieces are black bishops, so conclude you must make sure you stay on white squares) then it could perfectly well solve the problem. These things are unlikely to be in a standard chess algorithm because they'd probably be judged to be only relevant in an obscure, and artificial, situation and therefore never worth implementing. Machine 'intelligence' implemented in the way it likely will be in a chess program (optimised to win normal games) won't solve the puzzle. But there is no reason a computer can't, if it is optimised to solve different puzzles. The question is when the (very, very, significant) effort to create a general purpose algorithm is deliverable, given that special cases matter. The half-way house (an algorithm coded to look for the traits this puzzle exhibits and then solve it) is achievable now IMO - that's what a chess program does for normal chess traits.

The problem highlights that an optimised, single purpose, algorithm isn't intelligence despite being able to beat a human intelligence on a bespoke problem. It highlights that chess programs (today) aren't general purpose intelligences. But it doesn't tell us that (at some point) a learning algorithm couldn't mimic a human well enough to solve general purpose problems (including this one) and (subject to philosophical debate) be an intelligence.

  • Thanks but is it actually true? I mean has anyone tested this using a modern computer chess program? – felipa Mar 17 '17 at 19:23

Other answers have considered the issue of how computer programs usually think (calculate), i.e. what kind of an algorithm they use to find moves to play.

In addition to that, I think it's also important to consider what they are likely to have been made to think about: most likely winning the game as per the rules, including the starting position. Possibly also analyzing positions encountered during a game, in which the players have been trying to win.

This is not the case here:
to get to this position, both players must have been collaborating to create a dead-end position for black.

  • Black, having moved their pieces so that most of them have no moves, and also promoting one two of their pawns to bishops taking care to do so on appropriately coloured squares.
  • White, having allowed black to gain a considerable material advantage, and also enabling black to move their pawns sideways to block the other black pieces.

Very little of this would happen if even one of the players tried to win, so the position is outside the scope of your usual computer chess program.

Whether a computer can solve this problem or not depends on how you program it. A computer would not need to keep track of a large number of positions in order to find a strategy that white could use to force a draw.

If the white king was to keep moving between two white squares, there is no way for black to force the white king away from there. And black would only be able to move the pawns between 26 squares. That's a total of 2600 possible positions for the pawns and 2 for the king for a total of just 5200 positions.

If a computer was going to actively search for a strategy to keep alternating between a small number of possible board positions, it should be possible to find the solution with those 5200 positions in a split second.

All of those positions could easily be fit in 512KB of memory, and the computer then just has to realize that black can never get to any other position than those neither force white to move to any other position.

But many other algorithms commonly used in chess software would not find the solution. So this all boils down to whether the designer of the chess software included an algorithm applicable to this scenario. With the right algorithm a 90s home computer would have the computing power to solve it.

The drawback of such an algorithm is that it is rarely useful in more realistic game scenarios. In your example white already has achieved a position where black has very limited mobility. But if white had to first spend a few moves forcing black into such a restricted position, the number of computations goes up. It is much less realistic to say compute all possibilities for the next 4 moves and from each of those positions evaluate whether one player can force the game into a stall where it keeps getting back into the same set of less than 10k positions.

  • 1
    Ah... the white king can move to almost any white square, and most black squares, not just 2 squares (kings can move diagonally) The computer would also try white advancing his pawn for each position. BTW the 3 black pieces in the open are called bishops. – boboquack Mar 18 '17 at 2:54
  • Additionally, I am not aware of any chess programs that plan strategy. They merely analyze positions and calculate all possible variations. – Herb Wolfe Mar 18 '17 at 3:19
  • @boboquack The point is when looking for a strategy for white you can choose to ignore many of the moves which white could do, but you have to take into account all of the moves which black could do. – kasperd Mar 18 '17 at 9:27

The question was: This question was posed by Roger Penrose who is a great and successful academic. Why it is interesting? Is it really true that computers can't solve it?

What really Penrose was attempting to tell us, is that human have a rather interesting way of solving problem. Humans are not trying to solve them in an algorithm way (like computers), we try to understand the inner working of the problem. This isn't about chess, it is about "thinking" for lack of a better word. I'm a 40 year veteran of computer programming. I can say one thing for sure, computer are really unintelligent. They do not "know" anything and certainly do not understand anything. What they do well, in fact almost "God like", is to manipulate symbols and follow rules in a rigid way. This gives a computer the appearance on intelligence, when in fact it is just a machine following the rules given by a human. So if a "problem" can be approached in some way using well stated rules, a computer, given enough resources and time, will usually (not always) give back an answer. Bernard B.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.