# 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:** 16\ **Page:** 3
**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 17, 2017, 9:32am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/41 "2017-03-17T09:32:05Z")
> [@coremelt](#): > > … > 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. > … He’s not even really correct about that. Neural nets can be emulated in procedural languages. Even a non-proceedural language, if it’s executed on a standard digital Von Neumann (or Harvard) architecture, is, at its lowest level , executed as, or by, procedural binary code. Of course, there are novel hardware AI architectures that are not procedural. These are more efficient, but can still be emulated, however inefficiently, on a standard computer. And i don’t think Penrose’s argument is about efficiency. Quantum computers deserve mention, and those can’t be emulated, at least not in any practical sense. I think Penrose is arguing that true intelligence requires quantum effects. I don’t think that this chess problem is proof of that. ---
**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 17, 2017, 10:00am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/42 "2017-03-17T10:00:12Z")
> [@coremelt](#): > > 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 International Master Level | MIT Technology Review](https://www.technologyreview.com/s/541276/deep-learning-machine-teaches-itself-chess-in-72-hours-plays-at-international-master/) From the article: > [@](#): > > So it’s no surprise that deep neural networks ought to be able to spot patterns in chess and that’s exactly the approach Lai has taken. His network consists of four layers that together examine each position on the board in three different ways. > > The first looks at the global state of the game, such as the number and type of pieces on each side, which side is to move, castling rights and so on. The second looks at piece-centric features such as the location of each piece on each side, **while the final aspect is to map the squares that each piece attacks and defends**. Based on that, it seems pretty likely that we could (maybe have?) developed an AI that can solve Penrose’s puzzle. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [March 17, 2017, 10:25am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/43 "2017-03-17T10:25:23Z")
And it’s not even true to say that a computer can’t look 50 moves in advance. It can’t _exhaustively_ look that far in advance, but then, why would it? No chess computer any more tries to do that. But trim the tree enough, and it can look as far in advance as you’d like. Like **Stanislaus** ’ cell phone did. Put another way, his phone thought at first glance that the position favored black, but then thought about it a little more and realized it was a draw. Just like a human would have. The mechanics of the “thought a little more” might be different, but the result is the same. ---
**Author:** ![Eguy71](https://avatars.discourse-cdn.com/v4/letter/e/ecae2f/32.png) [@Eguy71](https://boards.straightdope.com/u/Eguy71)\ **Post date:** [March 17, 2017, 11:21am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/44 "2017-03-17T11:21:58Z")
White moves and draws in 3 via threefold repetition rule. ---
**Author:** ![Asympotically\_fat](https://avatars.discourse-cdn.com/v4/letter/a/e47c2d/32.png) [@Asympotically\_fat](https://boards.straightdope.com/u/Asympotically_fat)\ **Post date:** [March 17, 2017, 11:32am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/45 "2017-03-17T11:32:17Z")
It is possible to anticipate play 50+ moves, though for chess puzzles with mate in 50+ the move order will be very forced and the position often will be artificial. Also due to endgame tables arrived at from retrograde analysis computers can and do play many endgames arising from normal play perfectly where the forced mate is more than 50 moves off. These days even a chess engine running on a bog standard computer can look 20 moves ahead in a matter of seconds for any position. For example a web-based version of Stockfish running on my laptop takes about a minute to analyse the starting position exhaustively to a depth of 20 without effecting the performance of any of the other programs I am running. Obviously for each successive depth though the time taken increases rapidly. ---
**Author:** ![Asympotically\_fat](https://avatars.discourse-cdn.com/v4/letter/a/e47c2d/32.png) [@Asympotically\_fat](https://boards.straightdope.com/u/Asympotically_fat)\ **Post date:** [March 17, 2017, 11:34am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/46 "2017-03-17T11:34:58Z")
> [@Eguy71](#): > > White moves and draws in 3 via threefold repetition rule. That’s certainly not the case, black can avoid the position being repeated for many moves. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [March 17, 2017, 2:48pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/47 "2017-03-17T14:48:42Z")
Penrose is a stubborn ass. Was a great scientist, no argument there. But he claimed in a book published around 1990 that there were machines whose stopping problem was recursively undecidable but that we humans could decide. I am others pointed out that this was absurd, but he doubled down and kept insisting on it. Of course, he gave no example and his argument had a deep flaw. In fact, it was old enough to have a name attached (Lucasz, IIRC) and had been refuted many times. This is clearly supposed to be an example. Probably it will turn out that a human chess master will eventually realize that the board is turned sideways, or something stupid like that. Don’t take it seriously. ---
**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:44pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/48 "2017-03-17T15:44:21Z")
> [@Hari\_Seldon](#): > > Probably it will turn out that a human chess master will eventually realize that the board is turned sideways, or something stupid like that. No, it’s not that kind of puzzle. There’s no trick to it. It’s simply a very very easy chess problem. White’s next move is obvious. Humans will solve it immediately and instinctively, but machines can only detect after a long search. ---
**Author:** ![TimeWinder](https://avatars.discourse-cdn.com/v4/letter/t/bcef8e/32.png) [@TimeWinder](https://boards.straightdope.com/u/TimeWinder)\ **Post date:** [March 17, 2017, 3:55pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/49 "2017-03-17T15:55:23Z")
> [@Peter\_Morris](#): > > 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… That’s one way that a computer can work, but the assertion here is that it’s the only way. “No program has been written that solves this” is a long way from “No program _can_ be written that solves this.” Even the P =/!= NP problem hasn’t been rigorously proven yet, and that’s a much simpler case. This is directly analogous to Searle’s Chinese Room argument, which, simply stated is also: “because I can’t think of a way to do this, no such way exists.” That’s fine for armchair philosophy, but it doesn’t stand up to any actual rigor. [QUOTE=Peter Morris] 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. [/QUOTE] And as always, the fundamental problem with statements like that is that there’s no evidence that the human brain is anything other than a computer. We don’t understand how the _mind_ (the program) works, but we’ve got a pretty good handle on at least the basics of the mechanism on which it runs, and there’s no magic parts there. Penrose’s argument is essentially the old religious argument for God again: things are happening we can’t explain, therefore no explanations can possibly exist and it must be “supernatural.” In his case you can substitute “mind” for God and “vaguely quantummy thing” for “supernatural,” but it’s still the argument from ignorance, and has basically zero predictive or explanatary value. ---
**Author:** ![Steve\_MB](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/steve_mb/32/5339_2.png) [@Steve\_MB](https://boards.straightdope.com/u/Steve_MB)\ **Post date:** [March 17, 2017, 4:58pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/50 "2017-03-17T16:58:50Z")
> [@RitterSport](#): > > Well, he’s good at physics, but he thinks that makes him an expert at neurology, artificial intelligence, computer science, etc. His book “The Emperor’s New Mind” was one of the dumbest difficult books I’ve ever read. He goes through all this quantum physics and ends up with, neurons are different than silicon chips, so AI isn’t possible. This. His “argument” (assuming that anything that does X must necessarily employ the same physical mechanisms as known things that do X), is _precisely_ equivalent to [this notorious howler](https://en.wikipedia.org/wiki/William_D._Leahy#Atomic_bomb): [QUOTE=Admiral William D. Leahy] That is the biggest fool thing we have ever done. The atomic bomb will never go off, and I speak as an expert in explosives. [/QUOTE] ---
**Author:** ![BeepKillBeep](https://avatars.discourse-cdn.com/v4/letter/b/9e8a1a/32.png) [@BeepKillBeep](https://boards.straightdope.com/u/BeepKillBeep)\ **Post date:** [March 17, 2017, 5:16pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/51 "2017-03-17T17:16:39Z")
Not only is this problem not impossible, it isn’t even that hard of a problem for a chess AI to solve. I have a toy chess AI I wrote several years ago just to play around with searching algorithms. I.e. it isn’t very good. My algorithm uses a Monte Carlo approach with exploration/exploitation factors as modifiers (again to be clear this is not a good approach, it is just a toy). I programmed in this position and what happens is very quickly the exploitation factors for moving anything except the king become very low. So even though my program doesn’t have a very deep look ahead, isn’t very sophisticated and _definitely_ isn’t state of the art, it realizes that moving anything except the king is disaster. ---
**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, 6:49pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/52 "2017-03-17T18:49:28Z")
I think you’ve missed the point. Your toy chess program might select the correct move, but does it \*know \*that a draw lies 50 moves ahead? ---
**Author:** ![RitterSport](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rittersport/32/6326_2.png) [@RitterSport](https://boards.straightdope.com/u/RitterSport)\ **Post date:** [March 17, 2017, 7:54pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/53 "2017-03-17T19:54:12Z")
Is it possible for white to win without black screwing up? That seems to be implied in the original article. If it is, could someone post how without using chess notation? Maybe something like “move the pawn from C6 to C7”, etc.? I don’t need every move, just the end game – so, moving the king to D8 might take a lot of moves, but I’m happy to take that as given. If white can win with black screwing up, I assume black can too, right? ---
**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, 8:11pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/54 "2017-03-17T20:11:39Z")
> [@RitterSport](#): > > Is it possible for white to win without black screwing up? That seems to be implied in the original article. If it is, could someone post how without using chess notation? No. If White moves a pawn, he loses. If he advances the c6 pawn to c7 it gets taken by a bishop, and then Black’s king can’t be prevented from escaping via b7, as **glee** explained earlier. If White captures with the pawns on b3 or c4, that pawn gets taken and Black’s queen can escape. Once Black’s pieces are out of that cage, it’s game over for White. ---
**Author:** ![BeepKillBeep](https://avatars.discourse-cdn.com/v4/letter/b/9e8a1a/32.png) [@BeepKillBeep](https://boards.straightdope.com/u/BeepKillBeep)\ **Post date:** [March 17, 2017, 11:53pm UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/55 "2017-03-17T23:53:56Z")
> [@Peter\_Morris](#): > > I think you’ve missed the point. > > Your toy chess program might select the correct move, but does it \*know \*that a draw lies 50 moves ahead? The current version doesn’t but it would be trivial to change it so that it would find it. All I would need to do is turn it into an adaptive search that searches deeper on the nodes that are highly exploitative. I would then remove the depth limit and replace it with a total nodes opened. Since pawn moves are not exploitative, it would look deeper into king moves. Non-diagonal king moves would then get pruned out quickly as well, thus causing it to search deeper. I really don’t think it would be take that long to get to 50 move look ahead for this problem. And that’s using a terrible algorithm. A good chess AI that certainly has optimizations for looking at the search space is going to have no trouble with this. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [March 18, 2017, 1:35am UTC](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154/56 "2017-03-18T01:35:08Z")
I really do have to wonder if Penrose ever even thought to try the simple expedient of plugging this into a chess computer. Yeah, yeah, I know, he’s a theorist, not an experimentalist, but that’s a really easy experiment. [Previous page](https://boards.straightdope.com/t/solve-penroses-chess-puzzle-thats-impossible-for-a-computer/782154.md?page=2)