18 ms·

Grandmaster-level chess without search

365 points by lawrenceyan 2y ago

hlfshell 2y ago
I did a talk about this! (And also wrote up about my talk here[1]). This paper is a great example of both knowledge distillation. It's less of a paper about chess and more about how complicated non linear search functions - complete with whatever tuning experts can prepare - can be distilled into a (quasi-linear, if it's a standardized input like chess) transformer model. [1]: https://hlfshell.ai/posts/deepmind-grandmaster-chess-without-search/ https://hlfshell.ai/posts/deepmind-grandmaster-chess-without...
- janalsncm 2y ago
  I think the vs. humans result should be taken with a huge grain of salt. These are blitz games, and their engine’s elo was far higher against humans than against other bots. So it’s likely that time was a factor, where humans are likely to flag (run out of time) or blunder in low time situations. It’s still very cool that they could learn a very good eval function that doesn’t require search. I would’ve liked the authors to throw out the games where the Stockfish fallback kicked in though. Even for a human, mate in 2 vs mate in 10 is the difference between a win and a draw/loss on time. I also would’ve liked to see a head to head with limited search depth Stockfish. That would tell us approximately how much of the search tree their eval function distilled.
  - hlfshell 2y ago
    The reason the time (blitz) games make sense is because the distilled functionality is of a 50ms Stockfish eval function. The engine likely would perform worse as only the human would benefit from the additional time. As for limited search tree I like the idea! I think it's tough to measure, since the time it takes to perform search across various depths vary wildly based on the complexity of the position. I feel like you would have to compile a dataset of specific positions identified to require significant depth of search to find a "good" move.
    - janalsncm 2y ago
      My point is that if the computer never flags it will have an inherent advantage in low time controls. If not, why not just test it in hyperbullet games? Games where humans flag in a drawn or winning position need to be excluded, otherwise it’s unclear what this is even measuring. And limited depth games would not have been difficult to run. You can run a limited search Stockfish on a laptop using the UCI protocol: https://github.com/official-stockfish/Stockfish/wiki/UCI-%26-Commands https://github.com/official-stockfish/Stockfish/wiki/UCI-%26...
    - codeflo 2y ago
      But the headline is “GM-level performance without search”, not “computer beats human at mouse movement speed contest”.
joelthelion 2y ago
I wonder if you could creatively combine this model with search algorithms to advance the state of the art in computer chess? I wouldn't be surprised to see such a bot pop up on tcec in a couple years.
- alfalfasprout 2y ago
  The thing is classical chess (unlike eg; go) is essentially "solved" when run on computers capable of extreme depth. Modern chess engines play essentially flawlessly.
  - KK7NIL 2y ago
    The developers of stockfish and lc0 (and the many weaker engines around) would disagree, we've seen their strength improve considerably over the last few years. Currently there's a very interesting war between small neural networks on the CPU with high search depth alpha-beta pruning (stockfish NNUE) and big neural networks on a GPU with Monte Carlo search and lower depth (lc0). So, while machines beating humans is "solved", chess is very far from solved (just ask the guys who have actually solved chess endgames with 8 or less pieces).
    - GaggiX 2y ago
      Stockfish and lc0 would always draw if they are not put in unbalanced starting positions, the starting position will be swapped in the next game to make it fair.
      - KK7NIL 2y ago
        In classical controls (what TCEC mainly uses), yes. They can play pretty exciting bullet chess without a forced opening though.
    - KolmogorovComp 2y ago
      > ask the guys who have actually solved chess endgames with 8 or less pieces Source?
dgraph_advocate 2y ago
This is missing a makefile to automate the manual installation steps
ChrisArchitect 2y ago
Associated discussion on the paper: Grandmaster-Level Chess Without Search https://news.ycombinator.com/item?id=39301944 https://news.ycombinator.com/item?id=39301944
tzs 2y ago
OT: what's the state of the art in non-GM level computer chess? Say I want to play chess with an opponent that is at about the same skill level as me, or perhaps I want to play with an opponent about 100 rating points above me for training. Most engines let you dumb them down by cutting search depth, but that usually doesn't work well. Sure, you end up beating them about half the time if you cut the search down enough but it generally feels like they were still outplaying you for much of the game and you won because they made one or two blunders. What I want is a computer opponent that plays at a level of my choosing but plays a game that feels like that of a typical human player of that level. Are there such engines?
- rtlaker 2y ago
  No, not with adjustable rating. The best human-like engine is fairymax, but its Elo is estimated between 1700-2000.
- danielmarkbruce 2y ago
  It doesn't seem that difficult to pull off - take one of the existing engines, get the top y moves, choose randomly. For each level down increase y by 1.
  - agubelu 2y ago
    It doesn't work that way. There are many positions with lots of moves that are reasonable, but many others with only 1-2 sensible moves. It would make lots of obvious blunders that an amateur human would never make.
    - chmod775 2y ago
      Also attention. Lower level human players are more likely to make a move close to their own/their opponent's recent move. They're focused on one area of the board. Basic computer opponents on the other hand can make moves all over the place. They look at the board state holistically. This can be very frustrating to play against as a human who has enough problems just thinking their way through some subset of the board, but is thrown off by the computer again and again. It's not that bad in chess at least (compared to Go), but still something worth to keep in mind if you're trying to make an AI that is fun to play against as an amateur.
osti 2y ago
https://lczero.org/blog/2024/02/how-well-do-lc0-networks-compare-to-the-greatest-transformer-network-from-deepmind/ https://lczero.org/blog/2024/02/how-well-do-lc0-networks-com... The best neural network chess engine's authors wrote about this deepminds publication.
- stabbles 2y ago
  LC0 hasn't been the best neural network chess engine since Stockfish added NNUE in 2020.
  - vlovich123 2y ago
    That isn’t quite accurate. Stockfish’s NNUE was trained against Leela evaluated positions. > Generally considered to be the strongest GPU engine, it continues to provide open data which is essential for training our NNUE networks. They released version 0.31.1 of their engine a few weeks ago, check it out! The main difference is that Stockfish is targeting to run on the CPU while Leela targets the GPU. That stockfish is able to be competitive with Leela is of course impressive. https://lichess.org/@/StockfishNews/blog/stockfish-17-is-here/7LRhV68w https://lichess.org/@/StockfishNews/blog/stockfish-17-is-her...
  - osti 2y ago
    True, but since stockfish uses a way way smaller network, I still prefer to think of stockfish as the traditional engine.
YeGoblynQueenne 2y ago
Excellent work but I suggest a slightly different title: "What would Stockfish Do?" A more appropriate title; because Stockfish is a search-base system and DeepMind's approach wouldn't work without it. Oh, btw, this is (yet another) a Neurosymbolic system of the "compiling system 2 to system 1" type.
jackmalpo 2y ago
what i would love is an engine that thinks more like a human. presumably since this uses stockfish annotated games, it basically ends up thinking like a computer. thinking like a human would be awesome for game reviews to walk through things to note in different positions (tuned to my elo).
- levocardia 2y ago
  Or a model whose performance is measured via its efficiency of learning--in other words, how many games does it need to play to learn to play at X level? The reason Magnus Carlsen is impressive is because he's reached his ability level in chess under enormous time and computation constraints, compared to a computer. His efficiency of learning is extraordinary compared to that of any chess engine.
- 7373737373 2y ago
  Or even the opposite end of the spectrum - with extremely limited resources (memory/program size/computation time): https://rlc-chess.com/ https://rlc-chess.com/ - like demoscene programs. Capable 1kb chess programs exist!
imranhou 2y ago
From the page: "We also show that our model outperforms AlphaZero's policy and value networks (without MCTS) and GPT-3.5-turbo-instruct." Why compare this to GPT-3.5-turbo-instruct? Is that near SOTA in this space?
- famouswaffles 2y ago
  As far as anyone knows, 3.5-turbo-instruct is the best chess playing (certainly it was at the time of the paper) LLM. About 1800 Elo and < 0.1% Illegal move rate. It's unclear why it was so much better than 4 (lack of RLHF?, Data?) and I don't know if anyone has bothered to test 4o similarly but it was pretty big news online at the time.
  - Davidzheng 2y ago
    OA definitely purposefully trained its chess strength
    - famouswaffles 2y ago
      I'm sure they did but there's no reason to believe they pretrained it on chess anymore than 4 so there's some speculation the post training processes mess things up. Turbo instruct does not go through RLHF for instance.
RayVR 2y ago
I forget the rough adjustment factors, but it is worth noting that lichess Elo is not the same as chess.com or FIDE. I think lichess is typically ~300 points above chess.com. This implies the model is around 2500 blitz vs humans. As blitz elo are often much higher than in classical time controls, 2500 elo on chess.com places it firmly in the 'good but not great' level. I am very curious to know whether the model suffers from the same eval problems vs the well known "anti-bot" openings that stockfish is susceptible to at limited search depths.
- gpm 2y ago
  > I think lichess is typically ~300 points above chess.com. Yeah, no. They are two different rating systems (not ELO incidentally) with different curves, there isn't a fixed difference you can apply. At the high end of the scale lichess ratings are below, not above, chess.com ratings. E.g. Magnus Carlsen is 3131 blitz on lichess [0], 3294 blitz on chess.com [1]. This website [2] tries to translate between the sites, and figures that a 2925 lichess blitz rating (the closet on the website to the one reported in the paper of 2895) translates to 3000 chess.com. [0] Multiple accounts but this is the one I found with the most blitz games: https://lichess.org/@/DrNykterstein/perf/blitz https://lichess.org/@/DrNykterstein/perf/blitz [1] https://www.chess.com/member/magnuscarlsen https://www.chess.com/member/magnuscarlsen [2] https://chessgoals.com/rating-comparison/#lichesschesscom https://chessgoals.com/rating-comparison/#lichesschesscom
  - jdck1326 2y ago
    Elo. Not acronym, named for its inventor Arpad Emmerich Elo https://en.wikipedia.org/wiki/Elo_rating_system https://en.wikipedia.org/wiki/Elo_rating_system
  - RayVR 2y ago
    Cool, thanks for the information! I did not realize the curves were that different. 3000 definitely bumps it up but it would still be worse than the top humans. stockfish is better by a lot.
- deleted 2y ago
  [deleted]
rawsh 2y ago
You can actually get solid performance with pretrained chat models: https://raw.sh/posts/chess_puzzles https://raw.sh/posts/chess_puzzles On lichess puzzles gpt4o with the compiled prompt is around 70%, I think the 270M transformer is around 95%
- sinuhe69 2y ago
  It depends on the difficulties of the puzzles. If you read the article of the Leela author, (link cited by other comment), then you will see a much different picture: the new DeepMind is better then AlphaZero but much worse than the best open source model. Not specially trained transformer like ChatGPT4o (and even 5o) has absolutely no chance to solve the more difficult puzzles.
squidgedcricket 2y ago
Would it be feasible to create a complete lookup table of 'best' moves for all given board configurations? I'm not sure how to determine the total number of configurations. Not the same as a tablebase, just a single next move rather than sequence to checkmate. It wouldn't be competitive against top tier players and AI, but I wouldn't be surprised if it could beat me. 'Instantly' knowing the next move would be a cool trick.
- k2xl 2y ago
  The amount of data that would be required for a lookup table for all best moves for every board configuration would be infeasible. They have managed to create one for 7 pieces. Last update on trying to get to 8 piece database: https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-progress-update-and-some-results https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-...
  - squidgedcricket 2y ago
    Yup, and it looks like a complete tablebase from the start of the game won't ever be feasible. > From May to August 2018 Bojun Guo generated 7-piece tables. The 7-piece tablebase contains 423,836,835,667,331 unique legal positions in about 18 Terabytes.
  - andrelaszlo 2y ago
    Almost halfway there ;)
    - jeremyjh 2y ago
      There are 32 pieces on the board at the start of the game.
- jeremyjh 2y ago
  There are more possible chess games than there are atoms in the universe. It can't be solved by brute force.
Scene_Cast2 2y ago
If anyone is looking to get into chess neural nets, I highly recommend this repo - https://github.com/sgrvinod/chess-transformers https://github.com/sgrvinod/chess-transformers It uses paradigmatic PyTorch with easy to read code, and the architecture is similar to the current best performing chess neural nets.
sourcepluck 2y ago
I believe GM and chess author (and all-round lovely fellow) Matthew Sadler rigged up Leela Zero to effectively play off intuition and do very little or no search for training games. He could usually beat it, but not always. Think it might have been in The Silicon Road to Chess Improvement.
- Davidzheng 2y ago
  I mean for lczero you can just set the max depth at 1 ply for example
  - sourcepluck 2y ago
    Oh, maybe it was that simple!
- Scarblac 2y ago
  He also has very entertaining Youtube videos about the kind of wild opening discoveries Leela comes up with when contempt is set really high (ie it wants to maximally avoid draws), combined with his 2700+ commentary on them.
barelyusable 2y ago
What are some of the go-to books/articles for computer chess? I like the game and have a decent understanding of basics, so studying algorithms based on the game would be a good opportunity for me to learn conventional algos, but also RL/ML/MCTS etc. Also I wonder what is the go-to codebase these days?
- janalsncm 2y ago
  Stockfish and Leela are the two best engines and they’re both on GitHub. Although I will say they are hyperoptimized to win. You can also ask any noob questions on their Discords.
- sinuhe69 2y ago
  https://www.chessprogramming.org/ https://www.chessprogramming.org/ Is the portal to go. From there, you can dig deeper in many relevant themes.
dougSF70 2y ago
Slightly off topic but I built https://chessladders.com https://chessladders.com
- 1bit_e 2y ago
  Nice! I built https://www.chesspuzzlebot.com/ https://www.chesspuzzlebot.com/ (Puzzles against stockfish)
xiaodai 2y ago
this paper is so dumb. so you modeled the output of stockfish? stockfish does use simulation or selfplay or search. so you've outsourced search and dont do it yourself so you can claim to be "without search"
- hilux 2y ago
  Do you understand how ML models are trained?
- scotty79 2y ago
  I think what they say is valid. Same way ChatGPT can answer questions google could answer without doing any search like google does.
BoardsOfCanada 2y ago
It's somewhat telling that they chose Stockfish as the oracle and not AlphaZero.
- Davidzheng 2y ago
  It's well established that SF today is stronger. Btw this is pretty bullish case for open source recreations of RL advancements to be catching up with ~2 year lag. Hopefully alphaproof is also reproduced in that timeframe
- epolanski 2y ago
  Stockfish is stronger than AlphaZero or any other chess engine from quite some time. Another interesting tidbit, both engines share (or at least, shared) the same lead developer.
  - vlovich123 2y ago
    To be fair though, deep mind hasn’t been working to improve alpha zero for chess playing. Their focus is a bit difference than the dedicated volunteers working on stockfish (+ it’s been a few years)
bicsi 2y ago
They built a dumber clone of Stockfish, and they call it ‘zero’ for some reason. What is the meaning behind ‘zero’ anyways? It used to refer to zero-shot, but now it seems like it’s just a marketing term.
- ralegh 2y ago
  I assume it's 'zero' turns lookahead/search, i.e. only look at the current board state.
- janalsncm 2y ago
  I assume you’re referring to AlphaZero and Leela Chess Zero. AlphaZero was the successor to AlphaGo. AZ was notable because unlike AG, it used zero human games to learn to play: it just played games against itself. Typically in “supervised” machine learning you take human data and train a model to imitate it. AZ used zero human data to learn. Leela Chess Zero started out as an open source copy of AZ but it’s probably better than AZ now.
- pertymcpert 2y ago
  Zero doesn't mean zero shot learning. It was coined by Deepmind for AlphaGo Zero where they used zero human input into the training data. It was trained entirely by playing against itself.
  - hilux 2y ago
    And they gave Sir Demis a Nobel Prize!
chvid 2y ago
But the gigantic synthetic dataset that is used for training is created with plenty of traditional search. So it is all a bit silly but I guess cool none the less ...
- chvid 2y ago
  If anything it demonstrates the limits of NN. A human brain can learn based on far fewer examples.
  - jxy 2y ago
    Nature's evolution algorithm took millions of years to find the architecture and the base model, which then takes decades to be fine tuned to be able to form this opinion.
- amunozo 2y ago
  It's a knowledge distillation. You can then use this smaller, more efficient models instead of the larger one.
  - chvid 2y ago
    Or maybe it is just memorizing a very large number of games.
    - azakai 2y ago
      They address the possibility of memorization in the PDF: > This effect cannot be explained by memorization since < 1.41% of the initial puzzle board states appear in our training set.
    - tech_ken 2y ago
      Seems more like a 'compression' of the large number of games, or even like an approximate 'index' of the database
  - alkonaut 2y ago
amoss 2y ago
If you solve chess then you have a tree that is too large for us to currently compute (about 10^80 although my memory may be way off). Annotating that tree with win / loss / draw would allow an optimal player without search. The two obvious approaches to compression / optimization are to approximate the tree, and to approximate the annotations. How well those two approaches would work depends a lot on the structure of the tree. This result seems to tell us less about the power of the training approach (in absolute terms) and more about how amenable the chess game tree is to those two approaches (in relative terms). What I would take away is that a reasonable approximation of that tree can be made in 270M words of data.
- timerol 2y ago
  Note that the exact version of this technique is used in chess for the endgame, referred to as a tablebase. Chess is solved once there are 7 pieces on the board, in an 18.4TB database, described here: https://lichess.org/@/lichess/blog/7-piece-syzygy-tablebases-are-complete/W3WeMyQA https://lichess.org/@/lichess/blog/7-piece-syzygy-tablebases...
  - 7373737373 2y ago
    Makes me wonder what % of games end with <=7 pieces
    - adgjlsfhk1 2y ago
      at a high level, almost all of them that aren't draws. if you have pieces in the right place, you should've be checkmateable. Without blunders, wins occur after a small advantage is followed by slightly favorable trades into a winning position
vanjajaja1 2y ago
what i like about this is that it implies you can build heuristics good enough to make it to GM level. this is great because i find calculating moves a headache
- jvanderbot 2y ago
  The thing is the heuristic done by a huge network might be insanely complex and doing all kinds of calculations. it's just that it's one function call so we ignore all those calculations. It's not immediately obvious that deploying a transformer to solve for next best move means that a human mind can avoid difficult calculations and just play by gut. There's just too much wordplay going on with "heuristic"
  - mewpmewp2 2y ago
    Arguably intuition and gut feeling are also insanely complex systems doing all kinds of calculations.
    - jvanderbot 2y ago
      Sure, but apples and oranges have a lot in common too, and if we call everything fruit, it's unnecessarily hard to differentiate them ... is all I'm saying.
veltas 2y ago
Playing chess with a 20TB cerebellum
bob1029 2y ago
https://arxiv.org/abs/2402.04494 https://arxiv.org/abs/2402.04494 > Board states s are encoded as FEN strings which we convert to fixed-length strings of 77 characters where the ASCII-code of each character is one token. A FEN string is a description of all pieces on the board, whose turn it is, the castling availability for both players, a potential en passant target, a half-move clock and a full-move counter. We essentially take any variable-length field in the FEN string, and convert it into a fixed-length sub-string by padding with ‘.’ if needed. We never flip the board; the FEN string always starts at rank 1, even when it is the black’s turn. We store the actions in UCI notation (e.g., ‘e2e4’ for the well-known white opening move). To tokenize them we determine all possible legal actions across games, which is 1968, sort them alphanumerically (case-sensitive), and take the action’s index as the token, meaning actions are always described by a single token (all details in Section A.1). I am starting to notice a pattern in these papers - Writing hyper-specific tokenizers for the target problem. How would this model perform if we made a small change to the rules of chess and continued using the same tokenizer? If we find we need to rewrite the tokenizer for every problem variant, then I argue this is just ordinary programming in a very expensive disguise.
- kidintech 2y ago
  // personal opinion: I think machine learning as it currently stands is widely overhyped How is this the top comment? > I am starting to notice a pattern in these papers - Writing hyper-specific tokenizers for the target problem. This is merely expressing what they consider as part of a game state, which is entirely needed for what they set out to do. > I argue this is just ordinary programming "Ordinary programming" (what does that mean?) for such a task implies extraordinary chess intuition, capable of conjuring rules and heuristics for the task of comparing two game states and saying which one is "better" (what does better mean?). > How would this model perform if we made a small change to the rules of chess and continued using the same tokenizer? If by "small change" you are implying i.e. removing the ability to castle, then sure, the tokenizer would need to be rewritten. At the same time, the entire training dataset would need to be changed, such that the games are valid under your new ruleset. How is this controversial or unexpected? It feels like you are expecting that state of the art technology allows us to input an arbitrary ruleset and the mighty computer immediately plays an arbitrary game optimally. Unfortunately, this is not the case, but that does not take anything away from this paper.
sksxihve 2y ago
Isn't generating the training data by running stockfish on all the board positions for all the games just encoding the search tree into the transformer model? So increasing the number of parameters to the model would allow it to encode more of the search tree and give better performance, which doesn't seem all that interesting.
- mewpmewp2 2y ago
  How could it be possible to encode a search tree like this though.
  - timmg 2y ago
    Imagine you collected a billion unique, feasible board positions (all positions is intractable, but most possible positions are impractical) and the best nest move for each. That "best next move" is the result of a tree search. Now use a transformer to "compress" that information into its model. It sounds like that is approximately what is going on here. Certainly, the model is likely to generalize some aspects of the data (just like LLMs do). But for the most part, the model encodes the information from the Stockfish evaluation. (This is just my guess of what we are seeing.)
    - sksxihve 2y ago
      Exactly, the title says "without search" but in the paper it says "without explicit search", having a system learn to play chess at a grandmaster-level without any search for play or training would be far more impressive, what this does seems pretty obvious that it would work.
QuantumGood 2y ago
This repository provides an implementation of our paper Grandmaster-Level Chess Without Search. https://arxiv.org/abs/2402.04494 https://arxiv.org/abs/2402.04494 The recent breakthrough successes in machine learning are mainly attributed to scale: namely large-scale attention-based architectures and datasets of unprecedented scale. This paper investigates the impact of training at scale for chess. Unlike traditional chess engines that rely on complex heuristics, explicit search, or a combination of both, we train a 270M parameter transformer model with supervised learning on a dataset of 10 million chess games. We annotate each board in the dataset with action-values provided by the powerful Stockfish 16 engine, leading to roughly 15 billion data points. Our largest model reaches a Lichess blitz Elo of 2895 against humans, and successfully solves a series of challenging chess puzzles, without any domain-specific tweaks or explicit search algorithms. We also show that our model outperforms AlphaZero's policy and value networks (without MCTS) and GPT-3.5-turbo-instruct. A systematic investigation of model and dataset size shows that strong chess performance only arises at sufficient scale. To validate our results, we perform an extensive series of ablations of design choices and hyperparameters.
- QuantumGood 2y ago
  However, the Lichess blitz ELO vs bots is about 700 points lower than vs humans.
dudeinjapan 2y ago
OK but when will someone make grandmaster-level search without chess?

365 points by lawrenceyan 2y ago

I did a talk about this! (And also wrote up about my talk here[1]). This paper is a great example of both knowledge distillation. It's less of a paper about chess and more about how complicated non linear search functions - complete with whatever tuning experts can prepare - can be distilled into a (quasi-linear, if it's a standardized input like chess) transformer model. [1]: https://hlfshell.ai/posts/deepmind-grandmaster-chess-without-search/ https://hlfshell.ai/posts/deepmind-grandmaster-chess-without...

janalsncm 2y ago
I think the vs. humans result should be taken with a huge grain of salt. These are blitz games, and their engine’s elo was far higher against humans than against other bots. So it’s likely that time was a factor, where humans are likely to flag (run out of time) or blunder in low time situations. It’s still very cool that they could learn a very good eval function that doesn’t require search. I would’ve liked the authors to throw out the games where the Stockfish fallback kicked in though. Even for a human, mate in 2 vs mate in 10 is the difference between a win and a draw/loss on time. I also would’ve liked to see a head to head with limited search depth Stockfish. That would tell us approximately how much of the search tree their eval function distilled.
- hlfshell 2y ago
  The reason the time (blitz) games make sense is because the distilled functionality is of a 50ms Stockfish eval function. The engine likely would perform worse as only the human would benefit from the additional time. As for limited search tree I like the idea! I think it's tough to measure, since the time it takes to perform search across various depths vary wildly based on the complexity of the position. I feel like you would have to compile a dataset of specific positions identified to require significant depth of search to find a "good" move.
  - janalsncm 2y ago
    My point is that if the computer never flags it will have an inherent advantage in low time controls. If not, why not just test it in hyperbullet games? Games where humans flag in a drawn or winning position need to be excluded, otherwise it’s unclear what this is even measuring. And limited depth games would not have been difficult to run. You can run a limited search Stockfish on a laptop using the UCI protocol: https://github.com/official-stockfish/Stockfish/wiki/UCI-%26-Commands https://github.com/official-stockfish/Stockfish/wiki/UCI-%26...
  - codeflo 2y ago
    But the headline is “GM-level performance without search”, not “computer beats human at mouse movement speed contest”.

joelthelion 2y ago

I wonder if you could creatively combine this model with search algorithms to advance the state of the art in computer chess? I wouldn't be surprised to see such a bot pop up on tcec in a couple years.

alfalfasprout 2y ago
The thing is classical chess (unlike eg; go) is essentially "solved" when run on computers capable of extreme depth. Modern chess engines play essentially flawlessly.
- KK7NIL 2y ago
  The developers of stockfish and lc0 (and the many weaker engines around) would disagree, we've seen their strength improve considerably over the last few years. Currently there's a very interesting war between small neural networks on the CPU with high search depth alpha-beta pruning (stockfish NNUE) and big neural networks on a GPU with Monte Carlo search and lower depth (lc0). So, while machines beating humans is "solved", chess is very far from solved (just ask the guys who have actually solved chess endgames with 8 or less pieces).
  - GaggiX 2y ago
    Stockfish and lc0 would always draw if they are not put in unbalanced starting positions, the starting position will be swapped in the next game to make it fair.
    - KK7NIL 2y ago
      In classical controls (what TCEC mainly uses), yes. They can play pretty exciting bullet chess without a forced opening though.
  - KolmogorovComp 2y ago
    > ask the guys who have actually solved chess endgames with 8 or less pieces Source?

dgraph_advocate 2y ago

This is missing a makefile to automate the manual installation steps

ChrisArchitect 2y ago

Associated discussion on the paper: Grandmaster-Level Chess Without Search https://news.ycombinator.com/item?id=39301944 https://news.ycombinator.com/item?id=39301944

tzs 2y ago

OT: what's the state of the art in non-GM level computer chess? Say I want to play chess with an opponent that is at about the same skill level as me, or perhaps I want to play with an opponent about 100 rating points above me for training. Most engines let you dumb them down by cutting search depth, but that usually doesn't work well. Sure, you end up beating them about half the time if you cut the search down enough but it generally feels like they were still outplaying you for much of the game and you won because they made one or two blunders. What I want is a computer opponent that plays at a level of my choosing but plays a game that feels like that of a typical human player of that level. Are there such engines?

rtlaker 2y ago
No, not with adjustable rating. The best human-like engine is fairymax, but its Elo is estimated between 1700-2000.
danielmarkbruce 2y ago
It doesn't seem that difficult to pull off - take one of the existing engines, get the top y moves, choose randomly. For each level down increase y by 1.
- agubelu 2y ago
  It doesn't work that way. There are many positions with lots of moves that are reasonable, but many others with only 1-2 sensible moves. It would make lots of obvious blunders that an amateur human would never make.
  - chmod775 2y ago
    Also attention. Lower level human players are more likely to make a move close to their own/their opponent's recent move. They're focused on one area of the board. Basic computer opponents on the other hand can make moves all over the place. They look at the board state holistically. This can be very frustrating to play against as a human who has enough problems just thinking their way through some subset of the board, but is thrown off by the computer again and again. It's not that bad in chess at least (compared to Go), but still something worth to keep in mind if you're trying to make an AI that is fun to play against as an amateur.

osti 2y ago

https://lczero.org/blog/2024/02/how-well-do-lc0-networks-compare-to-the-greatest-transformer-network-from-deepmind/ https://lczero.org/blog/2024/02/how-well-do-lc0-networks-com... The best neural network chess engine's authors wrote about this deepminds publication.

stabbles 2y ago
LC0 hasn't been the best neural network chess engine since Stockfish added NNUE in 2020.
- vlovich123 2y ago
  That isn’t quite accurate. Stockfish’s NNUE was trained against Leela evaluated positions. > Generally considered to be the strongest GPU engine, it continues to provide open data which is essential for training our NNUE networks. They released version 0.31.1 of their engine a few weeks ago, check it out! The main difference is that Stockfish is targeting to run on the CPU while Leela targets the GPU. That stockfish is able to be competitive with Leela is of course impressive. https://lichess.org/@/StockfishNews/blog/stockfish-17-is-here/7LRhV68w https://lichess.org/@/StockfishNews/blog/stockfish-17-is-her...
- osti 2y ago
  True, but since stockfish uses a way way smaller network, I still prefer to think of stockfish as the traditional engine.

YeGoblynQueenne 2y ago

Excellent work but I suggest a slightly different title: "What would Stockfish Do?" A more appropriate title; because Stockfish is a search-base system and DeepMind's approach wouldn't work without it. Oh, btw, this is (yet another) a Neurosymbolic system of the "compiling system 2 to system 1" type.

jackmalpo 2y ago

what i would love is an engine that thinks more like a human. presumably since this uses stockfish annotated games, it basically ends up thinking like a computer. thinking like a human would be awesome for game reviews to walk through things to note in different positions (tuned to my elo).

levocardia 2y ago
Or a model whose performance is measured via its efficiency of learning--in other words, how many games does it need to play to learn to play at X level? The reason Magnus Carlsen is impressive is because he's reached his ability level in chess under enormous time and computation constraints, compared to a computer. His efficiency of learning is extraordinary compared to that of any chess engine.
7373737373 2y ago
Or even the opposite end of the spectrum - with extremely limited resources (memory/program size/computation time): https://rlc-chess.com/ https://rlc-chess.com/ - like demoscene programs. Capable 1kb chess programs exist!

imranhou 2y ago

From the page: "We also show that our model outperforms AlphaZero's policy and value networks (without MCTS) and GPT-3.5-turbo-instruct." Why compare this to GPT-3.5-turbo-instruct? Is that near SOTA in this space?

famouswaffles 2y ago
As far as anyone knows, 3.5-turbo-instruct is the best chess playing (certainly it was at the time of the paper) LLM. About 1800 Elo and < 0.1% Illegal move rate. It's unclear why it was so much better than 4 (lack of RLHF?, Data?) and I don't know if anyone has bothered to test 4o similarly but it was pretty big news online at the time.
- Davidzheng 2y ago
  OA definitely purposefully trained its chess strength
  - famouswaffles 2y ago
    I'm sure they did but there's no reason to believe they pretrained it on chess anymore than 4 so there's some speculation the post training processes mess things up. Turbo instruct does not go through RLHF for instance.

RayVR 2y ago

I forget the rough adjustment factors, but it is worth noting that lichess Elo is not the same as chess.com or FIDE. I think lichess is typically ~300 points above chess.com. This implies the model is around 2500 blitz vs humans. As blitz elo are often much higher than in classical time controls, 2500 elo on chess.com places it firmly in the 'good but not great' level. I am very curious to know whether the model suffers from the same eval problems vs the well known "anti-bot" openings that stockfish is susceptible to at limited search depths.

gpm 2y ago
> I think lichess is typically ~300 points above chess.com. Yeah, no. They are two different rating systems (not ELO incidentally) with different curves, there isn't a fixed difference you can apply. At the high end of the scale lichess ratings are below, not above, chess.com ratings. E.g. Magnus Carlsen is 3131 blitz on lichess [0], 3294 blitz on chess.com [1]. This website [2] tries to translate between the sites, and figures that a 2925 lichess blitz rating (the closet on the website to the one reported in the paper of 2895) translates to 3000 chess.com. [0] Multiple accounts but this is the one I found with the most blitz games: https://lichess.org/@/DrNykterstein/perf/blitz https://lichess.org/@/DrNykterstein/perf/blitz [1] https://www.chess.com/member/magnuscarlsen https://www.chess.com/member/magnuscarlsen [2] https://chessgoals.com/rating-comparison/#lichesschesscom https://chessgoals.com/rating-comparison/#lichesschesscom
- jdck1326 2y ago
  Elo. Not acronym, named for its inventor Arpad Emmerich Elo https://en.wikipedia.org/wiki/Elo_rating_system https://en.wikipedia.org/wiki/Elo_rating_system
- RayVR 2y ago
  Cool, thanks for the information! I did not realize the curves were that different. 3000 definitely bumps it up but it would still be worse than the top humans. stockfish is better by a lot.
deleted 2y ago
[deleted]

rawsh 2y ago

You can actually get solid performance with pretrained chat models: https://raw.sh/posts/chess_puzzles https://raw.sh/posts/chess_puzzles On lichess puzzles gpt4o with the compiled prompt is around 70%, I think the 270M transformer is around 95%

sinuhe69 2y ago
It depends on the difficulties of the puzzles. If you read the article of the Leela author, (link cited by other comment), then you will see a much different picture: the new DeepMind is better then AlphaZero but much worse than the best open source model. Not specially trained transformer like ChatGPT4o (and even 5o) has absolutely no chance to solve the more difficult puzzles.

squidgedcricket 2y ago

Would it be feasible to create a complete lookup table of 'best' moves for all given board configurations? I'm not sure how to determine the total number of configurations. Not the same as a tablebase, just a single next move rather than sequence to checkmate. It wouldn't be competitive against top tier players and AI, but I wouldn't be surprised if it could beat me. 'Instantly' knowing the next move would be a cool trick.

k2xl 2y ago
The amount of data that would be required for a lookup table for all best moves for every board configuration would be infeasible. They have managed to create one for 7 pieces. Last update on trying to get to 8 piece database: https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-progress-update-and-some-results https://www.chess.com/blog/Rocky64/eight-piece-tablebases-a-...
- squidgedcricket 2y ago
  Yup, and it looks like a complete tablebase from the start of the game won't ever be feasible. > From May to August 2018 Bojun Guo generated 7-piece tables. The 7-piece tablebase contains 423,836,835,667,331 unique legal positions in about 18 Terabytes.
- andrelaszlo 2y ago
  Almost halfway there ;)
  - jeremyjh 2y ago
    There are 32 pieces on the board at the start of the game.
jeremyjh 2y ago
There are more possible chess games than there are atoms in the universe. It can't be solved by brute force.

Scene_Cast2 2y ago

If anyone is looking to get into chess neural nets, I highly recommend this repo - https://github.com/sgrvinod/chess-transformers https://github.com/sgrvinod/chess-transformers It uses paradigmatic PyTorch with easy to read code, and the architecture is similar to the current best performing chess neural nets.

sourcepluck 2y ago

I believe GM and chess author (and all-round lovely fellow) Matthew Sadler rigged up Leela Zero to effectively play off intuition and do very little or no search for training games. He could usually beat it, but not always. Think it might have been in The Silicon Road to Chess Improvement.

Davidzheng 2y ago
I mean for lczero you can just set the max depth at 1 ply for example
- sourcepluck 2y ago
  Oh, maybe it was that simple!
Scarblac 2y ago
He also has very entertaining Youtube videos about the kind of wild opening discoveries Leela comes up with when contempt is set really high (ie it wants to maximally avoid draws), combined with his 2700+ commentary on them.

barelyusable 2y ago

What are some of the go-to books/articles for computer chess? I like the game and have a decent understanding of basics, so studying algorithms based on the game would be a good opportunity for me to learn conventional algos, but also RL/ML/MCTS etc. Also I wonder what is the go-to codebase these days?

janalsncm 2y ago
Stockfish and Leela are the two best engines and they’re both on GitHub. Although I will say they are hyperoptimized to win. You can also ask any noob questions on their Discords.
sinuhe69 2y ago
https://www.chessprogramming.org/ https://www.chessprogramming.org/ Is the portal to go. From there, you can dig deeper in many relevant themes.

dougSF70 2y ago

Slightly off topic but I built https://chessladders.com https://chessladders.com

1bit_e 2y ago
Nice! I built https://www.chesspuzzlebot.com/ https://www.chesspuzzlebot.com/ (Puzzles against stockfish)

xiaodai 2y ago

this paper is so dumb. so you modeled the output of stockfish? stockfish does use simulation or selfplay or search. so you've outsourced search and dont do it yourself so you can claim to be "without search"

hilux 2y ago
Do you understand how ML models are trained?
scotty79 2y ago
I think what they say is valid. Same way ChatGPT can answer questions google could answer without doing any search like google does.

BoardsOfCanada 2y ago

It's somewhat telling that they chose Stockfish as the oracle and not AlphaZero.

Davidzheng 2y ago
It's well established that SF today is stronger. Btw this is pretty bullish case for open source recreations of RL advancements to be catching up with ~2 year lag. Hopefully alphaproof is also reproduced in that timeframe
epolanski 2y ago
Stockfish is stronger than AlphaZero or any other chess engine from quite some time. Another interesting tidbit, both engines share (or at least, shared) the same lead developer.
- vlovich123 2y ago
  To be fair though, deep mind hasn’t been working to improve alpha zero for chess playing. Their focus is a bit difference than the dedicated volunteers working on stockfish (+ it’s been a few years)

bicsi 2y ago

They built a dumber clone of Stockfish, and they call it ‘zero’ for some reason. What is the meaning behind ‘zero’ anyways? It used to refer to zero-shot, but now it seems like it’s just a marketing term.

ralegh 2y ago
I assume it's 'zero' turns lookahead/search, i.e. only look at the current board state.
janalsncm 2y ago
I assume you’re referring to AlphaZero and Leela Chess Zero. AlphaZero was the successor to AlphaGo. AZ was notable because unlike AG, it used zero human games to learn to play: it just played games against itself. Typically in “supervised” machine learning you take human data and train a model to imitate it. AZ used zero human data to learn. Leela Chess Zero started out as an open source copy of AZ but it’s probably better than AZ now.
pertymcpert 2y ago
Zero doesn't mean zero shot learning. It was coined by Deepmind for AlphaGo Zero where they used zero human input into the training data. It was trained entirely by playing against itself.
- hilux 2y ago
  And they gave Sir Demis a Nobel Prize!

chvid 2y ago

But the gigantic synthetic dataset that is used for training is created with plenty of traditional search. So it is all a bit silly but I guess cool none the less ...

chvid 2y ago
If anything it demonstrates the limits of NN. A human brain can learn based on far fewer examples.
- jxy 2y ago
  Nature's evolution algorithm took millions of years to find the architecture and the base model, which then takes decades to be fine tuned to be able to form this opinion.
amunozo 2y ago
It's a knowledge distillation. You can then use this smaller, more efficient models instead of the larger one.
- chvid 2y ago
  Or maybe it is just memorizing a very large number of games.
  - azakai 2y ago
    They address the possibility of memorization in the PDF: > This effect cannot be explained by memorization since < 1.41% of the initial puzzle board states appear in our training set.
  - tech_ken 2y ago
    Seems more like a 'compression' of the large number of games, or even like an approximate 'index' of the database
- alkonaut 2y ago

amoss 2y ago

If you solve chess then you have a tree that is too large for us to currently compute (about 10^80 although my memory may be way off). Annotating that tree with win / loss / draw would allow an optimal player without search. The two obvious approaches to compression / optimization are to approximate the tree, and to approximate the annotations. How well those two approaches would work depends a lot on the structure of the tree. This result seems to tell us less about the power of the training approach (in absolute terms) and more about how amenable the chess game tree is to those two approaches (in relative terms). What I would take away is that a reasonable approximation of that tree can be made in 270M words of data.

timerol 2y ago
Note that the exact version of this technique is used in chess for the endgame, referred to as a tablebase. Chess is solved once there are 7 pieces on the board, in an 18.4TB database, described here: https://lichess.org/@/lichess/blog/7-piece-syzygy-tablebases-are-complete/W3WeMyQA https://lichess.org/@/lichess/blog/7-piece-syzygy-tablebases...
- 7373737373 2y ago
  Makes me wonder what % of games end with <=7 pieces
  - adgjlsfhk1 2y ago
    at a high level, almost all of them that aren't draws. if you have pieces in the right place, you should've be checkmateable. Without blunders, wins occur after a small advantage is followed by slightly favorable trades into a winning position

vanjajaja1 2y ago

what i like about this is that it implies you can build heuristics good enough to make it to GM level. this is great because i find calculating moves a headache

jvanderbot 2y ago
The thing is the heuristic done by a huge network might be insanely complex and doing all kinds of calculations. it's just that it's one function call so we ignore all those calculations. It's not immediately obvious that deploying a transformer to solve for next best move means that a human mind can avoid difficult calculations and just play by gut. There's just too much wordplay going on with "heuristic"
- mewpmewp2 2y ago
  Arguably intuition and gut feeling are also insanely complex systems doing all kinds of calculations.
  - jvanderbot 2y ago
    Sure, but apples and oranges have a lot in common too, and if we call everything fruit, it's unnecessarily hard to differentiate them ... is all I'm saying.

veltas 2y ago

Playing chess with a 20TB cerebellum

bob1029 2y ago

https://arxiv.org/abs/2402.04494 https://arxiv.org/abs/2402.04494 > Board states s are encoded as FEN strings which we convert to fixed-length strings of 77 characters where the ASCII-code of each character is one token. A FEN string is a description of all pieces on the board, whose turn it is, the castling availability for both players, a potential en passant target, a half-move clock and a full-move counter. We essentially take any variable-length field in the FEN string, and convert it into a fixed-length sub-string by padding with ‘.’ if needed. We never flip the board; the FEN string always starts at rank 1, even when it is the black’s turn. We store the actions in UCI notation (e.g., ‘e2e4’ for the well-known white opening move). To tokenize them we determine all possible legal actions across games, which is 1968, sort them alphanumerically (case-sensitive), and take the action’s index as the token, meaning actions are always described by a single token (all details in Section A.1). I am starting to notice a pattern in these papers - Writing hyper-specific tokenizers for the target problem. How would this model perform if we made a small change to the rules of chess and continued using the same tokenizer? If we find we need to rewrite the tokenizer for every problem variant, then I argue this is just ordinary programming in a very expensive disguise.

kidintech 2y ago
// personal opinion: I think machine learning as it currently stands is widely overhyped How is this the top comment? > I am starting to notice a pattern in these papers - Writing hyper-specific tokenizers for the target problem. This is merely expressing what they consider as part of a game state, which is entirely needed for what they set out to do. > I argue this is just ordinary programming "Ordinary programming" (what does that mean?) for such a task implies extraordinary chess intuition, capable of conjuring rules and heuristics for the task of comparing two game states and saying which one is "better" (what does better mean?). > How would this model perform if we made a small change to the rules of chess and continued using the same tokenizer? If by "small change" you are implying i.e. removing the ability to castle, then sure, the tokenizer would need to be rewritten. At the same time, the entire training dataset would need to be changed, such that the games are valid under your new ruleset. How is this controversial or unexpected? It feels like you are expecting that state of the art technology allows us to input an arbitrary ruleset and the mighty computer immediately plays an arbitrary game optimally. Unfortunately, this is not the case, but that does not take anything away from this paper.

sksxihve 2y ago

Isn't generating the training data by running stockfish on all the board positions for all the games just encoding the search tree into the transformer model? So increasing the number of parameters to the model would allow it to encode more of the search tree and give better performance, which doesn't seem all that interesting.

mewpmewp2 2y ago
How could it be possible to encode a search tree like this though.
- timmg 2y ago
  Imagine you collected a billion unique, feasible board positions (all positions is intractable, but most possible positions are impractical) and the best nest move for each. That "best next move" is the result of a tree search. Now use a transformer to "compress" that information into its model. It sounds like that is approximately what is going on here. Certainly, the model is likely to generalize some aspects of the data (just like LLMs do). But for the most part, the model encodes the information from the Stockfish evaluation. (This is just my guess of what we are seeing.)
  - sksxihve 2y ago
    Exactly, the title says "without search" but in the paper it says "without explicit search", having a system learn to play chess at a grandmaster-level without any search for play or training would be far more impressive, what this does seems pretty obvious that it would work.

QuantumGood 2y ago

This repository provides an implementation of our paper Grandmaster-Level Chess Without Search. https://arxiv.org/abs/2402.04494 https://arxiv.org/abs/2402.04494 The recent breakthrough successes in machine learning are mainly attributed to scale: namely large-scale attention-based architectures and datasets of unprecedented scale. This paper investigates the impact of training at scale for chess. Unlike traditional chess engines that rely on complex heuristics, explicit search, or a combination of both, we train a 270M parameter transformer model with supervised learning on a dataset of 10 million chess games. We annotate each board in the dataset with action-values provided by the powerful Stockfish 16 engine, leading to roughly 15 billion data points. Our largest model reaches a Lichess blitz Elo of 2895 against humans, and successfully solves a series of challenging chess puzzles, without any domain-specific tweaks or explicit search algorithms. We also show that our model outperforms AlphaZero's policy and value networks (without MCTS) and GPT-3.5-turbo-instruct. A systematic investigation of model and dataset size shows that strong chess performance only arises at sufficient scale. To validate our results, we perform an extensive series of ablations of design choices and hyperparameters.

QuantumGood 2y ago
However, the Lichess blitz ELO vs bots is about 700 points lower than vs humans.

dudeinjapan 2y ago

OK but when will someone make grandmaster-level search without chess?