How many Connect 4 positions are there?
Vložit
- čas přidán 27. 07. 2023
- In this video, I give an original proof into how many Connect 4 positions there are. This video is a submission for #SoME3, The Summer of Math Exposition 3, a competition designed to invite people to make educational math videos!
Feel free to point out anything in the video down in the comments!
Music:
• austin chen - masked (...
• Kenai - Nobody Knows ♡...
Bruteforcer:
tromp.github.io/c4/c4.html - Zábava
*Correction:*
At 5:14 and 5:55, I say 70 quintillion instead of 70 trillion, excuse my loss in translation!
Good video! Another type of illegal position that you're not considering is that just because a board state has an equal amount of red and yellow pieces doesn't mean that those pieces could have followed a turn structure. For example, imagine 4 pieces stacked vertically in one column. The bottom two pieces are yellow, and the top two pieces are red. This doesn't make any sense, since the only way this could have happened is if yellow played twice and then red played twice-- when it's standard for red to play first, and each player can only move once. Now you've got me interested, might get sucked into this problem now lol
I'd just like to imagine these next 2 years Gallium will become exponentially better, like their old videos compared to now.
The originality of this proof and the fact that this whole thing was built in freaking POWERPOINT and not Manim is absolutely tremendous. Your foundations are built, Gallium. You are ready to build your walls, and climb high. gl :)
Its quite refreshing seeing the occasional text only video, I really like it!
Also thank you for the thanks at the end!
The only thing i know is each player has 69 winning lines. Check it yourself, i made a connect 4 game with logic so i needed to do all of them and thats when i noticed
First off, I appreciate the thank you, and this is very impressive. Something I was wondering is how to filter illegal positions, I wonder if there is a way to make a formula that *detects* positions that are illegal using coordinates. Like maybe it outputs a certain integer based on the x and y. First it checks if a position has been won by counting the coordinates of each color, and it uses a formula to make sure each position that has been won already equals zero. Then we count how many pieces have been placed. If more have been placed after the win was complete, then it’s illegal.
This does seem very daunting though, and would take way more effort than it’s worth.
Maybe first make a detector to see how many positions have been won, call it w. Then we know that the number of illegal positions (i) is less than w. So we can take w away from all the possible permutations to get the final lowest possible number of positions.
You could just multiply a piecewise function f(x), returns 0 if illegal (so the sum won’t count it) and 1 (the sum will count it). f(x) could check if every possible case has 2 or more 4-in-a-rows, but even that isn’t enough, if yellow goes first and the counters are even, given only the board and nothing else, we can’t do anything! If we were to figure out that, it would probably only generalize to _that_ specific case, and I would consider that to be bruteforcing. So yeah, its tough!
@@gallium-gonzollium Yeah I ran into the same issue after I thought about returning 0. Brute forcing seems impossible right now, but we can’t know how impossible it is since we don’t know how many illegal parts there are.
Maybe there could be an assignment for every possible win state (Much smaller number) and if that number has been reached by a coordinate of one color then a win state has happened. Each win state could include the maximum number of moves needed to get there and if the moves exceeds that then we could count it as an illegal move.
This process wound eliminate some but not all illegal moves, it would give a more accurate estimate though I guess.
Or there could be a trial run where a computer runs some games using random placements, it goes with the rules and everything, and then it counts up how many games ended illegally and outputs a percentage. That could be the average number of games that are illegal and you could take that percent out of the total sum.
This method feels much less clean and more like guesswork so I dislike it, but felt I should comment it anyway.
ooh nice now i can memorize all quintillion positions so I can win connect 4 every time!
How do i always win chess then?
Stockfish
the connect 4!
Interesting! I'm really curious about the number of the legal positions as well. Too bad I have more important tasks to spend time on, haha.
i think r/Googology will like this video (though the number is tiny compared to what Googologists are dealing with)
I’m trying to find a general formula for probability that dominoes have the same side
In general with N dominoes or all 28?
I was thinking that I could calculate the number of total positions possible with each column having 0-6 pieces. Then calculated the number of positions accounting for color, if odd, one more red piece than yellow, and same number of red and yellow if even. Only order matters because of gravity. First count all positions with no lines of four of the same color, and have at least one red on the bottom row, as red goes first. Then use some code to count the number of boards with exactly one line of four, whether diagonal or horizontal or vertical, with at least one piece with nothing above it, as it must be the last piece placed. However, upon further thinking, only vertical lines have to be four. One can make lines of 5-7 diagonally and horizontally, or both on the same board by combining two separate parts with one piece. 2 rows of 3 with one in the center to make 7 for example. So we have to count all 4-7 piece combinations of horizontal, vertical, and diagonal positions given that they are connected by a single piece with nothing above it. If they are disconnected, it is impossible. It remains that all sections of length 4 of the same color have to have at least one piece with nothing above it. Then add all full boards with no lines of four, aka draws, and you're done. Someone who knows python or chat gpt might be able to do it.
Wowza
i hate maths but you just made it interesting
the number your provide: 70,728,639,995,483; is only in the trillions. Is there a quintillions number for the calculation?
oh my goodness, the word ‘trillion’ got lost in translation as ‘quintillion’.. Rookie mistake from me!
Hello bro, could you give me your email or any means to communicate you, I really want to learn from you
galliumgonzollium on discord