[This post assumes a familiarity with terminology from previous posts. Rather than try to gloss everything, I'm going to punt and respectfully ask the confused reader to at least skim through the previous few posts]
It's clear from watching a bunch of games that the two main types of chess engines have different styles, though not all that different. It's not as though anyone suddenly decided 1. g4 was a great opening. In broad strokes:
AB engines play very precisely and their evaluations of positions are fairly conservative. It's quite common for an NN engine to give a large advantage to one side in a position that an AB engine rates as fairly even. The ratings eventually come in line, but the convergence can happen in either direction.
If the NN engine is right, the AB eval comes up to meet it as the NN exploits an advantage that the AB engine missed. If it's wrong, the NN eval comes down and the result is often a draw, either because the NN engine failed to play precisely enough to convert a winning advantage, or the winning advantage was never really there to begin with. It would be interesting to track down statistics on this, and any interesting exceptions, but I don't have easy access to the data.
When NN engines first hit the scene, the initial take was that neural nets had captured some subtlety of positional understanding that the AB engines, with their relatively simple hard-coded evaluation rules couldn't fathom, even given the ability to look many moves ahead. This is mostly accurate, I think, but incomplete.
In the Blitz Bonanza, there were any number of NN wins over AB engines, at least the weaker ones, that started with the advance variation of the French Defense (1. e4 e3 2. d4 d4 followed soon after by white e5). This opens up a lot of space for white on the kingside and tends to push the black pieces over to the queenside -- or maybe "lure" is a better word, since there are plausible things for them to do there, including attacking white's pawn center. The problem is that white can now launch a fairly potent kingside attack and black doesn't have time or space to get enough pieces over to defend.
Apparently none of this looks too bad to an AB engine. Yes, white has an advanced pawn in the center, but there are chances to counterattack and weaken that pawn. Once the white attack really gets going, often aggressively pushing the g and h pawns, its king may start to look correspondingly weak -- except black doesn't have any pieces well-located to attack it. A typical AB engine's eval function doesn't try to account for that -- looking ahead it will either find an attack or it won't.
Probably this disconnect of white seeing good chances and black finding plusses and minuses to the same moves continues until black can see actual tactical threats coming, at which point it's toast since its pieces are now bottled up on the wrong side of the board. The natural explanation is that the NN engine understands that there are good attacking prospects on the kingside and blacks pieces are poorly placed to defend.
What's actually going on is probably a bit different. In its training phase, the code that trains the NN found that positions with, say, more black pieces on the queenside, lots of open squares on the kingside, and pawns pushed up near the black king tend to lead to wins. It didn't specifically note this as such, but those were some of the positions which -- in oversimplified terms -- caused some of the weights that favored those kinds of positions to be increased.
A human playing in the same style would probably say "My plan was to open up some space, get black's pieces bottled up on the queenside and launch a kingside attack". But here there is no plan. White is playing moves that tended to work well in similar situations in training.
As I mentioned in a previous post, this lack of a plan becomes blindingly obvious in endgames. Many endgames have an almost mathematical feel to them. White is trying to hold a draw. Black is up a bishop for two pawns. Picking off one of those pawns would allow one of black's own pawns to promote unimpeded. But white's pawns are all on the wrong color square for the bishop to attack and they're blocked against black's pawns (and vice versa), so all white has to do is keep black's king away.
Conversely, though, if black can draw white's king away from where it's blocking black's king, it can sneak its own king through and pick up the undefended pawns. And there just happens to be a tactical threat that will accomplish that ...
A human player can figure positions like this out logically and win or hold the draw, as the case may be, even against perfect play. An AB engine can often look ahead far enough to find the winning variation. An NN engine might or might not stumble on the right move.
Likewise, it's common for an NN engine to see a large advantage in a position that's clearly a draw. Suppose in the previous scenario there's a way for white to safely shuffle its king back and forth between two squares and keep the black king from getting through. Quite likely the AB engine will evaluate the position as dead even, and the human kibitzers will agree. The NN engine, if it's playing black in this example, will continue to see a sizable advantage almost up to the 50-move limit, even though all it's doing is rearranging its pieces in order to avoid threefold repetition.
If understanding chess means having a feel for what kind of positions have good or bad prospects without trying to calculate every possible variation, that is, playing like a human, then NN engines are clearly doing something similar.
On the other hand, if understanding chess means being able to find the right moves to win or draw a difficult endgame, that is, playing like a human, then AB engines clearly have the upper hand.
But if understanding chess means being able to reason about why an endgame is won, lost or drawn, or being able to put together a general plan of attack without knowing in advance exactly what moves need to happen in what order, that is, playing like a human, then neither type of engine is even trying.
Wednesday, May 22, 2019
What's chess to a computer?
It's now quite clear that computer chess is going to eat this blog for a while, so I'm in the process of unpacking several points that have come up in my earlier attempts to just make a few quick points and move on. I'm also coming to realize that, since I'm having even more trouble than usual organizing this into a coherent whole, I'll probably end up with N posts worth of material spread across N+1 posts, if not more. Apologies. This particular post is an excursion into computer science land to look at computer chess from that point of view, rather than trying to understand it as chess.
One thing that makes chess particularly interesting as a search problem is that it's not totally random, but it's not totally orderly either.
Imagine a search tree as a series of branching passageways. At the end of every passageway, after however many branches, is a card reading "black wins", "white wins" or "draw". If all you know is that the cards are there then you might as well pick randomly at each junction. On the other hand, if you have a map of the entire complex of passageways and which card is at the end of each of them, you can find your way perfectly. Depending on where the cards are, you might or might not be able to win against a perfect player, but if your opponent makes a mistake you'll know exactly how to take advantage.
In chess there are far too many passages to map out, but there are markings on the walls. For example, there are several types of endgame positions which even a human can always play perfectly. If you reach a position where you have a king and a rook and your opponent only has a king (and it's not a stalemate to start out with), you can win by following a pretty simple recipe.
There are also databases of positions ("tablebases") with known outcomes, found by exhaustively searching backwards from all possible checkmate positions. Currently every endgame with seven or fewer pieces (including the kings) is known to be either a win for white, win for black or a draw. If it shows up by working backward from one of the possible checkmates, it's a win. If it didn't, it's a draw (the process of working backwards from known positions is itself a tree search).
There are a few kinds of positions that are well-known to be immediate wins for one side or the other, regardless of what other pieces are on the board. The classic example is a back-rank mate, where one side's king is blocked between the edge of the board and its own pawns and the other side has major pieces able to give check. It's simple to calculate whether the defending side can capture all the pieces that can give check or can safely interpose (block). If not, it's game over. My understanding is that chess engines don't bother to special-case these, since they're typically looking several moves ahead anyway.
And then there's a lot of gray area. If one side gains a material advantage, it will generally win, eventually, but this is far from an ironclad rule. There are plenty of cases where one side will give up material (sacrifice) in order to gain an advantage. This ranges from spectacular combinations where one side gives up a queen, or more, in order to get a quick checkmate, to "positional sacrifices" where one side gives up something small, generally a pawn, in order to get an initiative. Whether a positional sacrifice will be worth it is usually not clear-cut, though in some well-known cases (for example, the Queen's gambit), it's generally agreed that the other side is better off not taking the material and should concentrate on other factors instead.
There are also temporary sacrifices where one side gives up material in order to quickly win back more. If you're playing against a strong player and it looks like they've left a piece hanging, be very careful before taking it.
In short, which side has more material is a clue to which side will win, and it's often a good idea to try to win material, but it's not a guarantee. This goes equally well for other generally accepted measures of how well one is doing. Maybe it's worth it to isolate or double one of your pawns in order to gain an initiative, but often it's not. Games between human masters often turn on whose estimations of which small trade-offs are correct.
From a computing point of view, since it's impossible to follow all the passageways, we have to rely on the markings on the wall, that is, the characteristics of particular positions. An AB engine will look exhaustively at all the passages that it explores (subject to the "alpha/beta pruning" that gives them their name, which skips moves that can't possibly lead to better results than are already known). But in most positions it will have to give up its search before it finds a definitive result. In that case it has to rely on its evaluation function. Basically it's saying "I've looked ten branches ahead and if I make this move the worst that can happen is I'll get to a position worth X".
That's much better than picking randomly, but it only works well if you explore quite deeply. A good human player can easily beat a computer that's only searching three moves (six plies) ahead because the human can easily find something that looks good in the short term but turns bad a few moves later. Once an AB engine is looking dozens of moves ahead, though, there are many fewer short-term traps that don't pan out until late enough for the search to miss them.
This is a lot like the problem of local minima in hill-climbing algorithms. If you're trying to get to the highest point in a landscape, but it's so dark or foggy you can only see a short distance around you, your best bet could well be to go uphill until you can't any more, even though that fails if you end up atop a small hill that's not actually the high point. The further you can see, the better chance you have of finding your way to the true high point, even if you sometimes have to go downhill for a while to get on the right path.
Humans and neural networks, however, are doing something slightly different. They can't look very far, but they're able to read the landscape better. It's kind of like being on a mountainside in the fog and being able to look at the vegetation, or smell the wind, or examine the types of rock in the area or whatever, and be able to say that the peak is more likely this way than that way.
This wouldn't work if there weren't some sort of correlation between the features of a position and how likely it is to ultimately lead to a win. It's not a property of tree-searching algorithms. It's a property of chess as a tree-searching problem. It's probably a property of any chess-like game that humans find interesting, because that's probably what we find interesting about chess: there's some order to it, in that some positions are clearly better than others, but there's some mystery as well, since we often can't tell for sure which option is better.
Chess, fundamentally, falls into a large class of problems called tree searches, in which a number of interconnected structures are explored by proceeding from a starting point to those that are connected directly to it, and those connected directly to the first set, and so forth. There are lots of different ways to do this, depending mostly on what order you do the visiting in.
Examples of tree searches, besides finding good chess moves, include figuring out the best way to route packets in a network, solving a puzzle where odd-shaped blocks have to be arranged to form a cube, finding the shortest path through a maze and following reflections and refractions to find what color a particular pixel in an image will be (ray-tracing). There are many others.
Each point in a tree search is called a node. In chess, the nodes are chess positions (including where the pieces are, which side is to move and a few other bits such as whether each side's king has moved). At any point in a tree search you are either at a leaf node, meaning you have no further choices to make -- in chess, you have arrived at a win, loss or draw, or more often simply decided not to explore any deeper -- or not, in which case you have one or more child nodes to choose from. In chess, the children of a position are all the positions that result from legal moves in the current position.
Examples of tree searches, besides finding good chess moves, include figuring out the best way to route packets in a network, solving a puzzle where odd-shaped blocks have to be arranged to form a cube, finding the shortest path through a maze and following reflections and refractions to find what color a particular pixel in an image will be (ray-tracing). There are many others.
Each point in a tree search is called a node. In chess, the nodes are chess positions (including where the pieces are, which side is to move and a few other bits such as whether each side's king has moved). At any point in a tree search you are either at a leaf node, meaning you have no further choices to make -- in chess, you have arrived at a win, loss or draw, or more often simply decided not to explore any deeper -- or not, in which case you have one or more child nodes to choose from. In chess, the children of a position are all the positions that result from legal moves in the current position.
Since there is no element of chance in chess, there is one and only one game tree that starts at the initial position (the root node) and includes every possible position resulting from every series of legal moves. This means that in theory there it's possible to know whether any position is a win for white, a win for black or a draw, assuming each side plays perfectly. That includes the initial position, so in theory there is an optimal strategy for each player and all perfectly-played games of chess have the same result.
The problem is that the game tree for chess is incomprehensibly huge. There are way, way more legal chess positions than fundamental particles in the known universe. No computer will ever be able to examine more than a minuscule fraction of them. That doesn't necessarily mean that chess will never be "solved", in the sense of proving what the optimal strategies are for each player and what the result will be with perfect play. In theory there could be a way to rule out all but a tiny fraction of possible positions and exhaustively search what's left. In practice, we're nowhere near being able to do that.
Instead, we're left with approximate approaches. Either exhaustively search a tiny, tiny fraction of the possibilities, which is what AB engines do, or find some sort of approximate measure of what constitutes a "good" position and "just play good moves", using a partial search of the possible continuations to double-check that there aren't any obvious blunders. This is what humans and NN engines do.
One thing that makes chess particularly interesting as a search problem is that it's not totally random, but it's not totally orderly either.
Imagine a search tree as a series of branching passageways. At the end of every passageway, after however many branches, is a card reading "black wins", "white wins" or "draw". If all you know is that the cards are there then you might as well pick randomly at each junction. On the other hand, if you have a map of the entire complex of passageways and which card is at the end of each of them, you can find your way perfectly. Depending on where the cards are, you might or might not be able to win against a perfect player, but if your opponent makes a mistake you'll know exactly how to take advantage.
There are also databases of positions ("tablebases") with known outcomes, found by exhaustively searching backwards from all possible checkmate positions. Currently every endgame with seven or fewer pieces (including the kings) is known to be either a win for white, win for black or a draw. If it shows up by working backward from one of the possible checkmates, it's a win. If it didn't, it's a draw (the process of working backwards from known positions is itself a tree search).
There are a few kinds of positions that are well-known to be immediate wins for one side or the other, regardless of what other pieces are on the board. The classic example is a back-rank mate, where one side's king is blocked between the edge of the board and its own pawns and the other side has major pieces able to give check. It's simple to calculate whether the defending side can capture all the pieces that can give check or can safely interpose (block). If not, it's game over. My understanding is that chess engines don't bother to special-case these, since they're typically looking several moves ahead anyway.
And then there's a lot of gray area. If one side gains a material advantage, it will generally win, eventually, but this is far from an ironclad rule. There are plenty of cases where one side will give up material (sacrifice) in order to gain an advantage. This ranges from spectacular combinations where one side gives up a queen, or more, in order to get a quick checkmate, to "positional sacrifices" where one side gives up something small, generally a pawn, in order to get an initiative. Whether a positional sacrifice will be worth it is usually not clear-cut, though in some well-known cases (for example, the Queen's gambit), it's generally agreed that the other side is better off not taking the material and should concentrate on other factors instead.
There are also temporary sacrifices where one side gives up material in order to quickly win back more. If you're playing against a strong player and it looks like they've left a piece hanging, be very careful before taking it.
In short, which side has more material is a clue to which side will win, and it's often a good idea to try to win material, but it's not a guarantee. This goes equally well for other generally accepted measures of how well one is doing. Maybe it's worth it to isolate or double one of your pawns in order to gain an initiative, but often it's not. Games between human masters often turn on whose estimations of which small trade-offs are correct.
From a computing point of view, since it's impossible to follow all the passageways, we have to rely on the markings on the wall, that is, the characteristics of particular positions. An AB engine will look exhaustively at all the passages that it explores (subject to the "alpha/beta pruning" that gives them their name, which skips moves that can't possibly lead to better results than are already known). But in most positions it will have to give up its search before it finds a definitive result. In that case it has to rely on its evaluation function. Basically it's saying "I've looked ten branches ahead and if I make this move the worst that can happen is I'll get to a position worth X".
That's much better than picking randomly, but it only works well if you explore quite deeply. A good human player can easily beat a computer that's only searching three moves (six plies) ahead because the human can easily find something that looks good in the short term but turns bad a few moves later. Once an AB engine is looking dozens of moves ahead, though, there are many fewer short-term traps that don't pan out until late enough for the search to miss them.
This is a lot like the problem of local minima in hill-climbing algorithms. If you're trying to get to the highest point in a landscape, but it's so dark or foggy you can only see a short distance around you, your best bet could well be to go uphill until you can't any more, even though that fails if you end up atop a small hill that's not actually the high point. The further you can see, the better chance you have of finding your way to the true high point, even if you sometimes have to go downhill for a while to get on the right path.
Humans and neural networks, however, are doing something slightly different. They can't look very far, but they're able to read the landscape better. It's kind of like being on a mountainside in the fog and being able to look at the vegetation, or smell the wind, or examine the types of rock in the area or whatever, and be able to say that the peak is more likely this way than that way.
This wouldn't work if there weren't some sort of correlation between the features of a position and how likely it is to ultimately lead to a win. It's not a property of tree-searching algorithms. It's a property of chess as a tree-searching problem. It's probably a property of any chess-like game that humans find interesting, because that's probably what we find interesting about chess: there's some order to it, in that some positions are clearly better than others, but there's some mystery as well, since we often can't tell for sure which option is better.
Tuesday, May 21, 2019
Computer chess engines fall in line
[This post came out of trying to figure out what computer chess results tell us about what kind of problem chess-playing is. It goes into quite a bit of detail about cycles where player A beats player B beats player C beats player A and why they don't seem to happen. Shortly after I posted this, the Computer Chess Championship "Deep Dive" round finished up, and there was a slight anomaly: Stockfish won the tournament, but second-place LC0 beat it head to head, by the narrow margin of 4-3-43, implying an Elo difference of 8 points. I don't think this affects the post greatly, but it does reinforce the point that NN engines are less consistent than AB engines. Stockfish didn't lose a game to 4th-place Houdini while LC0 both won and lost. I'll update this slightly when chess.com makes the full results available --D.H. May 2019]
One thing jumps out from watching the ongoing computer chess tournaments that is so ordinary-seeming that it's easy to dismiss entirely: The rankings from a preliminary round with a couple dozen contestants, are strikingly linear. If you look at the cross-table, which shows everyone's results against everyone else's, wins in green, losses in red and draws in gray, not only do everyone's scores improve down the table, but for the most part all the red is above and all the green below. Stronger engines very consistently beat weaker engines, especially considering that at least some of the apparent upsets were due to system crashes and such.
I've seen this happen twice now, once for the "Blitz Bonanza" (5 minutes plus two seconds per move) and the Deep Dive (15 minutes plus 5 seconds per move). The Deep Dive preliminary, which just finished a few days ago, was played in "escalation" format, meaning that each new player plays everyone who's already played (twice as white and twice as black). After a few opponents, you can be pretty confident about where a new player will land -- above whoever whoever it's beat head-to-head, below whoever it's lost to, and close to anyone it drew all four games with.
It shouldn't be a total shock that stronger players beat weaker players, or even that they beat them very consistently. My point is more that it doesn't have to be that way. While there are only two basic styles of engine*, each dev team has its own philosophy and each one evaluates positions differently. In the case of neural net-based engines (generally referred to as NN), the evaluation of positions is done radically differently.
It seems at least plausible that, as with human players, engines might tend to do better or worse than otherwise expected against particular styles of play. An engine that attacks aggressively might lose to one that's tuned for careful defending, but beat a middle-of-the-road approach that can outplay the careful defender positionally. This would create a cycle of attacker beats middle-of-road beats defender beats attacker, but this sort of situation doesn't seem to happen in practice.
Without going back and checking the actual numbers, my impression is that AB engines -- the conventional style which does an exhaustive search a far ahead as it can manage, using fairly understandable hand-coded rules to evaluate positions quickly -- win more by being able to look further ahead than by having cleverer evaluation rules. That is, evaluation speed is a good predictor of who will win.
Clearly if two engines have identical evaluation rules, but one implements them more efficiently, the faster engine should win because it can see further ahead. The faster engine will see everything the slower engine sees, but it can also see which of two seemingly equal moves leads to a better result. It will therefore be able to steer toward winning positions and the slower engine won't see the danger until it's too late.
Even with each team using its own particular evaluation rules, something like this still happens. Typically when two AB engines play, there will be a period where the weaker engine shows a more favorable evaluation for itself than the stronger one does, e.g., the weaker engine is playing white and it sees a half-pawn advantage for white while the stronger engine sees a small advantage for black.
The weaker engine thinks everything's going fine while the stronger engine knows that it has the edge. Eventually the weaker engine's evaluation starts to drop as it realizes things are no longer as good as they looked, and the stronger engine pushes its small advantage into an overwhelming one.
Again, it isn't a foregone conclusion that a faster engine will beat a slower one with a different evaluation function, but it's what we see in practice. My suspicion is that evaluation functions hit diminishing returns after certain point. You've accounted for material, you've got some concept of tactical considerations like pins and hanging pieces, and a bit on positional factors like space and pawn structure. Further improvements are certainly possible, in the form of slightly better evaluation functions, slightly faster evaluation, or both, but the low-hanging fruit was picked long ago.
Adding a detailed model of, say, pawn structure, is likely just to slow the evaluation down without providing enough benefit to make up for the decrease in depth. This is the "dumb is smarter" principle that seems to have held sway for the past few decades.
Stockfish -- currently the clear champion among AB engines -- demonstrates this nicely with its "fishtest". As I understand it, developers try out changes to the program to see if their locally patched version consistently beats the current released version. Only winning changes are brought into the next release. While Stockfish has improved significantly as a result of fishtest, progress has been incremental, and the end result is that Stockfish can evaluate positions very quickly. I'm not 100% sure it's the fastest, but it's certainly high up there.
I'm sure everyone, open source or not, playtests potential improvements (and the training phase of NN engines take this to an extreme), but crowdsourcing this ought to keep development from fixating on some particular person or small group of people's idea of what must be right. Again, fewer assumptions means better results.
Bringing NN engines into the picture doesn't seem to change this linear ranking. NN engines are on the other extreme of the smart vs. fast tradeoff. For a given number of layers and so forth a position generally takes just as long to evaluate regardless of the exact parameters of the net being used, so the only difference in play will be due to the net itself. Evaluation speed is not a factor since it doesn't change.
This doesn't necessarily rule out A-beats-B-beats-C-beats-A cycles, in fact, it seems like they might be more likely since different nets will put different weights on different factors -- assuming there's more than one way to be good at chess. So far, though, there don't seem to be any. In the tournament results I've seen so far, there are three strong NN engines: Leela Chess Zero (generally known as LC0) Leelenstein and Antifish (a modified Leela trained specifically to beat Stockfish). In the Blitz Bonanza, LC0 had winning records against the other two and Leelenstein had a winning record against Antifish. Antifish does not seem to do better than the others against Stockfish. If anything it does slightly worse.
There are only two NN engines in the Deep Dive finals (rules now prohibit more than one variant of the same engine reaching the finals, so Antifish is out). Obviously there will be no cycle between them. For what it's worth, LC0 is currently slightly ahead of Leelenstein, but they're dead even head-to-head.
There is one clear deviation from the orderly world of AB engines. Since NN engines evaluate so slowly, they take a random sample of positions when looking ahead, rather than searching exhaustively like AB engines. I believe the sample is weighted towards moves the net considers likely to be good, but in any case this introduces some inconsistency. NN engines occasionally lose to weak AB engines since not all good-looking moves turn out actually to be good, while strong AB engines almost never do. Against strong AB engines, NN engines can find good moves that the AB opponent overlooks because it doesn't lead to good results quickly enough for the exhaustive search to turn it up, but they can also play good-looking moves that turn out to be unsound if you search well enough.
The net effect is that strong NN engines don't do as well against weak AB engines as you'd expect from how they do against strong engines. In the current Deep Dive finals, Stockfish is (at this writing) noticeably ahead of LC0, but head-to-head they're nearly even (3 wins to 2 with 41 draws, implying an ELO difference of 8 points; by contrast, human world champion Carlsen is currently rated about 57 points ahead of second-ranked Caruana) [and in fact, Stockfish won the finals but lost to LC0 head-to-head].
The difference is that Stockfish has done better against the weaker opposition. Stockfish is 9-0 against 4th-place Houdini (with a whole bunch of draws), while LC0 is 12-3 against Houdini (with correspondingly fewer draws). Stockfish also does better against the other NN engine, 3rd-place Leelenstein.
So there don't seem to be any cycles in the ranking of chess engines, and the (small) difference between top AB engines and top NN engines looks to be due to consistency. What does this tell us about chess-playing as a problem? There are several possible conclusions:
One thing jumps out from watching the ongoing computer chess tournaments that is so ordinary-seeming that it's easy to dismiss entirely: The rankings from a preliminary round with a couple dozen contestants, are strikingly linear. If you look at the cross-table, which shows everyone's results against everyone else's, wins in green, losses in red and draws in gray, not only do everyone's scores improve down the table, but for the most part all the red is above and all the green below. Stronger engines very consistently beat weaker engines, especially considering that at least some of the apparent upsets were due to system crashes and such.
I've seen this happen twice now, once for the "Blitz Bonanza" (5 minutes plus two seconds per move) and the Deep Dive (15 minutes plus 5 seconds per move). The Deep Dive preliminary, which just finished a few days ago, was played in "escalation" format, meaning that each new player plays everyone who's already played (twice as white and twice as black). After a few opponents, you can be pretty confident about where a new player will land -- above whoever whoever it's beat head-to-head, below whoever it's lost to, and close to anyone it drew all four games with.
It shouldn't be a total shock that stronger players beat weaker players, or even that they beat them very consistently. My point is more that it doesn't have to be that way. While there are only two basic styles of engine*, each dev team has its own philosophy and each one evaluates positions differently. In the case of neural net-based engines (generally referred to as NN), the evaluation of positions is done radically differently.
It seems at least plausible that, as with human players, engines might tend to do better or worse than otherwise expected against particular styles of play. An engine that attacks aggressively might lose to one that's tuned for careful defending, but beat a middle-of-the-road approach that can outplay the careful defender positionally. This would create a cycle of attacker beats middle-of-road beats defender beats attacker, but this sort of situation doesn't seem to happen in practice.
Without going back and checking the actual numbers, my impression is that AB engines -- the conventional style which does an exhaustive search a far ahead as it can manage, using fairly understandable hand-coded rules to evaluate positions quickly -- win more by being able to look further ahead than by having cleverer evaluation rules. That is, evaluation speed is a good predictor of who will win.
Clearly if two engines have identical evaluation rules, but one implements them more efficiently, the faster engine should win because it can see further ahead. The faster engine will see everything the slower engine sees, but it can also see which of two seemingly equal moves leads to a better result. It will therefore be able to steer toward winning positions and the slower engine won't see the danger until it's too late.
Even with each team using its own particular evaluation rules, something like this still happens. Typically when two AB engines play, there will be a period where the weaker engine shows a more favorable evaluation for itself than the stronger one does, e.g., the weaker engine is playing white and it sees a half-pawn advantage for white while the stronger engine sees a small advantage for black.
The weaker engine thinks everything's going fine while the stronger engine knows that it has the edge. Eventually the weaker engine's evaluation starts to drop as it realizes things are no longer as good as they looked, and the stronger engine pushes its small advantage into an overwhelming one.
Again, it isn't a foregone conclusion that a faster engine will beat a slower one with a different evaluation function, but it's what we see in practice. My suspicion is that evaluation functions hit diminishing returns after certain point. You've accounted for material, you've got some concept of tactical considerations like pins and hanging pieces, and a bit on positional factors like space and pawn structure. Further improvements are certainly possible, in the form of slightly better evaluation functions, slightly faster evaluation, or both, but the low-hanging fruit was picked long ago.
Adding a detailed model of, say, pawn structure, is likely just to slow the evaluation down without providing enough benefit to make up for the decrease in depth. This is the "dumb is smarter" principle that seems to have held sway for the past few decades.
Stockfish -- currently the clear champion among AB engines -- demonstrates this nicely with its "fishtest". As I understand it, developers try out changes to the program to see if their locally patched version consistently beats the current released version. Only winning changes are brought into the next release. While Stockfish has improved significantly as a result of fishtest, progress has been incremental, and the end result is that Stockfish can evaluate positions very quickly. I'm not 100% sure it's the fastest, but it's certainly high up there.
I'm sure everyone, open source or not, playtests potential improvements (and the training phase of NN engines take this to an extreme), but crowdsourcing this ought to keep development from fixating on some particular person or small group of people's idea of what must be right. Again, fewer assumptions means better results.
Bringing NN engines into the picture doesn't seem to change this linear ranking. NN engines are on the other extreme of the smart vs. fast tradeoff. For a given number of layers and so forth a position generally takes just as long to evaluate regardless of the exact parameters of the net being used, so the only difference in play will be due to the net itself. Evaluation speed is not a factor since it doesn't change.
This doesn't necessarily rule out A-beats-B-beats-C-beats-A cycles, in fact, it seems like they might be more likely since different nets will put different weights on different factors -- assuming there's more than one way to be good at chess. So far, though, there don't seem to be any. In the tournament results I've seen so far, there are three strong NN engines: Leela Chess Zero (generally known as LC0) Leelenstein and Antifish (a modified Leela trained specifically to beat Stockfish). In the Blitz Bonanza, LC0 had winning records against the other two and Leelenstein had a winning record against Antifish. Antifish does not seem to do better than the others against Stockfish. If anything it does slightly worse.
There are only two NN engines in the Deep Dive finals (rules now prohibit more than one variant of the same engine reaching the finals, so Antifish is out). Obviously there will be no cycle between them. For what it's worth, LC0 is currently slightly ahead of Leelenstein, but they're dead even head-to-head.
There is one clear deviation from the orderly world of AB engines. Since NN engines evaluate so slowly, they take a random sample of positions when looking ahead, rather than searching exhaustively like AB engines. I believe the sample is weighted towards moves the net considers likely to be good, but in any case this introduces some inconsistency. NN engines occasionally lose to weak AB engines since not all good-looking moves turn out actually to be good, while strong AB engines almost never do. Against strong AB engines, NN engines can find good moves that the AB opponent overlooks because it doesn't lead to good results quickly enough for the exhaustive search to turn it up, but they can also play good-looking moves that turn out to be unsound if you search well enough.
The net effect is that strong NN engines don't do as well against weak AB engines as you'd expect from how they do against strong engines. In the current Deep Dive finals, Stockfish is (at this writing) noticeably ahead of LC0, but head-to-head they're nearly even (3 wins to 2 with 41 draws, implying an ELO difference of 8 points; by contrast, human world champion Carlsen is currently rated about 57 points ahead of second-ranked Caruana) [and in fact, Stockfish won the finals but lost to LC0 head-to-head].
The difference is that Stockfish has done better against the weaker opposition. Stockfish is 9-0 against 4th-place Houdini (with a whole bunch of draws), while LC0 is 12-3 against Houdini (with correspondingly fewer draws). Stockfish also does better against the other NN engine, 3rd-place Leelenstein.
So there don't seem to be any cycles in the ranking of chess engines, and the (small) difference between top AB engines and top NN engines looks to be due to consistency. What does this tell us about chess-playing as a problem? There are several possible conclusions:
- Chess skill really is a linear ranking, at least once you get to the level of computer engines. If A beats B and B beats C, then A beats C.
- A bit stronger: There is one true way to play chess and stronger engines approximate this better.
- On the other hand: AB engines are linearly ranked because only depth/evaluation speed really matters while NN engines are linearly ranked because only the quality of the net doing the evaluation matters. It's not surprising, though not inevitable, that combining two linear rankings gives another linear ranking.
- Also, NN engines are all playing on or near the level of the current AB champion, so they're really only being compared to one style of play since there's only one really competitive opponent.
My feeling is that we don't really have enough to know for sure, but most likely we'll continue to see improvement in playing strength and that the linear ranking will hold. Next year's champion will be able to beat any other opponent head-to-head, the one after that will be able to beat it and everyone else, and so forth, regardless of whether the next champion is AB, NN or some hybrid of the two. There are noticeable differences between how AB engines and NN engines play (I'd like to get into the details in a future post), but be that as it may, stronger is stronger.
* Technically, there are two choices on two dimensions: Alpha/Beta tree search vs. Monte Carlo and neural-net based evaluation vs. hand-coded rules. However, NN engines always use Monte Carlo since it takes them roughly a thousand times longer to evaluate a particular position, so they can't search exhaustively. On the other hand, conventional engines generally use AB searches because they can. There have been fairly successful experiments in using Monte Carlo with hand-coded rules. Those tend to be called hybrid.
Subscribe to:
Posts (Atom)