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

[arivero]

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.

I think the idea for the stalemate is it to be in c8, with a Bishop in c7. Then if black cooperates Qxb5, it is stalemate. Without cooperation, I can not see how.

 

[.Scott]

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.

It is certainly possible to program the computer to look for opportunities like this. But the common tact is to play out all combinations for both sides until something decisive happens - with lots of strategic optimizations. This is trap for that kind of processing. You have two easy rook kills that will be tallied as promising moves. Then you have "endless" (50 black/white moves) that eventually ends in a draw. Possible move combinations exceed anything that move look-aheads could tackle. There is an optimization that can help - recognizing that without moving the pawns, there are "only" certain configurations possible with the white king and three bishops (47x26x25x24/6), so if you evaluate all 122,200 positions you would discover that only good things can happen.

 

[PAllen]

It is certainly possible to program the computer to look for opportunities like this. But the common tact is to play out all combinations for both sides until something decisive happens - with lots of strategic optimizations. This is trap for that kind of processing. You have two easy rook kills that will be tallied as promising moves. Then you have "endless" (50 black/white moves) that eventually ends in a draw. Possible move combinations exceed anything that move look-aheads could tackle. There is an optimization that can help - recognizing that without moving the pawns, there are "only" certain configurations possible with the white king and three bishops (47x26x25x24/6), so if you evaluate all 122,200 positions you would discover that only good things can happen.

No, it is a fact that no major current programs err in this position. They just give a silly evaluation.

[edit: the reason is simple. Using current search technology, which is not pure brute force, all so called promising bad moves are rapidly calculated to lead to disaster. They meet heuristics for deep search for forcing moves. Meanwhile, the correct moves preserve the evaluation. Thus, in a fraction of a second, correct moves are found for both sides. Further, if a black error is played, the correct win for white is rapidly found.]

 

[epenguin]

Have not read the thread but seems to me almost any legal series of moves by the white King but preferably a monotonous alternation like K-d3, ..., K-e2, repeated forces a draw, since the King cannot be attacked nor can any pawns and black can only move the bishops, and the same arrangement of peices must be reached three times or the same sequence of moves is forced after a very long time, oh I see this solution has been given.

Not certain but it looks to me a game could be played that results in this position. A game of no interest to human players. Even a game with three same-colored bishops must never or hardly have happened in history. Only when the object of the game becomes to achieve just that, not winning.

 

[arivero]

I see this solution has been given. .

Yep, so now the thread is about second-guessing Penrose and why he is asking people to email them about such trivial answer. It has even put a cross in the board to indicate the "trap" to induce black to move its king into check mate.

A possibility is that he is just building a list of emails for next problems. Another one is that they really have a stalemate, without 50 steps rule, and we are not seeing it.

 

[Auto-Didact]

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.

There is much that is understood, but even today w.r.t. biology and neuroscience more remains to be unknown than known. In order to actually characterize many dynamical processes, not even statistical mechanics can always help us much either, seeing life is an open system, often far from equilibrium. This new physical theory of non-equilibrium statistical mechanics simply has not yet been put in definitive mathematical form yet.

Of course, in the cases of QM and the SM, one could always appeal to the correspondence principle and to Wilson's effective field theory criteria. Even in physics this however need not carry over cleanly to larger scale systems, and this mock example should make that clear: given only the SM, derive the complete theory of superconductivity and so determine all possible high $T_c$ superconductors.

The same counter-argument against QFT or the SM being sufficient to fully explain some phenomenon applies doubly in the case of biological systems, of which the relevant mathematics and physics can be very far from clear, much less understood, apart from some trivial aspects of chemical composition.

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.

The regime of superposition of mesoscopic masses (from about $10^{-21}$ up to about $10^{-7} \rm{kg}$) in standard QM for one. This is a regime for which it has not yet been shown that QM predictions using large quantum numbers match classical predictions.

Moreover, new physics does not only signify advances in high energy particle theory; the overthrow of or modification to any accepted orthodox physical theory by experimental data, whether that be in condensed matter theory, in biophysics or just in plain old mechanics, constitutes new physics. History greets us with no shortage of examples.

 

[PAllen]

Yep, so now the thread is about second-guessing Penrose and why he is asking people to email them about such trivial answer. It has even put a cross in the board to indicate the "trap" to induce black to move its king into check mate.

A possibility is that he is just building a list of emails for next problems. Another one is that they really have a stalemate, without 50 steps rule, and we are not seeing it.

Even without 50 move rule, draw must occur by 3 fold repetition eventually, if neither side blunders.

 

[SSequence]

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

On not a fully serious note (as I feel a serious (mathematical) answer would detract quite a bit from the thread), if someone harnessed such a device I would give that to person A (in my previous post). Unless the device malfunctioned at some point :p.
Or perhaps even worse the device proved to be a trickster (working for only first few values and then just giving wrong answers).

 

[arivero]

Even without 50 move rule, draw must occur by 3 fold repetition eventually, if neither side blunders.

Hmm under 3 fold repetition rule, surely at the end white is forced to move some pawn. After very long game.

 

[PAllen]

Hmm under 3 fold repetition rule, surely at the end white is forced to move some pawn. After very long game.

White is never forced to move a pawn. That would be idiotic loss. By not doing so, white forces draw. You may be confused by GO, where repeating position (in superko rule variants) is prohibited. In chess, repetition is not prohibited, and leads to draw, whenever both sides would face adverse consequence of avoiding repetition. That is precisely the case here. Thus, this position is an absolute draw without idiotic blunder which even weak programs will not make.

 

[PAllen]

Just as an experiment, I restored a 15 year old chess program I had saved. It has no trouble with all the nuances of correct play despite the silly evaluation of 22 in favor of black. Even at one second per move, it plays flawlessly. Penrose is just totally off base here.

 

[durant35]

Computer programs playing these games on an expert level.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.

This is more philosophy than physics, we don't know what consciousness is and how it emerges. In a sense the emergence of consciousness already is a miracle. I think that you as a physicist are going too far with 'it's all a bunch a particles which can be simulated".

Do you have any insight on the problems in the philosophy of mind (which are clearly related with your post) or are you just speculating about consciousness based on your physics insights? It is a enormous reach to claim with such a certain tone that neurons/consciousness can be simulated.

You should read Searle's Chinese room thought experiment before insisting on a such clear path between physics and consciousness.

 

[Demystifier]

Unless you propose some magic outside the realms of physics, there is nothing a human can do that a computer could never achieve.

One should distinguish what a human can do, from what a human can experience. The former can be described and explained by physics. The latter is a "magic" that cannot be described or explained by known physical laws.

 

[.Scott]

No, it is a fact that no major current programs err in this position. They just give a silly evaluation.

[edit: the reason is simple. Using current search technology, which is not pure brute force, all so called promising bad moves are rapidly calculated to lead to disaster. They meet heuristics for deep search for forcing moves. Meanwhile, the correct moves preserve the evaluation. Thus, in a fraction of a second, correct moves are found for both sides. Further, if a black error is played, the correct win for white is rapidly found.]

Okay, so for this to be an algorithm trap, not only would we need the winning line to involve a prohibitive deep search, but the losing line must be provably disastrous only after a prohibitively deep search.

But, of course, there are always better algorithms. Anything logic that can be followed by a person, can be replicated in an algorithm. When I tackle a nasty algorithm problem, I often start by saying to myself "given the information, what would I as a person be able to deduce, and how would I know what to do?".

 

[Auto-Didact]

One should distinguish what a human can do, from what a human can experience. The former can be described and explained by physics. The latter is a "magic" that cannot be described or explained by known physical laws.

That is quite a bit bolder than I would normally put it, but I fully agree. The capability of experiencing implies having some kind of awareness; it is argued that insight relies on both and it should be quite clear computers or AI seem to have nothing of the sort.

Unless this phenomenon can somehow actually fully be explained away using functionalism, which I don't believe is possible at all on the grounds that that would de facto constitute a refutation of the thesis of physicalism, I think it is quite obvious that not merely the SM but contemporary physics itself obviously has a gaping hole.

 

[PAllen]

That is quite a bit bolder than I would normally put it, but I fully agree. The capability of experiencing implies having some kind of awareness; it is argued that insight relies on both and it should be quite clear computers or AI seem to have nothing of the sort.

Unless this phenomenon can somehow actually fully be explained away using functionalism, which I don't believe is possible at all on the grounds that that would de facto constitute a refutation of the thesis of physicalism, I think it is quite obvious that not merely the SM but contemporary physics itself obviously has a gaping hole.

Note, this is altogether different from what Penrose argues. He believes the brain and consciousness are products of physics. He disagrees with some others about which physics is involved (quantum entanglement).

 

[mfb]

but even today w.r.t. biology and neuroscience more remains to be unknown than known.

It does not matter. You keep arguing "but we cannot simulate it today" - that is not the point.

I cannot build a rocket that goes to space today. But with sufficient resources, I know I could. Why? Because rockets that can go to space exist, and they are made out of atoms - atoms I can get and arrange as well. Assembling a rocket atom by atom (or simulating it atom by atom if we just want to predict its actions) is a stupid approach - but it shows the general feasibility.

given only the SM, derive the complete theory of superconductivity and so determine all possible high $T_c$ superconductors.

Give me a sufficiently powerful computer and I tell you $T_c$ of all materials.

This is a regime for which it has not yet been shown that QM predictions using large quantum numbers match classical predictions.

It has been shown mathematically that classical motion is the quantum mechanical limit for small $\hbar$ - or "large" systems. But that is not the point. It can be studied.

Moreover, new physics does not only signify advances in high energy particle theory; the overthrow of or modification to any accepted orthodox physical theory by experimental data, whether that be in condensed matter theory, in biophysics or just in plain old mechanics, constitutes new physics.

It only produces new effective models. Which you don't need if you have unlimited computing power to simulate everything without effective models.

This is more philosophy than physics, we don't know what consciousness is and how it emerges.

For the chess AI, it does not matter if the brain simulation has consciousness, or what that means in the first place.

You should read Searle's Chinese room thought experiment before insisting on a such clear path between physics and consciousness.

I did not discuss anything related to consciousness yet. I am well aware of the standard thought experiments, thank you.

One should distinguish what a human can do, from what a human can experience. The former can be described and explained by physics. The latter is a "magic" that cannot be described or explained by known physical laws.

I said "can do" on purpose.

The capability of experiencing implies having some kind of awareness; it is argued that insight relies on both and it should be quite clear computers or AI seem to have nothing of the sort.

It is a bit off-topic, but why do you think this is clear? To me, this is just the old "we must be special!" story. First Rome had to be the center of the world. Why? Because. Then the Earth had to be the center of the world. Then the sun. Then our galaxy. In parallel, humans made up stories how humans were created different from all other animals. After Darwin, it was "tool use is only human", "long-term planning is only human", and so on - all refuted with more observations. "tool use is only found in mammals", "long-term planning is only found in mammals" - again refuted. "tool production is only human"? Same thing.
"Only humans can play Chess well" - until computers beat humans in Chess.
"Okay, they can play Chess, but Go requires insights computers don't have" - until computers beat humans in Go.
"Okay, but Poker is different" - until computers won in Poker.

There is absolutely no indication that humans can do or have anything other systems cannot do/have.

 

[Demystifier]

"Okay, but Poker is different" - until computers won in Poker.

Can computers read the human body language associated with bluffing? The rest is "trivial".

 

[mfb]

Can computers read the human body language associated with bluffing? The rest is "trivial".

The poker AI just saw the cards played by humans, and the human players only saw the cards played by the AI as well.
The rest is clearly not trivial, it took until 2017 to make an AI that can bluff properly.

Independent of the poker competition: There is software that can interpret human body language. The quality is not very convincing so far.

 

[Demystifier]

it took until 2017 to make an AI that can bluff properly.

Where can I see more details?

 

[mfb]

Libratus had the first consistent win against professional players, and it won with a significant margin.
I don't know if they wrote a paper about it.

 

[Auto-Didact]

Note, this is altogether different from what Penrose argues. He believes the brain and consciousness are products of physics. He disagrees with some others about which physics is involved (quantum entanglement).

I am arguing that brain and consciousness are part of physics as well, merely that our present-day understanding of physics is insufficient to describe consciousness. This is precisily what Penrose has argued for years

Spoiler

i.e. that standard QM is a provisional theory which will eventually be replaced by a more correct theory, i.e. a theory of not 'quantum gravity' but 'gravitized QM' where gravitationally induced wavefunction collapse (objective reduction, OR) due to unstable superposed spacetime curvutares, with mass functioning as the stability parameter in the bifurcation diagram. Moreover, he posits the full dynamical theory around this process will essentially contain non-computable aspects as well as a generalized Liouville theorem guaranteeing that information loss in black holes is exactly offset by information gain due to this non-computational gravitational OR process.

The functionalist argument on the other hand posits computers or AI of being capable of literally doing everything humans can do without utilizing the same physics that brains use, i.e. not only full substrate independence but also dynamics independence of consciousness. There is sufficient theoretical argument to doubt this and no experimental reason to believe that functionalism is true at all.

It seems to me that physicists who accept functionalism do not realize that they are essentially saying physics itself is completely secondary to computer science w.r.t. the description of Nature.

It does not matter. You keep arguing "but we cannot simulate it today" - that is not the point.

I'm not just arguing we cannot simulate it today, I am arguing we do not even have a proper theory today, i.e. it is not even clear whether or not it exists and what are the relevant properties. Positing that something can be understood in principle using some effective theory is useless if that something lacks a definite theoretical description, and it is doubly useless if unlimited computational resources are required as well.

It has been shown mathematically that classical motion is the quantum mechanical limit for small $\hbar$ - or "large" systems. But that is not the point. It can be studied.

Mere mathematical demonstration is not sufficient, only the experimental demonstration matters; this is why physics can be considered scientific at all.

It only produces new effective models. Which you don't need if you have unlimited computing power to simulate everything without effective models.

You are basically saying 'given enough computer power and the SM, the correct dynamical/mathematical theory of literally any currently known or unknown phenomenon whatsoever will automatically role out as well'. This is patently false if the initial conditions aren't taken into consideration as well, not even to mention the limitations due to chaos. The SM alone will certainly not uniquely simulate our planet nor the historical accidents leading to the formation of life and humanity.

It is a bit off-topic, but why do you think this is clear? To me, this is just the old "we must be special!" story. [...]

I am not arguing for some 'human specialness' in opposition to the Copernican principle. I am merely saying that human reasoning is not completely reducible to the same kind of (computational) logic which computers use, but it is instead qualitatively different in much the same way that performing flux pinning or the Meissner effect on superconductors is a completely different method of physically achieving 'suspension in the air' compared to a bird flapping its wings. Empirical observation and experimentation supports this position, even without a nice mathematically defined overarching theoretical framework.

 

[SSequence]

Well actually since the thread has derailed/expanded significantly, I would simply put a small part of my viewpoint.

Basically it all depends on abstraction that one takes. Among the below mentioned abstractions it is very clear which one I take to be correct, so I won't even mention it. This is after years of experience and development of mathematical sense.
So I won't justify it anymore except that I absolutely take it to be correct for a rational/idealised mathematical agent, whose initial training (possibly self-learned) and mathematical adeptness (and perhaps more importantly sense) has been developed beyond a certain point.

But basically if someone was inclined on taking the abstraction-2 (personal reasons, not having philosophical inclination etc.), I am more inclined to agree with mfb's viewpoint (as far as the functional part is concerned). Even though I don't necessarily take any side on this, it is true that people severely tend to underestimate what computer programs (as a whole collection -- which mfb was alluding to in one post) are able to do (at least "after" the "formalisation" stage). It only becomes more clear when one has tried quite a few examples (and much more clearer with more examples).
See post#51 (my previous post in this thread) as an example. Another example is that about four years ago, I tried a very large number of diagonalisation tricks (about a dozen perhaps -- I don't even remember most of them). And no matter how smart the trick was, there was always some sort of underlying explanation that foiled the trick. And it didn't matter what the trick was, or how difficult the explanation of why it didn't work was***, the key point was that it didn't work.

Though it is true that the process from pre-formalisation to formalisation (that is converting impules/responses from and to environment) is a complex one. Also there is an element of choices**** (such as card games etc.). It is bit beyond mathematics (and I am honestly much more interested in "post-formalisation" stage) so I leave it at that.

Here are the abstractions:
(1) Finite Memory Machine
This says the correct level of abstraction is a finite memory machine. Also (2) and (3) are incorrect.
(2) Computer Programs
The correct level of abstraction is a computer program. Also (3) is incorrect.
(3) Solver Level
The correct level of abstraction is being able to writing down notations for arbitrarily large elements of ω_CK.Note that in (3) nowhere (at all) the demand is made that program indexes corresponding to all notations have to be enumerated (let alone decided which is an even stronger condition). And while these are sound mathematical questions, obviously my opinion is that for the purposes of conceptual/mathematical understanding of problem (of a sentient mind) these are not the right questions.

Note that (as directly just by stating it) (3) doesn't violate the church's thesis at all (of course which the question(s) mentioned in above paragraph did directly).

But perhaps this is also a difference between logician and intuitionist mindset. A logician seemingly would insist on some notion of proof based upon some kind of axioms (I should add that this isn't an easy task). An intuitionist would insist that you should just be able to discern and understand patterns until there is no doubt whatsoever left (obviously real-world circumstances forcing to make an quick conclusions isn't the main point here -- the point is idealised circumstances).
There is a lot of similarity here with views of "later Godel" (which I read very recently) --- but perhaps there might be some differences too. His criticism of constructivism is also something I agree with.

In fact, it doesn't seem to me (as directly just by stating it) that with (3) you can't make a computer program fail the turing test (with infinite time that is) either. That's because a computer program could give you an absolutely horrible number (essentially "deceiving" so to speak) and claim that it is a notation for such and such element (which you might not be able to verify or refute in any clear way at all).
But I think perhaps it would be failed (but still not in a preconceived mechanised manner) with much more severe restrictions placed (the restrictions being forced to follow line of reasoning or patterns). But basically this isn't mathematical domain (the previous paragraph was more in-line with mathematical domain) --- well at least strictly speaking it seems.

Also, as a last but significantly important point, there is a very important difference between (3) and what was described in post#51 (my previous post). In post#51 you had to cross every threshold at the right time (and being "aware" of it). Here for example, you can create a demarcation within ω_CK (using program lengths for example). However, nowhere there is any condition that you have to be "aware" that a certain threshold has been crossed. The only condition is that it has to be eventually crossed.

*** In hindsight though, building a corresponding program would have been much more direct (and perhaps somewhat easier) than an explanation. But the explanation is usually somewhat more difficult (and also more illuminating).
**** Some would argue that this goes into domain of statistics perhaps? I don't know much about it.

 

[Buzz Bloom]

Hi @Auto-Didact:

Something seems to be missing from the problem statement. A chess position is given, but what is the statement of the problem? Also technically missing, but not particularly important in this case is: Whose move is it?

A glance tells me that no matter whose move it is, careful play leads to a draw by the 50 move rule, although I think that for some matches it has become a 75 move rule. Another observation is that with bad play either player can lose.

I gather that one purpose is to investigate how bad a computer chess program has to be before it loses, or what the human brain's neurological behavior differences are between a human who loses and a human who draws. I am not sure what useful insight if any might be learned from computer programs regarding this test. The article seems to be rather fuzzy about that. I gather since the article is very recent, there has been no actual test data collected yet.

Regards,
Buzz

 

[PAllen]

Hi @Auto-Didact:

Something seems to be missing from the problem statement. A chess position is given, but what is the statement of the problem? Also technically missing, but not particularly important in this case is: Whose move is it?

A glance tells me that no matter whose move it is, careful play leads to a draw by the 50 move rule, although I think that for some matches it has become a 75 move rule. Another observation is that with bad play either player can lose.

I gather that one purpose is to investigate how bad a computer chess program has to be before it loses, or what the human brain's neurological behavior differences are between a human who loses and a human who draws. I am not sure what useful insight if any might be learned from computer programs regarding this test. The article seems to be rather fuzzy about that. I gather since the article is very recent, there has been no actual test data collected yet.

Regards,
Buzz

Yes there is test data. An earlier post links to a chessbase article where this was tested on current progroms. An earlier post here describes a test using gnuchess. I posted the results of testing with a 15 year old chess program. All handle the position perfectly, including exlpoitation of errors by either side, despite the silly evaluation. In an earlier post I explained why this is so, and also that there are long known positions which much better show limitations in current chess programs. The core issue here is understanding fortresses. The better problem position has the feature that an immediate sacrifice has to be made to achieve a fortress eventually, while any other move eventually loses. All current chess programs fail this test. (while strong human players pass, without even calculating everything, just seeing that any alternative to sacrificing and aiming for a fortress is clearly hopeless) However, this is just a question of where programmers put their effort. Suggestions for how to generally handle fortresses go back twenty years; they just have not been implemented.

 

[Buzz Bloom]

It seems to me that physicists who accept functionalism do not realize that they are essentially saying physics itself is completely secondary to computer science w.r.t. the description of Nature.

Hi @Auto-Didact:

I do not understand this point of view. I understand functionalism to simply be taking into account "emergent phenomena", and hypothesizing that human consciousness may be such a phenomenon. Do you disagree with this?

Regards,
Buzz

 

[Buzz Bloom]

Yes there is test data.

Hi Paul:

What I don't get is what the chess program experiments are actually trying to discover, or what did they did discover. Can you summarize that?

Regards,
Buzz

 

[PAllen]

Hi Paul:

What I don't get is what the chess program experiments are actually trying to discover, or what did they did discover. Can you summarize that?

Regards,
Buzz

The tests show two things:

1) All programs tested give an avaluation that black is much better. This wrong, given that the position is drawn.
2) However, this has no impact on the computer's ability to play the position correctly, because wrong moves are correctly evaluated to worsen the position. The huge number of superfluous moves does not distract computers from finding this due to selective search heuristics being triggered by the forcing nature of the bad moves.

 

[Buzz Bloom]

Even without 50 move rule, draw must occur by 3 fold repetition eventually, if neither side blunders.

Hi Paul:

That might work reliably for computers, but I think for many reasonably competent human players, recognizing when a position has occurred three times might be difficult since even on the restricted fortress layout, the number of possible positions is rather large.

Regards,
Buzz

 

[Buzz Bloom]

1) All programs tested give an avaluation that black is much better. This wrong, given that the position is drawn.
2) However, this has no impact on the computer's ability to play the position correctly, because wrong moves are correctly evaluated to worsen the position. The huge number of superfluous moves does not distract computers from finding this due to selective search heuristics being triggered by the forcing nature of the bad moves.

Hi Paul:

This is sort of interesting, but how does that result relate to the purpose that Penrose had when he posed the problem?

Regards,
Buzz