Grandmaster-Level Chess Without Search
arxiv.org
arxiv.org
The "no-search" chess engine uses search (Stockfish) in in two ways:
1. To score positions in the training data. This is only training data, no search is performed when actually playing.
2. To play moves when the position has many options with a 99% win rate. This is to prevent pathological behavior in already won positions, and is not "meaningful" in the objective of grandmaster-level play.
Thus, "without search" is a valid description.
It's true that this is a relatively large deficiency in practice: how strong would a player be if he played the middlegame at grandmaster strength but couldn't reliably mate with king and rook?
The authors overcame the practical problem by just punting to Stockfish in these few cases. However, I think it's clearly solvable with LLM methods too. Their model performs poorly because of an artifact in the training process where mate-in-one is valued as highly as mate-in- fifteen. Train another instance of the model purely on checkmate patterns - it can probably be done with many fewer parameters - and punt to that instead.
When we have a won position we want to progress and convert it to an actual win.
I think the operational definition I would use for progress is a prediction of how many more moves the game will last. A neural network can be used for that.
However, in reality all positions are actually wins (for black or white) or draws. One reason they gave for why stockfish is needed to finish the game is because their evaluation function is imperfect, which is also an notable result.
I do suspect that this pathological behavior could be trained out with additional fine tuning, but likely not without slightly diminishing the model's overall ability.
Neural networks are universal approximators. Choose a function and get enough data from it and you can approximate it very closely and maybe exactly. If initially creating function F required algorithm Y ("search" or whatever), you can do your approximation to F and then say "Look F without Y" and for all we know, the approximation might be doing things internally that are actually nearly identical to the initial F.
What is interesting is performing well under reasonable computational constraints i.e. doing it faster/with fewer flops than stockfish.
Also found in the paper: "While our largest model achieves very good performance, it does not completely close the gap to Stockfish 16". It's actually inferior but they still think it's an interesting exercise. But that's the thing, it's primarily an exercise like calculating pi to a billion decimal points or overclocking a gaming laptop.
So you're estimating from data a function which is itself not necessarily optimal. Moreover, the point is more like how far can we get using a really generic transformer architecture that is not tuned to domain-specific details of our problem, which Stockfish is.
So the network still needs to do some impressive generalization in order to „interpolate“ between those samples.
I think so, anyway (didn‘t read the paper but worked on alphazero-like algorithms for a few years)
But if someone grew an actual dragon in a lab by splicing together DNA fragments, that would still be a major feat. Similarly, training a neural net to play grandmaster level chess is simple in theory but extremely difficult in practice.
That's like saying you can have eggs without chickens, because when you make an omelette you don't add chickens. It's completely meaningless and a big fat lie to boot.
The truth is that the system created by DeepMind consists of two components: a search-based system used to annotate a dataset of moves and a neural-net based system that generates moves similar to the ones in the dataset. DeepMind arbitrarily draw the boundary of the system around the neural net component and pretend that because the search is external to the neural net, the neural net doesn't need the search.
And yet, without the search there is no dataset, and without the dataset there is no model. They didn't train their system by self-play and they certainly didn't hire an army of low-paid workers to annotate moves for them. They generated training moves with a search-based system and learned to reproduce them. They used chickens to make eggs.
Their approach depends entirely on there being a powerful chess search engine and they wouldn't be able to create their system without it as a main component. Their "without search" claim is just a marketing term.
The whole thing is just political: DeepMind use neural nets, GOFAI is dead and that's the way to AI. That's their story and they're sticking with it.
This has two possible applications: 1. There's far less need to invent techniques like MCTS in the first place. 2. A single AI might be able to play grandmaster level chess by accident.
The catch is you need high quality data in large amounts.
It could have luckily coalesced from gas (a Boltzmann egg), or perhaps even more radically, been laid by a duck.
you say
>They didn't train their system by self-play and they certainly didn't hire an army of low-paid workers to annotate moves for them.
So you are certainly aware that there are avenues to creating the data set. Given that, it is quite reasonable to say that search is unnecessary.
They should do one of those instead of using search before they claim it’s possible to not use search.
Or to borrow your analogy, you’ll need to show me a duck egg to prove you can make omelettes without chickens. Making an omelette from chicken eggs and claiming hypothetically some mystery other animal could have done it is nonsense.
How is it unnecessary? They used none of those methods, so they had to use search. That is search being necessary, not the opposite.
I just took it in the same way as saying that being a vegetarian is generally better for animal welfare, as you're not harming chickens as directly by eating an omelette, as you would by eating their wings.
It's like saying ChatGPT isn't a human brain.
It was trained with human brains. But it isn't a human brain.
It forced Stockfish to up its game, essentially by adopting neural techniques themselves (though a different type, Stockfish uses nnue).
I wonder how many time-annotated chess play logs are out there. (Between humans, I mean.)
I think that, to simulate worse human-like players, it would be better to just increase the temperature: don't always select the best move, at every step just select one of the top 10, randomly proportional to some function of the model-predicted probability of it being "the best" move (e.g. a power of the probability; very large powers give always the best move, i.e. the strongest player, and powers close to 0 tend to choose uniformly at random, i.e. the weakest player). The only thing I'm not certain about is, if you train the original network well enough, stupid blunders (that a very bad human player like me would make) are still scored so low that there's no way this algorithm will pick them up - the only way to know would be to try.
Engines already do this when you turn down their skill level. It does not lead to human-like play.
The problem is that bad (or just non-expert) human players don't make completely random mistakes. They tend to make very specific types of mistakes. For example, they may miss certain types of tactics, or underestimate king safety, or forget about hanging pieces.
In order to make a bot that feels like a human, you need to somehow capture the specific weaknesses that human players have.
> Our agent’s aggressive style is highly successful against human opponents and achieves a grandmasterlevel Lichess Elo of 2895. However, we ran another instance of the bot and allowed other engines to play it. Its estimated Elo was far lower, i.e., 2299. Its aggressive playing style does not work as well against engines that are adept at tactical calculations, particularly when there is a tactical refutation to a suboptimal move.
The idea that Tal mostly made dubious sacrifices is largely a myth heavily based in a joke he himself made. In actual fact he always did deep calculation and knew that no easy refutation existed, and that he had a draw by perpetual check in hand(until beaten by Ding a few years ago, Tal actually had the record streak of unbeaten games in classical chess). He was making calculated risks knowing his opponents would not be likely to outcalculate him. He also had a very deep understanding of positional play, he just had a very different style of expressing it, relying more on positional knowledge to create sharp positions centered around material imbalance.
They note that though in the paper:
>Since transformers may learn to roll out iterative computation (which arises in search) across layers, deeper networks may hold the potential for deeper unrolls.
Sure
>it’s also possible it has just memorized the evaluations from 10M games and is performing some function of the similarity of the input to those previously seen.
That's not possible. The possible set of moves in chess is incredibly large and it is incredibly easy to play a game that has diverged from training. a model that has just memorized all evaluations would break within ten or so moves tops much less withstand robust evaluations.
However this model may work exactly and how much or little it relies on search is unknown but it is no doubt a model of the world of chess. https://adamkarvonen.github.io/machine_learning/2024/01/03/c...
Neural nets memorize all sorts of things. They memorize ad clicks in high dimensional state spaces. Transformers trained on the whole internet can often reproduce entire texts. It’s lossy, but it’s still memorizing.
That seems like the simplest explanation for what’s happening here. There’s some sort of lossy memorization, not a search. The fact that the thing it has memorized is the result of a search doesn’t matter.
I don't have a "search hypothesis". I don't know what strategy the model employs to play. I was simply pointing out that limited search learned by the transformer is not out of the question. Stockfish finishing is not necessary to play chess well above the level a memorization hypothesis makes any sense. This is not the first LLM chess machine.
>Neural nets memorize all sorts of things. They memorize ad clicks in high dimensional state spaces. Transformers trained on the whole internet can often reproduce entire texts. It’s lossy, but it’s still memorizing.
Intelligent things memorize. Humans memorize a lot. I never said the model hasn't memorized a fair few things. Many human chess grandmaster memorize openings. What i'm saying is that it's not playing games via memorization any more than a human is doing the same.
>That seems like the simplest explanation for what’s happening here. There’s some sort of lossy memorization, not a search.
The options aren't only lossy memorization or lossless search.
>performing some function of the similarity of the input to those previously seen.
This is indeed what transformers do. But obviously it learns some sort of interpolation/extrapolation which lets it do well on board states/games outside the training set.
Edit: looking further than the abstract, this is rather an exploration of scale necessary for a strong engine. Could go without "without search" in the title I guess.
[1]: IIRC, it also uses a Leela-inspired NN for evaluation.
ChatGPT isn't human, but it was trained with humans.
To get the evaluation of the whole position, you add up all of these mappings for the pieces on the board with opposite signs for the opposing players.
If you blur your eyes a little, this already looks a lot like a neural net. It's just a big summation of terms, and if you leave in a 0*(whatever value) for every piece that's not present, you've effectively embedded your lookup table into a giant mathematical expression that can be optimised by gradient descent.
The reason computer shogi programmers stumbled on this is that they were experimenting with adding more dimensions to the piece-square table, specifically via indexing by king position as well. So now you have 4 or 5 dimensions, making for a pretty massive array. Hand-tuning all the values becomes less and less feasible, and so I think discovering this idea of rearchitecting it as a neural-net was more or less inevitable.
So NNUE is actually just a pretty natural evolution of what they were doing before.
For most games, if you can see a way to an end state within 3-5 steps under these idealized conditions, there's only so much that an actual opponent can do to make the board deviate from the initial static board state that you used in your assumption. The optimal strategy will always be just a few minor corrections of edit distance from this dumb no-theory-of-mind strategy. You can always be sure that whoever has the longer path to victory has to do something to interfere with the shorter path of their opponent, and there's only ever so many pieces which can interact with that shorter path. Meaning whatever path to victory is currently shortest short circuits the search for potential moves.
Chess against humen is different. Usually, there is no path to victory, only to remis. People just follow strategic plans that people told them would be slightly beneficial later on. Along following that strategic plan people mess up and the first one to realize that the opponent messed up usually wins. Like having a piece advantage of 2-3 is usually considered a win already.
I think this algorithm is better than many other algorithms that people come up with, however.
(As an aside, when I play a card game I sort my cards with a merge sort instead of an insertion sort. People said you would never use these algorithms in real life, but you can if you want to!)
Huh, guess I'm doing a sort of human heuristic version of Quicksort
"Improve the position of your worst placed piece."
For better players, determine which is most effective:
1 Improve the position of your worst placed piece.
2 Exchange or minimize the potential of your opponent's best-placed piece (e.g. trade off their bishop on a long diagonal)
3 Maximize the potential of your best-placed piece (sometimes by a sacrifice)
4 Prevent your opponent from developing some pieces
This is over-simplified, of course, but the balance of the position must be taken into account.
In higher level play it usually loses to opponents that are aware they're not playing alone, at least that's the case with bots that do in fact stay unaware of their opponent.
Take scholars mate for example. You can win in 4 moves from the initial position and it is an easy win if the opponent doesn't defend it but playing against someone that knows chess it is a horrible opening because it is easy to defend and leaves you in a weak position.
https://schach-computer.info/wiki/index.php?title=Novag_Supe...
https://www.schach-computer.info/wiki/index.php?title=Mephis...
“To prevent some of these situations, we check whether the predicted scores for all top five moves lie above a win percentage of 99% and double-check this condition with Stockfish, and if so, use Stockfish’s top move (out of these) to have consistency in strategy across time-steps.”
> We annotate each board in the dataset with action-values provided by the powerful Stockfish 16 engine, leading to roughly 15 billion data points.
So some of the learning data comes from Stockfish.
In training, traditional search is absolutely used to score positions.
In playing, search is not used. (*Except to finish out an already-won position.)
For winning any game at some point (at the end of the game) there will be a position with >99% winning chances. The move that follows are decisive.
Anyone that knows how to play can beat a GM with a big enough advantage at the end of the game (which is what's reflected in the win probability).
If Stockfish detects a mate-in-k (e.g., 3 or 5) it outputs k and not a centipawn score. We map all such outputs to the maximal value bin (i.e., a win percentage of 100%). Similarly, in a very strong position, several actions may end up in the maximum value bin. Thus, across time-steps this can lead to our agent playing somewhat randomly, rather than committing to one plan that finishes the game quickly (the agent has no knowledge of its past moves). This creates the paradoxical situation that our bot, despite being in a position of overwhelming win percentage, fails to take the (virtually) guaranteed win and might draw or even end up losing since small chances of a mistake accumulate with longer games (see Figure 4). To prevent some of these situations, we check whether the predicted scores for all top five moves lie above a win percentage of 99% and double-check this condition with Stockfish, and if so, use Stockfish’s top move (out of these) to have consistency in strategy across time-steps.
So they freely admit that their thing will draw or even lose in these positions. It's not merely making the win a little cleaner.
Yeah, they didn't use Stockfish for the lols.
They create a search-less engine for chess. And then used a search engine to pay a small minority of the game.
This is cheating, plain and simple. It would never fly in human play or competitive computer play. And it's most definitely disingenuous research. They made an engine, it plays a certain level, and then they augment it with preexisting software they didn't even write themselves to beef up their claims about it.
Except we're talking about moves where no human player would choke because they are basically impossible to lose except by playing at random (which is what the bot does).
It makes no sense to try and compare to a human player in the same situation because no human player could at the same time end up in such a position against a strong opponent and be unable to exploit them once there…
It's basically a bug, and what they did is just working around this particular bug in order to have a releasable paper.
Edit: Recently I brought some ancient (1978) chess software back to life https://github.com/billforsternz/retro-sargon. These two phases of chess, basically two different games, were quite noticeable with that program, which is chess software stripped back to the bone. Sargon 1978 could play decently well, but it absolutely did not have the technique to convert winning positions (because this is different challenge to regular chess). For example, it could not in general mate with rook (or even queen) and king against bare king. The technique of squeezing the enemy king into a progressively smaller box was unknown to it.
What if a human only used Stockfish in winning positions? Is it cheating? Obviously it is.
Grandmasters very literally do it all the time.
> What if a human only used Stockfish in winning positions? Is it cheating? Obviously it is.
Yes, but this isn't that.
This is a computer that is playing chess. And FYI (usually) without search.
> Indecisiveness in the face of overwhelming victory
> If Stockfish detects a mate-in-k (e.g., 3 or 5) it outputs k and not a centipawn score. We map all such outputs to the maximal value bin (i.e., a win percentage of 100%). Similarly, in a very strong position, several actions may end up in the maximum value bin. Thus, across time-steps this can lead to our agent playing somewhat randomly, rather than committing to one plan that finishes the game quickly (the agent has no knowledge of its past moves). This creates the paradoxical situation that our bot, despite being in a position of overwhelming win percentage, fails to take the (virtually) guaranteed win and might draw or even end up losing since small chances of a mistake accumulate with longer games (see Figure 4). To prevent some of these situations, we check whether the predicted scores for all top five moves lie above a win percentage of 99% and double-check this condition with Stockfish, and if so, use Stockfish’s top move (out of these) to have consistency in strategy across time-steps.
Chess is on my priority list for the next game. Now I know that ML strategy is on par with search algorithms.
It's on par with very strong humans, but not as good as a normal engine.
I'd be interested to see how well the ELO holds up when the model is quantized.
At INT8 a small transformer like this could have a pretty amazing speed and efficiency on an Edge TPU or other very low power accelerator chip. The question becomes then is it faster / more efficient than Stockfish 16 on a similarly powered CPU. As we've seen with LLM's, they can be extremely speedy when quantized and all the stops pulled out on hardware to efficiently infer them compared to the raw FP16 and naive implementations.
For one thing, statelessness deprives it of easy solutions to repetition and endgame decisiveness.
0. Have model A.
1. Use Monte Carlo with A to get supervised data.
2. Train model B with data from A.
3. Use Monte Carlo with B to get supervised data.
4. Train model C with data from B...
https://medium.com/applied-data-science/alphago-zero-explain...
But the "other stuff" is pretty important. That is what pulls it away from just constantly re-amplifying the bias in the initial training data.
For example, somewhere in the training data the string "All cats are red" should get detected when lots of other data in the training set contradicts the statement.
And obviously it doesn't have to be simple logical statements, but also bigger questions like "how come the 2nd world war happened despite X person and Y person being on good speaking terms as evidenced by all these letters in the archives?"
When AI can do that, it should be able to turn our body of knowledge into a much bigger/more useful one by raising questions that arise from data we already have, but never noticed.
Now arguably it’s doing it differently, maybe? But still a search
At the most basic level, the model is just giving probabilities for the next moves, or in the case of value approximation, guessing which bucket the value falls into.
Text generation without human writers
Image generation without human artists
Video generation without production crews
The impressive part about AlphaZero is that it did the Monte-Carlo Tree Search itself, without being trained on human decision-making.
While this ... well, this is just taking credit for all the search and work that was done by Stockfish, or humans, at a massive scale over centuries and then posted nearly for free online. It's then using all that data and generating similar stuff. Whoop de doo. Oh, and it's even used cheap labor for the last mile, too:
https://time.com/6247678/openai-chatgpt-kenya-workers/
It's not the same thing as actual search to, for example, automatically derive scientific laws (e.g. Kepler's laws of motion) from raw data fed to it (e.g. of star movements). AI doing that can actually model the real space, not the latent space. It can go out and learn without humans or stockfish massively bootstrapping its knowledge.
I mean, don't get me wrong ... learning a lot about the latent space is what students strive to do in schools and universities, and the AIs are like a very smart student. In fact, they can be huge polymaths and polyglots and therefore uncover a lot of interesting connections and logical deductions from the latent space. They can do so at a huge scale... and I have often said that swarms of AIs will be unstoppable. So at the end of the day, although this isn't very impressive when it comes to the credit of who did the search and curation, AI is going to be extremely impressive with what it can do with the results on the next N levels.
?
I know that computers have already beaten humans at Go. But what's interesting is that in both the chess and Go cases, a lot of real-time compute was necessary to win the games. Now we have a potential way to build the model ahead of time such that the computer during interactive play is much smaller.
This means that we can be much more portable with the solution, and it also means that for online game companies, they can spend a lot less money on gameplay, especially if gameplay is most of their compute.