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?
Optimal Strategy for Connect 4
21–30 of 34 posts
Re: Optimal Strategy for Connect 4
#22I'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
1. The video is amazing. It does deserve a shoutout.
2. I actually prefer when HN links to articles rather than videos. I kind of expect interesting reads, not watches when I open this forum.
Re: Optimal Strategy for Connect 4
#23Connect 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.
Not that serious, since you can solve the 7x6 game from scratch on a typical 2013 single core in a few minutes (and in 67s on an Apple M2):
$ time ./SearchGame 0.191 + 0.408
real 2m24.904sRe: Optimal Strategy for Connect 4
#24This guy’s videos are awesome. He also has one on Klotski and the double pendulum. Beautiful graph animations.
OH it's that guy. His double pendulum video was orgasmic. Edit: Oh wait, no, I was thinking of the Drew's Campfire double pendulum video. That video was extra interesting because the creator is not a typical content producer. He just has a few videos without any views, then dropped what might be one of the best videos of all time, and then went back to his technical videos. [1] https://www.youtube.com/watch?v=8jVogdT…
Not sure why this is being downvoted, but I watched the recommended video in a single riveted sitting. Absolutely amazing.
Re: Optimal Strategy for Connect 4
#25for 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.
Re: Optimal Strategy for Connect 4
#26I'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?
Re: Optimal Strategy for Connect 4
#27I'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 betwee…
isn't this very similar or a case of trading space for time or vice versa (e.g in algorithm analysis)
Re: Optimal Strategy for Connect 4
#28I'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 betwee…
isn't this very similar or a case of trading space for time or vice versa (e.g in algorithm analysis)
That is certainly an example of it, but I feel like what I'm talking about is more general. In algorithms you tend to be able to say concretely exactly how much space vs time you're trading off. But in a game like Connect 4 or chess it's a lot harder to say exactly how much you gain from, say, adding one more heuristic to your board analysis, or memorizing one more opening subtree. I don't know how to think about that mathematically, and I would like to. It's related, I guess, to what the OP says about finding a graph which is information-theoretically small rather than graph-theoretically small.
Generally it's interesting to contemplate that there may exist heuristics which no one has thought of yet that dramatically improve your overall performance. Actually I thought of an example of this. When AlphaZero and Leela (the ML-based chess engines) started beating Stockfish (the preeminent graph-search chess engine), one of the early things people noticed was that they loved to push their a- and h- pawns down the board, which was, I guess, a sorta passive move that people had systematically undervalued before (cf [1]; I remember seeing a good youtube video about it also but I can't recall what it was). Which means that just having this heuristic was worth some amount of ELO the whole time, just, no one had realized it! Presumably the optimal play for a human in chess, whose mental capacity is limited, is a certain mix of memorizing fixed positions vs heuristics, and the interactions between those are what's interesting.
[1]: https://www.reddit.com/r/chess/comments/ljp151/why_is_h4_pla...
Re: Optimal Strategy for Connect 4
#29Sadly 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
This is the first human-learnable weak solution for connect 4. Surely it can be improved.
Re: Optimal Strategy for Connect 4
#30No, 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?
Tic-Tac-Toe is the existing game the machine realises can't be won, and then Global Thermonuclear War is the next game it simulates and discovers also cannot be won according to the metrics it is using.
Connect 4 is a win for the first player