Grand-Master Level Chess Without Search: Modeling Choices and Their Implications
gist.github.com
gist.github.com
I’ve built a chess engine in the past so I was less hung up on the “without search” component like a lot of the original thread seemed to be. I don’t care if I have to take an argmax over all possible moves in a position and whether that technically qualifies as a search, or if the model may be doing some implicit search within its weights. What matters to me is that it is several orders of magnitude lower search required than stockfish, and those operations cost much less because they’re being executed in parallel on a TPU (GPU also works).
Optimizing static evaluation for the hardware we have is still a super interesting topic. It’s arguably why deep learning took off: matrix multiplication happens to be really cheap on GPUs.
Multiplication of large matrices is intrinsically simple to parallelize, and in addition it has great data locality and a very regular structure. It's just a great operation to perform efficiently on a parallel processor.
> The paper mentions that the model could not follow the "don't repeat the same board position three times in a row" rule (aka "threefold repetition").
That is not the rule. It is not illegal to repeat a position for a third time.
The rule only says that a player can claim a draw in the case of a three fold repetition [1].
There is a little known rule in tournament chess that if a position is reached 5 times, an arbiter can step in and rule the game as a draw without a claim. Usually only comes up in scholastic tournaments and very rarely in blitz tournaments.
Do you happen to know if this can be applied even several rounds later, in a swiss format? In most tournaments, even if there are score sheets, the arbiters rarely look over the game if the players agree on the result. And sometimes I don't look over my own games until a few days later if I'm disgusted enough with how I played...
> it looked at a game position, then used a strong chess-engine to expand a tree of possible game continuations from this position spanning hundreds of thousands if not millions of moves into the future. The game engine then used its internal knowledge of chess to assess the percentage of winning board positions within the possible continuations, which is the "probability of win" for a position. Then, the learner tried to learn this number. This is not learning from observations, it is learning from a super-human expert.
Apparently it was able to summarize the knowledge of that expert pretty well, though.
And then we get some rant about how 'it's not really learning how to plan' because it doesn't know to win in as few moves as possible. But again this just doesn't matter! The model was trained to maximize its odds of winning. You don't get to make up a new rule that you're supposed to win quickly. Totally beside the point. But somehow this observation is taken to mean that 'well it's not actually planning/reasoning/understanding. It's just imitating its training data.' Such statements are usually operationally meaningless, and the argument could just as well apply to human learning.
Point taken that the training method can't learn arbitrary rules (this is a good point, and it sounds like it needed to be made, though I didn't see the Twitter-storm myself). But the tone of this article irked me a bit.
I feel that the sort of structures we implicitly operate over during search can be usefully "flattened" in a higher dimensional space such that whole paths become individual steps. I feel that implicitly that's the sort of thing that the network must be doing.
If you watch videos of grandmasters talking about chess positions, often they'll talk about the "structure" of the position, and then confirm the structure via some amount of search. So, implicitly grandmasters probably do some kind of flattening too which connects features of the present state to future outcomes in a way requiring less mental effort.
Yes that's sort of the point of the approach. Imagine when the board is any position, you have a list of all possible moves which are ranked based on how good they are (i.e., how likely they are to lead to you winning). In order to make this ranking you've "flattened" the future outcomes of that move into a single number which is used to rank the list. Then, you can play optimally without search: simply pick the best move at every board position. (Richard Bellman showed that, for the right definition of "best", this gives the optimal strategy for playing entire games, not just single moves.)
Now the question is, how does one actually calculate this sorted list of the best moves? The straightforward answer is essentially search and various techniques to make the search computationally tractable. What Deepmind's approach is use such a list computed by Stockfish (which explicitly searches) to compile a dataset which is then trained on in order to approximate the function that produces this ranking (called the Q-function). But the point is that search is just an algorithmic strategy to estimate the Q-function, mathematically speaking it is merely a function of the current board state and therefore in theory could be determined without any search. So, maybe a deep neural network could learn how to do this?
In many positions there’s surprisingly little actual computation going on.
I think most strong chess players can "evaluate" a board and decide who is stronger to within a small error compared to an engine score. I think if you were to test this by giving strong players N seconds per position -- not enough time to calculate to any depth -- it would be shown that many are within a small (but consistent) margin of error compared to an engine.
This process happens in much the same way as facial recognition. For most faces, we just “know” who the person is. We don’t consciously search a database of acquaintances, filtering by facial features, eye color, hairstyle, etc. We see and we recognize.
I'd imagine one could directly realise this by training a network with chess games and the distances between them -- by some useful path related measure -- as inputs. I think that the network would succeed in learning an embedding for chess games. I wouldn't be surprised if such an embedding could be fine tuned to output win probability instead for example.
I also wouldn't be surprised if you could train a network on an auto-completion task of one-move-ahead prediction, and then using that to assign win probabilities, much in the same way that LLMs are used for part of speech tagging.
The whole paper is just an argument against people who still think of transformers as "stochastic parrots".
Probably it's even a mainly internal Deep Mind debate, since people outside have long ago accepted that transformers obviously learn algorthms and do something akind to planning.
You can see this undertone many places in the paper, like when they emphasize the systems plays strongly without _explicit_ search. Or if you read the conclusion.
Even doing these things at an average level would be pretty mind blowing.
Guidelines meditation for you.
https://news.ycombinator.com/newsguidelines.html
"Please don't comment on whether someone read an article. "Did you even read the article? It mentions that" can be shortened to "The article mentions that". "
I actually think their conclusion is mis-stated. Instead of saying this shows transformers aren’t mere statistical pattern recognizers but are powerful algorithm approximators they should say that it shows statistical pattern recognition trained on enough samples is sufficient for approximating sophisticated algorithms.
Grandmaster-Level Chess Without Search - https://news.ycombinator.com/item?id=39301944 - Feb 2024 (128 comments)
It's a shame it's not getting as much traction on here as the paper itself. Once again, Deepmind's shameless embellishments of their research will become HN myths because most people will only have seen the paper and not this.
This is of course a general trend; critiques and even retractions rarely get as much attention as the hyperbolised form of the original research and while the field itself moves on, the laypeople come out of it less informed than they were before.
It's also understood by people who have ever looked at the area (which is the audience of academic papers). 'Without search' is understood.
They claim it outperforms Alpha Zero's policy network when Alpha is not the state of the art for its architecture anymore and hasn't been for years. Leela is. A fair comparison would use Leela, not Alpha Zero.
And of course, as usual, they seem not to provide any source code or weights, so no one can check their research independently.
"2895 lichess blitz elo without search (except for edge cases due to the threefold rep rule)" ?
The non optimal endgame play wouldn't really be a problem except for the threefold rule, in practice (i think). It would eventually bumble around and win.
The fact that they're willing to do that just to get a better headline is pretty telling.
I don't think it is tainted. In practical terms, those games have been won.
Also, the idea of this + search as being the next step is wrong. That was the last step, ie it's been done. No search is the next step.
I think wrong is a strong word here. You can keep making a bigger model, that's one direction to go for sure. But adding search is certainly an interesting one at the very least. And it's definitely the way forward to see if this is an approach that can advance the strength of chess playing programs. I seriously doubt this would ever outperform a search based paradigm on its own. For one thing it gets no advantage from extra time(which is another reason the grandmaster strength claim is dubious btw; it would be outplayed in longer time controls). For another, search might be necessary to make this thing able to train without the help of Stockfish, by playing itself(iterated amplification and distillation, how AlphaZero was trained). For a third, due to the game complexity of chess, it's likely that model size without search would have to scale exponentially to become stronger.
And all this brings me back to my previous points about releasing weights and code. If they had done so, I would be trying all of these things out myself right now instead of arguing about it on the internet. But time and time again Deepmind have demonstrated that they won't engage with the wider computer chess community. And so their research, which is no doubt innovative and inspiring, fails to have the impact it could have, because the community has to redo all the work with less money and compute. We saw this with Alpha Zero; it took years and a lot of hard work by volunteers for Leela just to get where Alpha Zero was originally and eventually surpass it. And it will probably take a long time to see state of the art competitive engines based on this new approach in the wild. Because Deepmind don't really care about that beyond making a splash with their initial publication. They're only peripherally interested in chess, which is fine, but as a chess player and computer chess enthusiast it makes me sad that they won't engage with the community in an open way.
You are right though, they are only peripherally interested in chess.
Also, the fact that AlphaZero has search is irrelevant. This is a completely different model architecture. Stockfish had search before AlphaZero, does that mean AlphaZero wasn't interesting either? Or hell, why not just say all computer chess developments are uninteresting because alpha-beta was invented in the 50s?
I guess I'm saying their goal here was to do no search and get high performance, not create the highest possible performance. The trade off between run time search and more training (better models) is an explicit area of research, and this paper is in that realm. Noam Brown has talked a lot about this in the context of poker and diplomacy.
[0] https://arxiv.org/pdf/2402.04494.pdf
[1] https://matteoraso.github.io/board-game-engines-are-about-tr...