B Can you solve Penrose's chess problem and win a bonus prize?

[mfb]

In order to win, white can trap the king (mr obvious) by taking the rook closer to the king with the third row pawn, and then take the second rook with the fourth row pawn (the second row pawn will protect it).

The queen takes the first pawn - and the second if you move that in as well. Black can move the king and queen, and white loses.

 

[WWGD]

I'm joking. Penrose seemed to be using this problem as an example of something that could be solved by human insight, but not be a computer.

Yes, I think his main argument in the book is that human thought is not computable by which I think he meant not describable by a finite algorithm. EDIT I know and understand the main concepts but I keep mixing up computability and decidability.

 

[WWGD]

I came so far as to think this is an upside-down chessboard, since there are no coordinates on the board, and now White promotes to a Queen, but no, I don't think Sir Roger would play such a trick on us...

Aren't there, though, once you choose a side for either the Whites or Blacks, the rest is determined?

 

[Demystifier]

Yes, it would require promoting a black pawn to a bishop. I can't imagine any reason for doing that.

I can. Suppose that the bishop, queen, or whatever the black pawn will be promoted to, can be taken immediately by a white bishop, after which the white bishop can be taken immediately by a black knight. Then the black can think this way: "If I promote the pawn into a queen, then the white will certainly take it, and I will not have it anymore. If I promote it to a bishop, then the white might conclude that it is not worth taking it. So it can be better to promote it to a bishop."

 

[nuuskur]

Black is so far ahead in material, any engine would think black has a forced win. With white to play, there is no reason to move the pawn. Stay on light squares with the king. The game is endless or it will be a three fold repetition. If you start grabbing the rooks, you lose, because you let the queen out. Any two chess players would agree to a draw here since obviously nobody can make progress.

One may notice there is an opportunity with the c-pawn. The white king can guard d7, but black is then forced to relinquish one darksquared bishop (or he will lose, when c promotes to bishop). There is no further progress to be made.
White can never capture any of the bishops and black can always maintain two bishops on the b8-h2 diagonal.

When one speaks of winning in a chess puzzle, they mean a sequence of forcing moves. There are no forcing moves except for one and that is 1. c7, followed by bishop takes and nothing else of significance.
If you attack the bishops, I can simply block all your progress leaving your only legal move with the king.

 

[TeethWhitener]

Yes, it would require promoting a black pawn to a bishop. I can't imagine any reason for doing that.

There are sometimes decent reasons for underpromoting. In the case of underpromoting to a rook or a bishop, it's usually to avoid situations where promoting to a queen would result in a stalemate. Underpromotion trades material strength and a draw for less material and a possible checkmate.
https://en.wikipedia.org/wiki/Promotion_(chess)#Promotion_to_rook_or_bishop

Edit: Here's an example in a real game where white's promotion to a queen or rook would have pinned the black bishop and stalemated black, but promotion to a bishop secures the mate:
http://www.chessgames.com/perl/chessgame?gid=1287069
In fact, further on in that thread, they talk about Rybka (a very strong chess program) having trouble evaluating positions where underpromotion to a bishop or rook is required.

 

[mfb]

Black is so far ahead in material, any engine would think black has a forced win.

GNUChess thinks it is a draw, see post 6. This is the only tested engine so far (?), and it is a counterexample already.

 

[TeethWhitener]

GNUChess thinks it is a draw, see post 6. This is the only tested engine so far (?), and it is a counterexample already.

I should clarify: this was an online applet powered by GNUChess. I don't have access to all the internals, so I don't know if GNUChess evaluated the position as a black win, but it certainly plays to the draw easily.

 

[sysprog]

White must maintain the blockade that contains all black's men other than the 3 bishops, and can afford to release it only if his king is on d7 (or d8, which allows Black a 1-move delay) and none of Black's bishops is attacking or occupying c7, in which case c7 ... , followed by c8=B or (if ... K-b7) c8=Q, wins.

White can get to d7 in 5 moves. From there he should alternate for the next 44 moves between e6 or e8 (switching which to avoid threefold repetition) and d7 or d8. White could alternate between d7 and d8, and await Black vacating the h2-b8 diagonal, resorting to e6 or e8 only to avoid threefold repetition. If e.g. on move 49 he finds none of the bishops attacking or occupying c7, i.e. none anywhere along the h2-b8 diagonal, and White's king is on d7, he can play c7 on move 50, and then c8=B or c8=Q, having reset the 50 count by advancing a pawn on the previous move, and so win -- if White's king is on d8 Black can delay for a move with a check that let's the White king go to d7.

Whenever it is White to move with his king on d7 or d8, Black must concurrently have at least one of the bishops on the h2-b8 diagonal, or Black loses. Otherwise, as long as White does not release the blockade, it is a draw by 50 move rule or threefold repetition rule.

 

[Aufbauwerk 2045]

When I was studying basic AI I wrote a simple chess program, and I learned about the controversy in chess programming between the so-called "brute force school" and the "knowledge school." It's a classic example of how people underestimate what computers can do.

The brute force school pointed to graphs showing how the chess rating had been going up as computers became faster and had more memory. This made is seem inevitable that, in a few more years, chess programs would dominate all human players.

The knowledge school said that while brute force might work against masters, it would fail against grandmasters and definitely against the world champion. The knowledge school folks claimed that at the very highest levels, chess involved "creativity," "imagination," "insight," and other undefinable and perhaps mystical human qualities which could never be implemented in a computer algorithm.

Obviously the brute force school won that argument.

 

[mfb]

Obviously the brute force school won that argument.

Did it? The best computer programs don't just brute force. They use neural networks and various heuristics to determine what to do. You could argue that the programs got some of this "creativity", "imagination", "insight" or whatever.

 

[Aufbauwerk 2045]

Did it? The best computer programs don't just brute force. They use neural networks and various heuristics to determine what to do. You could argue that the programs got some of this "creativity", "imagination", "insight" or whatever.

Good point. Meanwhile a computer has beaten a world champion of Go, something the experts have been saying was years away because brute force search would never work. Maybe the Go program uses neural networks?

 

[sysprog]

Using a computer you can PROVE there's no forced stalemate. It's enough to prove that there's no forced stalemate even if black only plays only Bh2-g3 (until white moves a pawn. If black only plays this move, there are only about 80 positions to consider, and in all of these positions a pawn move by white leads to a forced mate by black.

Agree that there's no way to force a stalemate. That is provable as follows: For a stalemate to occur, even by co-operation, White's king would have to be on a8. Assuming b8 was attacked, the stalemate would depend on Black's king staying at a6 to prevent White's king from going to b7. At some point, White has to use up his c4xR+ move, whereupon Black could reply Kxp, which would allow White's king to escape to b7.

 

[mfb]

Maybe the Go program uses neural networks?

It does. Nearly every good computer program for games uses them in some way, unless the game is so small that a computer can consider every relevant position.

 

[Aufbauwerk 2045]

I want to clarify what I'm agreeing with.

It does. Nearly every good computer program for games uses them in some way, unless the game is so small that a computer can consider every relevant position.

I'm not so sure about that. Do video games in general use neural networks? I'm thinking about popular games such as League of Legends, Call of Duty, Grand Theft Auto, The Sims, etc. Or would you not consider these "good computer programs for games?"

In your earlier post you say "The best computer programs don't just brute force. They use neural networks and various heuristics to determine what to do. You could argue that the programs got some of this "creativity", "imagination", "insight" or whatever."

If we are talking about all types of programs, then in many cases the "best" program may have nothing to do with neural networks or heuristics. So I assume we are talking about AI programs such as chess programs. So I agree in some cases.

Just to clarify, the best chess programs of course don't just use brute force, meaning they don't simply use minimax or even minimax with alpha-beta pruning. They use book knowledge of openings, for example, and as you say various heuristics or "rules of thumb." So we can say they have some "knowledge" in that sense. This has been true of chess programs for decades.

But I think we need to be careful about saying they "got some of this "creativity", "imagination", "insight" or whatever" because at the end of day it's still just a machine which runs through its program step by step.

Strictly speaking the computer never has creativity, imagination, or insight. This is true whether it is running a simple program to perform some arithmetic, or a complex program that uses AI techniques such as recursive search with backtracking or pattern recognition.

Even a neural network program is just another program. I can implement a neural network in C. It can "learn" to recognize letters of the alphabet. Does that mean my little program is "intelligent?" Obviously not.

I have written programs to compose music. Are they creative? Not at all. It's just recursive search with backtracking, subject to various heuristics.

Of course some argue that, once we know enough, we will be able to create a machine with consciousness, creativity, and so on. Some say we are just a computer running a program. I am fascinated by this idea, and it may be proved correct sooner than many expect.

 

[PeroK]

Penrose diagram clearly shows "white to play and draw - easy for humans". The Telegraph science editor, however, doesn't know the difference between draw and stalemate.

 

[mfb]

It does. Nearly every good computer program for games uses them in some way, unless the game is so small that a computer can consider every relevant position.

I'm not so sure about that. Do video games in general use neural networks? I'm thinking about popular games such as League of Legends, Call of Duty, Grand Theft Auto, The Sims, etc. Or would you not consider these "good computer programs for games?"

Computer programs playing these games on an expert level.

But I think we need to be careful about saying they "got some of this "creativity", "imagination", "insight" or whatever" because at the end of day it's still just a machine which runs through its program step by step.

A human brain is just a bunch of cells firing once in a while. The basic steps alone don't tell you what the overall product is capable of.
In particular, a human is in in princple able to fully simulate a computer transistor by transistor with pen and paper, and a computer is in principle able to fully simulate a human brain neuron by neuron or even atom by atom, given enough memory and time. Unless you propose some magic outside the realms of physics, there is nothing a human can do that a computer could never achieve.

 

[PeroK]

Agree that there's no way to force a stalemate. That is provable as follows: For a stalemate to occur, even by co-operation, White's king would have to be on a8. Assuming b8 was attacked, the stalemate would depend on Black's king staying at a6 to prevent White's king from going to b7. At some point, White has to use up his c4xR+ move, whereupon Black could reply Kxp, which would allow White's king to escape to b7.

Bc7 puts a stop to the white King getting to a8.

White could also play for a stalemate on b1, but Bc7, leaving a1 free stops that as well.

 

[Auto-Didact]

A human brain is just a bunch of cells firing once in a while. The basic steps alone don't tell you what the overall product is capable of.
In particular, a human is in in princple able to fully simulate a computer transistor by transistor with pen and paper, and a computer is in principle able to fully simulate a human brain neuron by neuron or even atom by atom, given enough memory and time. Unless you propose some magic outside the realms of physics, there is nothing a human can do that a computer could never achieve.

I would like to qualify this 'in principle' argument: Even if a computer could simulate the human brain, we actually do not possesses the experimentally verified biophysical model of an entire neuron, let alone of an entire brain. Given that there are potentially relevant quantum effects at play (e.g. histonic proton tunneling) the computer would need to be capable of quantum processing as well; I think it is pretty obvious there is enough work there left to be done as well. Lastly, growing a functioning artificial brain can end up counting as 'making a computer', seeing the term has already been thrown around loosely at any and everything which even remotely resembles the core concept; this is a bait-and-switch argument, which obviously wouldn't prove that contemporary computers could simulate a human mind.

The argument of 'either magic or physics' is a strawman, seeing that the discovery of new physics outside of contemporary (bio)physics is sufficient to challenge any currently accepted physical theory or hypothesis, including the classical neuron doctrine. There are sufficient specialised research programmes which have been spawned by taking this route. There actually are multiple studies which demonstrate that not just the human brain, but biological phenomena in general, tend to be much more complicated than the classical models often naively assumed. From such a point of view, the classical neuron doctrine has already been falsified as a biophysical theory.

A somewhat well-known example is the recent quantum biology programme from biophysics, which has even led to popular books on the subject (McFadden & Al-Khalili, 2014). Another very high level different theoretical biology approach is the non-equilibrium thermodynamics approach of open systems, defining and characterizing necessary and sufficient conditions for life in the form of physical laws; this one is actually fully physics proper. What all of these have in common is that there is a multitude of both theoretical and experimental work left to do, but only always relatively few applicants.

Obviously, not many people from the physics/math work in or go into such fields, seeing the prerequisites often pretty much tend to be degrees in theoretical/mathematical physics or applied mathematics AND some serious interest in biology, AND no substantial worries of not having a clearly defined career path ahead; I don't know anyone from physics grad school who meets all three requirements simultaneously; those that have the required skills tend to simply not care about biology, like at all. On the biology side, there are enough but they usually never have the mathematical prerequisites. Seriously recognizing any or all of these issues, it becomes sufficiently clear we are decades if not centuries away from settling this discussion.

 

[mfb]

I would like to qualify this 'in principle' argument

We certainly cannot do it today. But that is not the point.
Turing didn't invent Turing machines to make better computers - a Turing machine is a horribly inefficient computer. He invented them to classify computer systems.

The argument of 'either magic or physics' is a strawman, seeing that the discovery of new physics outside of contemporary (bio)physics is sufficient to challenge any currently accepted physical theory or hypothesis, including the classical neuron doctrine.

Biology is irrelevant at this point. If all parts of the brain follow physical laws, and we can find the physical laws, then a computer can in principle simulate a brain.
The first condition is "no magic", the second condition is the basic assumption of science - and I'm highly confident we know all physical laws relevant for a brain already, there is nothing beyond the Standard Model necessary to understand human brains.

No chess AI will ever simulate a human brain atom by atom. That would be a horribly inefficient AI. But there is some way to do everything a human brain can do - and simulating a human brain is a very weak upper limit for the necessary computing power.

 

[SSequence]

I greatly admire Penrose as a brilliant thinker, but I actually don't think that his thoughts about consciousness, or human versus machine, are particularly novel or insightful. My feeling is that human thinking is actually not even Turing-complete. Because our memories are fuzzy and error-prone, I think that there are only finitely many different situations that we can hold in our heads. It's an enormous number, but I think it's still finite. Any kind of "insight" about finitely many situations is computable. Every function on a finite domain is computable; to go beyond what's computable, the domain must be infinite, and I just don't think that humans can really figure out problems with an arbitrarily large number of parameters.

Well, for it's worth, errors themselves can be handled with various schemes. Now before I describe those, first note that you could say that if you allow even just allow one error for each input value then you could solve the halt function. That's true, but I think you would run into problems very fast for harder problems.
Here are the schemes:
(1) Have an upper bound for number of errors (for any given input value) in terms of a recursive function.
(2) Ask the person who is supposedly calculating the function himself to write down the maximum number of errors (in unambiguous decimal form) in advance. However, that must be done before any output value (for the given input) has been written at all by that person.

Now in (1), if you were very skeptical, you could argue that one could make an "error" while calculating the "error function" :P.

=====

My feeling (having an intuitionistic mindset -- while making no claim to specific expertise) is that the issue is of "cognitive reliability" or "cognitive acceptability". Note that much of this is mathematical point of view (and perhaps somewhat philosophical). I don't make any comment on any other issues.

Here is a simple thought experiment (no limitations of limited lifetime, memory, workspace or time etc. assumed). You (person B) give someone (person A) a pen and paper (the paper being as big as they want it to be), and ask them to take as much time as they want to (with no restrictions whatsoever) and write down a number (in simple standard decimal form). That is ANY number, taking as much time/work-space as they wish. When that person is done writing it they hand it to you to read off the number. Let's write this value as A(0).
Similarly this process is repeated over and over and we keep getting values A(1), A(2), ... and so on etc.

Assuming standard currently held assumptions, person A can't give a guarantee that the values that will be written will dominate a certain function (called the "busy one"). And that's my point. The person A has no "real" or "acceptable" way to see when he has crossed a certain threshold***. The issue hardly is that he is pressed for time or work-space or any such things (in any way whatsoever). He just simply can't tell what exactly he has to do. Well he can tell what to do, but he just simply can't break it down further down to cognitively understandable/visualisable bits.

Currently, for example, mathematicians know the first 10 or so values of the "busy one" and if they were given infinite time, they could guarantee (mechanically) that they could probably calculate it for a dozen more values.
But what about 100 or 1000? What about 10000?
Basically we are asking for any mathematician(s) to stand ("on trial") in place of person A and beat the "busy one".

But well, someone could object and say that you should allow the person A to retract his answer (assume that the number of possible retractions is handled by scheme(2) mentioned above). But then once again in close proximity "another busy one" will be waiting.
I really doubt that this affects the real issue**** in the thought experiment any significant way (except just displace it a little further).

*** At least not in a mathematically meaningful way. Perhaps psychologically person A could claim that. But I don't think that's within the domain of maths anymore, so I will leave it here.

**** Certainly errors of judgement or mistakes are an issue. But also remember in the experiment you are also given unbounded time to clear them. Still probably "realistically" one would keep them. I am just saying that it wouldn't affect the underlying mathematical problem.

Edit: Removed a comment (possibly incorrect) that I put in haste :P.
Also I didn't describe my own views, as I thought it would get a bit off-topic.

 

[Auto-Didact]

We certainly cannot do it today. But that is not the point.
Turing didn't invent Turing machines to make better computers - a Turing machine is a horribly inefficient computer. He invented them to classify computer systems.

I fully agree. The hypothesis at hand is therefore whether or not the brain, or more specifically the neural mechanism of consciousness, is a Turing machine. Trivial heuristic presumptions aside, this has not been demonstrated either way.

Biology is irrelevant at this point. If all parts of the brain follow physical laws, and we can find the physical laws, then a computer can in principle simulate a brain.
The first condition is "no magic", the second condition is the basic assumption of science - and I'm highly confident we know all physical laws relevant for a brain already, there is nothing beyond the Standard Model necessary to understand human brains.

The argument that the Standard Model is fully sufficient in this case is of course the standard falsifiable hypothesis, and it goes without saying that 'no magic' is a basic tenet of physics, I'm certainly not questioning that; what I am questioning is the assumption that the possibility of relevant new physics seems to be precluded on the basis of taking a contemporary theory (SM) as essentially factual beyond its experimentally checked limits, especially when there are other competing rival theories which have not been experimentally ruled out yet in all relevant regimes.

Moreover, I also question the position that new physics must always necessarily meet the same mathematical criteria as known physics, since this was clearly not true in the past. Whether or not it turns out in the future that Nature utilises some mathematical criteria of non-computability, as Penrose argues, is not a matter to decide by argument, but something for experiment to decide.

No chess AI will ever simulate a human brain atom by atom. That would be a horribly inefficient AI. But there is some way to do everything a human brain can do - and simulating a human brain is a very weak upper limit for the necessary computing power.

I am thoroughly convinced AI can (if not already, eventually) convincingly imitate anything humans can do.

 

[PAllen]

Did it? The best computer programs don't just brute force. They use neural networks and various heuristics to determine what to do. You could argue that the programs got some of this "creativity", "imagination", "insight" or whatever.

No, they don't use neural networks ( at least none of top performers in computer chess championships have). However, they dont' use brute force either. They combine many heuristics for pruning and when to search a line deeply, not that different from what humans do - except the amount of computation done by the computer is much larger. In GO is where little progress was made without neural networks.

[edit: in other words, if you replace your 'and' with 'or', I have no disagreement with your statement]

 

[mfb]

I fully agree. The hypothesis at hand is therefore whether or not the brain, or more specifically the neural mechanism of consciousness, is a Turing machine. Trivial heuristic presumptions aside, this has not been demonstrated either way.

That is not even necessary. An approximation by a Turing machine is sufficient. We can study all the particles that make up a brain, we know we understand their interactions extremely well, and we can simulate these interactions.
We don't have a full-scale brain simulation today, but the loopholes for arguments why it could be impossible get really obscure.

what I am questioning is the assumption that the possibility of relevant new physics seems to be precluded on the basis of taking a contemporary theory (SM) as essentially factual beyond its experimentally checked limits, especially when there are other competing rival theories which have not been experimentally ruled out yet in all relevant regimes.

Which relevant regime? All discussed alternatives to the SM are only relevant at high energies, for extremely short-living particles not present in human brains, for extremely rare processes, or otherwise irrelevant for everyday matter. New physics cannot play a relevant role in everyday matter - otherwise we would have found it.

 

[arivero]

What about the same problem with another rook instead of queen?

 

[Mastermind01]

The problem mainly has to do with computer evaluation of the position. Stockfish apparently shows a massive advantage (nearly -30) but of course it is unable to find a win for black.

 

[arivero]

The problem mainly has to do with computer evaluation of the position. Stockfish apparently shows a massive advantage (nearly -30) but of course it is unable to find a win for black.

I see. And with a bishop instead of the queen, does the computer find the trivial win of white? I would hope so.

 

[PAllen]

The problem mainly has to do with computer evaluation of the position. Stockfish apparently shows a massive advantage (nearly -30) but of course it is unable to find a win for black.

However the evaluation per se has never been a goal of chess programming. Finding strong moves is the goal. In this case, even the weakest chess programs play the right moves for both sides, and declare a draw when either 50 move rule or 3 fold repetition is approached. This example just fails to be convincing. The chessbase article referenced earlier gives much better example of current weaknesses of chess programs (position designed by a chess grandmaster), where the program fails to find the drawing move (sacrificing more material), and instead loses. The strongest current programs lose this position while reasonably strong human players solve it.

 

[.Scott]

View attachment 195050
What a person can do is recognize that in the current configuration, black can do nothing effective.

Select text to read:
So, for white to draw, it simply has to avoid releasing any black pieces.
For example, P-QB7 allows black: K-QN2, Kx, Q-QR3, Q-QB1 and white is doomed.
Or: PxR allows black QxP and white is doomed.
So white simply needs to move the king around - perhaps chasing the bishops. After 50 moves, the game is a draw.
The only possible win for white involves incredible mistakes by black.
-------------------

 

[PAllen]

View attachment 195050
What a person can do is recognize that in the current configuration, black can do nothing effective.

Select text to read:
So, for white to draw, it simply has to avoid releasing any black pieces.
For example, P-QB7 allows black: K-QN2, Kx, Q-QR3, Q-QB1 and white is doomed.
Or: PxR allows black QxP and white is doomed.
So white simply needs to move the king around - perhaps chasing the bishops. After 50 moves, the game is a draw.
The only possible win for white involves incredible mistakes by black.
-------------------

But any of today's chess programs find best moves for both sides, including winning with white if black errs. The only thing funny is the evaluation, which has never been an end in itself for chess programmers.