This chess puzzle has become popular in the last few days:
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?
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:
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.
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.
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.
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.
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.
