On human and computer intelligence in chess (with solution!)
4/24/2017 – In March there was an international furore over a chess position, published by famous mathematics professor Sir Roger Penrose. It purported to show a key difference between human and computer thinking, and have general implications for our understanding of Artificial Intelligence. The example was unconvincing, but as a reaction a number of chess players and AI researchers have sent us papers we want to share with you. We start with a challenge to humans and machines issued by GM Miguel Illescas.
In March there was an international furore over a chess position, published by mathematics professor Sir Roger Penrose, who gained world-wide renown in 1988 by working out black hole singularities together with Stephen Hawking. The chess problem was devised to defeat an artificially intelligent (AI) computer but be solvable for humans: “We plugged it into Fritz, the standard practice computer for chess players, which did three-quarters of a billion calculations, 20 moves ahead," explained James Tagg Co-Founder and Director of the Penrose Institute. "It says that one side or the other wins. But," Tagg continued, "the answer that it gives is wrong."
We reported on the Penrose problem, and confirmed that chess engines give a very high evaluation in favour of Black, who has a huge material advantage. But the pieces are all constricted and cannot be used against the lone white king, supported by four pawns. Humans will recognize that it is trivially easy for White to hold the draw, but computers display a +25-30 pawn advantage for Black – while defending perfectly with white! Not the best example of the difference between human and machine thinking.
I described a similar situation that occurred in a well-publicized game between IM David Levy and the computer program CHESS 4.8 in 1979. Levy had a queen and the computer a c-pawn on the seventh rank. It thought it was completely lost but defended the position perfectly to a draw.
In the first article I gave an example of a more relevant position, one in which there is a theoretical draw that humans can find, but where computer will play the wrong move and actually lose:
Here the correct first move for White, who is at an overwhelming material disadvantage, is to sacrifice even more material. It is the only way to secure a draw: White must play 1.Ba4+!, and after 1...Kxa4 play b3+, c4+, d5+, e6+ and finally f5 to completely lock up the position. This is a much more relevant test, as chess engines, playing the white side, will actually select the wrong strategy and lose the game – while in the Penrose position computers think that White is losing, but hold the draw without any problem.
After the above articles appeared I received a number of very interesting emails, which I intend to share with our readers over the next few weeks. They have to do mainly with the fortress theme and the way it is handled by computers. Today I will start with a communication from Miguel Illescas, a top Spanish GM and trained computer scientist, who worked for the Deep Blue team that beat World Champion Garry Kasparov in 1997. Miguel wrote:
"Several years ago I shared with my colleague [from the Deep Blue team] Murray Campbell an idea to make the computer 'understand' a fortress, but nobody has done it so far (I think). It looks simple to me: if the evaluation of several best moves is exactly the same and it stays stable it means there is no win. If that is true it shows computer programmers are not interested to solve something which is so unlikely to happen – or they are simply lazy!"
The Illescas Challenge
Together with this message I received a challenge which I pass on to our readers:
You are invited to analyse the position here on our news page, or show it to your favourite chess engine (FEN: 1r6/1n1R1b2/8/1p1p3k/pPpPp1p1/2P1P3/P2K1PP1/8 w - - 0 1) and solve it with machine assistance. The solution and analysis will be added to this article in a few days – after which I will share the thoughts and ideas of other AI scientist on chess positions that are difficult for computers to comprehend.
Solution
[Event "Fortress study"] [Site "?"] [Date "2017.03.20"] [Round "?"] [White "Illescas, Miguel"] [Black "White to play and draw"] [Result "1/2-1/2"] [Annotator "Illescas,Miguel"] [SetUp "1"] [FEN "1r6/1n1R1b2/8/1p1p3k/pPpPp1p1/2P1P3/P2K1PP1/8 w - - 0 1"] [PlyCount "27"] [EventDate "2017.??.??"] 1. Rxb7 $3 (1. Rxf7 g3 $1 2. fxg3 Nd6 3. Rf6 Rd8 4. Ke2 Kg5 {with advantage for Black.}) 1... Rf8 $1 (1... Rxb7 2. g3 $1 Kg5 3. Ke2 Rb6 4. Kf1 Rh6 5. Kg2 { Draw.}) 2. g3 $1 Kg6 $1 3. Rb6+ $1 (3. Ke2 Rh8 4. Rxb5 Rh1 5. Ra5 Be8 $1 { with advantage for Black.}) 3... Kg7 4. Rh6 $3 Kxh6 5. Ke2 $1 Kg5 6. Kf1 $1 Rh8 7. Kg2 a3 8. Kg1 $1 Ra8 9. Kg2 Ra4 10. Kf1 $1 Be6 11. Ke1 Ra8 12. Kf1 $1 Bf7 13. Kg2 Ra4 14. Kf1 {Draw.} 1/2-1/2
[Event "Fortress study"] [Site "?"] [Date "2006.05.07"] [Round "?"] [White "Illescas, Miguel"] [Black "White to play and draw?"] [Result "*"] [Annotator "Illescas,Miguel"] [SetUp "1"] [FEN "1r6/1nR2bp1/7k/1p1p4/pPpPp1p1/P1P1P3/3K1PP1/8 w - - 0 1"] [PlyCount "4"] [SourceDate "2006.05.01"] {This was my original study in 2006. I first thought that} 1. Rxb7 $1 {makes a draw} (1. Rxf7 g3 $1) {but Black can play} 1... Rf8 $3 ({After} 1... Rxb7 2. g3 $1 Rb6 3. Ke2 Kg5 4. Kf1 Rh6 5. Kg2 $11 {[%csl Rf7,Rg5][%cal Rh6h1]}) {White still tries} 2. g3 $1 {but after} (2. Ke2 g3 $1) 2... Kg6 $1 {the black rook will reach h1 one day and White is definitely worst.} *
Feedback and mail to our news service
Please use this account if you want to contribute to or comment on our news page service
Thats pretty simple too
Pardon me Sagitta but perhaps you may be deviating from the point.
I think many humans will find this trivial and maybe amusing. As I understand it this is a test of whether a silicon based engine can solve it.
I think many humans will find this trivial and maybe amusing. As I understand it this is a test of whether a silicon based engine can solve it.
I believe:
1. Rxb7 Rxb7 (1... Rh8 2. Rxf7 Kg6 3. Rb7=) 2. g3 Rb8 3. Ke2 Kg6 4. Kf1 Rh8 5. Kg2 And Black no longer enter, fortress; Can not do anything with its material advantage. After the 1. Rxb7 move, Stockfish assigns a net advantage to Black (-9.0?). This is normal, fortresses are the last frontier of the engines.
1. Rxb7 Rxb7 (1... Rh8 2. Rxf7 Kg6 3. Rb7=) 2. g3 Rb8 3. Ke2 Kg6 4. Kf1 Rh8 5. Kg2 And Black no longer enter, fortress; Can not do anything with its material advantage. After the 1. Rxb7 move, Stockfish assigns a net advantage to Black (-9.0?). This is normal, fortresses are the last frontier of the engines.
> It looks simple to me: if the evaluation of several best moves is exactly the same and it stays stable it means there is no win. If that is
> true it shows computer programmers are not interested to solve something which is so unlikely to happen – or they are simply
> lazy!"
I cannot believe he is a trained computer scientist, because otherwise he wouldn't say such stupid things...
> true it shows computer programmers are not interested to solve something which is so unlikely to happen – or they are simply
> lazy!"
I cannot believe he is a trained computer scientist, because otherwise he wouldn't say such stupid things...
you forget that after 3. Ke2 a3! and black can try the idea Ra8-Ra4-Rxb4 idea to get a passed c pawn. Even then, the rught King moves can thwart this plan too.
Why is this considered so interesting by ChessBase? Most chess engines are programmed to play "real chess" well, not to solve artificial compositions that will never occur in real games. It's not like computers *cannot* solve these problems - it's just not worth the effort for the programmers to code these exceptional situations just to give more accurate evaluations in say 0.00001% of the chess positions.
It's like saying that since the best football player cannot play chess, "humans" cannot play chess. No: chess engines are simply not aimed at solving these weird fortress positions.
It's like saying that since the best football player cannot play chess, "humans" cannot play chess. No: chess engines are simply not aimed at solving these weird fortress positions.
@charlesthegreat - after 3... a3 then 4. Kf1 Ra8 5. Ke2 Ra4 6. Kf1 Rxb4 7. cxb4 c3 8. Ke2 c2 9. Kd2 = And Black has not solved anything.
Ai techniques tend to divide into 'neat' (logic-based) and 'scruffy' (emulating the way the human brain works). Chess was the first major problem to fall to AI, using 'neat' techniques. However, most subsequent breakthroughs in AI have used 'scruffy' techniques such as neural networks (Watson, Go, etc). The world-championship-beating Go program, for instance, did not look as far ahead even as a human amateur (since the board is too big for exhaustive search to be effective), but imitated the human player behaviors that paid off, based on millions of games.
So, I wonder if it might be useful to apply neural networks, or other 'scruffy' techniques, to chess?
So, I wonder if it might be useful to apply neural networks, or other 'scruffy' techniques, to chess?
In the Illescas problem, my stockfish iphone gives black -3.5 advantage in the initial position. In reality, however, white has a drawing line which gives him a fortress position. Starting with Rxd7 and if black recaptures with Rxd7, white can play g3 next to fix the position. After which, black can not use his two piece advantage to penetrate white's position. Black's bishop is useless, so is his King. He can try a3, then Ra8 to go to a4, then Rxb4. But the c pawn has nowhere to go as the white King can defend against this. So it should be a draw.
But the computer does not recognize this because it gives evaluations based on material advantage and due to certain limitations as to the depth of its calculations, it is possible that computers may miss the initial move Rxd7.
But the computer does not recognize this because it gives evaluations based on material advantage and due to certain limitations as to the depth of its calculations, it is possible that computers may miss the initial move Rxd7.
Sorry, my fault. The initial move is Rxb7, not Rxd7. The white king is already on d7.
Humanwise, the concept in the final puzzle is obvious in terms of what you need to do as white: sac on the knight, play g3, and then use the king to guard the h-file.
'Fortress' type endgames are far from uncommon these days, and the fact that engines sometimes handle them suboptimally is a genuine and non-trivial deficiency.
It's also worth looking at some games of Tigran Petrosian (1929-84) who would deliberately set up hyper-closed 'fortress' type formations in the middle-game, and then win by extremely long and convoluted sequences many moves long that would finally open the fortress to his advantage. I suspect that engines might not always predict the best defense against this type of strategy.
It's also worth looking at some games of Tigran Petrosian (1929-84) who would deliberately set up hyper-closed 'fortress' type formations in the middle-game, and then win by extremely long and convoluted sequences many moves long that would finally open the fortress to his advantage. I suspect that engines might not always predict the best defense against this type of strategy.
An efficient "solution" to this in AI would be trivial, not requiring the introduction of anything that isn't already in the AI literature. It would also likely not have any applications beyond chess (in fact, beyond this type of unusual position in chess). So in science parlance, the problem is "not worth addressing". Chess players and problem composers can have fun with it, though.
benedictralph - As to the AI solution being 'trivial' - if that is so, why not outline it here?
As to these idea having no practical application: the logic of 'fortresses' in chess closely resembles that of complex write-access resource-locking situations in relational databases (SQL Server, mySQL, Oracle etc): a very practical problem to which current solutions are definitely suboptimal.
As to these idea having no practical application: the logic of 'fortresses' in chess closely resembles that of complex write-access resource-locking situations in relational databases (SQL Server, mySQL, Oracle etc): a very practical problem to which current solutions are definitely suboptimal.
@WildKid: It's a relatively trivial matter in computing/AI to perform simple pattern recognition to detect 'fortress-like' positions in chess where average piece mobility is lower than would be expected given similar board density/clutter. The real reason we don't see this sort of thing coded into most engines is that it would probably consume an additional 1-5% of computing resources while addressing only 0.001% of positions. So it's a useful trade-off of sorts. As for application of this to relational databases, I highly doubt it as I just don't see the connection. Perhaps you'd like to illustrate clearly the link between a potentially novel method of solving fortress-like positions in chess and demonstrably improving relational database management.
By the way, you know what type of position would really demonstrate a "flaw" in chess engine design? A forced mate (e.g. 3-5 moves long) that a human could solve but a good engine couldn't. Or even one a human could solve more quickly. That's because computers are certainly coded to hell and back to find those.
benedictralph: the similarity is that the potential logic chains are very long and have many branches - too many to explore one by one. And simplistic 'pruning' will not be effective, since the correct solution will be beyond the pruning depth. There are constraints in both cases, that, if recognized, could prune the tree very drastically and make it computationally navigable, but a computer might have trouble finding the simplifying 'insight' ('this lock is the one that is causing the whole thing to seize up, so if I can find a way to release the locks prior to it, the whole chain will eventually release'), even thought to a human being it would be quite obvious.
bendictralph: one last comment: you say it's a relatively simple matter to detect fortress positions using piece mobility measures, and in principle I agree. In fact, I don't think such a measure would add measurably to execution time - we're talking a few hundred cycles of billions. The problem is not detecting a fortress setup, but DOING something about it - actually solving the problem that has been posed.
@WildKid: The "doing" something about fortress positions is the easy part. You just need a set of rules or principles to follow in such positions in order to solve them (the same things a human player would look for). These can be coded into heuristics easily, but they need to outweigh typical material considerations in precisely those positions. Basically a set of new heuristics and associated weights *after* such a position has been identified. The computational stress is in identifying them which means by default assuming every position is potentially a fortress and checking for it. It does add up in terms of cycles required.
Why do you think pruning the game tree is necessary regardless? It's a depth versus breadth search problem. There are no "clever" ways to get around this without creating even bigger loopholes. It's been studied to death in AI. Unless computers can become "creative" somehow, which means they can sometimes get from point A to E without having to systematically go through B, C and D. Now *that* would help with relational databases too but it's a much larger problem than the solution to fortress positions in chess. It's bordering on the P vs NP issue if not precisely that.
Why do you think pruning the game tree is necessary regardless? It's a depth versus breadth search problem. There are no "clever" ways to get around this without creating even bigger loopholes. It's been studied to death in AI. Unless computers can become "creative" somehow, which means they can sometimes get from point A to E without having to systematically go through B, C and D. Now *that* would help with relational databases too but it's a much larger problem than the solution to fortress positions in chess. It's bordering on the P vs NP issue if not precisely that.
bendictralph: You just need a set of rules or principles to follow in such positions in order to solve them (the same things a human player would look for)
You may think that's trivial - I don't. Any particular heuristic can obviously be coded, but to find a set of heuristics that would cover all, or the great majority of, cases is not, in my opinion. And the tree needs to be 'pruned because otherwise you are dealing with ((number of possible moves)**depth) alternatives, which will not work in 'fortress' positions. I think you're right that P equals? NP is probably lurking somewhere behind the question of whether this is generally solvable.
You may think that's trivial - I don't. Any particular heuristic can obviously be coded, but to find a set of heuristics that would cover all, or the great majority of, cases is not, in my opinion. And the tree needs to be 'pruned because otherwise you are dealing with ((number of possible moves)**depth) alternatives, which will not work in 'fortress' positions. I think you're right that P equals? NP is probably lurking somewhere behind the question of whether this is generally solvable.
Reminds me of the following endgame, where the powerful side which is blocked behind the wall can actually win - but how?
Paul Lamford, 1981
8/8/8/1k3p2/p1p1pPp1/PpPpP1Pp/1P1P3P/QNK2NRR
White to play and win
Paul Lamford, 1981
8/8/8/1k3p2/p1p1pPp1/PpPpP1Pp/1P1P3P/QNK2NRR
White to play and win
@Zvi Mendlowitz - Nice your position:
But is there a solution? Can the White Win? I could not find it.
At first time I thought had found the solution:
1. Kd1 Kc6 2. Ke1 Kb6 3. Rg2 Kc5 (3... hxg2? +#17) 4. Re2 Kd6 (4... dxe2? +#15) 5. Kf2 Kc7 6. Re1 Kc6 7. Rg1 Kb6 8. Rg2 Kc7 (8... hxg2? +#17) 9.Kg1 Kd7 10. Rd1 Ke7 11. Re2 Kd7 (11... dxe2? +#16) 12. Ree1 Kc6 13. Qa2 bxa2 14. b3 axb3 (14... cxb3 15. c4 a1=Q 16. Nc3+-) 15. a4 a1=Q 16. Na3 Qxa3 17. Ra1 Qb2 18. a5 +- 1-0.
But there is a refutation: But there is a refutation:(14... Kb5! 15. Rc1 a1=Q 16. b4 =)
But is there a solution? Can the White Win? I could not find it.
At first time I thought had found the solution:
1. Kd1 Kc6 2. Ke1 Kb6 3. Rg2 Kc5 (3... hxg2? +#17) 4. Re2 Kd6 (4... dxe2? +#15) 5. Kf2 Kc7 6. Re1 Kc6 7. Rg1 Kb6 8. Rg2 Kc7 (8... hxg2? +#17) 9.Kg1 Kd7 10. Rd1 Ke7 11. Re2 Kd7 (11... dxe2? +#16) 12. Ree1 Kc6 13. Qa2 bxa2 14. b3 axb3 (14... cxb3 15. c4 a1=Q 16. Nc3+-) 15. a4 a1=Q 16. Na3 Qxa3 17. Ra1 Qb2 18. a5 +- 1-0.
But there is a refutation: But there is a refutation:(14... Kb5! 15. Rc1 a1=Q 16. b4 =)
14...Kb5! instead of 14...axb3, and so all the my maneuver did not serve anything.
I think the Paul Lamford position (shared by Zvi Mendlowitz) shows the real problem.
It's easy to "heuristically" argue that such positions are drawn, and it's fun to mock computer programs (and programmers) for not applying such rules, but how does one know that the heuristics are accurate? Knowing that Illescas's position is a problem that is claimed to be drawn, I can easily convince myself that 1. Rxb7 Rxb7 2. g3 holds the fort. I can even try some simple winning ideas for Black, determine how White foils them, and convince myself that "of course" Black doesn't have a way through. But what if I've missed a line? What if Black has some clever tempo maneuver to break through? My claim that "I know it's clearly drawn" rings a bit hollow since I can't rigorously prove it. Of course, I happen to be right about that one (I assume), but for the Lamford position similar arguments would (apparently) lead me astray.
To put it another way, a human is likely to evaluate both positions (Illescas's and Lamford's) as drawn while a computer is likely to evaluate both positions as winning. Each is right half the time, but it's not clear which error should be considered more severe. IMO, since actual fortresses are likely far rarer than "pseudo-fortresses," the computer is probably erring in the right direction.
It's easy to "heuristically" argue that such positions are drawn, and it's fun to mock computer programs (and programmers) for not applying such rules, but how does one know that the heuristics are accurate? Knowing that Illescas's position is a problem that is claimed to be drawn, I can easily convince myself that 1. Rxb7 Rxb7 2. g3 holds the fort. I can even try some simple winning ideas for Black, determine how White foils them, and convince myself that "of course" Black doesn't have a way through. But what if I've missed a line? What if Black has some clever tempo maneuver to break through? My claim that "I know it's clearly drawn" rings a bit hollow since I can't rigorously prove it. Of course, I happen to be right about that one (I assume), but for the Lamford position similar arguments would (apparently) lead me astray.
To put it another way, a human is likely to evaluate both positions (Illescas's and Lamford's) as drawn while a computer is likely to evaluate both positions as winning. Each is right half the time, but it's not clear which error should be considered more severe. IMO, since actual fortresses are likely far rarer than "pseudo-fortresses," the computer is probably erring in the right direction.
albitex But is there a solution? Can the White Win? I could not find it.
At first time I thought had found the solution:
1. Kd1 Kc6 2. Ke1 Kb6 3. Rg2 Kc5 (3... hxg2? +#17) 4. Re2 Kd6 (4... dxe2? +#15) 5. Kf2 Kc7 6. Re1 Kc6 7. Rg1 Kb6 8. Rg2 Kc7 (8... hxg2? +#17) 9.Kg1 Kd7 10. Rd1 Ke7 11. Re2 Kd7 (11... dxe2? +#16) 12. Ree1 Kc6 13. Qa2 bxa2 14. b3 axb3 (14... cxb3 15. c4 a1=Q 16. Nc3+-) 15. a4 a1=Q 16. Na3 Qxa3 17. Ra1 Qb2 18. a5 +- 1-0.
But there is a refutation: But there is a refutation:(14... Kb5! 15. Rc1 a1=Q 16. b4 =) You had the right idea of sacrificing the queen on a2! but you needed to prepare it better. Move rooks to e1 and last rook to c2 when King is on d1 then you are ready for the Qa2! sac after moving Kc1. It is this position that fools computers that even the loose definition of a fortress that GM Illescas proposed will fail.
At first time I thought had found the solution:
1. Kd1 Kc6 2. Ke1 Kb6 3. Rg2 Kc5 (3... hxg2? +#17) 4. Re2 Kd6 (4... dxe2? +#15) 5. Kf2 Kc7 6. Re1 Kc6 7. Rg1 Kb6 8. Rg2 Kc7 (8... hxg2? +#17) 9.Kg1 Kd7 10. Rd1 Ke7 11. Re2 Kd7 (11... dxe2? +#16) 12. Ree1 Kc6 13. Qa2 bxa2 14. b3 axb3 (14... cxb3 15. c4 a1=Q 16. Nc3+-) 15. a4 a1=Q 16. Na3 Qxa3 17. Ra1 Qb2 18. a5 +- 1-0.
But there is a refutation: But there is a refutation:(14... Kb5! 15. Rc1 a1=Q 16. b4 =) You had the right idea of sacrificing the queen on a2! but you needed to prepare it better. Move rooks to e1 and last rook to c2 when King is on d1 then you are ready for the Qa2! sac after moving Kc1. It is this position that fools computers that even the loose definition of a fortress that GM Illescas proposed will fail.
@FiddleSticksNZ: It seems that the knights are completely immobile and useless. The general solution would probably be to get Black to capture the white queen with one of his pawns (or the queen captures the black pawn instead) and then to break open the position with a white pawn moving forward.
Chiron, the Italian champion engine, resolves instantly the Illescas position. Chiron 2 immediately finds himself, 1. Txb7 with proper draw evaluation.
Analysis by Chiron 2 64bit 8T:
1.Txb7 Txb7 2.g3 Rg6 3.Re2 Ag8 4.Rd2
= (0.00) Profondità: 6/10 00:00:00 1kN
1.Txb7 Txb7 2.g3 Rg6 3.Re2 Ag8 4.Rf1 Ah7 5.Re2 Ag8 6.Rf1 Ah7 7.Re2 Ag8
= (0.00) Profondità: 34/38 00:00:01 9511kN
…
1.Txb7 Txb7 2.g3 Rg6 3.Re2 Ag8 4.Rf1 Ah7 5.Re2 Ag8 6.Rf1 Ah7 7.Re2 Ag8
= (0.00) Profondità: 41/49 00:00:05 40192kN
…
1.Txb7 Txb7 2.g3 Rg6 3.Re2 Ag8 4.Rf1 Ah7 5.Re2 Ag8 6.Rf1 Ah7 7.Re2 Ag8
= (0.00) Profondità: 42/55 00:00:11 85901kN
…
Engines do not consider the 50 move rule?
1