A chess position to defeat computers? | Hacker News Reader

A chess position to defeat computers?

telegraph.co.uk

111 pointsbalsam127 comments

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

This is why I dislike most science reporters.

The article starts already with the "World prize". The reporter obviously didn't think or check anything before publishing.

Struck me as odd as well!

It should have said "Wolf Prize." Not vastly off (while being of course completely wrong.)

Won't someone please think of the poor cat. All alone in that box until we figure it out.

don't think about his cat and he won't be in the box

What cat? There is no cat

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

> you won't ever see ...

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.

> you won't ever see an autonomous vehicle winning a World Rally Championship

Never say never. These guys seem to be on the right track. https://www.youtube.com/watch?v=1AR2-OHCxsQ

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

[1] https://philtcs.wordpress.com/2011/10/06/class-4-the-p-vs-np...

Yes, most decent modern SAT solvers have no trouble with the pigeonhole problem.

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

No, it actually doesn't mean anything about far faster. It means the rate of increase is linearly related to the current value.

You touch on something interesting that I don't see often mentioned with NP-hard problems, and that's the actual inputs for where they're hard.

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.

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

https://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsac...

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

Interesting! I didn't know they were related. Thanks!

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.

Thanks for pointing out that those were bishops in the diagram. I found it difficult to parse the drawing for some reason.

There's a computer chess rendition of the position halfway down the article that's a lot easier to parse than the drawing...

I was looking for something like that, seems my browser didn't want to show it.

none of the black pieces except the bishops have any legal moves,

Why couldn't black move the topmost pawn forward?

Black is moving down the board.

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.

King is in way, only pieces black can move are bishops.

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.

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.

How does this account for the black pawns playing in the same rank?

To me it looks like a board transformation occurs, resulting in a left-to-right movement as opposed to a up-to-down movement.

Black abc pawns are in their original file.

d and e pawns captured pieces to get to a and b.

Two of the three remaining pawns promoted to a bishop.

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.

https://en.lichess.org/analysis/8/p7/kpn5/qrpPb3/rpP2b2/pP4Q...

here's a preceding position which stockfish completely fails to play correctly.

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.

doh, I meant Bd6*.

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.

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.

http://www.chessgames.com/perl/chessgame?gid=1497429

'The chess problem - originally drawn by Sir Roger - has been devised to defeat an artificially intelligent (AI) computer but be solvable for humans.'

I take issue with that statement. All chess engines I'm aware of will correctly play out the draw, so it doesn't defeat them. The engines will _evaluate_ a material advantage for black.

Frankly, this isn't really a surprise.

Incidentally I once won money on Betfair (a P2P betting site) by evaluating a position in a Kasparov vs computer game that looked like a win to computers for the computer, but that I knew Kasparov would prevail in. My fellow gamblers were trusting the computer evaluations :)

will a chess engine, as white, enter this position from any of the possible preceding positions?

Why does that matter?

https://en.lichess.org/analysis/8/p7/kpn5/qrpPb3/rpP2b2/pP4Q...

stockfish loses here, but could easily draw.

If anyone wants to play with this, here is the board in lichess: https://en.lichess.org/analysis/8/p7/kpP5/qrp1b3/rpP2b2/pP4b...

Constantly valuating at about -30...

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.

I played it out on lichess.org. After 47 moves, Stockfish sacrifices a bishop to keep the game going.

I was wondering if it would repeat that 47 moves later, but it didn't. Settled for the draw.

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.

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.

Technically, a stalemate is a draw and the 50 move rule is a different way to get a draw.

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.

[1] https://gameknot.com/help-answer.pl?question=44

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.

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.

Keep in mind, they are not looking for the answer to the chess question.

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.

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

Underpromotion is real thing and has its (very rare) uses. Even underpromoting to a bishop can turn a draw into a win:

https://en.wikipedia.org/wiki/Promotion_(chess)#Bishop_under...

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

Here's a position derived from the one shown in which stockfish plays white incorrectly.

https://en.lichess.org/analysis/8/p7/kpn5/qrpPb3/rpP2b2/pP4Q...

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.

This is a terrible puzzle. I'm glad I didn't rack my brain for hours looking for the "flash of insight" when all I had to do was be reminded of the 50 move rule.

The 50-move rule is a hack and the wrong way to think about it. What's really going on is "black can never force a win, therefore the position is drawn".

The draw is fairly easy but the author mentions a win. Any ideas?

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.

It's actually a shame, they failed to remove the obvious hint for this, which is the green x drawn on the hand drawn version of the puzzle.

Why would it need to move the king? As long as the bishops move, moving the pawn and turning into queen or bishop wins.

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.

Why not?

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

I remember coming home from the 1982 AAAI AI conference with my "AI, it is for real!" and thinking of how little skepticism about AI that I heard at the conference. Years later I bought Penrose's book "The Emperor's New Mind: Concerning Computers, Minds and The Laws of Physics" to 'know the enemy', but over the years I have started to agree more with Penrose's position on AI.

An important thing to consider is that this puzzle is designed by a human for humans.

The way we solve this problem is not by thinking in term of pure chess logic. We solve it by thinking "what did the puzzle creator thought". So we recall from memory what kind of patterns are suitable for such a problem and start a tree search. It is similar the what a chess AI does but nodes are abstract patterns rather than just chess moves.

This puzzle follows a mental pathway that is common for most humans. We could also design problems that can easily be solved by specific chess AIs but not by humans or other chess AIs : just make it so that the AI naturally moves in the right direction, for example by making specific heuristics always right.

So while this problem is interesting for getting insight into the way humans solve puzzles, it doesn't make the human brain special.

This is not a "hard" problem. It is just a problem you can't solve with brute force.

I think you just push the king around on white squares, hope all three bishops eventually blunder off the same diagonal (come on), and promote that c6 pawn to a queen. That's not a very satisfying "mate" solution but I don't see anything more clever.

Reading other comments, I see you'd also need to use the white king to guard the white pawn at c7 - I missed that - but even with that, you'd still need to hope that all three black bishops would go off that diagonal.

Anyway, this seemed mostly about visual pattern recognition and thinking geometrically, visualizing vectors, seeing unblocked pathways. That's not how computers do it.

There's sort of a silly argument as to how you could get mate. If a computer is playing black, it reads the board as greatly to its advantage. So when it's coming up on the 50-move draw, it might offer you a bishop to take to prolong the game. It has such a material advantage, a draw "feels like" a bad outcome, so it's worth giving up some material to continue the game and go for the win. Which is a very computer way of "thinking". Once you take all 3 bishops in this manner, you promote the pawn and get checkmate.

Once you take all 3 bishops it is a draw as black can't move any pieces.

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.

The heuristic would probably show black as ahead, but it would also show that black can make no progress. So it's an obvious draw.

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.

[1]: https://www.youtube.com/watch?v=-YX17fljs4E

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

If you actually play this state in a chess engine they play it "correctly", they just can't tell what the final outcome is going to be.

https://en.lichess.org/analysis/8/p7/kpn5/qrpPb3/rpP2b2/pP4Q...

All this might prove is that humans are less intelligent.

We are we wasting brain and heuristics solving problems that would never exist in real chess play? Seems like an inefficiency to me.

An artifact from our lack of ability to play chess as intelligently as machines.

Just like an inferior machine might be able to do something like burn outs because it doesn't have antilock braking. (I don't get cars insert real example here)

I'm more interested in how the board got this way.

https://en.wikipedia.org/wiki/Retrograde_analysis

White King goes to a8, only using white squares and b8. Black has to make the mistake to leave b8 unguarded for one move. Then white pawn to c7. Black King cannot b7 because of the white King on a8. Black bishop has to take the pawn, or pawn c8Q will be mate. Black bishop on c7 however is forced stale, since the white King cannot move.

As long as the King stays on white squares it will result in a draw in 30 moves... -shrugs- I think the computer could see this. It would revert to the rules that it knows. It would know +1, +2, +3.. and so forth moves down that it is growing closer to the draw line. It will wait for a pawn move from White. Without a pawn move... draw.

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?

You mean draw, not stalemate. A stalemate is one particular type of draw that has nothing to do with the 50 move rule.

I bet machines will have a hard time with Blathy's mate in 290 too.

https://www.chess.com/forum/view/more-puzzles/longest-checkm...

I can't tell which way the board is oriented? Where did white start?

In chess illustrations white is always at the bottom.

By convention, chess diagrams are presented with White's home rank on the bottom and Black's on the top.

I must be missing something... isn't it impossible for black to win no matter what white does with her king (as long as she doesn't move her pawn)?

That's the answer they're looking for. (White could still lose by making really bad moves, but so could black.)

I thought it would be more complicated than that, as they really play up the "puzzle" aspect of the article (even offering a prize!)

Assuming the bishops stay on their bottom-left to top-right diagonal, you could move the king to b1 and then

white b3xa4

black Qa4 (queen is forced because otherwise a4xb5 mate)

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.

Yes, not sure how I could overlook that pawns, just assumed them all blocked

Can white get a stalemate in 7 moves instead of 50 by just moving its king next to the black king? or is that not allowed?

No you can't move a king adjacent to another king. There must be at least a square between the kings for the move to be valid.

You can't check with the king.

I think the claim that this position would defeat a computer is nonsense. Any decent program would draw as white.

This chess position doesn't defeat computers. A decent engine will draw this every time. But the disparity in the efficiency of line of reasoning (a humans' being much more efficient than a computers for this problem) illustrates the value add of a programmer to a computer, and what the job of computer programming really is.

Computers basically know nothing--which is good and bad. It's good because they don't require much convincing before performing boring, repetitive tasks. They simply don't know or care that a given task is repetitive or boring, or even useful or not useful, so they will keep chugging along until they can return their output. The downside of this is that if they are to know anything at all, they must be programmed to know it.

They can also learn through evolutionary iterations once programmed conceptively. One could conceive of a computer program that would spit out random logical relationships to describe a large set of data, (what humans might refer to as "life experiences") and prune the logical statements until they eventually returned accurate logic describing the data. But this would require large quantities of generations for pruning, and careful programming of heuristics for logical evaluation at inception.

We can observe that our brains are born out of a system of evolution that has already undergone such processes. We have had a powerful survival heuristic on our genetic program for developing a broad set of skills, including logical reasoning, and it has been running for billions of years, pruning countless generations to give rise to our inherent level of intelligence that can discover logical shorcuts like the one in this problem. The evolutionary process also gives rise to possibly illogical but robust sets of skills, since survival and procreation are hueristically more valuable than being logically perfect in reasoning.

Sure, theoretically, and given sufficient computing resources and time, a man made computer system could approximately match and even exceed the human capacity for discovering logical shortcuts. But when paired with a competent human programmer, or team of programmers, the programmers can vastly reduce the time and resources required to achieve this process of intelligent evolution, and produce intelligent programs much more quickly than a computer program left to simply evolve it's intelligence on its own.

It took us humans quite a while to get here. Why would we assume that a computer could evolve faster than us, autonomously, without being programmed by us to do so? It is possible I suppose, but it's even more unlikely than the evolution of human intelligence, which sure, it happened autonomously, but over a course of billions of years.

Which 'decent engines' will draw this every time?

I'm just an amateur chess player. How does black have 3 bishops on the board?

Black promoted 2 of his pawns to bishops.

I must be pretty dumb because the solution to the problem isn't "obvious" at all, nor do I see how this proves quantum intelligence.

could this info, once cracked, simply be fed to the machine?

Obviously. The question is why can't the machine figure it out itself.

King to bishop 3.

so it's the halting problem? https://en.wikipedia.org/wiki/Halting_problem

How is this related to the halting problem? I'm not seeing it.

unless you catch 50 moves it's a runaway algorithm

The fact that a particular algorithm never halts is only tangentially related to the halting problem.

It's even possible to write non-halting algorithms in non-Turing-complete systems for which the Halting problem doesn't hold.

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.

Reply on news.ycombinator.com