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

[Auto-Didact]

This chess problem - originally drawn by Sir Roger Penrose - has been devised to defeat an artificially intelligent (AI) computer but be solvable for humans. The Penrose Institute scientists are inviting readers to workout how white can win, or force a stalemate and then share their reasoning.

The team then hopes to scan the brains of people with the quickest times, or interesting Eureka moments, to see if the genesis of human ‘insight’ or ‘intuition’ can be spotted in mind.

Can you solve the puzzle? | Scientists want to hear from you if you've cracked it
The puzzle above may seem hopeless for white, with just a King and four pawns remaining, but it is possible to draw and even win.

Scientists have constructed it in a way to confound a chess computer, which would normally consider that it is a win for black.

However an average chess-playing human should be able to see that a draw is possible.

A chess computer struggles because it looks like an impossible position, even though it is perfectly legal.

The three bishops forces the computer to perform a massive search of possible positions that will rapidly expand to something that exceeds all the computational power on planet earth.

Humans attempting the problem are advised to find some peace and quiet and notice how the solution that arises. Was there a flash of insight? Did you need to leave the puzzle for a while and come back to it?

The main goal is to force a draw, although it is even possible to trick black into a blunder that might allow white to win.

The first person who can demonstrate the solution legally will receive a bonus prize.

Both humans, computers and even quantum computers are invited to play the game and solutions should be emailed to puzzles@penroseinstitute.com.

Source: http://www.telegraph.co.uk/science/2017/03/14/can-solve-chess-problem-holds-key-human-consciousness/

 

[PeroK]

It would interesting to see how a computer would play white!

I can't see how a computer could possibly lose with black.

PS unless the computer actually resigned, I suspect it would play all the right moves. It would draw as white.

It's the assessment of the position that is key.

 

[jedishrfu]

This is a job for the Sun Tze Bing Fa ie The Art of War:

http://www.history.com/topics/the-art-of-war

 

[Aufbauwerk 2045]

"A chess computer always assumes black will win"

How so?

I'm not a good chess player and I haven't played much since high school. But this seems trivial to me. Let's see if I'm right. If I'm wrong, it just proves what a bad chess player I am. :)

Black could lose, as the problem says, if it blunders. A chess program that made this blunder would be pathetically weak.

It's white to move. Let's set up the possible black blunder with a white blunder.

If white moves the pawn from c6 to c7, black must capture using the bishop on e5. Otherwise, on the next move, white would move the pawn again, have a pawn on c8, promote it to queen (although even bishop would be enough) and checkmate black.

So let's ignore this blunder situation, and go for a draw. This is easy to figure out for a human. I think a chess program with good heuristics would also figure it out. The key is to program the right heuristic for a case like this. Perhaps it has already been done.

The way to force a draw is for white to simply move his king around on safe squares. He could just move from e2 to f1 and back.

In that case the only legal replies black will ever have is another pointless move of a bishop. Black can't move any other pieces as long as white keeps them hemmed in with his pawns. None of the black bishops can capture a white pawn because they are on different colored squares.

This would go on until the 50 move rule is invoked.

So, assuming I have analyzed this correctly, using my weak chess knowledge, what exactly is the point of this problem?

(EDIT -- I do see what the article claims is the point. I just don't agree that this problem would be such a challenge for a correctly programmed chess computer to solve.)

 

[Aufbauwerk 2045]

P.S.

If black was so weak as to move all bishops off the diagonal where they defend c7, then the white pawn could move there, and checkmate on the next move as already explained.

 

[TeethWhitener]

I call BS.

1) Just plugged this into an online server running GNUChess and it drew (threefold repetition). I suspect that the fact that only the bishops can legally move makes it significantly easier to evaluate than even the most mundane middlegame position. Especially since most decent chess programs have positional weighting schemes in addition to the straightforward tactical piece-value calculations.

2) As has been pointed out, this is pretty obviously a draw. More interesting would be to give a chess engine some classic endgame study without the benefit of tablebases. I guarantee you someone (likely a chess player and not a GR researcher) has done this

Bingo: https://en.wikipedia.org/wiki/Endgame_study#Studies_and_chess_engines

The Telegraph article implies that this is more of Penrose's quantum consciousness gobbledygook. It is interesting that there exist positions that computers struggle with, but I would contend that there are likely few of any positions that computers struggle with which are easy for humans.

 

[TeethWhitener]

I take that back; I found a position that's easier for humans than for computers: https://en.m.wikipedia.org/wiki/Rules_of_chess#Initial_setup

 

[EnumaElish]

For a draw in chess anyone of the following rules should satisfy :

1. stalemate
2. threefold repetition of a position (with the same player to move)
3. if there has been no capture or a pawn being moved in the last fifty moves
4. if checkmate is impossible
or
5. if the players agree to a draw.

My guess is it's 3. It may also be 4, but I haven't verified it.

 

[Auto-Didact]

I call BS.

1) Just plugged this into an online server running GNUChess and it drew (threefold repetition). I suspect that the fact that only the bishops can legally move makes it significantly easier to evaluate than even the most mundane middlegame position. Especially since most decent chess programs have positional weighting schemes in addition to the straightforward tactical piece-value calculations.

It is possible, possibly even likely, that Penrose is referring solely to the more pure old school chess programmes, which can only calculationally brute force their way through; the reason for this limiting is also pretty clear from a psychology standpoint. For similar reasons, adding in extra insightful plays in whatever form into the code would, I believe, somewhat confound the purpose of the entire study seeing it is the human programmer or some other human who has come up with these insights, not the program itself.

As for tablebases, these are based on retrograde analysis and should therefore be excluded as well. Using deep neural nets/GANs/etc instead of regular chess programs would be an interesting study in itself, one that likely is already being or already has been done.

2) As has been pointed out, this is pretty obviously a draw. More interesting would be to give a chess engine some classic endgame study without the benefit of tablebases. I guarantee you someone (likely a chess player and not a GR researcher) has done this

Bingo: https://en.wikipedia.org/wiki/Endgame_study#Studies_and_chess_engines

I wouldn't be too keen on dismissing Penrose as merely 'a GR researcher' seeing, first off, he is first and foremost a pure mathematician specialising in algebraic geometry, and second, as record has it, Penrose grew up in a highly chess competitive environment (NB: his father was both an avid player and an endgame composer and he made all the kids compete, leading Roger's older brother to become Oxford champion and his younger brother to win the British championship ten times, beat a reigning world champion and go on to become a Grand Master).

More importantly, the particular game here is a selection criteria specifically for humans, not the end-all scenario for any possible programmable chess program whatsoever, although it probably is for bruteforce programs which again seem to be the only relevant programs in this case. It is highly likely that the evaluation of other endgame scenarios and whatnot, which are difficult for (brute force) chess programs, by human subjects are also part of the actual study.

The Telegraph article implies that this is more of Penrose's quantum consciousness gobbledygook. It is interesting that there exist positions that computers struggle with, but I would contend that there are likely few of any positions that computers struggle with which are easy for humans.

Actually, what they are attempting to study here using functional imaging is a well-known empirical phenomenon from experimental psychology about human reasoning, known as dual process theory. This field has a rich experimental history since the early 70s.

The kind of study they are attempting here has both practical and scientific merit; I have actually done related research myself and can confidently say that many type 1 reasoning strategies can be extremely difficult, often even practically if not de facto impossible, to reduce to mere computation or pure deduction. Calculation on the other hand, and pretty much anything that is directly reducible to computation, are archetypically forms of type 2 reasoning.

Using brain imaging studies to better map the associated brain areas for specific kinds of problems like chess (which is harder than elementary arithmetics, but simpler than, say, physics) has immense implications for all possible forms of type 1 reasoning, and possibly even practical utility for learning and teaching, most obviously the learning and teaching of mathematics at all levels.

To dismiss this study as part of "Penrose' quantum consciousness gobbledygook" is a highly biased and unscientific standpoint. Whatever relation this all might have to Penrose' ideas on consciousness are at best indirect and I would even say completely secondary; the fact that his ideas have inspired many, myself included, to study such phenomena more carefully and more rigorously, even giving us clean 'natural experiments' from areas of mathematics and logic which many would likely otherwise never been exposed to, is nothing short of praiseworthy.

 

[Auto-Didact]

(EDIT -- I do see what the article claims is the point. I just don't agree that this problem would be such a challenge for a correctly programmed chess computer to solve.)

'Correctly programmed' likely involves a change of the actual hypothesis under investigation. This hypothesis seems to be: 'actual chess playing by competent human chess players does not resemble, nor is reducible to, (bruteforce) computation, but instead requires insight, pattern recognition, heuristics and so on.' Incompetent human chess playing is exactly bruteforce trial-and-error, i.e. an exercise in computation.

An analogous hypothesis about another form of human reasoning, namely mathematics, is that many human mathematicians employ intuition to solve most problems, and many if not most reported solutions in the form of perfect logically deductive schemes are purely post hoc constructions which do not remotely resemble the prior actual reasoning process, and which are made for aesthetic, conventional and sociological reasons, i.e. in order to present the findings in a clean, simple and clearly communicable fashion.

 

[TeethWhitener]

For similar reasons, adding in extra insightful plays in whatever form into the code would, I believe, somewhat confound the purpose of the entire study seeing it is the human programmer or some other human who has come up with these insights, not the program itself.

But the human programmer comes up with the entire algorithm, including the brute force calcuations. Why do we get to include the brute force and exclude the insights? (Do we exclude, e.g., the idea of point values for various pieces? That's an insight in itself, not intrinsic to the rules of chess.) Is the hypothesis that some problems are more difficult to solve with brute force than with some special insight really that controversial?

The kind of study they are attempting here has both practical and scientific merit;

I'm sure it does, but maybe not for the reasons the linked article alluded to. If they want to study the "flash of insight" by fMRI, why do they need a task which is hard for computers? How is that at all relevant? A particularly thorny tactical problem in a standard middlegame might induce a flash of insight for a person but be relatively trivial for a strong chess engine to solve.

To dismiss this study as part of "Penrose' quantum consciousness gobbledygook" is a highly biased and unscientific standpoint.

The bias is grounded in decades of people taking Penrose's predictions, actually experimentally testing them, and falsifying them. I'd say that's pretty scientific.

Whatever relation this all might have to Penrose' ideas on consciousness are at best indirect and I would even say completely secondary; the fact that his ideas have inspired many, myself included, to study such phenomena more carefully and more rigorously, even giving us clean 'natural experiments' from areas of mathematics and logic which many would likely otherwise never been exposed to, is nothing short of praiseworthy.

Wait, who's biased?

 

[Auto-Didact]

Disclaimer: this thread is not about (Orch) OR, I will try to definitively answer all relevant points about OR w.r.t. the studies in the OP in this post, but I will not discuss it any further.

But the human programmer comes up with the entire algorithm, including the brute force calcuations. Why do we get to include the brute force and exclude the insights? (Do we exclude, e.g., the idea of point values for various pieces? That's an insight in itself, not intrinsic to the rules of chess.) Is the hypothesis that some problems are more difficult to solve with brute force than with some special insight really that controversial?

See my post above about dual process theory.
Whether it is controversial or not is irrelevant, the question is what has been mapped out already and what has not. Chess seems to be a wonderful natural experiment for investigating such matters seeing it is mathematically well understood and can easily be played mentally giving only pictures to the subject and asking them to verbalise their thoughts, giving a very clean way of empirically distinguishing reasoning processes in vivo, which is also generalizable to other mental activities.

The hypothesis paraphrased:
P1) All (directly explicit) algorithmic action, calculation and computation are tasks of purely type 2 reasoning.
P2) Understanding (or comprehension) is a form of type 1 reasoning.
P3) Human reasoning does not solely consist of type 2 reasoning, we are also capable of type 1 reasoning.
P4) Computers or Turing machines or clearly non-conscious adding machines like abaci and calculators, strictly perform tasks that belong to type 2 reasoning.
C) Therefore such machines can not fully simulate human understanding.

It has already been demonstrated that brute force reasoning falls squarely under the type 2 reasoning tasks and it is therefore scientifically, i.e. from the point of view contemporary experimental psychology, completely uninteresting to study it further in humans. It should also be abundantly clear that competent chess players do not play chess purely by utilizing brute force, but also by using type 1 reasoning; to insist on investigating such matters w.r.t. the current hypothesis is to attempt an empirically sterile in vitro artificial experiment.

What you are asking isn't about the hypothesis at hand. Moreover, there actually seems to be two very subtle points at play here:
1) insight has both an operational definition (from psychological theory) and an informal definition; to conflate the two definitions is to construct and attack a strawman argument
2) you also seem to be confusing the hypothesis which is a de re statement (some human reasoning is such that it is necessarily non-computational) for the de dicto statement (necessarily, some human reasoning is such that it is non-computational). These are two distinct hypotheses.

I'm sure it does, but maybe not for the reasons the linked article alluded to. If they want to study the "flash of insight" by fMRI, why do they need a task which is hard for computers? How is that at all relevant? A particularly thorny tactical problem in a standard middlegame might induce a flash of insight for a person but be relatively trivial for a strong chess engine to solve.

That is extremely relevant, in fact that is the entire argument: they want to study such flashes of insights in real time and so experimentally map their neural characteristics. This has already been done for forms of type 2 reasoning.

The bias is grounded in decades of people taking Penrose's predictions, actually experimentally testing them, and falsifying them. I'd say that's pretty scientific.

Which specific predictions? Many of the takedowns I've seen (Feferman, Churchland, Grush, Dennett, Tegmark, etc) are strawman arguments, indirect arguments or failures to comprehend the argument altogether. Moreover, I believe there might an actual direct takedown from the point of view of logic which has not been given any large degree of coverage. Almost all of the experimental 'takedowns' have been addressed in the 2014 review of the theory.

More importantly, Penrose' hypothesis of human understanding being seemingly a non-computational activity is fully consistent with contemporary experimental psychology findings; he only happens to use somewhat different terms, him of course not being intimately familiar with the fields specific jargon or its modern empirical theories such as dual process theory. What this means is, he has incidentally rediscovered a hypothesis which happens to have already been investigated and has survived being falsified.

Perhaps most importantly, all of the above has nothing, in principle, to do with gravitational objective reduction (OR) theory, Orch OR or twistor theory. These are all experiments which stand or fall on the basis of their own merits. These results say nothing about his further hypotheses that I) understanding requires awareness, II) awareness requires consciousness, III) the mechanism of proto-consciousness is mass-dependent gravitationally induced OR of the wavefunction, IV) human consciousness is neuronal microtubules undergoing gravitational OR in an orchestrated fashion.

Scientifically, with regard to physics, OR is a falsifiable scheme and there are multiple experiments underway to falsify it. There have been no experiments which have falsified OR yet, the latest estimates by experimentalists places us at years if not decades away from being able to carry out the required experiments. All that can be said at the moment is that the experiments will either demonstrate superposition from orthodox QM persists at all mass scales up to macroscopic masses or show a regime where QM fails and some form of OR will point in the direction of the new theory. That is really all that is relevant at the moment.

It is only after the experimental parameter space at each scientific level has been mapped out carefully enough, that eventually some deeper physical theoretical explanations for psychology, such as Orch OR or some other competing theory, may be required and thus pointed out. This thread was not meant to discuss (Orch) OR, so I hope this post has addressed all relevant scientific issues about it with respect to the research in the OP.

Wait, who's biased?

I'll immediately admit my bias :P
The man is one of the major reasons I went into physics in the first place. He is without reserve or question a genius, one with a remarkable breadth and depth of knowledge, a dispassionate independent mind with a healthy philosophical curiosity and an equally healthy dose of humility - all good qualities for a scientist, and for a mathematician very reminiscent of the universalists of old. Saying any of this does not jeopardise my scientific integrity; I and many others have said far crazier things about the likes of Newton and Einstein.

To quote Feynman:

What is necessary for the very existence of science is just the ability to experiment, the honesty in reporting results, and finally, the intelligence to interpret the results, but, an important point about this intelligence is that it should not be sure ahead of time about what must be.

Now, it can be prejudiced and say, “That’s very unlikely; I don’t like that…” Prejudice is different than absolute certainty–bias, but not strict bias, not complete prejudice. As long as you’re biased it doesn’t make any difference because, if the fact is true there will be a perpetual accumulation of experiments that perpetually annoy you until they cannot be disregarded any longer. They can only be disregarded if you are absolutely sure ahead of time of some precondition that science has to have. In fact it is necessary for the very existence of science that minds exist which do not allow that nature must satisfy some preconceived condition.”

Lastly, there have actually been several extremely great mathematicians who have focused on the issues of human psychology, philosophy of mind and their relationship to mathematics. Two prominent mathematicians who have written extensively about these issues which I have read are Poincaré (The Foundation of Science) and Hadamard (An essay on the psychology of invention in the mathematical field). I highly recommend these two books to any mathematically inclined person. It is a veritable shame that this type of research has fallen out of repute with the shift of the intellectual world capital out of Europe during the darker years of the 20th century and the simultaneously occurring over-specialisation/balkanisation of science and its subsequent professionalisation.

Of course, there have also been many mathematicians who have written a lot of plain mystical nonsense regarding these topics, most painfully noticeable major figures like von Neumann and Wigner. In either case, I believe a historical reading of Penrose' work, especially his clarified position in Shadows of The Mind and his further errata, safely places him among the former intellectual group instead of the latter more mystical group, and his works on these issues can be seen as a natural evolution of the earlier debate on many of these issues earlier brought to prominence by Poincaré, Hadamard et al. The argument that he is a mystic because he has associated with known charlatans like Chopra is equally empty as Feynman being one too because he frequently associated with not only new age types but also with hippies, stoners, strippers and gamblers.

 

[Demystifier]

To solve the puzzle, a human does not think about exact moves he will play. Instead, a human only has a vague long term strategy, to wander with white king around black bishops, hoping that black might make a wrong move with his bishops. Computer algorithms are not good in such vague strategies.

But what if we program computer differently, not by giving it the precise chess algorithm, but by training it with deep learning neural network (which is how programmers recently trained computers to win the Go game against best human Go players)? I have a feeling that this kind of computer program could much better better play such easy-for-human situations.

 

[Auto-Didact]

To solve the puzzle, a human does not think about exact moves he will play. Instead, a human only has a vague long term strategy, to wander with white king around black bishops, hoping that black might make a wrong move with his bishops. Computer algorithms are not good in such vague strategies.

But what if we program computer differently, not by giving him the precise chess algorithm, but by training him with deep learning neural network (which is how programmers recently trained computers to win the Go game against best human Go players)? I have a feeling that this kind of computer program could much better better play such easy-for-human situations.

As I said before, it wouldn't surprise me if this has already been researched, seeing the recent explosive popularity of deep learning methods. In any case, I also think such a neural net (NN) could quite possibly overtake humans w.r.t. such problems, at least given that such problems feature adequately in the initial learning data set given to the NN.

It would be even more interesting if such problems weren't included in the initial data set and the NN still managed to reliably outperform humans on these problems; in such cases studying the used strategy of the NN might even be able to provide invaluable novel mathematical information about the problems to researchers and human chess players.

 

[mfb]

To solve the puzzle, a human does not think about exact moves he will play. Instead, a human only has a vague long term strategy, to wander with white king around black bishops, hoping that black might make a wrong move with his bishops. Computer algorithms are not good in such vague strategies.

But what if we program computer differently, not by giving it the precise chess algorithm, but by training it with deep learning neural network (which is how programmers recently trained computers to win the Go game against best human Go players)? I have a feeling that this kind of computer program could much better better play such easy-for-human situations.

Neural networks are used to evaluate the strength of positions. Unless one side makes a stupid mistake, all future positions have the same strength - the king and the bishops will be in different places, but that doesn't change the situation. A good neural net will tell you that. And then? It will draw. Which is not bad, but that is something even much simpler computer programs can do.

 

[TeethWhitener]

I'm really interested in this thread, and @Auto-Didact seems to know a lot about this area, but in order to respond constructively, I need to give your post much more attention than I can currently give it. This is really unfortunate, and for that I apologize. I also have to apologize for misinterpreting the chess problem as being much easier to solve than it actually is. At least according to the Telegraph article, the task is specifically to force a stalemate (that is, not a checkmate, but no legal moves for white). This is significantly more difficult than forcing a draw. Maybe I'll have my own flash of insight at some point.

 

[TeethWhitener]

Ok, I've sufficiently nerd-sniped myself. I think I might have gotten it:

Spoiler

First, walk the white king up to c8. The black bishops do whatever while still controlling the h2-b8 diagonal to prevent the white pawn on c6 from marching up and checkmating.
Then, once the white king is on c8, push the pawn to
1. c7.
Black can respond in one of 2 ways.
1 ...ignore the pawn at c7. Then,
2. Kb8 Bxc7+ (necessary to prevent c8=Q#)
3. Ka8 stalemate
or
1 ...Bxc7
2. cxb5+ Qxb5 stalemate

The final wrinkle is if ignoring the pawn at c7 involves stepping the last bishop completely off the h2-b8 diagonal. In that case, we get
1. Kb8 B (steps back onto the h2-b8 diagonal)
This pins the pawn to the king and keeps it from promoting and checkmating. But in this case, we simply have
2. Ka8 Bxc7 stalemate.

EDIT: problems with this solution:
First branch: If there's only one black bishop on the h2-b8 diagonal after Ka8, nothing prevents it from stepping off, forcing the king to move out of his safe square.
Second branch: Nothing stops the black king from getting himself out of check by capturing. This leaves b7 and d7 open to the white king.

EDIT: I found a whole bunch of problems with this solution. Disregard.

 

[stevendaryl]

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.

 

[kith]

This problem seems odd to me.

If it is not about forcing a stalemate, it is easy to go for the 50 move rule. Here is an article from chessbase.com where someone confirms that (old?) chess algorithms strongly predict that black will win. But why should they put up a prize and sample people by sending them an email if the solution is so easy?

If on the other hand the problem is how to force a stalemate, it seems to be really hard to me. I have thought about it a bit myself and searched online for people who have a solution and didn't find anything. So it doesn't just seem to take an "average chess-playing human".

 

[willem2]

There's no forced stalemate. I've used a computer to find out that playing b3xa4, c4xb5 or c6-c7 allways loses, wherever the white king is, if black only plays the bishop from h2 to g3 and back. Whenever you do one of these things, there will be mate in at most 13 moves.

 

[stevendaryl]

There's no forced stalemate. I've used a computer to find out that playing b3xa4, c4xb5 or c6-c7 allways loses, wherever the white king is, if black only plays the bishop from h2 to g3 and back. Whenever you do one of these things, there will be mate in at most 13 moves.

Hmm. I came to that conclusion, too, but timidly assumed that I might have overlooked something. But since you used a computer, instead of your human insight, you've fallen into Penrose' trap: the correct answer can't be found by computer.

 

[puzzled fish]

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...

 

[gmax137]

I don't know much about chess either, but how/why would black end up with three black-square bishops? Wouldn't black have two more queens instead? I could see promoting a pawn to a knight in certain conditions but why a bishop, and why a bishop twice in one game?

And yes I realize this is kind of off-topic. Except I have to wonder about the "computer" black player that picked bishops...

 

[stevendaryl]

I don't know much about chess either, but how/why would black end up with three black-square bishops? Wouldn't black have two more queens instead? I could see promoting a pawn to a knight in certain conditions but why a bishop, and why a bishop twice in one game?

And yes I realize this is kind of off-topic. Except I have to wonder about the "computer" black player that picked bishops...

I don't think anyone claims that it is a plausible game state, only that it is a possible one. Yes, it would require promoting a black pawn to a bishop. I can't imagine any reason for doing that.

The arrangement of black pawns seems highly unlikely, as well. I would like to see a transcript of a game that develops into this position.

 

[willem2]

Hmm. I came to that conclusion, too, but timidly assumed that I might have overlooked something. But since you used a computer, instead of your human insight, you've fallen into Penrose' trap: the correct answer can't be found by computer.

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.

 

[stevendaryl]

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.

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.

 

[koolkakao]

Well the stalemate is easy, the pawn has to move up, the bishop will kill it so it won't spawn a queen and there you go.. 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).. This is nothing hard to see, but we have to assume that the computer has an IQ < 80 if that makes sense [emoji23]

 

[willem2]

Well the stalemate is easy, the pawn has to move up, the bishop will kill it so it won't spawn a queen and there you go.

A Draw is easy. A stalemate means that white has no legal moves. There's no way for white to force this.

 

[mfb]

There's no forced stalemate. I've used a computer to find out that playing b3xa4, c4xb5 or c6-c7 allways loses, wherever the white king is, if black only plays the bishop from h2 to g3 and back. Whenever you do one of these things, there will be mate in at most 13 moves.

How can white lose with c6-c7? Black still cannot do anything apart from moving the bishops, which means we run into the 50 move rule - or a stalemate.

 

[kith]

How can white lose with c6-c7? Black still cannot do anything apart from moving the bishops, which means we run into the 50 move rule - or a stalemate.

If the white pawn leaves c6, black can move the king.

 

[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.