Comment by sillysaurusx | Hacker News Reader

Comment by sillysaurusx | Hacker News Reader

This seems closely related to the problem of getting GPT-2 to play chess.

Vanilla neural networks can predict the next average move, which isn't necessarily the best move. If the model sees a lot of chess games, it will learn a lot of opening moves. But it'll get hopelessly lost within 13 moves.

What's needed is a formulation of self-play, i.e. to apply the AlphaZero / MuZero algorithm. With Game of Life, the game is: given the current board state, predict the next board state. You can have a simple rule like "start with 100 lives; every misprediction subtracts one life."

Since AlphaZero / MuZero plans with respect to a tree search, self-play should rapidly improve for Game of Life.

The crucial difference here is that you're training on a simulation, not examples. It's like the difference between walking around the real world vs seeing random photos of random places.

The alphazero algorithm is quite fun to implement, and somewhat understandable with a bit of effort: https://web.stanford.edu/~surag/posts/alphazero.html

Honestly, turning a supervised learning problem into a reinforcement learning problem is an extremely wasteful way to burn a lot of electricity.

Supervised learning is orders of magnitude more efficient and better understood than reinforcement learning.

Reinforcement learning is an algorithm that can help you find unknown solutions to interact in an optimal way with a system. To predict the next board state, you know the solution already. So, this is a supervised learning problem.

If that were true, there wouldn't be any reason to write this submission's article. But the article points out that it's not merely a supervised learning problem; the number of board states for a 768x768 board is 768x768xN, where N is the number of time steps. How would you gather labels for every possible board state? It would require 768 factorial labels to represent every possibility.

Consider the problem of face completion: https://scikit-learn.org/stable/auto_examples/miscellaneous/...

Given a set of faces, mask off random parts of the face, then try to fill in the holes.

Neural nets excel at that kind of task, because as you say, it's a supervised learning problem: you "know the solution" (the missing face) and you can penalize / reward the model so that it learns a correct face on average.

But game of life is nothing like that. Every board is a valid board. You can set the board to whatever values you want, and then say "Go!" and game of life will happily simulate it.

Therefore the neural network's goal isn't to learn the board state; it's to learn the rules, and to obey the rules. Hence, self-play seems like a reasonable formulation.

Without self-play, your learned network will always overfit or underfit different scenarios. E.g. even if it does well in general, a sparse board might throw it off. Or a board with a bunch of pieces in one corner. Or a board in a checkerboard pattern. But self-play will automatically handle all of these cases, because it's forced to learn the patterns over time.

Minesweeper is another example: it's possible to win every game using nothing but logic (disregarding tiebreakers), so therefore the solution is known. But I don't think it can be formulated as a supervised learning problem. There are too many board states, and the board states are related to each other via logic ("am I obeying the game state?") rather than atoms ("what does a human face look like?")

I can try to address some of your arguments one by one:

> How would you gather labels for every possible board state? It would require 768 factorial labels to represent every possibility.

You don't need to represent every possibility. Just a sufficiently large dataset and a neural network with a sufficient amount of prior and size. Note that e.g. video continuation networks already exist and deals with comparable data sizes.

> But game of life is nothing like that. Every board is a valid board.

Yes, but given the previous board (or the board N steps ago) there is only one valid board. Hence, a supervised learning problem.

> Without self-play, your learned network will always overfit or underfit different scenarios.

This confuses me. Why do you think self-play avoids over- and underfitting? How could one approach even solve both over- and underfitting at the same time?

> Minesweeper is another example: it's possible to win every game using nothing but logic (disregarding tiebreakers), so therefore the solution is known. But I don't think it can be formulated as a supervised learning problem.

Sure it can. If the solution is known, just train a neural network to mimic the solution. That's what network distillation is all about.

I've never heard of video continuation networks before and I would love to learn about it. Can you provide a link?

A pointless project I've wanted to do but don't have time is training GPT-2 to play Core War https://corewars.org/

I haven't been involved in that for years, but I'd be very curious to see the (presumably) very non-intuitive code that could be generated.

Self play applies to adversarial games, where both players are the same AI being trained (instead of AI VS humain or AI vs best known AI).

Game of life is not an adversarial game, there is no opponent, you can not apply self play to learn the rules.

So... I'm no AI expert, but I play some StarCraft 2, and I'm curious about how exactly Alpha Zero learns and why it's not applicable to some problems.

Contrary to go or chess, StarCraft includes asymmetric matchups (three very, very distinct races, so in 1v1 - six possible matchups). Every matchup is played very differently; one trivial example: if you'd try to play a Protoss vs Zerg match like you'd play a Protoss vs Protoss, you're going to lose really, really badly within minutes: the standard PvP opener (wall-off at the main base) is going to leave your natural expansion completely defenceless against a trivial early attack (mass zerglings), which snowballs into a very, very bad economical disadvantage.

So basically when AlphaStar learns, it absolutely must be really good at handling these kinds of asymmetric scenarios (both players/actors having a vastly different arsenal at their disposal, starting from t=0), otherwise it would lose every single non-mirror matchup (while it's actually beating many grandmasters).

Another peculiarity of StarCraft is e.g. with Zerg, as the race that normally opts in to play the very early game a bit blindly (late scout with a slow Overlord vs an earlier worker scout), but must still make some strategic choices, the most common (and optimal) being greed, which occasionally means losing to aggression or missing a chance to punish a greedy opponent. Humans here kind of rely on intuition, metagame, etc.

My question is, can the capabilities to handle the asymmetry, and to play blindly, be exploited by re-modeling a class of problems, such that they become "StarCraft-like" enough? E.g. (naively) if the Game of Life board is not "correct enough" by iteration N, the opponent will flood your base with zerglings ;)

Reply on news.ycombinator.com