Optimal Strategy for Connect 4(2swap.github.io) |
Optimal Strategy for Connect 4(2swap.github.io) |
"I Solved Connect 4" https://www.youtube.com/watch?v=KaljD3Q3ct0
He has a program instead: https://github.com/2swap/swaptube/blob/1a0d5369d523536d48e4/... [1].
[1] Note that this commit ID is visible from the video itself: https://youtu.be/KaljD3Q3ct0?t=1002
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.
I'm not clear how they came to the steady state solution, or how it is memorizable, or is it just intended to be brute forced at that point?
At some point long ago, I was bored and memorized a whole bunch of openings and intuitive rules, and would end up with a 90%+ win rate. Lots of fun.
Deriving the steady state solutions was most interesting to me as well, author just described it as “a genetic algorithm”.
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).
Edit: oh, found it, it's from this repository: https://github.com/sidneycadot/connect4/blob/main/7x6/README...
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.
What is PLUS times PLUS?
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.
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?
$ time ./SearchGame < input.root
Fhourstones 3.2 (C)
Boardsize = 7x6
Using 8306069 transposition table entries of size 8.
Solving 0-ply position after . . .
44+26
45+28
42+27
47+26
4-29
+29
score = 5 (+) work = 29
1479113766 pos / 139494 msec = 10603.4 Kpos/sec
- 0.249 < 0.125 = 0.027 > 0.191 + 0.408
real 2m24.904sConnect 4 is a win for the first player
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...
I've stumbled onto deeply disguised dualities in my career. (One could argue with a straight face there are only two, but this is not formalized.) It's more a psychological process than a technical one.
It's always possible to ignore that one is standing in a tree farm. Trees have such interesting bark.
Do the work of indexing, or summarization or compression vs just do it retrieval on the raw records.
It could be embeddings, or presorts or indices.
But I think the parent poster is correct. There’s an inherent write vs read tradeoff as well as memory vs compute. Maybe with some generalization vs specialization.
Idk if im explaining properly. But you can always front load more effort on a narrower problem space and then utilize it on that space downstream.
I think with your llm example there is no code/data split. The llm is caching a solution to a narrow problem by writing the code.