5 ms·

Monte-Carlo graph search from first principles

397 points by bumbledraven 3y ago

rphln 3y ago
Somehow the paper they mention completely flew under my radar when I was researching MCTS. Surely it's gonna be a lot of fun to give this modification a spin on my next opportunity.
pixelpoet 3y ago
Immediately recognise the author in the HN url as the genius behind KataGo: https://github.com/lightvector/KataGo https://github.com/lightvector/KataGo His posts on https://www.reddit.com/r/cbaduk/ https://www.reddit.com/r/cbaduk/ are consistently excellent.
- bingbingbing777 3y ago
  The URL is literally within the KataGo repo.
  - pixelpoet 3y ago
    The HN URL preview for me "literally" says "(github.com/lightvector)", with no upfront mention of KataGo. sigh
    - elbear 3y ago
      Hovering over the title of the submission will show the full URL.
fabmilo 3y ago
I believe this kind of graph exploration is what we need to progress reasoning in AI. Plain LLMS will fail. The link has tons of good references, including the Zobrist hashing https://en.wikipedia.org/wiki/Zobrist_hashing https://en.wikipedia.org/wiki/Zobrist_hashing for game tables. We need to find a good hashing for language based state description so that graph exploration doesn't explode computationally. Another good read for Tree Search is Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 https://arxiv.org/abs/1705.08439 and Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642 https://arxiv.org/abs/2403.04642 comparing the MCTS approach to other current RL strategies.
- anonymous-panda 3y ago
  Would it be impossible to marry the two somehow? It’s hard for me to believe that the brain only uses a single technique for everything and likely has many different tools in its toolbox with a selector on top to know how to leverage each appropriately.
- vjerancrnjak 3y ago
  This looks too low level. What might be a step forward is a joint learning of the state representation with the search algorithm. Search algorithm explores the NN representation of the state for which you can get the cost. https://sites.google.com/view/genie-2024/ https://sites.google.com/view/genie-2024/ Genie from DeepMind is a good demonstration where discrete state is being modeled. NN learns a very complex representation with collision detection and actions. Instead of decoding that state into pixels, search could probably be done directly on that state. Of course, this architecture could be very different.
  - emmett 3y ago
    Active Inference is kinda "a joint learning of the state representation with the search algorithm"...or at least, related to the idea. I like framing it as a joint learning problem.
- andrewdb 3y ago
  An over-simplified approach that would be interesting to explore: 1. Given a collection of logical arguments, figure out how to assign a hash to each argument. 2. Build a Merkle tree representing the argument's hashes, nesting according to first principles. 3. If an argument is challenged successfully, the argument's hash changes, rendering descendent argument hashes invalid.
behnamoh 3y ago
A bit introduction about this would be nice.
- bionhoward 3y ago
  When we make game-playing AI (which is all AI, depending on your analogy comfort), one of the most promising techniques is Tree Search, which ranks moves based on the descendant moves. In games where you could reach the same state in many ways, much memory might be wasted to re-record the same state node on different branches. This article is a nice exploration of an approach called Graph Search, which essentially trades compute for memory by doing extra compute work (hashing the game states) to check to see if the nodes are already visited. That saves us from re-recording nodes we already saw, and consequently converts trees (free of cycles) into directed acyclic graphs. This forces some tinkering with the tree search to get correct results, specifically it demands a focus more on edges (actions or moves) as the unit of optimization, rather than on vertices (states). It’s a well written technical essay in literate programming written by someone who understands their subject.
  - 3abiton 3y ago
    This was an amazing high level recap with context about the background and importance of the technique!
  - TrueDuality 3y ago
    I would argue that this saves both compute and memory for any significant search. In a traditional tree-search without treating states as identical and revistable still requires you to store every node that you visit in memory to track the N, Q, and child relations. Applying the algorithm adds a hash associated with each node, and a counter on each edge. On the other side you're de-duplicating identical states in your search space, saving the memory of duplicate nodes but more importantly saving compute by not requiring independent searches of the same state space. Whether this trade off actually saves memory will be determined based on how likely duplicate states are in your search space. Otherwise your summary is absolutely spot on.
modeless 3y ago
> Also, as far as the name "Monte-Carlo Tree Search" itself, readers might note that there is nothing "Monte-Carlo" in the above algorithm - that it's completely deterministic! MCTS as commonly implemented is deterministic? How strange! I assumed there was randomness in the sampling.
- westurner 3y ago
  If there's randomness, is there convergence and after how much (CPU, RAM, GPU, TPU, QPU) resource-time?
- kadoban 3y ago
  Originally MCTS did have randomness, yes. I think the article mentions it, but this came in in the form of playouts at the end, used just to evaluate positions. This has been replaced in current similar projects by NN evaluations, which are higher quality (as you can probably imagine, just playing random moves to see who wins is not very good, it was just the best strategy known at the time). So the monte-carlo turned out to be an unessential (and suboptimal) part of what is now still called MCTS, making the name a bit unfortunate.
  - CuriousCosmic 3y ago
    In essence the NN evaluations are acting as a PRNG with values heavily biased by an established heuristic. So while it's very much a specialization of MCTS and probably should go by a different name, one could argue it's still using monte carlo methods.
    - pavlov 3y ago
      Sounds like the dice are loaded in Monte Carlo.
  - mzl 3y ago
    Small side note, standard MCTS is often implemented with heuristic guiding the moves in the playouts and not just random moves, as that gives more interesting information.
hansonpeter 3y ago
[dead]
Abhitaneja89 3y ago
[dead]
dooglius 3y ago
My chess experience is not that high, but enough that I'm skeptical of the claim that the same position would be duplicated in a search tree enough for it to matter. I'd be interested to see an actual measure of this with Leela Zero. (And I'm not even considering the threefold repetition and fifty-move rules, which when considered in the state make a repetition much less likely).
- tel 3y ago
  Ko is very common in Go, though. You can't validly repeat the board position (simplified way of handling Ko rules) but if tree search failed to evaluate ko positions correctly it'd be easy to construct situations where the AI would make bad moves.

397 points by bumbledraven 3y ago

Somehow the paper they mention completely flew under my radar when I was researching MCTS. Surely it's gonna be a lot of fun to give this modification a spin on my next opportunity.

pixelpoet 3y ago

Immediately recognise the author in the HN url as the genius behind KataGo: https://github.com/lightvector/KataGo https://github.com/lightvector/KataGo His posts on https://www.reddit.com/r/cbaduk/ https://www.reddit.com/r/cbaduk/ are consistently excellent.

bingbingbing777 3y ago
The URL is literally within the KataGo repo.
- pixelpoet 3y ago
  The HN URL preview for me "literally" says "(github.com/lightvector)", with no upfront mention of KataGo. sigh
  - elbear 3y ago
    Hovering over the title of the submission will show the full URL.

fabmilo 3y ago

I believe this kind of graph exploration is what we need to progress reasoning in AI. Plain LLMS will fail. The link has tons of good references, including the Zobrist hashing https://en.wikipedia.org/wiki/Zobrist_hashing https://en.wikipedia.org/wiki/Zobrist_hashing for game tables. We need to find a good hashing for language based state description so that graph exploration doesn't explode computationally. Another good read for Tree Search is Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 https://arxiv.org/abs/1705.08439 and Teaching Large Language Models to Reason with Reinforcement Learning: https://arxiv.org/abs/2403.04642 https://arxiv.org/abs/2403.04642 comparing the MCTS approach to other current RL strategies.

anonymous-panda 3y ago
Would it be impossible to marry the two somehow? It’s hard for me to believe that the brain only uses a single technique for everything and likely has many different tools in its toolbox with a selector on top to know how to leverage each appropriately.
vjerancrnjak 3y ago
This looks too low level. What might be a step forward is a joint learning of the state representation with the search algorithm. Search algorithm explores the NN representation of the state for which you can get the cost. https://sites.google.com/view/genie-2024/ https://sites.google.com/view/genie-2024/ Genie from DeepMind is a good demonstration where discrete state is being modeled. NN learns a very complex representation with collision detection and actions. Instead of decoding that state into pixels, search could probably be done directly on that state. Of course, this architecture could be very different.
- emmett 3y ago
  Active Inference is kinda "a joint learning of the state representation with the search algorithm"...or at least, related to the idea. I like framing it as a joint learning problem.
andrewdb 3y ago
An over-simplified approach that would be interesting to explore: 1. Given a collection of logical arguments, figure out how to assign a hash to each argument. 2. Build a Merkle tree representing the argument's hashes, nesting according to first principles. 3. If an argument is challenged successfully, the argument's hash changes, rendering descendent argument hashes invalid.

behnamoh 3y ago

A bit introduction about this would be nice.

bionhoward 3y ago
When we make game-playing AI (which is all AI, depending on your analogy comfort), one of the most promising techniques is Tree Search, which ranks moves based on the descendant moves. In games where you could reach the same state in many ways, much memory might be wasted to re-record the same state node on different branches. This article is a nice exploration of an approach called Graph Search, which essentially trades compute for memory by doing extra compute work (hashing the game states) to check to see if the nodes are already visited. That saves us from re-recording nodes we already saw, and consequently converts trees (free of cycles) into directed acyclic graphs. This forces some tinkering with the tree search to get correct results, specifically it demands a focus more on edges (actions or moves) as the unit of optimization, rather than on vertices (states). It’s a well written technical essay in literate programming written by someone who understands their subject.
- 3abiton 3y ago
  This was an amazing high level recap with context about the background and importance of the technique!
- TrueDuality 3y ago
  I would argue that this saves both compute and memory for any significant search. In a traditional tree-search without treating states as identical and revistable still requires you to store every node that you visit in memory to track the N, Q, and child relations. Applying the algorithm adds a hash associated with each node, and a counter on each edge. On the other side you're de-duplicating identical states in your search space, saving the memory of duplicate nodes but more importantly saving compute by not requiring independent searches of the same state space. Whether this trade off actually saves memory will be determined based on how likely duplicate states are in your search space. Otherwise your summary is absolutely spot on.

modeless 3y ago

> Also, as far as the name "Monte-Carlo Tree Search" itself, readers might note that there is nothing "Monte-Carlo" in the above algorithm - that it's completely deterministic! MCTS as commonly implemented is deterministic? How strange! I assumed there was randomness in the sampling.

westurner 3y ago
If there's randomness, is there convergence and after how much (CPU, RAM, GPU, TPU, QPU) resource-time?
kadoban 3y ago
Originally MCTS did have randomness, yes. I think the article mentions it, but this came in in the form of playouts at the end, used just to evaluate positions. This has been replaced in current similar projects by NN evaluations, which are higher quality (as you can probably imagine, just playing random moves to see who wins is not very good, it was just the best strategy known at the time). So the monte-carlo turned out to be an unessential (and suboptimal) part of what is now still called MCTS, making the name a bit unfortunate.
- CuriousCosmic 3y ago
  In essence the NN evaluations are acting as a PRNG with values heavily biased by an established heuristic. So while it's very much a specialization of MCTS and probably should go by a different name, one could argue it's still using monte carlo methods.
  - pavlov 3y ago
    Sounds like the dice are loaded in Monte Carlo.
- mzl 3y ago
  Small side note, standard MCTS is often implemented with heuristic guiding the moves in the playouts and not just random moves, as that gives more interesting information.

hansonpeter 3y ago

[dead]

Abhitaneja89 3y ago

[dead]

dooglius 3y ago

My chess experience is not that high, but enough that I'm skeptical of the claim that the same position would be duplicated in a search tree enough for it to matter. I'd be interested to see an actual measure of this with Leela Zero. (And I'm not even considering the threefold repetition and fifty-move rules, which when considered in the state make a repetition much less likely).

tel 3y ago
Ko is very common in Go, though. You can't validly repeat the board position (simplified way of handling Ko rules) but if tree search failed to evaluate ko positions correctly it'd be easy to construct situations where the AI would make bad moves.