Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Grandmaster-Level Chess Without Search

arxiv.org

Post reply on HN
Print view View original

41–50 of 133 posts

Re: Grandmaster-Level Chess Without Search

#41

Post by famouswaffles »

janalsncm wrote: post #38
famouswaffles wrote: post #13

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.

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.

>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/c...

Re: Grandmaster-Level Chess Without Search

#42

Post by karolist »

paulddraper wrote: post #6
fiforpg wrote: post #2

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.

Training uses search, but it plays without search. ChatGPT isn't human, but it was trained with humans.

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.

Re: Grandmaster-Level Chess Without Search

#43

Post by jrockway »

dayjaby wrote: post #33
IIAOPSW wrote: post #26

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 vic…

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…

I agree with this. My default approach to board games is basically to maximize victory points early. This usually works; when 4 people are playing a new game for the first time, I usually win. This doesn't really work when people know how to play the game specifically, though.

I think this algorithm is better than many other algorithms that people come up with, however.

(As an aside, when I play a card game I sort my cards with a merge sort instead of an insertion sort. People said you would never use these algorithms in real life, but you can if you want to!)

Re: Grandmaster-Level Chess Without Search

#44

Post by joe_the_user »

janalsncm wrote: post #40
joe_the_user wrote: post #37

Earlier quoted context omitted.

Sort of but it seems a bit of a cheat. Neural networks are universal approximators. Choose a function and get enough data from it and you can approximate it very closely and maybe exactly. If initially creating function F required algorithm Y ("search" or whatever), you can do your approximation to F and then say "Look F without Y" and for all we know, the approximation might be doing things internally that are actua…

A sufficiently large nn can learn an arbitrary function, yes. But stockfish is also theoretically perfect given infinite computational resources. What is interesting is performing well under reasonable computational constraints i.e. doing it faster/with fewer flops than stockfish.

Is the model more efficient than Stockfish? I think Stockfish runs on regular CPU computer and I'd guess this " 270M parameter transformer model" requires a GPU but I can't find any reference to efficiency in the paper.

Also found in the paper: "While our largest model achieves very good performance, it does not completely close the gap to Stockfish 16". It's actually inferior but they still think it's an interesting exercise. But that's the thing, it's primarily an exercise like calculating pi to a billion decimal points or overclocking a gaming laptop.

Re: Grandmaster-Level Chess Without Search

#45

Post by eldenring »

jackblemming wrote: post #39
joe_the_user wrote: post #37

Earlier quoted context omitted.

Sort of but it seems a bit of a cheat. Neural networks are universal approximators. Choose a function and get enough data from it and you can approximate it very closely and maybe exactly. If initially creating function F required algorithm Y ("search" or whatever), you can do your approximation to F and then say "Look F without Y" and for all we know, the approximation might be doing things internally that are actua…

No, arbitrarily wide neural networks are approximators of Borel Measurable functions. Big difference between that and “any function”. RNNs are Turing Complete though.

You can say the same thing about RNNs. Technically nothing is turing complete without infinite scratch space.

Re: Grandmaster-Level Chess Without Search

#46

Post by bionsystem »

IIAOPSW wrote: post #26

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 vic…

A lot of decision in chess would be like "this square would be nice for that piece, how can I get there ?" and then analyze what your opponent can do to prevent you to do that, or what counterplay that gives him. So what you are doing makes a lot of sense.

Re: Grandmaster-Level Chess Without Search

#47

Post by Vecr »

n2d4 wrote: post #9
zniturah wrote: post #5

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.”

The context of that sentence: > Indecisiveness in the face of overwhelming victory > If Stockfish detects a mate-in-k (e.g., 3 or 5) it outputs k and not a centipawn score. We map all such outputs to the maximal value bin (i.e., a win percentage of 100%). Similarly, in a very strong position, several actions may end up in the maximum value bin. Thus, across time-steps this can lead to our agent playing somewhat rando…

They should try to implement some kind of resolute agent in that case. Might be hard to do if it needs to be "not technically search" though.

Re: Grandmaster-Level Chess Without Search

#48

Post by dawnofdusk »

janalsncm wrote: post #38
famouswaffles wrote: post #13

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.

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.

Even if it's "implicit" I'm not sure if that matters that much. The point is that the model doesn't explicitly search anything, it just applies the learned transformation. If the weights of the learned transformation encode a sort of precomputed search and interpolation over the dataset, from an algorithmic perspective this still isn't search (it doesn't enumerate board states or state-action transitions).

>performing some function of the similarity of the input to those previously seen.

This is indeed what transformers do. But obviously it learns some sort of interpolation/extrapolation which lets it do well on board states/games outside the training set.

Re: Grandmaster-Level Chess Without Search

#49

Post by dawnofdusk »

joe_the_user wrote: post #37
paulddraper wrote: post #18

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 n…

Sort of but it seems a bit of a cheat. Neural networks are universal approximators. Choose a function and get enough data from it and you can approximate it very closely and maybe exactly. If initially creating function F required algorithm Y ("search" or whatever), you can do your approximation to F and then say "Look F without Y" and for all we know, the approximation might be doing things internally that are actua…

It doesn't get the actual optimal Q values computed from Stockfish (presumably this takes infinite compute to calculate), in fact it gets computed estimates from polling Stockfish for only 50ms.

So you're estimating from data a function which is itself not necessarily optimal. Moreover, the point is more like how far can we get using a really generic transformer architecture that is not tuned to domain-specific details of our problem, which Stockfish is.

Re: Grandmaster-Level Chess Without Search

#50

Post by janalsncm »

famouswaffles wrote: post #41
janalsncm wrote: post #38

Earlier quoted context omitted.

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.

>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 wo…

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.

Post reply on HN