by sillysaurusx
4 subcomments
- I'm surprised no one linked to his video on the topic. I can't overstate how high quality it is. The graphs are simply beautiful, and it made me think he had a whole production team behind him. That he was able to do cutting-edge work like this (it's new, which qualifies) while creating a work of art is incredible.
"I Solved Connect 4" https://www.youtube.com/watch?v=KaljD3Q3ct0
- > which is fundamentally different from existing strong and weak solutions
It doesn't seem fundamentally different from Victor Allis' solution, but 2swap managed to generalize and streamline the rules available for static solutions, while also picking the winning moves that reduce the overall tree size.
> A weak solution can be visualized in a way that a strong solution (14tb uncompressed, 350gb compressed) cannot.
That is using an overly strict interpretation of strong solution.
My database of all roughly 68000 8-ply positions allows for computing the best move from any position within seconds and takes only 12KB compressed (using one trit per 8-ply position, 5 trits per byte, using remaining 256-3^5=13 values for run length encoding).
[1] https://tromp.github.io/c4/c4.html
- I've been intrigued about the thing they call the "data product" for a long time: the fact that there's a sort of equivalence between precomputing position analysis and doing no runtime analysis vs knowing nothing and doing everything at runtime. It is a general property of a lot of algorithms that you can precompute various amounts of computation in order to reduce runtime complexity. It's also the difference between "telling an LLM to do a task" and "telling an LLM to write a bunch of code to do a task", which are also the two ends of a spectrum.
Especially interesting is the fact that the optimal strategy, where on the spectrum you go, is affected by the effectiveness of your algorithms on each side. The more efficiently you can cognitively compress precomputed decisions, the more it makes sense to precompute; the more efficiently you can apply techniques for move selection at runtime. And the two interact a lot: for instance in chess, there are simple heuristics for a lot of endgames, meaning that the state space you explore at runtime can terminate as soon as it gets to an endgame that you have memorized a solution for.
I wonder if anyone knows anyone examining this phenomenon in generality?
- FTA: “As a motivating example: player 1 (hereafter dubbed "Red") can win by playing in the center column on the first move and then following the weak solution's suggestions, but would not be guaranteed to win if the first disc is played elsewhere. The weak solution contains no information about what would happen in the other columns- As far as Red cares, it would be redundant to learn those branches, since they are not good.”
I don’t think that “since they are not good” is necessary for a weak solution. Even if every first move were winning, it still would be redundant to learn how to win for every possible opening move.
A weak solution gives you a guaranteed way to move from START to a win, whatever counterplay, not all ways to go from START to a win, whatever counterplay.
- This guy’s videos are awesome. He also has one on Klotski and the double pendulum. Beautiful graph animations.
by donkeyboy
1 subcomments
- Sadly this doesnt have a simple way to know how to win besides the ForceEven approach and offering an Anki Deck. I wish there was some more intuition or guidance around winning that humans can memorize
- for those who are into books i'd recommend taking a look at alphago simplified by mark liu. It has rule based strategies + DL for connect for and other simple games.
- This is the clearest breakdown of Connect 4 I’ve seen.
- sounds like 5 dimensional chess to me
by soumyaskartha
1 subcomments
- Connect 4 is one of those games that looks simple until you realize it was solved in 1988 and the optimal strategy still takes serious compute to run in real time.
by ineedasername
0 subcomment
- No, no-- I've seen the movie and I'm pretty sure it was established that the only winning move was not to play. Not ruling out the possibility I'm misremembering, there was more than one game in the movie, it could have been Galaga?
Hacker News