A chess problem solvable by intuition but not by computers

[Mathieu Cloutier]

Re: A chess problem solvable by intuition but not by computers

Paul,

You give way too much credit to Penrose. What he's been trying to prove for decades (with zero success) is that quantum mechanics happens at the scale of the human brain. And specifically with that chess position, he's trying to prove that our (supposedly) quantum brain is the reason why we see the solution, while a standard computer can't. It's incredibly stupid for a researcher of his stature to waste so much time without any reasonable premises for his hypothesis.

The reality is, as you've said, that we use a much more flexible 'computer' in the form of a neural network (our brain).

[Paul Bonham]

Re: A chess problem solvable by intuition but not by computers

....Penrose is contributing nothing new to either chess, computer science or mathematics here. Nothing new here. I read his book, "The Emperor's New Mind" years ago and was completely unimpressed. The guy is overrated.

Well, hold on a sec. Nowhere did I see it mentioned by Penrose or his Institute that this chess problem, in and of itself, introduces something new. He's aware that it has been known from the beginning of computers that humans and computers think differently. What Penrose seems to be doing is trying to start a process of discovering something new, and this problem is step 1 in the process.

Somewhere in the Telegraph article it mentions something about the Institute wants to "scan" the brains of the most promising solvers of the problem (I think they must have severely underestimated how easily most humans would solve the problem). Is it further mentioned anywhere what this "brain scanning" is all about? Is it MRI scanning?

At any rate, Penrose is trying to make some discoveries in an area where discoveries are extremely hard to come by. No one really knows how the human brain works. He has a theory that quantum effects in the brain are happening, we cannot either prove or disprove this. Let the research go on, albeit perhaps not funded by the public.

[Steve Douglas]

Re: A chess problem solvable by intuition but not by computers

Thanks, Kerry. The more I read Mathieu's following post the more uncertain I am of what he's trying to say.

Hi Peter:

There's a lot of chatter in this thread which seems to be somewhat beside the point. I mostly agree with Mathieu. The notion that this position is beyond the ability of chess engines to "understand" is deeply flawed. Is it easy for a human to figure out that the position is dead drawn unless white chooses to commit suicide? Yes. Does a human chess player "understand" the position better than a chess engine? Almost certainly. But when people talk about a computer "understanding" a position it is very different than an engine assessing a position. With "understanding" you're wandering into the world of AI and chess engines are a long way from artificial intelligence as most people would conceive of it.

A chess engine does basically two things: from a given input position it will provide a numerical evaluation as to which side is winning and by how much, and a recommended next move. For openings and endgames, it will "cheat" and look the position up in a database. Middlegame play is where the essence of the engine is.

The way an engine determines its evaluation varies from engine to engine but they all basically do the same thing: for a given board position they calculate a raw winning/losing evaluation based on however they were programmed. (Mostly materialistic.) Then they start evaluation of "all" the possible future moves in the game. It's not possible to calculate all of the possible future positions and evaluate them since computers do not have infinite processing speed or infinite memory in which to store all of the moves. So short-cuts are implemented to discard moves (and threads/chains/lines of moves) which seem to catastrophically worsen the position.

This leads to the so-called horizon effect where the chess engine has exhausted the computer resources to calculate and store new positions, or it has to start removing positions from its evaluation (and calculate no deeper upon them at all) in order to free up resources to calculate deeper in the most promising lines. Even then eventually a limit is reached.

Thus we get to the seemingly profound aspect of the position above. A human will evaluate it as a draw if white doesn't blunder. And a human will always be able to come up with the next move for white. Even without a 50-move-rule, the human player will play on forever and never lose.

A computer engine, unless it has enough resources, will evaluate the position as overwhelmingly winning for black, but if playing the white side of the game against either human or computer, it will always choose the proper move for white*.

If the engine has enough resources, it will correctly evaluate the position as drawn. Note that "enough" resources may not be possible for even high-end hardware today, but Moore's law says that "enough" resources will exist someday. In other words if the fastest and bestest computer today running the fastest and bestest chess engine can't evaluate this position properly, then just wait a few years.

Do human beings think differently than current chess engines? Of course they do. Does that mean that there's something going on at the "quantum level" in people's brains as Penrose has been ruminating about for years? Ummm, probably not. At least this example isn't going to show it.

Steve

* depending upon how its programmed, the engine may not play the best moves for black; the Nakamura - Rybka game mentioned above shows that.

P.S. If I take my preferred engine from many years ago, Hiarcs 8, and run it on my super-duper fast computer of the day, a Pentium II/350 with a whopping 128MB of ram, I doubt very much it will evaluate the position as a draw with even 1 black bishop. If I move to a single-core Pentium laptop from the mid-2000's with much more ram it figures it out as drawn fairly quickly with one bishop, but not with 2. When I feel like it I'll run it on something faster and see.

[Garland Best]

Re: A chess problem solvable by intuition but not by computers

You, know actually from a computing/endgame tablebase programming problem standpoint, it isn't THAT much to evaluate.

1) Start with the assumption that white never moves a pawn. There are 27 x 26 x 25 places available on the board for the bishops, including the possibilities that one or more bishops are captured. There are roughly 28 legal spaces remaining for the White king (Actual numbers depend on the positions of the bishops). That's approximately 491,400 possible positions on the board, assuming that the white pawns do not move. Let's call it 500,000 positions for good measure.

2) Any capture of a rook by a white pawn in the positions listed above leads to mate of the white king in only a few moves, with the exception of a few stalemate scenarios.

3) Advancing the c6 pawn loses except for scenarios where the pawn cannot be captured by a bishop on C7, and the white king is located on either d7, or a8 to d8. In those cases White mates the black king

So the total number of unique scenarios can be definitely be captured in a tablebase style setup, that someone could write a program for. It is definitely doable in this scenario.

This is a classic Godel situation (Read "Godel, Escher, Bach" by Douglas Hofstadter to know what I'm talking about). You have a formal mathematical system (here, the chess program). If the system is complex enough, you can create problems that have to be true or false, but cannot be proved within the rules written to solve the problem. So you can add rules (in the example above, a dedicated tablebase), only to have someone devices a new scenario to get around that rule. And on it goes, ad infinitium. Actually in a true mathematical sense, not ad infinitium, as there are only a finite number of possible legal positions on a chessboard. But you get my drift.

Penrose is contributing nothing new to either chess, computer science or mathematics here. Nothing new here. I read his book, "The Emperor's New Mind" years ago and was completely unimpressed. The guy is overrated.

[Peter McKillop]

Re: A chess problem solvable by intuition but not by computers

Thanks for adding that clarity, Paul. I appreciate it.

[Mathieu Cloutier]

Re: A chess problem solvable by intuition but not by computers

Well, Mathieu.... if you are so boned up on quantum physics that you can conclude, to the contradiction of Sir Roger Penrose, that there are DEFINITELY no quantum effects going on in the human brain....

then you must have read papers that are MUCH MUCH more lengthy than any of my posts, without complaining about their length!

In fact Paul, I agree with you that it would be much more interesting to use that kind of chess problems to develop better neural networks algorithms, something that Penrose isn't even contemplating.

[Paul Bonham]

Re: A chess problem solvable by intuition but not by computers

And as predictable as clockwork, Paul comes up with a lengthy post that only moves the discussion backwards....

Well, Mathieu.... if you are so boned up on quantum physics that you can conclude, to the contradiction of Sir Roger Penrose, that there are DEFINITELY no quantum effects going on in the human brain....

then you must have read papers that are MUCH MUCH more lengthy than any of my posts, without complaining about their length!

[Mathieu Cloutier]

Re: A chess problem solvable by intuition but not by computers

And as predictable as clockwork, Paul comes up with a lengthy post that only moves the discussion backwards....

[Paul Bonham]

Re: A chess problem solvable by intuition but not by computers

Thanks, Kerry. The more I read Mathieu's following post the more uncertain I am of what he's trying to say.

Originally Posted by Mathieu Cloutier
Paul,

First of all, the problem is titled 'A chess position to defeat computers'. Sorry, but I have to disagree. This position cannot be used to defeat modern engines even running on modest hardware. Penrose claims that even supercomputers don't understand the position. I say bollocks.

Try playing moves from the position with a modern engine running on infinite analysis. I did it with Komodo and Houdini and it's not long before the evaluation falls to 0.00. i.e. as soon as the 50 moves rules comes within the search horizon of the engine.

This whole thing boils down to a very simple fact: in chess, there is the 50 moves rule, which is in fact 100 plys for an engine and this is beyond their search depth. Change the 50 moves rule for a 15 or 20 moves rule and any engine will correctly assess the initial position. Nothing esoterical going on here, as Penrose claims.


Peter, it is clear that Mathieu is completely misunderstanding this problem. Mathieu thinks that this position is presented and both the humans and the engines get to actually play out moves from this position. He concludes that because both the humans and the engines would play correctly (not take a Rook, not advance the c6 Pawn) then the engines are NOT defeated as Penrose Institute indicates.

What Mathieu does not understand -- and perhaps he should be flown over to the Penrose Institute to have his brain scanned, as an example of what NOT to aspire to in computer engineering! -- is that no one gets to "play moves". There is no game that gets played, it is not a test of how an engine would PLAY from this position. It is an exam question where the humans and the engines must all ASSESS the position.

Note I put every emphasis on the words "play" and "assess" -- bolded them, underlined them, put them in all caps! I'm hoping this will wake Mathieu up to the simple error of his ways.

Mathieu even contradicts himself.... he says that if we change the 50 move rule to a 25 or 30 move rule, the engines will assess the position correctly. So suddenly he seems to realize that the engines are not assessing the position correctly with a 50 move rule! Which is the point of the problem!!!!

But alas, Mathieu then goes back to talking about "playing moves" (sigh). And he disses the Penrose Institute (well actually, Penrose himself) for stating that "he [Penrose] also stated that his problem was 'unsolvable' even for supercomputers and this is just false. Computers can PLAY that position and draw easily for either side."

Again, I had to add emphasis to show that Mathieu went back to talking about "playing" the position. Mathieu, get it straight: no one is "playing" the position. The problem is to correctly ASSESS the position.

Penrose is correct. No supercomputer on Earth will correctly assess this position, even if you give it maximum resources and let it run for centuries. It will never reach the 100 ply search depth needed.

I let Stockfish 8 run this problem for 31 minutes on one of my older computers, a quad core Intel i5 laptop with 6GB RAM. I even removed the Black dark square Bishop on g3, so Black only has 2 dark square Bishops. I thought that might reduce the possibilities such that Stockfish might actually reach the 100 ply search depth in some reasonable time, as Steve Douglas alluded to elsewhere in this thread.... Here is the top line it came up with:

56 -26.98
1.Kd3 Bh6 2.Ke4 Bc7 3.Kf3 Bc1 4.Ke2 B1f4 5.Ke1 Bfe5 6.Kf1 Bd4 7.Ke2 Bd6 8.Kd3 Bf4 9.Ke2 Bg3 10.Kd3 Bd6 11.Ke4 B6e5 12.Kd3 Bc3 13.Ke4 Bc7 14.Kd3 Bf4 15.Ke4 Bh2 16.Kd5 Bc7 17.Ke4 Bg3 18.Kf3 Bce5 19.Kg4 Bd6 20.Kf3 Bh4 21.Ke2 Bf6 22.Kf3 Bfe5 23.Kg4 Bd4 24.Kf5 Bg3 25.Ke4 Bdf2 26.Kd3 Bf4 27.Ke2 Bd4 28.Kd3 Bh6
1850.85 seconds
2.966 billion nodes

So it was on 56 ply search depth, gave a score of -27 (27 Pawns advantage to Black) and had searched almost 3 billion positions. Sounds not too bad? Well, in about the first 10 seconds it was at 50 ply search depth. It took about 15 minutes to go from 55 ply search depth to 56 ply search depth. It still has 44 more plies of depth to go, and if we assume each subsequent ply takes double the time of the previous ply (a very conservative estimate, since the search tree grows exponentially), that means take about 15 minutes and double that 44 times.... so that's 15 minutes times 17,592,186,044,416.... about 2,748,779,069,440 days.... 7,525,746,939 years..... a little over half the current estimated age of the universe.

And that's with only 2 Black dark square Bishops......

I've come down hard on Mathieu, but he deserves it. He came down hard on Penrose on the subject of this chess problem without even understanding the problem.

It's like Trump saying he understood how to defeat ISIS "better than the generals".... and then once elected, Trump asks the Generals to give him within 30 days a plan to defeat ISIS!!! Millions of Americans fell for this baloney.

But let's give Mathieu a break and put some blame on the wording of this problem. They should have made it absolutely clear that they meant to compare humans versus computer engines on assessing the position, not playing from the position. Some people are going to see the word "defeat" and think it means the computer or human might lose if playing from this position. I am 100% confident that is NOT what Penrose Institute meant... because no current engine in the top 100 would lose playing from this position as White.

And on the subject of Penrose investigating quantum effects in the brain, I don't know HOW such research can be conducted since quantum effects are (almost?) impossible to detect and measure especially in the context of an actual working human brain.... so maybe it is a valid point to say public funds should not be going towards such research. That is a question for voters of the U.K. to determine.

[Mathieu Cloutier]

Re: A chess problem solvable by intuition but not by computers

Thanks, Kerry. The more I read Mathieu's following post the more uncertain I am of what he's trying to say.

Well, you can't use the fact you don't understand engines (or the rules of chess) to prove anything...

[Peter McKillop]

Re: A chess problem solvable by intuition but not by computers

My understanding of 0.0 is that the engine does not see a significant edge for either side (one could interpret that as drawish or engine myopia or complete lack of understanding... :) )

Thanks, Kerry. The more I read Mathieu's following post the more uncertain I am of what he's trying to say.

Paul,

First of all, the problem is titled 'A chess position to defeat computers'. Sorry, but I have to disagree. This position cannot be used to defeat modern engines even running on modest hardware. Penrose claims that even supercomputers don't understand the position. I say bollocks.

Try playing moves from the position with a modern engine running on infinite analysis. I did it with Komodo and Houdini and it's not long before the evaluation falls to 0.00. i.e. as soon as the 50 moves rules comes within the search horizon of the engine.

This whole thing boils down to a very simple fact: in chess, there is the 50 moves rule, which is in fact 100 plys for an engine and this is beyond their search depth. Change the 50 moves rule for a 15 or 20 moves rule and any engine will correctly assess the initial position. Nothing esoterical going on here, as Penrose claims.

[Kerry Liles]

Re: A chess problem solvable by intuition but not by computers

Does a Komodo or Houdini evaluation of 0.00 always mean a draw or could it also mean, depending on the position, dynamic equilibrium?

My understanding of 0.0 is that the engine does not see a significant edge for either side (one could interpret that as drawish or engine myopia or complete lack of understanding... :) )

[Mathieu Cloutier]

Re: A chess problem solvable by intuition but not by computers

Does a Komodo or Houdini evaluation of 0.00 always mean a draw or could it also mean, depending on the position, dynamic equilibrium?

Define 'dynamic equilibrium'.

[Mathieu Cloutier]

Re: A chess problem solvable by intuition but not by computers

How much monies were invested (through grants etc) to get rid of "lunacy"? Some ideas are bad, some are good. Just no need to be stubborn and stuck to a single one.

Sometimes you know an idea is bad, you have experimental proof to back up the assessment and no further monies need to be spent on the subject.

But, strange enough, publicly funded scientific research doesn't always work that way.

[Peter McKillop]

Re: A chess problem solvable by intuition but not by computers

Does a Komodo or Houdini evaluation of 0.00 always mean a draw or could it also mean, depending on the position, dynamic equilibrium?