# Solve Penrose's chess puzzle that's 'impossible for a computer'! **URL:** \ **Category:** The Game Room\ **Created:** [March 14, 2017, 11:49am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154 "2017-03-14T11:49:06Z")\ **Posts on this page:** 20\ **Page:** 2
**Author:** ![flynnt](https://avatars.discourse-cdn.com/v4/letter/f/53a042/32.png) [@flynnt](https://boards.straightdope.com/u/flynnt)\ **Post date:** [March 15, 2017, 1:36pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/21 "2017-03-15T13:36:28Z")
> [@Half\_Man\_Half\_Wit](#): > > But that only tells us something about the way we write chess programs, not about any intrinsic differences between human minds and computers. That’s what I was thinking at first, but it occurred to me it’s not an accurate comparison since computers don’t have minds per se. Their “minds” are an imitation our minds, the thought processes of the people who program them (as you note). So while they could add additional rules specifically to determine a draw in Penrose’s chess problem, without actually running through all the permutations, I think his point is that we can only impart the mechanics of our intuition, not the intuition or human insight itself. ---
**Author:** ![Stanislaus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/stanislaus/32/3391_2.png) [@Stanislaus](https://boards.straightdope.com/u/Stanislaus)\ **Post date:** [March 15, 2017, 2:02pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/22 "2017-03-15T14:02:53Z")
How does this view of AI line up against the recent triumph of AlphaGo? As I understood it, AlphaGo learned to play Go in a manner more analogous to how a human would: playing lots and lots (and lots and lots and lots) of games and gradually discovering rules about what worked and what didn’t. If there is an AlphaChess, would it - at least in theory - be capable of learning for itself that bishops on the black squares can’t touch pawns on the white squares? ---
**Author:** ![blindboyard](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/blindboyard/32/2833_2.png) [@blindboyard](https://boards.straightdope.com/u/blindboyard)\ **Post date:** [March 15, 2017, 7:50pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/23 "2017-03-15T19:50:42Z")
Why has one of the squares got an “x” on it? ---
**Author:** ![glee](https://avatars.discourse-cdn.com/v4/letter/g/b5a626/32.png) [@glee](https://boards.straightdope.com/u/glee)\ **Post date:** [March 15, 2017, 7:58pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/24 "2017-03-15T19:58:41Z")
> [@Stanislaus](#): > > How does this view of AI line up against the recent triumph of AlphaGo? > > As I understood it, AlphaGo learned to play Go in a manner more analogous to how a human would: playing lots and lots (and lots and lots and lots) of games and gradually discovering rules about what worked and what didn’t. If there is an AlphaChess, would it - at least in theory - be capable of learning for itself that bishops on the black squares can’t touch pawns on the white squares? I’m not a Go expert, but I expect that it’s difficult to set short-term goals on Go (since there is a large board with new pieces constantly being added.) So you can’t use the computer chess method of brute force analysis. However in chess a computer can reasonably analyse quite a few moves ahead and assess each of the many, many positions it reaches solely on the basis of who is ahead on material. Therefore brute force works well. Here’s a position I made up which I believe illustrates Penrose’s point in a simpler and more game-like way. **White: King h1 Queen d3 pawn g2 Black: King f8 pawns g3, f2** White to play is effectively +8 pawns ahead and Black has no threats (nor any way to improve his position.) I put this position into a reasonable computer (well it was a free download!) Rybka 2.2.3a. After 6 hours of analysis it had analysed 36 moves ahead (for each side) and was giving White the advantage of +0.53 pawns. The position is drawn, which an experienced player would recognise in less than a minute. Here’s why it’s drawn: The White king and pawn have no moves. The White Queen can capture on g3, but this allows Black to promote his pawn on f1. The resulting Queen and pawn ending is drawn as long as Black can get his king in front of the White pawn. Here’s the two ways that Black could blunder: 1. If Black allows the g3 pawn to be captured with check (as the f pawn will go next) 2. If Black King gets stalemated on h8 (with White Queen on f7), then Black has to promote and immediately lose the f pawn. ---
**Author:** ![glee](https://avatars.discourse-cdn.com/v4/letter/g/b5a626/32.png) [@glee](https://boards.straightdope.com/u/glee)\ **Post date:** [March 15, 2017, 8:00pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/25 "2017-03-15T20:00:04Z")
> [@blindboyard](#): > > Why has one of the squares got an “x” on it? I assume it’s because White should try to get his King there (see my post 3 in this thread.) ---
**Author:** ![Dead\_Cat](https://avatars.discourse-cdn.com/v4/letter/d/9fc29f/32.png) [@Dead\_Cat](https://boards.straightdope.com/u/Dead_Cat)\ **Post date:** [March 16, 2017, 5:59pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/26 "2017-03-16T17:59:59Z")
That’s a much more realistic position, **glee**. Resolved: **glee** is better at chess than Roger Penrose :). ---
**Author:** ![MJHsquaaa](https://avatars.discourse-cdn.com/v4/letter/m/3be4f8/32.png) [@MJHsquaaa](https://boards.straightdope.com/u/MJHsquaaa)\ **Post date:** [March 16, 2017, 6:29pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/27 "2017-03-16T18:29:24Z")
\Check mate in 4 moves I think.\
Initial positions indexed as F8 for black king, E8 for black queen.\
\
\
\
\SPOILER\: \ \ \
\
B8 -\> B6 (Promoted to queen) Next black move irrelevant. (Say, G8-G7) D6 -\> E7 (check) E8 -\> E7 C7 -\> D8 (Promote to queen - check) E7 -\> D8 B6 -\> D8 (checkm8) \ \ \\
\
---
**Author:** ![MJHsquaaa](https://avatars.discourse-cdn.com/v4/letter/m/3be4f8/32.png) [@MJHsquaaa](https://boards.straightdope.com/u/MJHsquaaa)\ **Post date:** [March 16, 2017, 6:32pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/28 "2017-03-16T18:32:29Z")
Sorry i don’t know how to work the code ---
**Author:** ![davidm](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/davidm/32/225_2.png) [@davidm](https://boards.straightdope.com/u/davidm)\ **Post date:** [March 16, 2017, 9:12pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/29 "2017-03-16T21:12:25Z")
I came here to either post a thread about this or see if one has already been posted. I think Penrose’s point is as others here have said; that what a human can see intuitively would require and impossibly large search tree for a computer to discover. Penrose seems to be assuming that contemporary chess programs work by simply doing an exhaustive search of the move tree. This of course is ridiculous. Even when I was in college in the 80s and took a course in what would now be rudimentary AI, the professor explained that a good chess program had to use some heuristics to trim the search tree at each level. Surely the concept of avoiding bishops by staying on a different color is among those heuristics. Also keep in mind that many many of those tree branches would end in an early draw because of a position being repeated 3 times. ---
**Author:** ![Ximenean](https://avatars.discourse-cdn.com/v4/letter/x/aca169/32.png) [@Ximenean](https://boards.straightdope.com/u/Ximenean)\ **Post date:** [March 16, 2017, 11:39pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/30 "2017-03-16T23:39:43Z")
> [@MJHsquaaa](#): > > Check mate in 4 moves I think. > Initial positions indexed as F8 for black king, E8 for black queen. I think you’re saying that the board is displayed rotated by 90 degrees, with white moving right to left? A couple of problems with that: - the position is impossible - the colours of the squares are the wrong way round for that to be the case (“white on the right”, remember) - it would be rather unconventional to depict the promoted white pawn as still being a pawn ---
**Author:** ![MJHsquaaa](https://avatars.discourse-cdn.com/v4/letter/m/3be4f8/32.png) [@MJHsquaaa](https://boards.straightdope.com/u/MJHsquaaa)\ **Post date:** [March 17, 2017, 12:12am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/31 "2017-03-17T00:12:39Z")
> [@davidm](#): > > I came here to either post a thread about this or see if one has already been posted. I think Penrose’s point is as others here have said; that what a human can see intuitively would require and impossibly large search tree for a computer to discover. > > Penrose seems to be assuming that contemporary chess programs work by simply doing an exhaustive search of the move tree. This of course is ridiculous. Even when I was in college in the 80s and took a course in what would now be rudimentary AI, the professor explained that a good chess program had to use some heuristics to trim the search tree at each level. > > Surely the concept of avoiding bishops by staying on a different color is among those heuristics. > > Also keep in mind that many many of those tree branches would end in an early draw because of a position being repeated 3 times. I agree completely. It would be madness to brute force search through every tree branch with this type of problem. Brute force is great, but do it in the smallest dimensional subspace possible, and branch out only when necessary. The heuristic you mention is for sure one of the first that should be considered in reducing the parameter space before a solution is sought. ---
**Author:** ![MJHsquaaa](https://avatars.discourse-cdn.com/v4/letter/m/3be4f8/32.png) [@MJHsquaaa](https://boards.straightdope.com/u/MJHsquaaa)\ **Post date:** [March 17, 2017, 12:26am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/32 "2017-03-17T00:26:51Z")
> [@Ximenean](#): > > I think you’re saying that the board is displayed rotated by 90 degrees, with white moving right to left? A couple of problems with that: > > - the position is impossible > - the colours of the squares are the wrong way round for that to be the case (“white on the right”, remember) > - it would be rather unconventional to depict the promoted white pawn as still being a pawn The layout is not as you think. Check the image: [https://goo.gl/photos/cGvDP1hESHA5ZXSU8](https://goo.gl/photos/cGvDP1hESHA5ZXSU8) I think it’s correct. They likely left it as a pawn as it could be promoted to either a queen, rook, bishop or knight. I think it’s a legal move unless I missed something. I haven’t played chess in over a decade though… ---
**Author:** ![Ximenean](https://avatars.discourse-cdn.com/v4/letter/x/aca169/32.png) [@Ximenean](https://boards.straightdope.com/u/Ximenean)\ **Post date:** [March 17, 2017, 12:50am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/33 "2017-03-17T00:50:12Z")
> [@MJHsquaaa](#): > > The layout is not as you think. Check the image: > > [https://goo.gl/photos/cGvDP1hESHA5ZXSU8](https://goo.gl/photos/cGvDP1hESHA5ZXSU8) > > I think it’s correct. > > They likely left it as a pawn as it could be promoted to either a queen, rook, bishop or knight. I think it’s a legal move unless I missed something. I haven’t played chess in over a decade though… That position has black pawns on c8 and g8, which is impossible, never mind the white pawn on b8. That image does not match the square colouring of those in the OP’s article, either. ---
**Author:** ![Sage\_Rat](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/sage_rat/32/399_2.png) [@Sage\_Rat](https://boards.straightdope.com/u/Sage_Rat)\ **Post date:** [March 17, 2017, 1:11am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/34 "2017-03-17T01:11:41Z")
I think that a computer would first ask, “Who’s turn is it?” I find it strange that the article chooses not to reveal this tidbit. ---
**Author:** ![MJHsquaaa](https://avatars.discourse-cdn.com/v4/letter/m/3be4f8/32.png) [@MJHsquaaa](https://boards.straightdope.com/u/MJHsquaaa)\ **Post date:** [March 17, 2017, 1:16am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/35 "2017-03-17T01:16:37Z")
> [@Ximenean](#): > > That position has black pawns on c8 and g8, which is impossible, never mind the white pawn on b8. > That image does not match the square colouring of those in the OP’s article, either. Ok. so I was wrong 😃 I assumed the black were playing left to right. haha. A good reminder for myself to check the initial conditions. Too late to pretend I’m a computer :smack: ---
**Author:** ![Junior\_Spaceman](https://avatars.discourse-cdn.com/v4/letter/j/eb8c5e/32.png) [@Junior\_Spaceman](https://boards.straightdope.com/u/Junior_Spaceman)\ **Post date:** [March 17, 2017, 2:22am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/36 "2017-03-17T02:22:54Z")
This ‘problem’ doesn’t make any sense to me at all. Black might have a lot of pieces on the board, but they are all gridlocked except for the three bishops, but most importantly, there is nowhere any of the bishops can move which will strengthen black’s position. Other than the three instantly losing pawn moves (either c7 or taking one of the rooks), White can only move his King, but again, none of his moves - however many deep - strengthen _his_ position. Does Penrose only have access to really bad chess computers, that counts pieces but ignores potential moves? More troubling is the following quote. > [@](#): > > If successful, it could prove for the first time that the human brain is not simply a gargantuan supercomputer, but may exhibit quantum effects far beyond the realms of current imagining - a controversial theory that many scientists believe to be impossible. That just sounds like pure Chopra-esque technobabble. ---
**Author:** ![Peter\_Morris](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/peter_morris/32/359_2.png) [@Peter\_Morris](https://boards.straightdope.com/u/Peter_Morris)\ **Post date:** [March 17, 2017, 2:27am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/37 "2017-03-17T02:27:16Z")
I’ve actually studied how a chess computer works, and even programmed my own version. I see what the guy is driving at. The way a chess computer works is to list every possi8ble move from the current position, then consider every possible response to that, and every possible response to that, and so on. Even a few moves ahead the decision tree becomes enormous. No computer is capable of looking 50 moves ahead. The computation would take longer than the expected life of the universe. A human with a rudimentary knowledge of chess can see the solution in a few seconds. Just keep moving your King on white, and you’ll get a draw in 50 moves. A computer cannot see that. It can’t declare that it can force a draw. What a computer \*can \*do is look, say, 10 moves ahead and choose a move that won’t lead to a loss within 10 moves. Choosing the move will take many millions of calculations. The basic point is that computers have no intuition. Many things that are obvious to a human are simply beyond the ability of machines to calculate. This is one example of such, and not a very good one. ---
**Author:** ![MJHsquaaa](https://avatars.discourse-cdn.com/v4/letter/m/3be4f8/32.png) [@MJHsquaaa](https://boards.straightdope.com/u/MJHsquaaa)\ **Post date:** [March 17, 2017, 3:36am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/38 "2017-03-17T03:36:39Z")
> [@Peter\_Morris](#): > > I’ve actually studied how a chess computer works, and even programmed my own version. > > I see what the guy is driving at. > > The way a chess computer works is to list every possi8ble move from the current position, then consider every possible response to that, and every possible response to that, and so on. Even a few moves ahead the decision tree becomes enormous. > > No computer is capable of looking 50 moves ahead. The computation would take longer than the expected life of the universe. > > A human with a rudimentary knowledge of chess can see the solution in a few seconds. Just keep moving your King on white, and you’ll get a draw in 50 moves. > > A computer cannot see that. It can’t declare that it can force a draw. > > What a computer \*can \*do is look, say, 10 moves ahead and choose a move that won’t lead to a loss within 10 moves. Choosing the move will take many millions of calculations. > The basic point is that computers have no intuition. Many things that are obvious to a human are simply beyond the ability of machines to calculate. This is one example of such, and not a very good one. So is the problem with chess computers that they only calculate to win? What if before the chess computer attempts to calculate all possible moves, it first weighs the relative strength of the blacks and whites, scored on say the number of pieces and their maximum degrees of freedom, then when finding an imbalance such as in this game it switches to a survival strategy. Employing this by looking, say, 5 moves ahead and choosing the move that minimises the oppositions degrees of freedom whilst maximising its own. Then finding itself in the current situation with no interacting degrees of freedom available, declaring that it can force a draw? ---
**Author:** ![Peter\_Morris](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/peter_morris/32/359_2.png) [@Peter\_Morris](https://boards.straightdope.com/u/Peter_Morris)\ **Post date:** [March 17, 2017, 3:52am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/39 "2017-03-17T03:52:44Z")
> [@MJHsquaaa](#): > > So is the problem with chess computers that they only calculate to win? Uh, no. They might look 10 moves ahead, and select the best terminal position from that. Often it it a matter of selecting the least worse option. ---
**Author:** ![coremelt](https://avatars.discourse-cdn.com/v4/letter/c/4491bb/32.png) [@coremelt](https://boards.straightdope.com/u/coremelt)\ **Post date:** [March 17, 2017, 5:14am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/40 "2017-03-17T05:14:25Z")
I did some cognitive science course at university and yes Penrose may well be an amazing physicist / astrophysicist but his opinions on AI are worthless. At best his argument comes to something like normal procedural computer languages can never create real AI. That might be true, but all the big advances in AI are coming in neural networks and other biologically based models. A computer chess program that was trained using neural nets would “intuit” the draw in a way remarkably similar to the way a human does, eg it would not need to calculate 50 moves ahead. Eg see here: > **[Deep Learning Machine Teaches Itself Chess in 72 Hours, Plays at...](https://www.technologyreview.com/2015/09/14/247956/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/)** > > In a world first, a machine plays chess by evaluating the board rather than using brute force to work out every possible move. [Previous page](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154.md?page=1) [Next page](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154.md?page=3)