10 ms·

Grandmaster-Level Chess Without Search

198 points by jonbaer 3y ago

fiforpg 3y ago
Given that they used position evaluation from (a search chess engine[1]) Stockfish, how is this "without search"? 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.
- throwaway81523 3y ago
  Leela without search supposedly plays around expert level, but I thought the no-search Leela approach ran out of gas around there. Without search there means evaluating 1 board position per move. The engine in the paper (per the abstract) use a big LLM instead of a Leela style DCNN.
- deleted 3y ago
  [deleted]
- paulddraper 3y ago
  Training uses search, but it plays without search. ChatGPT isn't human, but it was trained with humans.
  - karolist 3y ago
    So it's a space time trade-off then? Store enough searched and weighted positions into the model and infer them. In this way, inference is replacing Stockfish search, just less accurately, but much faster and with memory required for the model.
- porphyra 3y ago
  Does Stockfish really use a Leela-inspired NN? I thought the NNUE was independently developed and completely different (it's a very tiny network that runs on the CPU).
  - Oreb 3y ago
    This is true, but at least for a while (I’m not sure if it’s still the case), Leela data was used (along with data generated from Stockfish self-play) to train Stockfish’s NN.
  - mtlmtlmtlmtl 3y ago
    Yeah, NNUE is a separate invention that unfortunately, Deepmind often get undeserved credit for inspiring. It didn't even originate in chess engines but a shogi version of Stockfish. Architecture is completely different from the nets in Leela or Alpha Zero.
    - epups 3y ago
      Wait, so progress on Stockfish would happen regardless of Alpha Chess? I always thought they were inspired by it in the newer versions, and got much improved rating from incorporating it.
      - mtlmtlmtlmtl 3y ago
        Well, NNUE is surprisingly similar to what Stockfish was doing before NNUE. Before it was doing what's called piece-square tables. The basic idea(the stockfish evaluator had a lot more going on in addition, using multiple tables and interpolating between them based on game phase) is to assign some heuristic value to every square, for every piece. So it's just a 6x8x8 array that maps piece positions to values. 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.
zniturah 3y ago
They do use Stockfish for playing thought … “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.”
- paulddraper 3y ago
  But only to complete a winning position.
  - phoe-krk 3y ago
    From the abstract: > 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.
    - paulddraper 3y ago
      The original comment was "for playing." In training, traditional search is absolutely used to score positions. In playing, search is not used. (*Except to finish out an already-won position.)
  - zniturah 3y ago
    That 'only' usage in the winning position could be a decisive for gaining GM rating.
    - famouswaffles 3y ago
      Search isn't used to play/win here. Just for training.
      - cool_dude85 3y ago
        It looks like it does use search here in the sense that Stockfish's top move is generated using search.
xianshou 3y ago
The path to AGI: 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...
- spencerchubb 3y ago
  That is an awesome idea. I wish the authors would open source the code and weights so this can be tried.
  - bigmadshoe 3y ago
    They basically just described alphaZero, the difference being that alphaZero uses MCTS during inference too.
- rprenger 3y ago
  This is pretty close to how AlphaZero works. https://medium.com/applied-data-science/alphago-zero-explained-in-one-diagram-365f5abf67e0 https://medium.com/applied-data-science/alphago-zero-explain...
- jedberg 3y ago
  That's basically how OpenAI is working. They use generated training sets from one model to train the next model (plus other stuff with it). 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.
  - londons_explore 3y ago
    I still want to see some examples of a "mistake" in the training data getting detected or reduced. 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.
famouswaffles 3y ago
Well without explicit search would probably be more accurate. 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.
- janalsncm 3y ago
  We don’t know if it’s using implicit search either. While it would be interesting if the network was doing some internal search, 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.
  - famouswaffles 3y ago
    >We don’t know if it’s using implicit search either. 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/chess-world-models.html https://adamkarvonen.github.io/machine_learning/2024/01/03/c...
    - janalsncm 3y ago
      If it could reliably win a mate in N position without inexplicably blundering, I would be more inclined to buy your search hypothesis. But it doesn’t, which is one of the reasons the authors gave for finishing with stockfish. So whatever it’s doing is clearly lossy which an actual search would not be. 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.
salamo 3y ago
I think this is an interesting finding from a practical perspective. A function which can reliably approximate stockfish at a certain depth could replace it, basically "compressing" search to a set depth. And unlike NNUE which is optimized for CPU, a neural network is highly parallelizable on GPU meaning you could send all possible future positions (at depth N) through the network and use the results for a primitive tree search.
- sp332 3y ago
  The Stockfish installer is ~45 MB. At 16 bits per parameter, the 270B model would be over 500 MB. The 9B model would be smaller than Stockfish, but you could probably find a smaller chess engine that achieves 2000 ELO.
  - salamo 3y ago
    The advantage of this approach that we can run many simultaneous computations on the GPU/TPU. Instead of using maybe a dozen CPU threads, we can approximate the value of a few thousand positions at the same time.
  - shmageggy 3y ago
    Dedicated chess computers were hitting 2000 ELO with an 8-bit 6502 running at <10MHz in the late 1980s. The Novag Super expert had 96KB of ROM, which also included the opening book, so yeah, quite a bit smaller. https://schach-computer.info/wiki/index.php?title=Novag_Super_Expert https://schach-computer.info/wiki/index.php?title=Novag_Supe... https://www.schach-computer.info/wiki/index.php?title=Mephisto_MM_V https://www.schach-computer.info/wiki/index.php?title=Mephis...
paulddraper 3y ago
There is rampant misunderstanding of some parts of this article; allow me to help :) 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.
- zniturah 3y ago
  "Aready won position" or "99% win rate" is statistics given by Stockfish (or professional chess player). It is weird to assume that the same statement is true for the trained LLM since we are assessing the LLM itself. If it is using during the game then it is searching, thus the title doesn't reflect the actual work.
  - dmurray 3y ago
    It's quite clear from the article that the 99% is the model's predicted win rate for a position, not its evaluation by Stockfish (which doesn't return evaluations in those terms). 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.
    - im3w1l 3y ago
      Human players have this concept of progress. I couldn't give a good succinct description of exactly what that entails, but basically if you are trading off pieces that's progress, if your king is breaking through the defensive formation of the pawn endgame that's progress. If you are pushing your passed pawn up the board that's progress. If you are slowly constricting the other king that's progress. 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.
jedberg 3y ago
Now do Go. :)
- Kon5ole 3y ago
  This used to be a comforting thought whenever computers beat humans in chess, but I think that time has passed. The paper mentions AlphaZero [1], which has beaten AlphaGo, which beat Lee Sedol back in 2016 [2]. [1] https://en.wikipedia.org/wiki/AlphaZero https://en.wikipedia.org/wiki/AlphaZero [2] https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol
  - jedberg 3y ago
    My pithy comment probably wasn't enough to express what I meant. :) 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.
IIAOPSW 3y ago
Slightly off topic but am I the only one that approaches strategy games by making a "zeroth order approximation". Eg find the shortest path to victory under the (obviously faulty) assumption that my opponent does nothing and the board is unchanging except for my moves. Now find my opponents shortest path to victory under the same assumption. Then evaluate, if we both just ignore each other and try to bum rush the victory condition, who gets there first? 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.
- xbpx 3y ago
  That's why white has a higher statistical win rate ya?
  - pixelpoet 3y ago
    Only if you play on the Tengen point.
- dayjaby 3y ago
  On beginner level this might work, but if people are more competitive they begin to realize the benefit of not only playing the own game, but reading the enemies plan (e.g. scouting in Starcraft/AoE2) to counteract it as much as possible. 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.
  - 3y ago
ivanjermakov 3y ago
I thought clickbaity titles were discouraged in whitepaper world.
bjourne 3y ago
That must mean they found some similarity metric for high-level chess which is very impressive. In chess one pawn moving one square can be the difference between a won and a lost position. But knowing that usually requires lots of calculation.
iamcreasy 3y ago
I guess this current method is not applicable to have the model explain why a given move was played as it is not planning more than one more ahead. Very cool, nonetheless.
penjelly 3y ago
i dont follow... even if its trained anc doesnt use search isnt the act of it deciding the next move a sortof search anyway based off its training? Ive heard people describe LLMs as extremely broad search, basically attempting to build world model and then predicting the next world based on that. Is this fundamentally different from search? Am i wrong in my assumptions here?
- janalsncm 3y ago
  We know the model is approximating the results of a search. We don’t know whether it is actually searching. 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.
tromp 3y ago
While its performance against humans is very impressive indeed, its performance against engines is somewhat less so: > 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.
- chongli 3y ago
  I like this even more that I’ve read that. That sounds like it makes this agent a much more human-like player than the perfect calculator traditional chess engines. It may end up being more fun for humans to play against if it’s strong but has holes in its play.
  - dev_tty01 3y ago
    I suppose. I wonder if one can adjust the engine's skill level.
- aexl 3y ago
  This sounds a lot like Mikhail Tal!
  - mtlmtlmtlmtl 3y ago
    Not really. Mikhail Tal was easily one of the strongest calculators in chess history. Definitely the strongest in his time besides maybe Fischer. 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.
asah 3y ago
imho fascinating experiment, even if it didn't produce world class Elo. For one thing, statelessness deprives it of easy solutions to repetition and endgame decisiveness.
charcircuit 3y ago
argmax and argmin are searching. Just because it isn't a search with a lot of depth that doesn't mean it isn't searching.
verteu 3y ago
How much of this "grandmaster-level" play is an artifact of low time controls? I notice they only achieve GM ELO in Blitz against humans, achieve significantly worse ELO against bots, and do not provide the "Lichess Blitz ELO" of any of their benchmark approaches.
- actionfromafar 3y ago
  I wonder if one could make a neural net play human-like, at various levels, by for instance training smaller or larger nets. And by human-like, I don't mean ELO level, but more like the Turing tests - "does this feel like playing against a human?" I wonder how many time-annotated chess play logs are out there. (Between humans, I mean.)
  - spi 3y ago
    I suppose varying the neural net size wouldn't be the best way of doing that; very small nets can have very "unhuman-like" behaviour. I'm not an expert on reinforcement learning, but for other fields in deep learning that's typically the case. 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.
    - DiogenesKynikos 3y ago
      > don't always select the best move, at every step just select one of the top 10 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.
KingOfCoders 3y ago
"We annotate each board in the dataset with action-values provided by the powerful Stockfish 16 engine, leading to roughly 15 billion data points [...] without any domain-specific tweaks or explicit search algorithms." ?
lettergram 3y ago
I immediately saw this and knew it was BS. It’s a search problem, the human brain even does a search. Model internally is scanning each position and determining the next probably position. That is a predictive search, you can’t just restructure the problem. Now arguably it’s doing it differently, maybe? But still a search
ad8e 3y ago
A quote from discord: "apparently alpha-zero has been replicated in open source as leela-zero, and then leela-zero got a bunch of improvements so it's far ahead of alpha-zero. but leela-zero was barely mentioned at all in the paper; it was only dismissed in the introduction and not compared in the benchmarks. in the stockfish discord they are saying that leela zero can already do everything in this paper including using the transformer architecture."
- shmageggy 3y ago
  Yeah, they need to compare against the latest BT2 policy head. It's probably about the same performance.
  - chaeronanaut 3y ago
    BT2 is old news, we have BT4 now
- isaacfrond 3y ago
  Leela zero was an amazing project improving on AlphaZero, showing the feasibility of large scale training with contributed cycles, and snatching the TCEC crown in Season 16 It forced Stockfish to up its game, essentially by adopting neural techniques themselves (though a different type, Stockfish uses nnue).
paradite 3y ago
Nice. I build AI-driven puzzle games where you can pick algorithms, tune parameters, or train ML models to play the game. Chess is on my priority list for the next game. Now I know that ML strategy is on par with search algorithms.
- im3w1l 3y ago
  > 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.
mtlmtlmtlmtl 3y ago
Grandmaster level chess for a computer is a massive, massive regression. Big whoop.
mk_stjames 3y ago
270M parameters at I guess FP/BF16? 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.
EGreg 3y ago
Next up, claims of ... Text generation without human writers Image generation without human artists Video generation without production crews The rub is that all the training data has been done by lots and lots of search, human writing, human artists, and human production crews. At every step, they curated the results and generated a beautiful latent space that the model was then trained on. 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/ 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.
- red75prime 3y ago
  I would very much prefer a model trained on human data that had absorbed a part of human values, than a completely de novo intelligence that bootstrapped itself using experimentation in the physical world.

198 points by jonbaer 3y ago

Given that they used position evaluation from (a search chess engine[1]) Stockfish, how is this "without search"? 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.

throwaway81523 3y ago
Leela without search supposedly plays around expert level, but I thought the no-search Leela approach ran out of gas around there. Without search there means evaluating 1 board position per move. The engine in the paper (per the abstract) use a big LLM instead of a Leela style DCNN.
deleted 3y ago
[deleted]
paulddraper 3y ago
Training uses search, but it plays without search. ChatGPT isn't human, but it was trained with humans.
- karolist 3y ago
  So it's a space time trade-off then? Store enough searched and weighted positions into the model and infer them. In this way, inference is replacing Stockfish search, just less accurately, but much faster and with memory required for the model.
porphyra 3y ago
Does Stockfish really use a Leela-inspired NN? I thought the NNUE was independently developed and completely different (it's a very tiny network that runs on the CPU).
- Oreb 3y ago
  This is true, but at least for a while (I’m not sure if it’s still the case), Leela data was used (along with data generated from Stockfish self-play) to train Stockfish’s NN.
- mtlmtlmtlmtl 3y ago
  Yeah, NNUE is a separate invention that unfortunately, Deepmind often get undeserved credit for inspiring. It didn't even originate in chess engines but a shogi version of Stockfish. Architecture is completely different from the nets in Leela or Alpha Zero.
  - epups 3y ago
    Wait, so progress on Stockfish would happen regardless of Alpha Chess? I always thought they were inspired by it in the newer versions, and got much improved rating from incorporating it.
    - mtlmtlmtlmtl 3y ago
      Well, NNUE is surprisingly similar to what Stockfish was doing before NNUE. Before it was doing what's called piece-square tables. The basic idea(the stockfish evaluator had a lot more going on in addition, using multiple tables and interpolating between them based on game phase) is to assign some heuristic value to every square, for every piece. So it's just a 6x8x8 array that maps piece positions to values. 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.

zniturah 3y ago

They do use Stockfish for playing thought … “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.”

paulddraper 3y ago
But only to complete a winning position.
- phoe-krk 3y ago
  From the abstract: > 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.
  - paulddraper 3y ago
    The original comment was "for playing." In training, traditional search is absolutely used to score positions. In playing, search is not used. (*Except to finish out an already-won position.)
- zniturah 3y ago
  That 'only' usage in the winning position could be a decisive for gaining GM rating.
  - famouswaffles 3y ago
    Search isn't used to play/win here. Just for training.
    - cool_dude85 3y ago
      It looks like it does use search here in the sense that Stockfish's top move is generated using search.

xianshou 3y ago

The path to AGI: 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...

spencerchubb 3y ago
That is an awesome idea. I wish the authors would open source the code and weights so this can be tried.
- bigmadshoe 3y ago
  They basically just described alphaZero, the difference being that alphaZero uses MCTS during inference too.
rprenger 3y ago
This is pretty close to how AlphaZero works. https://medium.com/applied-data-science/alphago-zero-explained-in-one-diagram-365f5abf67e0 https://medium.com/applied-data-science/alphago-zero-explain...
jedberg 3y ago
That's basically how OpenAI is working. They use generated training sets from one model to train the next model (plus other stuff with it). 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.
- londons_explore 3y ago
  I still want to see some examples of a "mistake" in the training data getting detected or reduced. 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.

famouswaffles 3y ago

Well without explicit search would probably be more accurate. 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.

janalsncm 3y ago
We don’t know if it’s using implicit search either. While it would be interesting if the network was doing some internal search, 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.
- famouswaffles 3y ago
  >We don’t know if it’s using implicit search either. 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/chess-world-models.html https://adamkarvonen.github.io/machine_learning/2024/01/03/c...
  - janalsncm 3y ago
    If it could reliably win a mate in N position without inexplicably blundering, I would be more inclined to buy your search hypothesis. But it doesn’t, which is one of the reasons the authors gave for finishing with stockfish. So whatever it’s doing is clearly lossy which an actual search would not be. 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.

salamo 3y ago

I think this is an interesting finding from a practical perspective. A function which can reliably approximate stockfish at a certain depth could replace it, basically "compressing" search to a set depth. And unlike NNUE which is optimized for CPU, a neural network is highly parallelizable on GPU meaning you could send all possible future positions (at depth N) through the network and use the results for a primitive tree search.

sp332 3y ago
The Stockfish installer is ~45 MB. At 16 bits per parameter, the 270B model would be over 500 MB. The 9B model would be smaller than Stockfish, but you could probably find a smaller chess engine that achieves 2000 ELO.
- salamo 3y ago
  The advantage of this approach that we can run many simultaneous computations on the GPU/TPU. Instead of using maybe a dozen CPU threads, we can approximate the value of a few thousand positions at the same time.
- shmageggy 3y ago
  Dedicated chess computers were hitting 2000 ELO with an 8-bit 6502 running at <10MHz in the late 1980s. The Novag Super expert had 96KB of ROM, which also included the opening book, so yeah, quite a bit smaller. https://schach-computer.info/wiki/index.php?title=Novag_Super_Expert https://schach-computer.info/wiki/index.php?title=Novag_Supe... https://www.schach-computer.info/wiki/index.php?title=Mephisto_MM_V https://www.schach-computer.info/wiki/index.php?title=Mephis...

paulddraper 3y ago

There is rampant misunderstanding of some parts of this article; allow me to help :) 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.

zniturah 3y ago
"Aready won position" or "99% win rate" is statistics given by Stockfish (or professional chess player). It is weird to assume that the same statement is true for the trained LLM since we are assessing the LLM itself. If it is using during the game then it is searching, thus the title doesn't reflect the actual work.
- dmurray 3y ago
  It's quite clear from the article that the 99% is the model's predicted win rate for a position, not its evaluation by Stockfish (which doesn't return evaluations in those terms). 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.
  - im3w1l 3y ago
    Human players have this concept of progress. I couldn't give a good succinct description of exactly what that entails, but basically if you are trading off pieces that's progress, if your king is breaking through the defensive formation of the pawn endgame that's progress. If you are pushing your passed pawn up the board that's progress. If you are slowly constricting the other king that's progress. 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.

jedberg 3y ago

Now do Go. :)

Kon5ole 3y ago
This used to be a comforting thought whenever computers beat humans in chess, but I think that time has passed. The paper mentions AlphaZero [1], which has beaten AlphaGo, which beat Lee Sedol back in 2016 [2]. [1] https://en.wikipedia.org/wiki/AlphaZero https://en.wikipedia.org/wiki/AlphaZero [2] https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol https://en.wikipedia.org/wiki/AlphaGo_versus_Lee_Sedol
- jedberg 3y ago
  My pithy comment probably wasn't enough to express what I meant. :) 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.

IIAOPSW 3y ago

Slightly off topic but am I the only one that approaches strategy games by making a "zeroth order approximation". Eg find the shortest path to victory under the (obviously faulty) assumption that my opponent does nothing and the board is unchanging except for my moves. Now find my opponents shortest path to victory under the same assumption. Then evaluate, if we both just ignore each other and try to bum rush the victory condition, who gets there first? 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.

xbpx 3y ago
That's why white has a higher statistical win rate ya?
- pixelpoet 3y ago
  Only if you play on the Tengen point.
dayjaby 3y ago
On beginner level this might work, but if people are more competitive they begin to realize the benefit of not only playing the own game, but reading the enemies plan (e.g. scouting in Starcraft/AoE2) to counteract it as much as possible. 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.
- 3y ago

ivanjermakov 3y ago

I thought clickbaity titles were discouraged in whitepaper world.

bjourne 3y ago

That must mean they found some similarity metric for high-level chess which is very impressive. In chess one pawn moving one square can be the difference between a won and a lost position. But knowing that usually requires lots of calculation.

iamcreasy 3y ago

I guess this current method is not applicable to have the model explain why a given move was played as it is not planning more than one more ahead. Very cool, nonetheless.

penjelly 3y ago

i dont follow... even if its trained anc doesnt use search isnt the act of it deciding the next move a sortof search anyway based off its training? Ive heard people describe LLMs as extremely broad search, basically attempting to build world model and then predicting the next world based on that. Is this fundamentally different from search? Am i wrong in my assumptions here?

janalsncm 3y ago
We know the model is approximating the results of a search. We don’t know whether it is actually searching. 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.

tromp 3y ago

While its performance against humans is very impressive indeed, its performance against engines is somewhat less so: > 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.

chongli 3y ago
I like this even more that I’ve read that. That sounds like it makes this agent a much more human-like player than the perfect calculator traditional chess engines. It may end up being more fun for humans to play against if it’s strong but has holes in its play.
- dev_tty01 3y ago
  I suppose. I wonder if one can adjust the engine's skill level.
aexl 3y ago
This sounds a lot like Mikhail Tal!
- mtlmtlmtlmtl 3y ago
  Not really. Mikhail Tal was easily one of the strongest calculators in chess history. Definitely the strongest in his time besides maybe Fischer. 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.

asah 3y ago

imho fascinating experiment, even if it didn't produce world class Elo. For one thing, statelessness deprives it of easy solutions to repetition and endgame decisiveness.

charcircuit 3y ago

argmax and argmin are searching. Just because it isn't a search with a lot of depth that doesn't mean it isn't searching.

verteu 3y ago

How much of this "grandmaster-level" play is an artifact of low time controls? I notice they only achieve GM ELO in Blitz against humans, achieve significantly worse ELO against bots, and do not provide the "Lichess Blitz ELO" of any of their benchmark approaches.

actionfromafar 3y ago
I wonder if one could make a neural net play human-like, at various levels, by for instance training smaller or larger nets. And by human-like, I don't mean ELO level, but more like the Turing tests - "does this feel like playing against a human?" I wonder how many time-annotated chess play logs are out there. (Between humans, I mean.)
- spi 3y ago
  I suppose varying the neural net size wouldn't be the best way of doing that; very small nets can have very "unhuman-like" behaviour. I'm not an expert on reinforcement learning, but for other fields in deep learning that's typically the case. 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.
  - DiogenesKynikos 3y ago
    > don't always select the best move, at every step just select one of the top 10 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.

KingOfCoders 3y ago

"We annotate each board in the dataset with action-values provided by the powerful Stockfish 16 engine, leading to roughly 15 billion data points [...] without any domain-specific tweaks or explicit search algorithms." ?

lettergram 3y ago

I immediately saw this and knew it was BS. It’s a search problem, the human brain even does a search. Model internally is scanning each position and determining the next probably position. That is a predictive search, you can’t just restructure the problem. Now arguably it’s doing it differently, maybe? But still a search

ad8e 3y ago

A quote from discord: "apparently alpha-zero has been replicated in open source as leela-zero, and then leela-zero got a bunch of improvements so it's far ahead of alpha-zero. but leela-zero was barely mentioned at all in the paper; it was only dismissed in the introduction and not compared in the benchmarks. in the stockfish discord they are saying that leela zero can already do everything in this paper including using the transformer architecture."

shmageggy 3y ago
Yeah, they need to compare against the latest BT2 policy head. It's probably about the same performance.
- chaeronanaut 3y ago
  BT2 is old news, we have BT4 now
isaacfrond 3y ago
Leela zero was an amazing project improving on AlphaZero, showing the feasibility of large scale training with contributed cycles, and snatching the TCEC crown in Season 16 It forced Stockfish to up its game, essentially by adopting neural techniques themselves (though a different type, Stockfish uses nnue).

paradite 3y ago

Nice. I build AI-driven puzzle games where you can pick algorithms, tune parameters, or train ML models to play the game. Chess is on my priority list for the next game. Now I know that ML strategy is on par with search algorithms.

im3w1l 3y ago
> 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.

mtlmtlmtlmtl 3y ago

Grandmaster level chess for a computer is a massive, massive regression. Big whoop.

mk_stjames 3y ago

270M parameters at I guess FP/BF16? 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.

EGreg 3y ago

Next up, claims of ... Text generation without human writers Image generation without human artists Video generation without production crews The rub is that all the training data has been done by lots and lots of search, human writing, human artists, and human production crews. At every step, they curated the results and generated a beautiful latent space that the model was then trained on. 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/ 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.

red75prime 3y ago
I would very much prefer a model trained on human data that had absorbed a part of human values, than a completely de novo intelligence that bootstrapped itself using experimentation in the physical world.