Beating Connect 4 with Graph Theory
Вставка
- Опубліковано 21 жов 2024
- I had way too much fun with 3d graphics this time.
Some references:
Amount of nodes after n plies: oeis.org/A212693 / web.archive.or...
Fhourstones, the first program to solve Connect 4 (to a depth of 8 plies,) which was also crucial for animating the graphs in this video: tromp.github.i...
The first published (weak) solution to Connect 4: tromp.github.i...
Rendered with github.com/2sw...
A (brand new and totally undeveloped) discord server for my channel: / discord
A nice discord community for Connect 4: / discord
Thanks again for the tunes, Tim!
In case you missed it, there are two communities you can join linked in the description! One is for 2swap the man himself and one is a connect four server that I totally have no vested interest in :)
guess its time to watch another really well made connect 4 video i dont understand
:')
Graph Theory is just determining the set of all eventualities.
@@neon_Nomad ...are you saying Graph Theory is my ex-wife's lawyer!?
it's*
don't*
"So far we've been interested in strategies of connect 4," instant sub. straight to the point. i love you.
💘
time for more "i don't remember this channel but i love past me for subscribing" content
:D
As a connect four expert, I understood about 5 of these words.
As a computer science/math student, I understood all but about 5 of these words.
As a drunkard, I understood the part where he talked about dancing dinosaurs.
connect + four
I built a solved connect 4 opponent on a raspberry pi, that would use image processing play you on a physical board. I used minimax with ab pruning. I could only go about 4 or 5 moves ahead within a reasonable amount of time. This is a really clever way to optimize the large tree of future moves. Wish I had thought of it then
sounds neat. how much time did it take to process those moves?
thinking of strategy in games as a compressed version for the actual solution is mind blowing
That's exactly what it is!
I really appreciate this comment lol, it's the first one to actually directly acknowledge the thesis of the video 😅
5:34 "we can now delete all other children"
is hilarious out of context
I knew someone would bring this up 🤣
Was about to comment this lmao
Every time i watch these game + graph theory type videos im always amazed and in awe of the beauty of such simple games. I really have to try implementing something like a basic minimax one day
Definitely give it a shot!
I used to be a teaching assistant for a class on search-based AI and minimax, so I am very happy to see such a well-made video on something so near to my heart. The visualizations of the state graphs showing the structure were extremely cool, and I'm excited for the insights you teased at the end! Connect four is way denser in transpositions than most games I'm used to like chess!
Hell yeah, I'm glad you liked it!
My initial reaction to your comment was to say, yeah, that's exactly right that connect 4 is oozing with transpositions in a way that chess isn't- but now I'm wondering if that's actually the case. I guess it depends on whether by transpositions you mean the strict notion of arriving at the same spot from 2 different paths, or in a looser sense of arriving at two positions whose continuation trees are isomorphic to each other. Honestly I am not so good at chess as to have a strong opinion, but I would be hesitant to say that chess doesn't manifest a bit of the latter kind of transposition. Maybe it's just harder to abstract out patterns from the noise in chess, and therefore harder to see the transpositions. Not sure!!
Therapist: left hand on top Mona Lisa doesn't exist, it can't hurt you.
7:58
lol
This is an incredible video. For a while I have been thinking about a pretty similar thing (in the context of optimal rubik's cube solutions), but I haven't actually put this idea into practice. I'm very excited for the next video.
Also very cool graphs. I recently wrote a program to draw graphs, but my simulation was limited to 2d. It's nice to see how much that kind of thing can be improved with 3d simulation.
similar video on rubiks cubes coming soon-ish!
started this video and immediately went on a tangent to watch every other video on the channel to get caught up lol. watching it for real this time!
A new 2swap video! I used to watch these when they first came out while I was in school, before dropping out, these are so well-explained and easy to follow!
Goodness, has our little community been going long enough for people to be nostalgic about it now?
@@sorin_markov Seemingly so.
Those graphics were incredible and so beautiful to watch! I also heard about the game of Connect 4 being solved back in the 80s, but didn't really know that much about its solution.
Thank you!!
hard to put into words how much i love + appreciate these videos, thanks a lot for making this
Thanks!! :)
YES NEW 2SWAPPPPP I LOVE CONNECT 4 THEORY
Another great video! I can't wait to see what's next!
😄
I am sad, why are there so many yucky compression artifacts on the video :(
I wonder if youtube is still doing some postprocessing or something... the black background behind the graphs doesn't look nearly as fuzzy or blocky on my end
I came to comment specifically to commend your animations, they look so clean and well thought out that it’s actually crazy. I am sorry it wasn’t exactly what you intended, but what it is is an amazingly crafted and beautiful video, so thank you so much for giving us quite possibly the best connect 4 video on the internet.
Thank you 🥹 im glad you liked it!!!
Ironic that a video about compression would suffer from it's own subject!
It's possible that uploading the original video in 4k would increase the bitrate and decrease compression at higher resolutions. Something to maybe keep in mind for future videos.
yeahhh. I'm gonna have to play around with it a lot. I'm passing a whole bunch of params into ffmpeg which seem relevant and are definitely tweakable, but I optimized that stuff ages ago up to how it looked on my end as opposed to youtubes end :/
If it helps, I watched on my phone, so much of the fine artistry was lost on me. 😭
HES BACK!!!!! LETS GOOOOOOOOOO
That… that is incredibly clever!! I never considered weak solutions as a thing, and applied theories specifically for networks is pretty brilliant.
this is actually insanely cool, subbed!
That Mona Lisa analogy is the best thing I’ve heard
Okay fine I'll watch the previous parts too lmao. I kept ignoring this rabbit hole, but I've finally clicked on it at 2am now and it's totally worth it to watch without being tired
mwahahahaha
@@twoswap alright, caught up. Can't wait for next episode!
Love this, yet another great one thank you! Keep it up
I did something like this for a variation of the 15 puzzle (with multiple solution states) once for a school project. Wish I saw this, it would have saved me a good bit of time with the ideas.
The goat has returned
Quit my job so I have a lot more free time now 🐐😎
This video is only 10 minutes, yet it feels like a full lecture on advanced algorithms and data structures
I'm gonna need some time to absorb this one
We are so back
The full tree is an example of data not information, colouring the nodes according to minimax starts to add information but it still isn't really the same as knowledge of the game's structure.
For a practical learnable strategy there needs to be a "why" for each choice. Everybody who plays connect 4 will acknowledge situations where the next move is "forced" in that it gives a win or avoids a loss. Stronger players look further ahead so have more comples "why"s. To be expert you would need either a means of prunning the tree or strategies that avoid the tree altogether.
very clear explanation and visuals, nice channel
Thank you!
It's not actually a tree, two moves each can end up at the same place if moves are transposed.
tree, dag, you get the idea 😅
Very cool visualisations!
One of my next few videos is gonna be about the busy beaver function 👀
@@twoswap, that's nice! I actually named my channel after the BB function
Let's fucking go another connect 4 dub for the boys
we are so back, we are the most back, the backest!!
Based and 4pilled
That Mona Lisa analogy was fucking awesome!
I made Connect 4 on my graphing calculator, I want to make it play against me but I'm too lazy, cool vid
amazing graphics! keep it up!
Thanks :D
Here it is, the generalisation I've been waiting for. Discrete mathematics rock!
I built a solved connect 4 opponent on a raspberry pi, that would use image processing play you on a physical board. I used minimax with ab pruning. I could only go about 4 or 5 moves ahead within a reasonable amount of time. This was plenty to beat most human opponents. This is a really clever way to optimize the large tree of future moves. Wish I had thought of it then.
I also played about 1000 games in the time, and studied James Allen and Victor Allis’ brilliant papers. Both are great reads in my opinion! 😉
Thats super cool, especially with the image recognition!
very underrated channel
Thank you!
wow, nice video. Very well made🙌🙌🙌
Thank you!!
Awesome video. I love math visualization
Billy Butcher would like to know your location.
Man, after learning about this solution for connect four, i dont even imagine how useless the solucion for chess will be. Probably completely unusable. Thanks for the video, as someone who participated in math competitions, this side of the "there is always a winning strategy" is a new perspective for me
To avoid combinatorial explosions, maybe try focusing on the end of the game, and forget about turn order. there are only 3 ways to win, horizontally, vertically, or diagonally, and those problems are transposed around the board. Your strategy to defend against these should not be in a global coordinate space, but local strategies relative to the dangerous arrangement. It should mix 2 strategies, defense and offense, depending on how dangerous the board is.
This is very similar to the idea in Victor Allis's paper (the one linked in the description!) Unfortunately, or at least with respect to that paper, that thought process was only considered formally with regard to the defensive aspect on behalf of player 1, and was used to show formally without search that the game is _at least_ a tie or better for player 1. Further search was required to show that the offensive endeavor on behalf of player 1 bears fruit.
1:18 but there are duplicates? (exact duplicates, not mirrors like mentioned later)
Those aren't double counted (which is the reason the table shown gets slower than 7^n at 3 moves.) Sequences 147 and 741 are (at least in this video) treated as the same node. That's also why some of the trees shown have loops in them :)
Guys, I actually learned about Minimax in universal paper clips, please applaud me and give me a standing ovation 😎😎😎
Awesome video!
Thanks!
fantastic video
Thanks!!!
I dont understand how but after about two years in middle school of playing the max difficulty connect 4 computers, I've become unbeatable (I always tie or win). I'm curious to see how this video deepens or changes my understanding of the game and my undetsanding of it.
This is so impressive! Do you have any suggested reading/literature/channels that go into more detail on graph reduction?
...no, sorry :'|
Wow that's helps me understand graph theory
Shouldn't the game tree actually be a DAG if we're talking about things like canonicalisation (elimination of mirror positions)? Never mind that you can reach the same position via many paths, i.e., the first optimization anyway is putting the positions in a hash table instead of storing them naively... maybe this was mentioned.
It absolutely is a dag, canonicalized or not!
i dont know what Im watching but im interested
My graphics card laughs at the thought of only calculating 4 trillion nodes. Time to spin up cuda xD
Great content
@2swap I'm really interested to see if you can prune enough via heuristics to create a human-learnable undefeatable strategy for the first player. Based on my own C4 experience I would guess that it is possible.
thats what I'm aiming on here :) I've pulled it off for about ~15% of openings so far, and I suspect I can keep on chugging along. It will take time and work (hence the filler videos haha)
@@twoswap you're killing it 🫡
for anyone who wanats to know geting rid of the bad options as seen at the beggining is called alpha beta pruning
This is interesting, but yea, as people say it's pretty hard to wrap the head around all of that ha ha
WOOOOOOOOOOOOOOOOOOO
Now do it with chess
"We can now delete all other children" - average computer scientist
3:30 animation looks cool but its kinda hard to see whats happening to actually understand it
Ahh man, I did not appreciate until now how faint it looks on OLED screens. That's probably why? Rendered it on desktop.
Hell yeah
are the nodes connected when they match another board exactly but the journey was in a different order? Also could you use TSNE?
Yep, nodes correspond to board states, not move sequences, and thus transpositions form undirected cycles. Nothing is stopping you from using TSNE, but thats not what I'm going for here- I still want to be able to discern graph structure, not just identify subcomponents.
mm yes i am going to forget all of this 30 minutes after closing the video
I don't think you mentioned transpositions, where different move orders reach the same game state. A lot of strategies rely upon these as a sort of knowledge compression trick.
At least with respect to the representation im using here, transpositions are already diagrammed as (undirected) cycles in the graph. Super helpful, but at the same time, if your goal is to compress the graph itself, those transpositions are _already being taken into account_, in some sense!
@@twoswap out of interest, what are you using to plot those 3d graphs ?
its all 100% custom, the repo is in the description! You are looking for the file called OrbitScene3D.cpp.
@@twoswap very nice work
You should be able to cut the # of games in half because of symmetry.
Won't help at all, but I love symmetries :)
For any given board configuration, flipping the board 180 degrees gives you a new configuration which has the same outcome
How did you make the trees visualisation?
my own tool! github.com/2swap/swaptube
1:30 why does the pattern not just continue as powers of 7? Other than 1 side being completely full or someone winning (both of which shouldn't be possible by the second move), how could the number of possible moves decrease?
the same reason the graphs animated are DAGs and not strict trees (in the sense that undirected cycles can come up). you can get to the same position by several different ways. For example, red plays column 1, yellow column 4, and red column 7, or the other way around (7 4 1.) You land in the same spot.
@@twoswap ohhh that makes sense.
4 trillion is fairly small right? You could brute force it
Not without a/b pruning and fancier methods than pure minimax! Or maybe with some super super pricey compute...
How are these graphs visualised? A game engine? Custom written program?
can you teach.? how you make those cool things ?
Fyi the visualizations are hard to read on the phone screen.
Yeah ;-; I only realized after posting how bad it looks on OLED
i find it funny how you're mentioning "in-reality a memory couldn't bare this task" while there are chess GM who are remembering thousands of endgame positions, and can recall games from a certain position without context... Magnus is said to remember more about 10,000 games and most GMs can play a near perfect endgame without seeing the board.
So I think that yes, a human can be a master in connect four without realising the entire context of his play.
there's a universe of difference between memorizing enough to be proficient vs memorizing enough to guarantee optimal play
Why isn't this a SoMEpi submission?
Don't know anything about SoME or the submission process, do I just slap the #SoMEPI in the title?
This is why I stopped playing Connect Four, too many sweats
What did you use to animate this video?
my own custom bespoke tool: github.com/2swap/swaptube
@@twoswap ooh, this tool is cool!
I suppose I have a reason to learn c++ now (as I want to get into animating similar styles of videos) or just port it to java or rust (which I am already learning.)
@@ees4. Man i need to learn rust lol.
If you start doing anything of the sort, tell me about it before hand :D i might be able to help or something. I thought about porting to rust myself
@@twoswap i'll let you know when i stop procrastinating and start porting ;D
Now do this but for go
lots of go vids coming sooner or later
@@twoswap 🔊📣📢
You say that 4 trillion is too much to compute, but that's not really true. If you computed 1 million nodes per second (easily doable in a system language like C) you would need just 46 days for the computations to finish. An experienced programmer could probably go far beyond 1 million/s.
...i don't want to wait 46 days!
Nowadays, people would brute force everything with deep learning. That's how you actually solve problems. Only a very small amount should require hammering with deep learning. And the brain consumes much less energy than these data centers with thousands of GPUs so it's better for the environment.