A recent discovery showing that computer chess (which was traditionally based on searching a combinatorial space, i.e. NP-hard) that is instead now being solved with transformer models, is actually playing better at the ELO level.
If you think about using search to play chess, it can go several ways.
Brute-forcing all chess moves (NP hard) doesn’t work because you need almost infinite compute power.
If you use a chess engine with clever heuristics to eliminate bad solutions, you can solve it in finite time.
But if you learn from the best humans performing under different contexts (transformers are really good at capturing context in sequences and predicting the next token from that context — hence their utility in LLMs) you have narrowed your search space even further to only set of good moves (by grandmaster standards).
The news that got my attention was https://arxiv.org/html/2402.04494v1 "Grandmaster-Level Chess Without Search" and an engine using this approach exceeding 2900 on Lichess (against humans) and over 2200 against engines.
I actually started a chess channel a couple of hourse ago to help humans take advantage of this (nothing there yet https://youtube.com/@DecisiveEdgeChess ).
I have long taught my students that its possible to assess positions at a very high level with very, very little calculation, and this news hit me as "finally, evidence enough to intrigue more people that this is possible!" (My interest in Chess goes way back. I finished in the money in the U.S. Open and New York Open in the '80's, and one of my longtime friends was IM Mike Valvo, since passed, who was the arbiter for the 1996 match between Garry Kasparov and IBM's Deep Blue, and a commentator for the '97 match alongside Grandmasters Yasser Seirawan and Maurice Ashley.)
https://arxiv.org/pdf/2402.04494
If you think about using search to play chess, it can go several ways.
Brute-forcing all chess moves (NP hard) doesn’t work because you need almost infinite compute power.
If you use a chess engine with clever heuristics to eliminate bad solutions, you can solve it in finite time.
But if you learn from the best humans performing under different contexts (transformers are really good at capturing context in sequences and predicting the next token from that context — hence their utility in LLMs) you have narrowed your search space even further to only set of good moves (by grandmaster standards).