4 ms·

This is interesting. If you approach this game as individual moves, the search tree is really deep. However, most levels can be expressed as a few intermediate

This is interesting. If you approach this game as individual moves, the search tree is really deep. However, most levels can be expressed as a few intermediate goals. In some ways, this reminds me of the history of AI Go (board game). But the resolution there was MCTS, which wasn't at all what we wanted (insofar as MCTS is not generalizable to most things).

rtpg 1y ago
> However, most levels can be expressed as a few intermediate goals I think generally the whole thing with puzzle games is that you have to determine the “right” intermediate goals. In fact, the naive intermediate goals are often entirely wrong! A canonical sokoban-like inversion might be where you have to push two blocks into goal areas. You might think “ok, push one block into its goal area and then push another into it.” But many of these games will have mechanisms meaning you would first want to push one block into its goal, then undo that for some reason (it might activate some extra functionality) push the other block, and then finally go back and do the thing. There’s always weird tricks that mean that you’re going to walk backwards before walking forwards. I don’t think it’s impossible for these things to stumble into it, though. Just might spin a lot of cycles to get there (humans do too I guess)
- matsemann 1y ago
  Yeah, often working backwards and forwards at the same time is how to solve some advanced puzzle games. Then you keep it from exploding in options. When thinking backwards from the goal, you figure out constraints or "invariants" the forward path must uphold, thus can discard lots of dead ends earlier in your forward path. To me, those discoveries are the fun part of most puzzle games. When you unlock the "trick" for each level and the dopamine flies, heh.
  - TeMPOraL 1y ago
    I usually get a good mileage out of jumping straight in the middle :). Like, "hmm let's look at this block; oh cool, there's enough space around it that I could push it away from goal, for whatever reason". Turns out, if it's possible there usually is a good reason. So whenever I get stuck, I skim every object in the puzzle and consider in isolation, what can I do with it, and this usually gives me anchor points to drive my forward or backward thinking through.
    - RainyDayTmrw 1y ago
      Interestingly, I can't be sure if this is a reference to Go or Sokoban, and it might be applicable to both.
      - TeMPOraL 1y ago
        I think it's applicable to both, but I didn't play much of either :). But it's a method I employ in other similar puzzles and games, including "Baba Is You" in particular. The approach works in big part because these kinds of puzzles intentionally have very few degrees of freedom. Every element of the puzzle has a specific role to play, so if you look at a piece at random and notice something interesting about it, it's almost certain that this aspect is a part of the solution. This is very similar to math and physics problems in school as well: they're intentionally structured to contain exactly the minimum amount of data that's necessary for a single solution; take anything away, and the problem is unsolvable. Solving these, students are taught to check if they used all data provided - if they didn't, it means their solution is wrong. A less obvious realization is that this also lets you make educated guesses at the solution - since every piece of information has, by design, a specific role to play, you can start guessing what those roles are; if those guesses start to connect into a structure, it's highly likely you've just identified the middle part of the solution. Non-puzzle games, as well as real-world scenarios are, unfortunately, almost always underconstrained and full of irrelevant information; most things you see are there for random reasons, entirely unrelated to the problem you're solving. However, they may still be useful, so it's worth looking around anyway.
kadoban 1y ago
> But the resolution there was MCTS MCTS wasn't _really_ the solution to go. MCTS-based AIs existed for years and they weren't _that_ good. They weren't superhuman for sure, and the moves/games they played were kind of boring. The key to doing go well was doing something that vaguely looks like MCTS but the real guts are a network that can answer: "who's winning?" and "what are good moves to try here?" and using that to guide search. Additionally essential was realizing that computation (run search for a while) with a bad model could be effectively+efficiently used to generate better training data to train a better model.
- eru 1y ago
  > Additionally essential was realizing that computation (run search for a while) with a bad model could be effectively+efficiently used to generate better training data to train a better model. That has been known since at least the 1990s with TD-Gammon beating the world champions in Backgammon. See eg http://incompleteideas.net/book/ebook/node108.html http://incompleteideas.net/book/ebook/node108.html or https://en.wikipedia.org/wiki/TD-Gammon https://en.wikipedia.org/wiki/TD-Gammon In a sense, classic chess engines do that, too: alpha-beta-search uses a very weak model (eg just checking for checkmate, otherwise counting material, or what have you) and search to generate a much stronger player. You can use that to generate data for training a better model.
  - kadoban 1y ago
    > That has been known since at least the 1990s with TD-Gammon beating the world champions in Backgammon. Yeah, I didn't mean to imply that reinforcement learning (or applying it in this way) is novel. It was just important to work out how to apply that to go specifically. > In a sense, classic chess engines do that, too: alpha-beta-search uses a very weak model (eg just checking for checkmate, otherwise counting material, or what have you) and search to generate a much stronger player. You can use that to generate data for training a better model. I would say that classic chess AIs specifically don't do the important part. They aren't able to use a worst model to, with computation, train a better model. They can generate training data, but then they have no way to incorporate it back into the AI.

rtpg 1y ago

> However, most levels can be expressed as a few intermediate goals I think generally the whole thing with puzzle games is that you have to determine the “right” intermediate goals. In fact, the naive intermediate goals are often entirely wrong! A canonical sokoban-like inversion might be where you have to push two blocks into goal areas. You might think “ok, push one block into its goal area and then push another into it.” But many of these games will have mechanisms meaning you would first want to push one block into its goal, then undo that for some reason (it might activate some extra functionality) push the other block, and then finally go back and do the thing. There’s always weird tricks that mean that you’re going to walk backwards before walking forwards. I don’t think it’s impossible for these things to stumble into it, though. Just might spin a lot of cycles to get there (humans do too I guess)

matsemann 1y ago
Yeah, often working backwards and forwards at the same time is how to solve some advanced puzzle games. Then you keep it from exploding in options. When thinking backwards from the goal, you figure out constraints or "invariants" the forward path must uphold, thus can discard lots of dead ends earlier in your forward path. To me, those discoveries are the fun part of most puzzle games. When you unlock the "trick" for each level and the dopamine flies, heh.
- TeMPOraL 1y ago
  I usually get a good mileage out of jumping straight in the middle :). Like, "hmm let's look at this block; oh cool, there's enough space around it that I could push it away from goal, for whatever reason". Turns out, if it's possible there usually is a good reason. So whenever I get stuck, I skim every object in the puzzle and consider in isolation, what can I do with it, and this usually gives me anchor points to drive my forward or backward thinking through.
  - RainyDayTmrw 1y ago
    Interestingly, I can't be sure if this is a reference to Go or Sokoban, and it might be applicable to both.
    - TeMPOraL 1y ago
      I think it's applicable to both, but I didn't play much of either :). But it's a method I employ in other similar puzzles and games, including "Baba Is You" in particular. The approach works in big part because these kinds of puzzles intentionally have very few degrees of freedom. Every element of the puzzle has a specific role to play, so if you look at a piece at random and notice something interesting about it, it's almost certain that this aspect is a part of the solution. This is very similar to math and physics problems in school as well: they're intentionally structured to contain exactly the minimum amount of data that's necessary for a single solution; take anything away, and the problem is unsolvable. Solving these, students are taught to check if they used all data provided - if they didn't, it means their solution is wrong. A less obvious realization is that this also lets you make educated guesses at the solution - since every piece of information has, by design, a specific role to play, you can start guessing what those roles are; if those guesses start to connect into a structure, it's highly likely you've just identified the middle part of the solution. Non-puzzle games, as well as real-world scenarios are, unfortunately, almost always underconstrained and full of irrelevant information; most things you see are there for random reasons, entirely unrelated to the problem you're solving. However, they may still be useful, so it's worth looking around anyway.

kadoban 1y ago

> But the resolution there was MCTS MCTS wasn't _really_ the solution to go. MCTS-based AIs existed for years and they weren't _that_ good. They weren't superhuman for sure, and the moves/games they played were kind of boring. The key to doing go well was doing something that vaguely looks like MCTS but the real guts are a network that can answer: "who's winning?" and "what are good moves to try here?" and using that to guide search. Additionally essential was realizing that computation (run search for a while) with a bad model could be effectively+efficiently used to generate better training data to train a better model.

eru 1y ago
> Additionally essential was realizing that computation (run search for a while) with a bad model could be effectively+efficiently used to generate better training data to train a better model. That has been known since at least the 1990s with TD-Gammon beating the world champions in Backgammon. See eg http://incompleteideas.net/book/ebook/node108.html http://incompleteideas.net/book/ebook/node108.html or https://en.wikipedia.org/wiki/TD-Gammon https://en.wikipedia.org/wiki/TD-Gammon In a sense, classic chess engines do that, too: alpha-beta-search uses a very weak model (eg just checking for checkmate, otherwise counting material, or what have you) and search to generate a much stronger player. You can use that to generate data for training a better model.
- kadoban 1y ago
  > That has been known since at least the 1990s with TD-Gammon beating the world champions in Backgammon. Yeah, I didn't mean to imply that reinforcement learning (or applying it in this way) is novel. It was just important to work out how to apply that to go specifically. > In a sense, classic chess engines do that, too: alpha-beta-search uses a very weak model (eg just checking for checkmate, otherwise counting material, or what have you) and search to generate a much stronger player. You can use that to generate data for training a better model. I would say that classic chess AIs specifically don't do the important part. They aren't able to use a worst model to, with computation, train a better model. They can generate training data, but then they have no way to incorporate it back into the AI.