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

Grandmaster-level chess without search

github.com

Post reply on HN
Print view View original

111–120 of 171 posts

Re: Grandmaster-level chess without search

#111

Post by Scarblac »

jeremyjh wrote: post #98
squidgedcricket wrote: post #51

Earlier quoted context omitted.

There's a lot of chess configs, but there's a LOT of atoms in the observable universe. I suspect there's a few in the unobservable universe too. Chess configs = 4.8 x 10^44, Atoms > 10^70 https://tromp.github.io/chess/chess.html https://physics.stackexchange.com/questions/47941/dumbed-dow... You might be able to pull off a low-resolution lookup table. Take some big but manageable number N (e.g 10^10) and calculate th…

I didn't say chess positions, I said chess games . That number has a lower-bound of 10^120. https://en.wikipedia.org/wiki/Shannon_number

But that's not the relevant thing if we're talking about storing a best move per possible position.

Re: Grandmaster-level chess without search

#112

Post by Scarblac »

sourcepluck wrote: post #55

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.

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.

Re: Grandmaster-level chess without search

#113

Post by amoss »

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.

Re: Grandmaster-level chess without search

#114

Post by gcr »

tzs wrote: post #20

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

Stockfish is the classic answer, though I’m not sure how well it’s graded. Someone must have a “Stockfish strength”-to-ELO mapping.

Re: Grandmaster-level chess without search

#116

Post by jvanderbot »

vanjajaja1 wrote: post #115

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

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"

Re: Grandmaster-level chess without search

#117

Post by timerol »

amoss wrote: post #113

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

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

Re: Grandmaster-level chess without search

#118

Post by teo_zero »

danielmarkbruce wrote: post #22
tzs wrote: post #20

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

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.

Better: take one of the existing engines, sort the moves from the best to the worst, if the top move has score S, randomly choose among the moves with score >= 0.9*S.

You can simulate a better/worse player by increasing/decreasing the factor: 1 plays as well as the chosen engine can do, 0 is typing random (yet valid) moves on the keyboard.

Re: Grandmaster-level chess without search

#119

Post by danielmarkbruce »

teo_zero wrote: post #118
danielmarkbruce wrote: post #22

Earlier quoted context omitted.

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.

Better: take one of the existing engines, sort the moves from the best to the worst, if the top move has score S, randomly choose among the moves with score >= 0.9*S. You can simulate a better/worse player by increasing/decreasing the factor: 1 plays as well as the chosen engine can do, 0 is typing random (yet valid) moves on the keyboard.

Yup this is better.

Re: Grandmaster-level chess without search

#120

Post by danielmarkbruce »

bobmcnamara wrote: post #26
danielmarkbruce wrote: post #22

Earlier quoted context omitted.

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.

Your engine would only mate once it had y options to mate.

Any time it had an option to mate it would have a chance to mate. It's choose randomly amongst top n, not take the nth.
Post reply on HN