Basically, computers could do the things that we humans think when we do. It turned out that chess, the old holy grail of AI, could pretty much be reduced to plain calculation, like "I go bam, you go wham, I go swoosh..." and so on. The asian board game of Go on the other hand seemed to be much more about that mysterious intuition and didn't easily yield to "good old" programming techniques.
Then came deep learning. And now it's pretty much the opposite. Computers are now good at the things we do without thinking. As Andrew Ng puts it around 4.45 into this video, a useful rule of thumb is that anything a typical person can do in one second can now be automated. Like recognizing whether or not a picture is of a bird.
The comic 1425 from xkcd (Randall Munroe) illustrates what has happened.
What I now find fascinating about this comic is that it was published in 2014, and the character Ponytail thinks she only needs five years, not that it's impossible. Somehow Randall Munroe seems to have known what was going on, even though many people in AI have testified that they didn't see it coming.
Using deep learning, the program AlphaGo from Deep Mind clearly defeated the best human Go players, and in December last year, the new version AlphaZero shocked the world of chess and AI by beating Stockfish, a state-of-the-art chess program way beyond human level, by a clear margin in a match of 100 games.
So the new situation is that computers are good at everything that just requires following a simple recipe, like multiplying thousand-digit numbers, and everything that just takes instinct and learning from examples, like recognizing what's in a photo or whether a position in a board game looks generally promising.
But there are still purely intellectual tasks where the human mind rules, and where software isn't of much help.
One thing that (surprisingly?) hasn't been automated yet is research in mathematics. In this talk from a few years ago, Tim Gowers discusses the problem of getting a computer to discover mathematical ideas, and I think everything he says is still relevant. Even though computers outperform us in arithmetic, it has turned out to be extremely difficult to get software to explore and answer questions of the type "Does there exist a number with the property that ... ?". Reasoning about a generic number called $n$ is different than handling a particular one like 756767765776.
The situation is similar in the realm of board games. Stockfish and AlphaZero are mindbogglingly strong when it comes to the basic problem of choosing a move in a typical position. But if we start asking questions of the type "Does there exist a position with the following property ... ", they can't give us the answer. That's a type of question that belongs on a different level.
There has been quite some discussion about chess positions that supposedly baffle the best software. A few years ago the physicist Roger Penrose claimed that a certain chess problem holds the key to human consciousness. But I guess a neural network in combination with Monte Carlo tree search (what AlphaZero does) will solve such problems in the near future, at least if they can train the neural network during the game (to tune it to the position at hand).
Whether or not they do, there is an old and well-established domain of chess dealing with constructing positions with extraordinary properties, and so far there is no software that can challenge the human mind in that area. So in any case it's not true that computers beat humans in all aspects of chess.
The traditional form of a chess problem is "Mate in $n$" (again $n$ is a generic number!), which means that White makes the first move, and forces a checkmate in at most the stipulated number of moves, against every possible defence by Black. There is software for solving such problems, but now we're talking about the construction of chess problems. This is a form of art where the composer (yes, that's what it's called!) tries to present a chess position where the optimal play has some remarkable and surprising properties.
Sometimes this develops into a sort of contest, where problem composers challenge each other to come up with chess positions with certain stipulated properties (not unlike research!). One of their favorite topics is so-called underpromotion, meaning promotion of a pawn to a piece other than queen.
It is easy to think of a situation where it's better to promote to a knight than to a queen, since the knight can move in ways that the queen can't. But there also exist situations where it's better to promote to a rook or a bishop, even though it seems that a queen can do anything that those pieces can. These situations all have to do with the rule of stalemate, according to which the game is drawn if a player doesn't have any legal moves. Since it's not legal to put one's king en prise, it's sometimes better to have a weaker piece than a stronger one, either because you want to get stalemated, or to avoid stalemating your opponent.
For decades, a seemingly impossible challenge was the Babson task: Composing a problem where after White's initial move, Black can promote a pawn, and where in White's second move, the only solution is for White to promote one of their pawns to the same piece as the one Black chose!
Several expert composers tried in vain to find such a position, and Pierre Drumare (who sort of solved the task in 1980 but with an illegal position) declared after twenty years that he didn't think such a position could exist. To begin to appreciate the difficulty, notice that (as I actually mentioned in one of my very first blog posts!) the defensive underpromotion to rook or bishop (in order to try to get stalemated) requires such special circumstances that in all of chess history, with databases of millions of games and libraries full of books, there is not a single known case of this happening in a real game. Even the offensive underpromotion (avoiding to stalemate one's opponent) is extremely rare, especially the promotion to bishop.
And the Babson task requires these promotions to work and to be necessary, simultaneously from the same position.
The task was first successfully achieved by Leonid Yarosh in 1983 (comment to establish that I was a nerd before it was cool: I knew about the Babson task before it was solved, in the days when this problem by Bo Lindgren was the best that had been achieved!), and in the following years a number of other Babson problems were composed by Yarosh, Drumare and others. Among them was the following particularly beautiful one, by some connoisseurs regarded as the most remarkable position ever set up on a chess board:
Karlheinz Bachmann, Peter Hoffmann and Martin Hoffmann, Die Schwalbe 1987.
Mate in 4.
White starts with the "key" 1. hxg7! Normally an initial capture is frowned upon in the problem world, but this key is thematic and opens up a flight square for the black king, so it's nice anyway.
If the black king takes back on g7, White will checkmate with 2. Ng5, 3. Rg8, and 4. Rg6 no matter what Black does. If Black promotes the d-pawn in move 2 (in any of the 12 possible ways!), then 3. Rg8 will be check, so Black doesn't have time for any counterplay.
If the black king takes back on g7, White will checkmate with 2. Ng5, 3. Rg8, and 4. Rg6 no matter what Black does. If Black promotes the d-pawn in move 2 (in any of the 12 possible ways!), then 3. Rg8 will be check, so Black doesn't have time for any counterplay.
Given that Black cannot move the king in move 1, White's main threat is 2. g8Q and 3. Qg6 mate. Promoting on c1 or e1 can delay this plan by at most one move, so the question is whether a black promotion on d1 can throw a spanner into White's works.
After 1. .. d1Q, 2. g8Q, Black can try to delay the checkmate with 2. .. Qxd4+. Now White cannot capture the queen because of stalemate, but instead White blocks the check with 3. c4!, at the same time pinning the black queen and checkmating in time.
But Black can be clever and instead promote to a rook! Then after 1. .. d1R, 2. g8Q Rxd4+, blocking with 3. c4 or taking the rook will be stalemate, and everything else allows Black to give one more check. To counter the stalemate idea, White too promotes to a rook so that after 1. .. d1R, 2. g8R! Rxd4+, 3. c4! (also perfectly blocking the bishop's diagonal!), there is 3. .. Kxf7 and 4. Rdf8 mate.
Black has yet another stalemate trap, the "self-paralysis" 1. .. d1B! after which the solution is 2. g8B!, allowing 2. .. Kg7. Since the black king is now confined to the long diagonal, White checkmates with 3. c4 and 4. d5.
Black's last trick is 1. .. d1N, which threatens to give not only one but two consecutive checks on the white king. White prevents this by being the first to give check: 2. g8N+! Kg7, 3. f6+ Kh7/g6, and 4. Qxc2 mate!
In each case, White's echoing of the Black promotion is the only solution. For instance, in the queen variation White actually needs a piece that moves in all directions. And looking at the knight variation we realize that 2. g8N+ was a threat all along, but that any black piece on d1 except a knight prevents the checkmate 4. Qxc2.
Peter Hoffman has continued to explore variations on the Babson task where the White promotions aren't necessarily echos of the Black ones, but instead form a permutation of the four pieces. For instance, the following problem realizes the pattern Queen->Rook, Rook->Knight, Knight->Queen, Bishop->Bishop.
After 1. cxd7, d1Q, White plays 2. dxe8R! so that 2. .. Qd7+ can be met with 3. Bxd7 without stalemate. On 1. .. d1R, White must promote to a knight, since in this problem not even a rook stops the old stalemate trap 2. .. Rxd4+. On 1. .. d1N on the other hand, White can now allow Black to give a check on b2 or c3, provided that they have a queen on e8! Finally the self-paralysis 1. .. d1B is again met with a bishop promotion. As in the previous problem, there are numerous details that amazingly make these White promotions the only moves that work.
In what very much looks like a mathematical research project (in a sense it is!), Hoffman has so far demonstrated eight permutations of the 24. By the way, in the table summarizing the results, the original Babson pattern (Q->Q, R->R, B->B, N->N), is called the echo. Mathematicians would call it the identity permutation, but I think echo is both more descriptive and beautiful, and I wish we would use it in mathematics. Imagine reading in an algebra book that "the only automorphism of the field of rational numbers is the echo"!
Among the 16 permutations not yet realized, Hoffman mentions the "reciprocal" pattern Q->N, N->Q, R->B, B->R as particularly attractive. But beware, not even the "3/4-Babson" pattern Q->N, R->B, B->R has been demonstrated!
If you want to try this challenge, it might be useful to have a chess program available. But it's a bit like using a pocket calculator in mathematical research. Currently the only thing the software will do for you is to look for the quickest forced mate in a position that you set up. You can't use it to systematically search through positions, and it will never tell you that "Had it not been for the flight square on g5, this variation might have worked, perhaps we should try adding a white pawn on f4 or h4".
Even though the permuted Babson tasks are well-defined questions with a finite search space, exactly the sort of task where computers are supposed to excel, there is to my knowledge no software that can even meaningfully attack them. It doesn't make sense to randomly throw out pieces and check whether it led to a permuted Babson, because those positions are so rare that you won't find one in a million years. But in order to search intelligently, it seems one has to use concepts that go beyond the way current software represents chess.
Peter Hoffman has continued to explore variations on the Babson task where the White promotions aren't necessarily echos of the Black ones, but instead form a permutation of the four pieces. For instance, the following problem realizes the pattern Queen->Rook, Rook->Knight, Knight->Queen, Bishop->Bishop.
Peter Hoffman, Die Schwalbe 2008.
Mate in 4.
After 1. cxd7, d1Q, White plays 2. dxe8R! so that 2. .. Qd7+ can be met with 3. Bxd7 without stalemate. On 1. .. d1R, White must promote to a knight, since in this problem not even a rook stops the old stalemate trap 2. .. Rxd4+. On 1. .. d1N on the other hand, White can now allow Black to give a check on b2 or c3, provided that they have a queen on e8! Finally the self-paralysis 1. .. d1B is again met with a bishop promotion. As in the previous problem, there are numerous details that amazingly make these White promotions the only moves that work.
In what very much looks like a mathematical research project (in a sense it is!), Hoffman has so far demonstrated eight permutations of the 24. By the way, in the table summarizing the results, the original Babson pattern (Q->Q, R->R, B->B, N->N), is called the echo. Mathematicians would call it the identity permutation, but I think echo is both more descriptive and beautiful, and I wish we would use it in mathematics. Imagine reading in an algebra book that "the only automorphism of the field of rational numbers is the echo"!
Among the 16 permutations not yet realized, Hoffman mentions the "reciprocal" pattern Q->N, N->Q, R->B, B->R as particularly attractive. But beware, not even the "3/4-Babson" pattern Q->N, R->B, B->R has been demonstrated!
If you want to try this challenge, it might be useful to have a chess program available. But it's a bit like using a pocket calculator in mathematical research. Currently the only thing the software will do for you is to look for the quickest forced mate in a position that you set up. You can't use it to systematically search through positions, and it will never tell you that "Had it not been for the flight square on g5, this variation might have worked, perhaps we should try adding a white pawn on f4 or h4".
Even though the permuted Babson tasks are well-defined questions with a finite search space, exactly the sort of task where computers are supposed to excel, there is to my knowledge no software that can even meaningfully attack them. It doesn't make sense to randomly throw out pieces and check whether it led to a permuted Babson, because those positions are so rare that you won't find one in a million years. But in order to search intelligently, it seems one has to use concepts that go beyond the way current software represents chess.
No comments:
Post a Comment