The position nearly plays itself - none of the black pieces except the bishops have any legal moves, so if white moves his king around, without capturing anything, a draw will result by the 50 move rule (the bishops can't mate the king, since they won't control any light squares). For black, the play is even more automatic, since moving the bishops back and forth on the dark squares is the only legal option.
I do think that a computer will play this correctly for both black and white; for white, a capture will result in a checkmate within a few moves, which the computer will be able to see. So this may result in incorrect computer evaluation, but not in incorrect play.
Forward for black pawns is down, in a standard chess diagram; white's side of the board is at the bottom.
So black pawns have no legal moves, while the white pawns could move (the topmost pawn) or capture either of the black rooks, although this would be disastrous for white, as the black pieces would then be able to leave their position and would checkmate white in a few moves.
He cannot move his king out of its way first due to check from the white pawn if that is what you mean. The article makes it sound like a difficult problem with some super prize. I can't believe that a chess program can't figure out it doesn't have any meaningful moves left.
Agreed. An example where a human easily finds a win while a computer fails would be much more convincing of the point Penrose is trying to make.
Anyway this position reminds me of the fact that if there is any kind of situation where computers struggle it's exactly these kinds : where everything is closed apart from a few pieces. IIRC that was exploited by grandmaster Hikaru Nakamura few years ago for his handicap match against chess engine Komodo.
yes, but the question isn't if a computer will play correctly given the position, it's "will the computer force this position as white, if it's the best move?" which relies on it's evaluation of the position.
It's not really a position you can force from further away than one move, since it would require complete cooperation between the players to create such a position.
But yes, given a chance to get into this position, sure it will - e.g. given https://en.lichess.org/analysis/8/p7/kpP5/qrp1b3/rpP2b2/p5b1..., it will correctly play b3 and force the original position, since everything else results in a mate that it can see. All it needs for correct play is to rank the alternatives in the right order, and mate ranks below playing on with a material disadvantage.
Yeah, that's a great enhancement to the original - having the queen around lets the computer avoid mate for longer than its horizon, so it prefers keeping the queen. Then again, I am not sure the computer will lose in even this scenario - it has so many queen checks that my evaluation of this position after 10 minutes of playing with it is "screw it", although I feel there has to be some way of punishing it.
well you're playing against a computer that doesn't understand the position, black should simply disentangle his pieces, he can sacrifice almost everything he has and still win in this position, even if white is allowed to keep the queen. He can sacrifice a queen and a rook to this end, easily.
how I play the position as black is Ne7 followed by Bd6. if white plays Qh4, I can play nd4+ followed by nf5 and nd6, and my king is safe. and I can slowly, safely, extricate myself and win.
I am not sure I follow you - you can't have Be6 since your bishops are all on dark squares. Anyway, I am not that interested in this particular position - there are better examples of horizon effects and so on. There is a great collection here: http://timkr.home.xs4all.nl/chess2/honor.htm, although it's likely that the advancements in chess engines have obsoleted some of these positions since they were played.
There's the white win if black blunders. If white moves the forwardmost pawn ahead and black does not capture it with the bishop (the blunder), then promoting the pawn to a queen or bishop is checkmate.
The claim that computers cannot solve this problem is never really clarified. Which chess AI's exactly? That it involves Roger Penrose and claims about special abilities of the human brain only makes me more suspicious.
Okay, here's my answer: all of black's pieces are blocked except for the bishops. The black king can't move without being checked by a pawn. All the black bishops are on black squares (meaning two must be promoted pawns -- unlikely but possible)
So the white king just needs to stay on a white square to stay safe.
The so-called "aha!" moment was remembering that bishops always stay on the same color. I can't claim any great insight, it's just something I read somewhere (so it could certainly be programmed into a computer).
I had to check that there was no way for the other pieces to escape. I'm not good at chess, so I just did a very quick check and then assumed it was probably fine -- given the nature of the puzzle it's unlikely there'd be a tricky edge case to cover there.
The thesis seems to be that a computer could never develop and use general theorems that let you short-circuit the search process. That's probably true for chess engines (and also mostly irrelevant to real chess matches, rather than puzzles). Definitely an interesting question to explore. My guess would be that real computer creativity is possible, but may require some new techniques.
> All the black bishops are on black squares (meaning two must be promoted pawns -- unlikely but possible)
Is this possible outside the context of purposely making bad moves to humiliate your opponent? I thought you got to choose whatever officer you wanted, which would mean bishops are strictly dominated by queens.
It kinda sucks that they changed to rule to require you to promote a pawn to a piece of your own color. The mate-in-1 puzzle on that promotion page that requires promoting a pawn to an opponent's knight is pretty neat and I can't see that rule having a practical impact on any real chess game.
I think the surfeit of bishopric is a hint that they are irrelevant >cough< - most people immediately see that the pawn promoted to queen gives white the win, a sort of 'don't even think about it' and that the likely solution is for white king to run forcing a draw. Black can only move the bishops back and forth. A dull end to what have must been a very strange game.
>The so-called "aha!" moment was remembering that bishops always stay on the same color. I can't claim any great insight, it's just something I read somewhere (so it could certainly be programmed into a computer).
Yes and no. You can easily encode any specific heuristic into a computer. And brute force (add more hardware) can ensure you hit a lot of the heuristics.
But the hard part is ensuring that your search of heuristics is intelligent, and only needs to do a small number of steps before it hits a good one; in your case, what caused the "same square" heuristic to reach the top of your mind so quickly? That's what we want to reproduce.
(To be sure, the "bishops stay on same squares" heuristic is simple, but once you have a lot of heuristcs/theorems to build off of, it's just one fish in a very big sea, so you need a scalable, general approach.)
No chess problem on a standard board can be the halting problem, because the halting problem requires an "infinite space". I could, in principle, play out all possible states you could reach from this position as a giant graph, and then look to see which path is best by brute force.
There are chess-like problems which invoke the halting problem, but they involve infinite boards with infinite numbers of pieces on them.
> The institute is also hoping to develop new technology to improve the treatment of brain disease and anesthetics, develop a new type of telescope to detect dark matter and even resolve the Schrodinger’s Cat paradox, which suggests a cat in a box could be alive and dead at the same time.
White cannot force a win. However, if it manages to move the king to D7, and the black bishops leave the B8-H2 diagonal (a huge blunder), then white can move its pawn to C7, and checkmate in the next move, by crowning the pawn into a queen.
Once the pawn moves to C7, black's king can play to B7. If white's king were not defending, black would be able to capture the promoted pawn in the next move.
But while a chess engine apparently can't see the draw as long as there is a possible helpmate on the board, it can see the danger of leaving the diagonal so will never play this.
Once you're on D7 the pawn can be captured or kept. If black moves to capture the pawn with a bishop, you move the king into pawn's old spot. You capture the black rook with the other pawn for the win.
If there are no more bishops on the diagonal, or if they move their king to the B column, then you get a Queen and finish them off.
> If black moves to capture the pawn with a bishop, you move the king into pawn's old spot. You capture the black rook with the other pawn for the win.
If you capture the black rook, black will capture your pawn with the queen (and proceed to mate you now that their queen can move).
They say black has to make a mistake for it to happen. So I'm guessing white promotes its pawn to a queen, after moving the king to a position where it can defend the new queen.
The mistake black makes is trying to get its king out of the morass as soon as the pawn moves, instead of just capturing the pawn with its bishops.
Rybka v Nakamura is this sort of anti-computer strategy where the computer clearly doesn't understand the position. 270 moves of Naka calmly moving back and forth behind a blockade, the exchange down. Rybka eventually tries to do something since it's up on material. And then it just gets slaughtered.
The claim here isn't that computers couldn't solve this, just that they currently don't. In general, computers and humans play the beginning and ending of chess games with some strong heuristics -- there are too many possible moves to enumerate, but there's a very limited number of worthwhile moves to consider.
In this puzzle, we have an extremely weird end-game. Humans can come up with a new heuristic on the fly, but current chess programs find all their existing heuristics fail and have to resort to brute-force search or really dumb heuristics and neither is helpful.
Obviously, it would be a matter of minutes to code up a new heuristic to detect this case. The interested question is what the humans are doing that lets us solve the problem so rapidly.
It might be possible (I haven't checked thoroughly) to draw a parallel: "Humans can come up with a new heuristic on the fly" for this chess problem <=> "Identify the incomplete part of this system -- in the sense of Gödel's incompleteness theorem".
So it might just be that humans process the game at a semantic level where we have developed the semantic tokens that can express the incompleteness, and from that produce a hypothesis, a heuristic.
Computers do not, generally, apply semantic reasoning to problem solving. At least, not yet. :)
The interested question is what the humans are doing that lets us solve the problem so rapidly.
The need for strategy is eliminated with tactically perfect play... Since computers are not yet to the point of having "solved" chess to tactical perfection, there will always be scenarios where strategy wins.
IMO this is the maximum win for human-machine interaction... humans define the strategy, and computers aid in the tactical execution of that strategy. I'm not really a big believer that AI is anywhere close to beating humans at being human, especially when you step outside the bounds of a simplistic game with a narrowed rule-set.
Like with cars and planes, you won't ever see an autonomous vehicle winning a World Rally Championship, and you won't ever see a computer figuring out how to make a Hudson river emergency landing. But computers can greatly assist with the braking, shifting, adjusting flaps, engine management, etc...
People have said that about mostly everything computers now do and is taken for granted. I won't be having discussions with my computer any time soon (before I die) but winning that rally doesn't seem 30-50 years out.
> you won't ever see an autonomous vehicle winning a World Rally Championship
Autonomous vehicles will surpass human rally teams. I've competed in rally here in the US.
The vision problems involved are difficult but don't underestimate how much humans struggle with sun and dust as well. With everything else the computer has the advantage.
WRC as an org may not ever run an autonomous class, but I would expect to see a robo rally event of some sort to show up, perhaps first as a spectacle at Pikes Peak or Isle of Man.
The example in the article isn't strategic, it's tactical. White cannot reach a losing position if he doesn't move his pawns, I don't have to invoke any wishy washy reasoning to claim that.
Scott Aaronson (himself a harsh Penrose critic on these matters!) had made this point several years ago, but in the context of 3SAT (an NP-complete problem). His "human favoring instance" was a 3SAT problem that encodes a violation of the pigeonhole principle.
Then [1], as now, I think that was still too generous to humans -- both Penrose and Aaronson have spent so much time around smart people that they've forgotten what the average person is like. The average person isn't clever enough, especially when even 4 pigeon/3 hole instances blow up to an absurd number of clauses.
Either way, I think the scaling problem rears its head:
- Only an exponentially small fraction of problems is pathological like this.
- Only an exponentially small fraction of humans can derive these theorems on the fly that simplify the problem.
- You can get everyone can solve it, but only by providing an exponentially precise hint. (The "good heuristic oracle" in the linked thread.)
Plus, I suspect there are general heuristics that avoid much of these "dumb" searches, for example if you represent the problem in a graph and check its symmetries to avoid loops of "hm, but what if I put pigeons 2, 3, and 4 in the holes... blast, that doesn't work either."
Nit: "exponentially" does not mean "really", as in "really small". It means increasing (or decreasing) at a far faster rate than what it's exponential with. Often time, but any metric can be used.
That ("has exp(n) scaling with respect to input size") is how I was using it, and that usage is a critical part of my point, that the involvement of humans does not change the problem's difficulty class.
If you have a reason to think that it is not literally exponential, I'd love to discuss that! (I have good reasons to believe this is the actual behavior on the first and third effects but not necessarily the second.)
>Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial.
Interestingly, that's the basis of the (now broken) Knapsack cryptosystem -- your private key is an easy knapsack, and you convert it to the public key -- a hard knapsack -- via modular multiplication. You encode your message by your choice of which items from the hard knapsack to add to the sum, which becomes the ciphertext.
Have you checked out lattice based crypto? It's the spiritual successor to merkel-hellman, based on the hardness of subset sum. I've got a rough presentation from when I talked about it at a reading group: https://docs.google.com/presentation/d/1_kLJ7M_7HKrzN0auz0-z...
That would lose - it would not be a stalemate, no matter where the bishops are, since white has pawn moves; and starting with the next move, black would begin checking white and will quickly checkmate.
I don't play chess regularly but the stalemate was obvious to me immediately and the mate after about 3 minutes. Kinda clever but I'd be surprised if a chess AI couldn't see this. Penrose is notorious for thinking that consciousness depends on some spooky quantum effects that machines cannot capture (See Emperor's New Mind).
Isn't it already a stalemate? As long as the king never leaves white squares, he will never be in danger, and thus the game will be a draw by the 50 move rule.
I don't see how mate is possible. In order to mate, you need to advance the white pawn to promotion, but it's impossible to advance the white pawn without one of the 3 bishops killing it.
His rules seem to require only that the move was legally possible, not necessarily likely. Maybe after moving around the board for a while, the bishops aren't readily able to strike at the pawn.
Black can offer his bishops to the white king for free, in order to delay the draw (it's 50 moves without pawn moves and without captures [1]). However, if black offers all 3 bishops, then white could help promote the pawn.
That's not what stalemate means. Stalemate means the current player has no legal moves but isn't in checkmate. White has legal moves. It's a drawn position with good play by both sides but not a stalemate.
To emphasise this point, he believes that consciousness is provided by a non-physical unmeasurable substance that has some kind of complex structure, in order to contain the complex consciousness. Could you build a human molecule by molecule to match another that was naturally born, then it wouldn't be conscious as you wouldn't have the means to build a consciousness to go with it.
Once I'd got this far with the book, I put it down.
Interesting, it took me reading the comments to realize the board orientation vs the piece movement. Like many people the fact that the black bishops are basically unable to attack anything stands out, and given the orientation that none of blacks other pieces can move. Once you see those two things, the solution does just pop out.
Can anyone with a chess engine handy confirm the claims in the article and explain what your engine is trying to do? I wouldn't be surprised if at least some engines have some kind of conservative heuristics built in, like "If I can't find something good after x cycles, let's play something safe." and "If the opponent isn't gaining any ground after several turns of me buying time, it is likely going to be a draw even though I don't know why."
Crazy enough, every chess player in the world can see immediately it's a draw from the very beginning, unless white concedes a helpmate, yet stockfish doesn't get it...
True, but the engine does see that a pawn move by white results in checkmate in a few moves, so it would actually play this position correctly and get a draw, despite the huge negative evaluation.
This reminds me somewhat of an interesting recent video from GM Simon Williams [1], analyzing a queen sac from a real game. He disagreed with the computer's favoring black, and my very uneducated guess about this is that the position is odd enough -- white is down a queen and an exchange, but all of black's pieces are tied up in defense -- that a GM can better understand the implications.
This just seems like an odd edge case on the 50 move stalemate rule, because it's such an unusual thing to shoot for to achieve a draw that a chess program doesn't normally bother to look for it.
Doesn't seem that useful a demonstration, except for people who don't know much about computers. Is this a bit like Hawking on AI?
I have a hard time believing that a chess computer wouldn't draw this game… the main issue is in the centipawn evaluation function which would show black ahead. This doesn't seem like a difficult thing to correct, and it might not even be a bad idea to have an evaluation function show black ahead in that position.
Practically, this isn't really an issue. In fact, running the position through the GarboChess JS engine (http://analysis.cpuchess.com), playing as white, it just moves the king around — exactly what a human would do to draw the game.
134 comments
[ 3.0 ms ] story [ 219 ms ] threadI do think that a computer will play this correctly for both black and white; for white, a capture will result in a checkmate within a few moves, which the computer will be able to see. So this may result in incorrect computer evaluation, but not in incorrect play.
Why couldn't black move the topmost pawn forward?
So black pawns have no legal moves, while the white pawns could move (the topmost pawn) or capture either of the black rooks, although this would be disastrous for white, as the black pieces would then be able to leave their position and would checkmate white in a few moves.
The orientation of board is white started on bottom and black on top.
Quick thing to also remember is that the bottom right square should always be white.
To me it looks like a board transformation occurs, resulting in a left-to-right movement as opposed to a up-to-down movement.
d and e pawns captured pieces to get to a and b.
Two of the three remaining pawns promoted to a bishop.
Anyway this position reminds me of the fact that if there is any kind of situation where computers struggle it's exactly these kinds : where everything is closed apart from a few pieces. IIRC that was exploited by grandmaster Hikaru Nakamura few years ago for his handicap match against chess engine Komodo.
But yes, given a chance to get into this position, sure it will - e.g. given https://en.lichess.org/analysis/8/p7/kpP5/qrp1b3/rpP2b2/p5b1..., it will correctly play b3 and force the original position, since everything else results in a mate that it can see. All it needs for correct play is to rank the alternatives in the right order, and mate ranks below playing on with a material disadvantage.
here's a preceding position which stockfish completely fails to play correctly.
how I play the position as black is Ne7 followed by Bd6. if white plays Qh4, I can play nd4+ followed by nf5 and nd6, and my king is safe. and I can slowly, safely, extricate myself and win.
So the white king just needs to stay on a white square to stay safe.
The so-called "aha!" moment was remembering that bishops always stay on the same color. I can't claim any great insight, it's just something I read somewhere (so it could certainly be programmed into a computer).
I had to check that there was no way for the other pieces to escape. I'm not good at chess, so I just did a very quick check and then assumed it was probably fine -- given the nature of the puzzle it's unlikely there'd be a tricky edge case to cover there.
The thesis seems to be that a computer could never develop and use general theorems that let you short-circuit the search process. That's probably true for chess engines (and also mostly irrelevant to real chess matches, rather than puzzles). Definitely an interesting question to explore. My guess would be that real computer creativity is possible, but may require some new techniques.
They are trying to understand what it is about humans that makes them instantly able to figure out how to figure out the answer.
Humans can learn, computer can't. They can train on data, but so far none can teach themself how to train.
Is this possible outside the context of purposely making bad moves to humiliate your opponent? I thought you got to choose whatever officer you wanted, which would mean bishops are strictly dominated by queens.
https://en.wikipedia.org/wiki/Promotion_(chess)#Bishop_under...
Yes and no. You can easily encode any specific heuristic into a computer. And brute force (add more hardware) can ensure you hit a lot of the heuristics.
But the hard part is ensuring that your search of heuristics is intelligent, and only needs to do a small number of steps before it hits a good one; in your case, what caused the "same square" heuristic to reach the top of your mind so quickly? That's what we want to reproduce.
(To be sure, the "bishops stay on same squares" heuristic is simple, but once you have a lot of heuristcs/theorems to build off of, it's just one fish in a very big sea, so you need a scalable, general approach.)
It's even possible to write non-halting algorithms in non-Turing-complete systems for which the Halting problem doesn't hold.
There are chess-like problems which invoke the halting problem, but they involve infinite boards with infinite numbers of pieces on them.
This is why I dislike most science reporters.
Once you're on D7 the pawn can be captured or kept. If black moves to capture the pawn with a bishop, you move the king into pawn's old spot. You capture the black rook with the other pawn for the win.
If there are no more bishops on the diagonal, or if they move their king to the B column, then you get a Queen and finish them off.
Am I missing something (I'm a very bad player)?
If you capture the black rook, black will capture your pawn with the queen (and proceed to mate you now that their queen can move).
The mistake black makes is trying to get its king out of the morass as soon as the pawn moves, instead of just capturing the pawn with its bishops.
http://www.chessgames.com/perl/chessgame?gid=1497429
In this puzzle, we have an extremely weird end-game. Humans can come up with a new heuristic on the fly, but current chess programs find all their existing heuristics fail and have to resort to brute-force search or really dumb heuristics and neither is helpful.
Obviously, it would be a matter of minutes to code up a new heuristic to detect this case. The interested question is what the humans are doing that lets us solve the problem so rapidly.
So it might just be that humans process the game at a semantic level where we have developed the semantic tokens that can express the incompleteness, and from that produce a hypothesis, a heuristic.
Computers do not, generally, apply semantic reasoning to problem solving. At least, not yet. :)
The need for strategy is eliminated with tactically perfect play... Since computers are not yet to the point of having "solved" chess to tactical perfection, there will always be scenarios where strategy wins.
IMO this is the maximum win for human-machine interaction... humans define the strategy, and computers aid in the tactical execution of that strategy. I'm not really a big believer that AI is anywhere close to beating humans at being human, especially when you step outside the bounds of a simplistic game with a narrowed rule-set.
Like with cars and planes, you won't ever see an autonomous vehicle winning a World Rally Championship, and you won't ever see a computer figuring out how to make a Hudson river emergency landing. But computers can greatly assist with the braking, shifting, adjusting flaps, engine management, etc...
People have said that about mostly everything computers now do and is taken for granted. I won't be having discussions with my computer any time soon (before I die) but winning that rally doesn't seem 30-50 years out.
Autonomous vehicles will surpass human rally teams. I've competed in rally here in the US.
The vision problems involved are difficult but don't underestimate how much humans struggle with sun and dust as well. With everything else the computer has the advantage.
WRC as an org may not ever run an autonomous class, but I would expect to see a robo rally event of some sort to show up, perhaps first as a spectacle at Pikes Peak or Isle of Man.
Never say never. These guys seem to be on the right track. https://www.youtube.com/watch?v=1AR2-OHCxsQ
Then [1], as now, I think that was still too generous to humans -- both Penrose and Aaronson have spent so much time around smart people that they've forgotten what the average person is like. The average person isn't clever enough, especially when even 4 pigeon/3 hole instances blow up to an absurd number of clauses.
Either way, I think the scaling problem rears its head:
- Only an exponentially small fraction of problems is pathological like this.
- Only an exponentially small fraction of humans can derive these theorems on the fly that simplify the problem.
- You can get everyone can solve it, but only by providing an exponentially precise hint. (The "good heuristic oracle" in the linked thread.)
Plus, I suspect there are general heuristics that avoid much of these "dumb" searches, for example if you represent the problem in a graph and check its symmetries to avoid loops of "hm, but what if I put pigeons 2, 3, and 4 in the holes... blast, that doesn't work either."
[1] https://philtcs.wordpress.com/2011/10/06/class-4-the-p-vs-np...
If you have a reason to think that it is not literally exponential, I'd love to discuss that! (I have good reasons to believe this is the actual behavior on the first and third effects but not necessarily the second.)
Packing a knapsack with many small items or items large relative to the knapsack make it relatively trivial.
It's often the case that NP real world problems actually have their inputs fall in the easier to solve ranges.
Interestingly, that's the basis of the (now broken) Knapsack cryptosystem -- your private key is an easy knapsack, and you convert it to the public key -- a hard knapsack -- via modular multiplication. You encode your message by your choice of which items from the hard knapsack to add to the sum, which becomes the ciphertext.
https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...
white b3xa4
black Qa4 (queen is forced because otherwise a4xb5 mate)
I don't see how mate is possible. In order to mate, you need to advance the white pawn to promotion, but it's impossible to advance the white pawn without one of the 3 bishops killing it.
[1] https://gameknot.com/help-answer.pl?question=44
Once I'd got this far with the book, I put it down.
Crazy enough, every chess player in the world can see immediately it's a draw from the very beginning, unless white concedes a helpmate, yet stockfish doesn't get it...
I was wondering if it would repeat that 47 moves later, but it didn't. Settled for the draw.
[1]: https://www.youtube.com/watch?v=-YX17fljs4E
Doesn't seem that useful a demonstration, except for people who don't know much about computers. Is this a bit like Hawking on AI?
Practically, this isn't really an issue. In fact, running the position through the GarboChess JS engine (http://analysis.cpuchess.com), playing as white, it just moves the king around — exactly what a human would do to draw the game.