FAQ and corrections in this comment! 1) Check out today's sponsor at brilliant.org/alphaphoenix/ for 20% off! 2) Yes, there will be a part 2 video, but no, it's not coming out next. these programming videos are monstrous to edit because they're all animations and I can't stand to look at this project anymore. hopefully the next video is something fun with the high speed camera! 3) I'd love to see more people take a crack at this! Someone on Patreon wrote a fantastic algorithm this week that could take loads of steps backwards on a glider, but apparently struggled with the larger "play button" pattern I was using. 4) A LOT of people are complaining about the complexity section, but I chose my words very carefully there. I said “NP complete is AT WORST exponential”. I also said “there’s no KNOWN algorithm” to solve NP hard questions in polynomial time. 5) AI would be awful for this problem. Neural nets also likes smooth parameter spaces, and they are good at finding “good” solutions not “exact” solutions. 6) a lot of people are pointing out that there can be more than one GoL board that leads to any given desired GoL board. On the surface it feels like this would make the problem easier, because there are more solutions to find, but it’s also this property that guarantees you will have “Eden” game boards that cannot be produced by a previous step. 7) Tile solver: a bunch of people have suggested pre solving tiles, and I love this idea - it’s one that I tossed around too late down my path of pixel-by-pixel SAT. You’re trading precompute time and memory to build an enormous library: find every way to back up a 3x3 area and save them, then catalog if a tile is used to back up a particular state, what tiles could be adjacent (this will chop down the long list to a less but still quite long list), then you can build a solution from tiles. Maybe by making tiles from tiles iteratively you could precompute solutions for quite large patterns. This may be an interesting way to cut down run-time complexity pretty massively. I didn’t initially go this way because I felt it would be difficult to keep the simulation small while taking multiple steps backwards, but that could be sorted by your tile selection method/biases (a sat solver would be faster but it’s not easily biasable)
@tomholroyd7519
10 күн бұрын
Garden of Eden patterns were proven to exist. So in the worst case it is irreversible. It may be hard to find examples of Gardens of Eden --- oh, it seems you found some!
@youngbloodbear9662
9 күн бұрын
Why couldn’t you invert the rules and check the possibilities that meet those rules?
@yaksher
9 күн бұрын
Minor correction is that "NP" (which as you say at one point) is "nondeterministic polynomial" which does _not_ mean it is not polynomial. We're "pretty sure" that NP-complete problems cannot be done in polynomial time, but proving it is literally a million dollar problem and it's not _known_ to be impossible to do in polynomial time.
@yorthundir7343
9 күн бұрын
It's not really important to the eventual purpose of the video, but I got caught up by the map at 17:30. I assume the edges wrap, which would account for the odd shape of the ring, but a lot of the top points on the ring are unbalanced despite being of equal height to full solutions next to them. I also don't see any space for solutions that are 3/4 one density and 1/4 of the other. In the end it's either just an imperfect example that demonstrates what it needs to just fine and I shouldn't be thinking about it this hard, or I'm missing something glaring, which is equally possible.
@georhodiumgeo9827
9 күн бұрын
Can you say what that library was and maybe a link? Python I'm assuming? Great video! I watch everything p vs np related and all of your videos so today was a great watch.
@Tandanuu
10 күн бұрын
Bro just made a whole series about entropy and thermodynamics and now he’s surprised that reversing something like Game of Life is hard? :D
@Windows__2000
10 күн бұрын
It is kinda unintuitive that a system can be deterministic in only one direction...
@ckq
10 күн бұрын
@@Windows__2000not really if there's multiple ways to undo a step but 1 way to go forward. Or just create a measure of entropy
@GigsVT
10 күн бұрын
@@Windows__2000a little bit but it's the idea behind cryptographic hashing and RNGs and a lot of CS stuff.
@hadensnodgrass3472
10 күн бұрын
@Windows__2000 Hashing is the fundamental principle of privacy on the internet, computers in general. Hashing is crazy simple in one direction, while becoming an NP Hard problem in reverse. Large prime encryption key methods work in a similarly way. However they encryption is easily reverseable if you have the private prime key. To compute the private key is an NP Hard problem. Gotta love NP problems, that is why it is one of the Millennium Problems.
@321ooo123
10 күн бұрын
Actually it's not as simple as that. Entropy can be decreased locally at the expense of an even bigger global increase. So it could be that you'd be able to reorder GoL at the expense of some other increase of entropy. (Not the case with GoL, however).
@satibel
10 күн бұрын
"we did it not because it was easy, but because we thought it would be easy" (Naive developer discovering that the algorithm they are trying to reverse is not bijective)
10 күн бұрын
Bijective or not doesn't necessarily make much of a difference for how hard it is to compute. Eg mapping between positive integers and their prime factorisation is bijective, but one direction is hard to compute.
@imsleepy620
10 күн бұрын
Bijectivity doesn't imply ease of computability in each direction, but lack of bijectivity might imply a lack of ease of computability to find the inverse image, for some general enough class of functions?
@brothertyler
10 күн бұрын
Surpised you didn't show a solved rubics cube and ask the viewer to try to figure out what unsolved state it began from
@AlphaPhoenixChannel
10 күн бұрын
lol I love that
@DeadJDona
9 күн бұрын
on step -1 of solving cube you could only rotate slices from single spatial direction, on step -2 from another (or same), etc. this kinda decrease field of possibilities
@HolmesHobbies
9 күн бұрын
Perfect analogy!
@BryanLu0
9 күн бұрын
@@DeadJDonabut a Rubix cube solve could've taken 20+ moves
@Jone952
9 күн бұрын
@@HolmesHobbies Is it? Every starting state is a valid one for a solved rubics cube
@procedurecall4219
9 күн бұрын
Computer scientist here. If you're just using the SAT-solver built-in to Z3 (as opposed to SMT constraints), you should really instead be using a specialized sat solver like cadical or kissat. They're much much much faster. >1 week for one sat solve at the problem scale you're dealing with is almost always unnecessary. The annual sat competition does a good job keeping track of what's currently fastest. If you're actually using SMT constraints in Z3 (like you were previously with integers), you should almost certainly switch to CVC5. It is also much faster than Z3 in almost all cases (save for some theories that you won't use). Also, you almost certainly should not be doing manual a local search for multiple steps like you are now. It should be very straightforward and fairly efficient to encode multiple steps of your constraints at once into SAT (or SMT). Then you don't implement manual backtracking (which I'm assuming is what you're doing currently with your "edens") - that's already what DPLL does (and hence what CDCL emulates). I'm not sure what your constraint formulation looks like, but also see if you can add any "symmetry breaking constraints". It shouldn't be too hard to find good resources on why these are useful and what they look like. Not super important, but also the thing you're calling a "phase space" is what would be called a "reconfiguration graph" in my field, since it's a graph over the space of configurations whose edges correspond to a certain type of "reconfiguration move" (in this case, flipping the colour of a grid point). There are some much cooler reconfiguration graphs. Fun fact the simplex method for linear programming is a greedy reconfiguration graph traversal.
@AlphaPhoenixChannel
9 күн бұрын
The most successful algorithm I’ve tried takes a number of steps backwards at once - as many as I can until it hits a computational limit of multiple days. I’d be very interested to know if there’s a solver optimized for inequalities - my best-performing single-step iterative solver was seeking to leave as few live cells as possible.
@AlphaPhoenixChannel
9 күн бұрын
I know it’s not kosher, but I colloquially call phase spaces, configuration spaces, and parameter spaces the same thing
@procedurecall4219
9 күн бұрын
@@AlphaPhoenixChannel You're much further along than I thought if you have a multi-step implementation, nice! For inequalities, ILP solvers are often recommended, but in my experience they don't perform very well on these sorts of highly combinatorial problems. Z3 has an optimizer built-in that I'm sure you've already found, but it is extremely slow, even on much smaller problems than what you're dealing with. Since actually finding the absolute minimum is actually a very strong constraint (requiring either exhaustion or a lower bound, or some combination of the two), you might get better results by relaxing it to some heuristic bound on the number of living cells - say, at most 10% more living cells than what you started with. Any chance you're planning to publish your code? I'm curious to see if there are low-hanging improvements. Also, if academic publications in overlapping math/cs ever interest you, this is exactly the kind of thing the folks at jcdcggg really like.
@AlphaPhoenixChannel
9 күн бұрын
@@procedurecall4219 I had luck with the SMT solver using an inequality to limit the number of live cells and slowly climbing with that limit until I got a solve. It didn’t work well (ground to a halt) for multi-step solves where I tried to limit the number of live cells in the final step, and I couldn’t come up with a way to limit the number of live cells once I went full Boolean (aside from just giving it a small bounding box)
@AlphaPhoenixChannel
9 күн бұрын
That 10% more limit is startlingly close to what I was actually able to attain lol
@Drawliphant
10 күн бұрын
"Conways Game of Death" completely fair name because it kills the developer
@sumner1107
10 күн бұрын
Covid 19 killed the developer (Conway)
@jasonhildebrand1574
3 күн бұрын
He survived this round.
@oafkad
9 күн бұрын
That false solution thing is also the mechanism behind a lot of "Why didn't evolution lead to X!" conversations. You basically never will go down a hill, even if the evolutionary mountain on the other side is four times as high. Creates these feedback loops where animals keep terrible systems because in order to improve they'd have to "unwind" first.
@bozodragojevic
9 күн бұрын
Meteors are the "unwind"
@CoolAsFreya
7 күн бұрын
The maths term is "local maxima" which might not be as high as the "global maxima" (largest peak)
@theapexsurvivor9538
7 күн бұрын
Yep, it's also what causes convergence, as certain local maxima are really massive in the phase space of selective pressure solutions, and thus regardless of how inefficient they might be, they continuously pull in more species. (Crabs aren't the ultimate body plan for most niches, but they're a Very attractive one due to how much their traits reinforce each other)
@Appletank8
Күн бұрын
my favorite fact is the laryngeal nerve needing to make a detour down to the heart before going to the neck. It'd be nice for the nerve to connect the right way from the start but there's no practical way to disconnect and reconnect elsewhere during embryo development. making it longer is way easier, which resulted in the poor giraffe not able to make proper sounds.
@moth.monster
10 күн бұрын
Another problem which is NP-hard is placing conveyor belts in Factorio. Someone made a modified SAT solver that just makes custom belt balancers for you.
@DackelDelay
10 күн бұрын
got a link by chance?👀
@adrianozambranamarchetti2187
10 күн бұрын
@@DackelDelayI concur
@user-nj1qc7uc9c
10 күн бұрын
link plz
@submachinegun5737
10 күн бұрын
Been playing factorio for a while now and I think I’ve mastered or at least understood most systems but compact belt balancers are just black magic to me, just grab a blueprint online and pray to the omnissiah it keeps working fine
@evanbarnes9984
10 күн бұрын
Dude I NEED that
@8bit_cat72
9 күн бұрын
During the video I considered this "what if you just checked every possible combination" but turns out that with a 10 by 10 board, if each combination takes one microsecond it'll take 40 quadrillion years to check them all.
@joshuascholar3220
10 күн бұрын
I get SO frustrated with other people's videos because they DON'T understand the problem they're looking at to the depth you do and they don't explain it. Thank you for making the first video I've seen in a long time that lacks the hand waving of incomprehension.
@mshonle
10 күн бұрын
The N always stands for Nondeterministic. The NP-hard problems in NP are those that can be *verified* in polynomial time. It’s an open problem (with a million dollar prize!) to prove or disprove if all the problems verifiable in polynomial time can be decided in polynomial time. - So, polynomials are still very much involved! (Note: the qualifier of “NP-hard in NP” in necessary, because there are undecidable problems that are NP-hard: the Halting problem is famously undecidable, but it’s trivially easy to reduce any NP problem to the halting problem: simply prepend a string representing a Turing machine that solves that NP problem. Likewise, if the N actually stood for “non” then it would include the halting problem as well.)
@ancom161-m3b
9 күн бұрын
while that's *true* (and I would assume alphaphoenix knows it is), I read that "Not Polynomial" more as a simplification for the viewers that might be less involved in computer science; as all simplifications do, it leaves out some detail, but since we're not here to solve a millenium problem, we might as well treat NP problems as not solvable in polynomial time
@jacksonmagas9698
9 күн бұрын
Its easier to just say NP complete, and only say NP hard if you actually mean to include EXP and beyond.
@manuelpena3988
10 күн бұрын
I once heard a very clever computer scientist say: We programmers do no choose what we work on because it is easy. We choose it because we thought it would be easy!
@jonasmaier6631
10 күн бұрын
24:10 to be completely precise, it is not known if NP-complete problems require non-polynomial time to solve (but it is widely believed to require exponential time and all current SAT solvers are running in exponential time (with some heuristics to hopefully be fast in easy cases)). Just one of those open problems in computer science.
@columbus8myhw
9 күн бұрын
Arguably it's _the_ open problem in computer science. It's the most famous one: P=NP.
@Frank01985
6 күн бұрын
In addition, although the entire class of SAT problems is NP-complete, that does not mean any one instance of a SAT problem can not be solved in polynomial time. In fact, it's quite easy to come up with subsets of SAT problems that can be solved in polynomial time (e.g. those that can be separated into smaller, fixed-size SAT problems because variables do not overlap). So it is very well possible that the problem of finding the previous state in game of life, expressed as a SAT problem, could be solved in polynomial time, even if it was proven that the entire class of SAT problems could not be solved in polynomial time.
@jonasmaier6631
6 күн бұрын
@@Frank01985 reversing game of life is NP-hard. You can do Turing machines in game of life, hence you can also do boolean circuits in game of life, and if you try to reverse those you're essentially solving SAT.
@Frank01985
6 күн бұрын
@@jonasmaier6631 That makes sense when considering reversing more than one step. I wonder if this still holds for reversing just one step into one feasible solution (instead of enumerating all solutions). A boolean circuit will need more steps to compute a more complex circuit. I could see it being the case that reversing one step can be done in polynomial time, but considering the combinatorial explosion of all possibilities that need to be searched for multiple reverse steps, that that is not feasible in polynomial time.
@MooImABunny
10 күн бұрын
I really love how Gerrymandering is relatively much more computationally easier than reversing GoL states. Like, oh, making this cool pattern pop out? insanely hard, computationally intensive. Abusing loopholes in a democratic system leading to political corruption? yeah dude, it's a walk in the park
@user-nj1qc7uc9c
10 күн бұрын
the reason it is easier is because we are just looking for a "good" solution; we are okay with reaching false summits with our gradient ascent algorithm with reversing GOL, we are specifically looking for a *perfect* solution so yeah, as it turns out, election rigging is computationally easy! :D
@NgenDoesGaming
9 күн бұрын
Relevant XKCD: 1425
@Dong_Harvey
6 күн бұрын
Get rid of the "representative" part, nobody can represent a group
@SkoddieAltair
9 күн бұрын
I’m a software engineer, and I used to work with data that required n-dimensional arrays. At first I was really confused trying to imagine a hypercube of cubes in my brain. As you’ve noted, it’s extremely difficult. One day I was staring across my office at my file cabinet, and I realized that when dealing with arrays using grids & cubes are just an abstraction. There’s no reason to conceptualize arrays in dimensions, it’s much easier to imagine them as containers. Like squares -> grid -> cube -> drawer -> cabinet -> storage room -> building -> etc. It’s not a complex shift in metaphor, but for me it made the notion of distance between cells much easier to understand. I use the same logic when thinking about configuration space. Containers of containers of containers of containers. It’s surprisingly effective!
@pykapuka
4 күн бұрын
Thanks Brian, I love this video so much! I didnt know something like Z3 existed. This is like telling me "Did you know: if you wiggle your arms like that, you can fly?"
@digantamukhopadhyaydex
10 күн бұрын
also afaik z3 doesn't have any progress bar, did u find that at all anxiety inducing? like if you had stopped the solve 1.9wk after start, maybe you would have missed a solution that you could have found with just one more day of solving
@AlphaPhoenixChannel
10 күн бұрын
I don't even remember what its solving right now, but there's been one going for like the past month that I haven't wanted to shut down. it's got to be close... right??
@ignaloidas
10 күн бұрын
It's the nature of the fact that the solving involves random guessing - you can't know how close to a solution are you. Some pure SAT solvers like Kissat can give you numbers on how many variables they have left, which essentially shows you the search space that is still left, but that still isn't that useful, because often that remaining search space could take until the heat death of the universe to complete.
@ivanovtv9817
10 күн бұрын
99% of z3 users terminate the program right before they find a solution
@Momi_V
9 күн бұрын
@@ivanovtv9817 *right before being a relative term in relation to the end of time itself
@Joonazan
9 күн бұрын
It has been shown that restarting after some (steadily increasing) time is optimal for certain SAT-solving algorithms. Probably Z3 already does this, though.
@Kargoneth
10 күн бұрын
It's like trying to reverse a hash.
@jimburton5592
9 күн бұрын
What season did Barry Allen finally defeat the Reverse Hash?
@dcnick3
9 күн бұрын
Reversing a (cryptographically strong) hash is kinda even worse, because there's no metric of how close you are, the only real algorithm is an exhaustive search of the inputs
@deltamico
6 күн бұрын
I searched if simple hashes are threatened by quantum computing and apparently not as much as assymetric keys
@jimburton5592
6 күн бұрын
@@deltamico I like adding color codes for an added layer of security. My favorite is hash browns
@spicybaguette7706
5 күн бұрын
Imagine using a game-of-life simulation as a hash function. It would perform terribly, but it would be super cool XD
@harold2718
10 күн бұрын
Have you looked at zero-suppressed decision diagrams also, they "break down" (by running out of memory) more often than SAT solvers but when they work they enable you to ask questions about the entire space of solutions (instead of just getting one of them, as SAT would, making you generate them one-by-one with extra constraints). Such as you can ask how many solutions there are, or even a list of pairs of how many solutions there are for each number of "live" cells, or find the solutions with the most or least life cells.
@Mikee512
9 күн бұрын
A ZDD is an efficient* way to encode solutions to a boolean function, but you still need to calculate the solutions, which I think is a significant portion of the difficulty here. *ZDDs are efficient in that they encode the solutions in the smallest possible datastructure which, because boolean logic, also turns out to be maximally efficient to search/query (assuming you can figure out how to write an efficient algorithm to query it for what you want to know, which is part of what SAT helps with in the first place.) However, just because it's maximally efficient doesn't mean a complete solution set (or even a sufficiently-interesting subset of solutions) will fit within storage/RAM constraints, or be traversable in a reasonable amount of time. The solutions the SAT solver finds could be used to build up a ZDD, perhaps incrementally, for efficient searching later? There's a software package called CUDD that helps working with ZDDs. Anyway, it's interesting to think about how it might be useful in this context. A few caveats may limit its usefulness: * Because building a ZDD presupposes having solutions to encode into it, if finding the raw solutions is the primary difficulty, then ZDD's usefulness may be limited * And while a ZDD is a highly efficient datastructure, whether you can express the precise query you want to ask in a form that runs efficiently, depends on whether you can reuse existing efficient queries or figure out how to craft your own, which can be non-trivial.
@harold2718
8 күн бұрын
@@Mikee512 You wouldn't create the ZDD by finding all the solutions and then converting them to a ZDD though (you could, but it's not efficient, as you identified), you'd build it by melding together ZDDs representing individual constraints
@Arkios64
5 күн бұрын
I'm incredibly chuffed at the recent trend of not deciding that "this video idea takes way too long to arrive at the final stage to be worth a video" and instead adapting it to "this incredibly simple looking thing took me incredible effort, let me explain to you the surprising reasons why". A lot of my favourite channels have been putting out partial successes or outright failures and creating absolutely wonderful pieces of content.
@carnac333
10 күн бұрын
Awesome video and explanation!! This reminds me of my research area of inverse problems, where one aims to reconstruct the object of interest from indirect measurements. As an example, in Computed Tomography (CT), we reconstruct the image of the imaged target from x-rays projected through the target. The information of the inner structures is encoded into the measured x-rays, which have been attenuated proportionally to the attenuation different tissues (for example very high in bones and lower in soft tissues). Commonly, the inverse problem is formulated using a model for the x-ray attenuation, known as the forward model and the sough after image is obtained by iteratively minimising the difference between the measured data and the predicted data produced by the forward model applied to the estimated image. Often, however, the problems are ill-posed, meaning that the solution might be non-unique, have many local maximum/minima, or noise can have a detrimental effect on the solution. In these cases we often employ regularisation, which imposes assumptions on the solution (such as smoothing) and makes the problem less ill-posed and more feasible to solve. Although this problem is completely different to ones I'm accustomed to, there are many parallels. The forward model is the algorithm that runs the game of life, the indirect measurements (measured x-rays in CT) are the starting point, the final sough after image (CT image) is the final image you are after for and problems with optimisation (local minima/maximima) are common. Very cool to video!
@Schlimbinger
10 күн бұрын
This reminds me of something. A while ago a buddy and me made something similar using langtons ant. We used multiple ants at different starting positions to “encrypt” a message. The world the ants reside in basically was a 2d-grid representation of the input message bytes. They then would do their thing for many iterations. Just a fun project, nothing serious. But it was nice to see your message emerge from “random” noise :D Never thought about how one could crack it but it would not surprise me if it’s relatively easy lol
@MrAppleGuySnake
8 күн бұрын
That's amazing, how did you implement it?
@Axolotine
9 күн бұрын
Heartbreaking: someone has solved your non trivial problem but used completely different terminology you were unaware of meaning that if you just knew what you didn't know you didn't know you would have saved yourself endless headache
@AlphaPhoenixChannel
9 күн бұрын
Care to enlighten?
@Axolotine
8 күн бұрын
@@AlphaPhoenixChannel I mean to say, I didn't know about SAT solvers and it could have saved me a lot of time lol
@OrangeC7
10 күн бұрын
Oh yeah! My favorite Blokus tile is the pentomino that's, like, a 2x2 square with another square attached to it. I don't really think it's the *coolest* one but, it's pretty unique all things considered so it ends up being my favorite
@AlphaPhoenixChannel
10 күн бұрын
i always thought that was one kind of a weird lump shape - granted when you can use it perfectly to flatten a rough wall, its extremely satisfying
@fuuryuuSKK
10 күн бұрын
so the P-pentomino. Also, the "r" mentioned earlier in the video is actually more commonly called the F-pentomino
@typicwhisper6569
10 күн бұрын
@fuuryuuSKK It's almost always referred to as an R-pentomino in the context of Conway's Game of life, as Conway had his own names for the pentominos.
@GDTerietto
10 күн бұрын
i gotta go with the C-pentomino
@fuuryuuSKK
9 күн бұрын
@@GDTerietto Pretty sure that one's commonly called the U?
@ohadcohen9813
10 күн бұрын
5 minutes into the video and I was screaming at the screen USE SAT SOLVERS! Glad you went there eventually, and I hope you had a wonderful eureaka moment :)
@jacksonmagas9698
9 күн бұрын
I saw the thumbnail, thought about it for about a minute, and then said "this is just SAT isn't it" Boolean variables (cells) with constraints, and you want to see if there is a satisfying assignment to those variables.
@top1cpvper
10 күн бұрын
Putting Alice and Bob outside of a cryptography problem should be considered a war crime
@AlphaPhoenixChannel
9 күн бұрын
😁
@dwightk.schrute8696
7 күн бұрын
You sound like Mallory!
@evannibbe9375
6 күн бұрын
Using exile as punishment is now a crime under international law (similar to stripping Alice and Bob of their citizenship to Cryptography land).
@Dong_Harvey
6 күн бұрын
They know what they did. Or maybe did not.
@InvaderMik
9 күн бұрын
Well, power to you! Discovering that your question is equivalent to SAT was already further than I would have gotten. When someone asks me “can you go backwards in the algorithm”, my usual answer is “no” without even thinking about it.
@NorthOfEarth
9 күн бұрын
At 10:00 I noticed something interesting. Traversing diagonally across a face always flips the same two pixels. Look a the front face. The top two pixels change along each diagonal, but the bottom one is never affected. Along the top face, diagonals flip the left and bottom pixels, but never the right one. Similarly, traversing the 3D diagonal flips all 3 pixels. A 4D diagonal four flip 4 pixels, etc. This means a path length of sqrt(n) would always flip n pixels, making plotting a path much easier to calculate. You could imagine a large image with huge chunks of pixels being the wrong color. Instead of navigating through configuration space in cardinal directions only, you could take a shortcut by pre-calculating and caching the diagonal that corresponds to flipping that entire chunk. Maybe divide the whole pixel array into smaller square chunks for faster processing, etc, etc.
@steubens7
10 күн бұрын
did you hear about Golly during this investigation? it runs finite automata extremely quickly because of a method called hashlife. it memoizes computed blocks to advance larger and larger patterns more quickly than evaluating the rules. you can use it to look backwards by looking forwards, unless there's an *incredibly* improbable situation that can never happen under a certain sized starting condition, it will find it
@SimonClarkstone
9 күн бұрын
I was wondering if you could do something like Hashlife too. It would start with all the ways to reverse a 2*2 configuration to get some 4*4 configurations, then try following back only the parts in the end image and matching the overlaps together to build up the ways to run the needed 4*4 configurations backwards 2 steps to get 8*8 configurations, then match up the edges of those (by the recursive hash) etc. I expect the hash tables would soon get impractically huge though.
@Avidiax
3 күн бұрын
For much of the video, I was wondering why there would not be a way to precompute all (k+1)*(k+1) automata as a way to stitch together a k*k solution. If k^2^2 ends up being too large for memory, then a variation of rainbow tables could be used, albeit with the problem that many states evolve to "everything dead", and for large k there are many states that are translations of each other that should ideally be coalesced.
@momom6197
Күн бұрын
It would indeed help a lot for reversing large configurations when you have some canonical preceding configuration (e.g. there are a lot of gliders in the figure and you make their ancestor another glider), but it wouldn't help with the hard part of the problem which is finding some ancestor in the first place.
@heh2393
10 күн бұрын
27:48 in practice we encode such "sum" constraints for SAT solving in a different way that's much more succint; see Tseitin's encoding
@AlphaPhoenixChannel
10 күн бұрын
Oooooh
@AlphaPhoenixChannel
10 күн бұрын
I tried to find something like this and didn’t know what to google! Thanks
@tonydai782
7 күн бұрын
26:06 Hexagons *are* the Bestagons after all.
@bennettpalmer1741
10 күн бұрын
It's funny, because my first instinct when I saw this was "Oh, this is basically minesweeper, that's an NP complete problem we are pretty good at solving, you should just convert it to that to solve it" and after messing around with configuration space for a bit, making me worried I was doing it wrong, you eventually decided "this is basically the SAT problem, I'll just convert it to that to solve it". I basically had the solution right off the bat, but we picked different NP-complete problems to use. I wonder if one is better/more efficient?
@BetaDude40
8 күн бұрын
That's the thing about NP-Completeness, they're all basically the same problem just phrased a little differently. If you could solve one in polynomial time, you could apply the same algorithms to all of the problems in NP-Complete.
@jokebird6479
2 күн бұрын
This has given me a really good understanding of configuration space and p vs. np problems. I’ve always wondered about p vs. np problems but I could never find an explanation I found intuitive. Also, I can’t imagine just how useful configuration space will be to me, being able to think and compute higher dimensions! Thank you for this video, it’s awesome!
@Krunked
10 күн бұрын
that is extremely abstract. but i love it. tickles my brain. i dont get this sorta thing at my work (site reliability engineer), but this reminds me of cool science classes i loved in higher ed. i love these vids thank you for making them :)
@andytroo
10 күн бұрын
the game of life is turing complete - assuming you have enough grid space ... does that mean solving this is a limited space halting problem? also, solution to sat: "I can't get no satisfaction 'cause I try and i try and i try" - Description of brute force SAT solving strategies, [Jagger, Richards, et al.; published in "Out of Our Hands, 1965, available online]
@AlphaPhoenixChannel
10 күн бұрын
What a great application of lyrics 😂
@typeswitch
10 күн бұрын
> the game of life is Turing complete This only matters if you're running the game of life forwards for an indefinite number of steps (& an unbounded grid space). Trying to reverse a finite game of life configuration by a single step is in NP, so it can be solved using a SAT solver, as practically demonstrated in this video.
@jeffreyblack666
9 күн бұрын
This is going backwards, not forwards. Comparing it to the halting problem, this is more like looking at the "end state" of the halting problem, in this case a program which never halts, and asking what input gets there.
@gamekiller0123
9 күн бұрын
It's not the halting problem. It's related to the existence of one-way functions, but the "reverse game of life" problem might be easy even if one way functions exist. The reason is that reductions rely on encoding Turing machines into the game of life, but you can reverse into states that aren't encoded Turing machines, which then won't give you the inverse of the one-way function.
@bretonkyle
9 күн бұрын
You know you've watched too much This Old Tony when the music at 7:09 reminds you of TIG welding and drilling holes
@acf2802
9 күн бұрын
I bet reddit still thinks it can't be done after watching this video.
@guy9360
9 күн бұрын
"He didn't ACTUALLY do it, he simply ..."
@JTCF
7 күн бұрын
33:33 "Eden found" did the computer just die and ascend to heaven?..
@arc8dia
8 күн бұрын
Maybe this is why entropy and causality go in one direction, and we call it time.
@SamChaneyProductions
5 күн бұрын
You make some of the best content on the platform. Incredibly informative without being dry
@I.____.....__...__
10 күн бұрын
3:47 As Brian found out, that's a specious question. The fact that the GoL has stable loops in the finite-state-machine, means that there's no deterministic way to find a unique pattern that would result in anything in particular. For example, the standard solid 2×2 block configuration could arise as the next step from a very large number of permutations of states from even just the surround few cells, or… another 2×2 block. … 33:12 👍 This video is speeding into NP-completeness territory. … 23:30 👍 34:19 Yeah, that makes sense, because the target pattern will be made from a LARGER pattern, which itself will be made from a larger pattern, and so on. You might get lucky and have a target pattern (or intermediate pattern) that can be made with gliders and spinners and such which can reduce the size of then parent pattern, but most patterns will usually be made from physically-larger non-repetetive patterns.
@duncanbyrne1134
8 күн бұрын
To me this sounds like a perfect inverse problem. Pretty much how do we go from a current state and work our way backwards to find the initial state, given that the initial state has pretty much infinite possibilities and there are infinite solutions. Inverse problems are pretty heavily studied at least in geophysics and hence there are some solid algorithms for them. That might be another approach to solve this problem which could make it much faster.
@Wackylemon64
10 күн бұрын
I love your explanations and visualizations! Your passion is clear! I've been trying to improve my intuition of latent/configuration spaces, and explanations like this are always welcome!
@lukatambourgi9372
3 күн бұрын
4:00 its impossible to compute THE previous state. Easy example: an empty board. Was the previous state an empty board too? 1 cell? 2 cells aligned but spaced by 2 empty ones? Or the space between was 3? 4? 99999? Graams number? Tree(3)?????? We cant know
@talis1063
10 күн бұрын
Just did a university homework on local search yesterday. The algorithm that selects the best next step based on a heuristic from a neighborhood of nodes is called the hill climbing algorithm. Even if finding the optimal solution is NP-complete, finding a solution might not be with a metaheuristic algorithm like hill climbing with random restarts. But of course there is no guarantee that a solution is found in a reasonable time, especially if the solution space is very sparse (which seems to be the case here). Not trying to say that anything is wrong in the video, just find it cool that this video popped in my feed with perfect timing and wanted to share.
@Sidewinder0010
7 күн бұрын
13:00 thank you so much! I have watched countless videos of people explaining higher dimensional spaces over the years and this finally clicked for me!
@AlmightyJu2
9 күн бұрын
As always this is such a good balance between complex, simplified but not too much that all the nuance of how it's complex is lost. Can't wait for the follow up!
@JochemKuijpers
10 күн бұрын
The main lesson from this video seems to be that you should use the right tool for the job 😄 SAT problems are "too discrete" for a gradient descent algorithm. Arbitrary changes don't result in predictable increases in the result space as there's no real continuous output of a SAT-solver that can tell you how close you are to a solution. The number of requirements met is not a useful metric here, a single requirement may prevent you from solving a problem even if you hit all other requirements. So any notion of 'derivative' or 'gradient' doesn't really make sense for these types of problems. A couple times you referred to the configuration space as 'continuous', but it really isn't continuous at all. Even in the city example you're dealing with discrete cells and boolean assignments. The parameters you used to divide the city may have been continuous but the output is discrete, which should've been the first hint that gradient descent may not have been the best tool for the job. The parameter space also excluded many valid solutions, such as a checkerboard pattern, that would've evenly divided the city. Unless you're certain that your simplifications in parameter space don't exclude the valid solution you're looking for, that's almost always a bad idea. (though, I understand that was a simplified example to make a point 🙂).
@MrTomyCJ
9 күн бұрын
I really wanted to see someone try a neural network approach to this. I feel like "deep intuition" may help traverse the messy configuration space.
@cannot-handle-handles
8 күн бұрын
True, it's not continuous, but it is at least Lipschitz. The checkerboard pattern isn't simply connected, however. Among the simply connected solutions, I would have liked to see those containing either 1 or 3 city quadrants.
@andersama2215
2 күн бұрын
When you opened with this video and started to explain the project, my initial thought was, oh this is like backtracking algorithms to solve sudoku, and then immediately was reminded of SAT solvers like Z3.
@jeffpkamp
10 күн бұрын
Videos like this can destroy somebody's entire year! I'm glad you were able to set the project down every now and then.
@dracuul78
9 күн бұрын
This is a captivating topic and an amazing presentation, thanks for putting in so much effort!
@yodxxx1
9 күн бұрын
Thanks dude, you are helping me a lot with this video, thanks to you i now have found a few new paths to solve a logic problem i had for some years now
@simpli_A
8 күн бұрын
The SATisfiable section reminded me of one of my favorite board games. Its called décorum. Essentially, its a party game where everyone is roommates. They each have specific needs for them to be happy, and so you take turns changing the furniture to make you happy, all while simultaneously making everyone else happy. Here’s the problem, . Every move you make, your roommates can only say if they like it or hate it. No reason why. Id highly suggest giving it a try if you have any friends
@BoogsMcNoogs
10 күн бұрын
I have no memory how I stumbled on your channel but I am very, very glad I did. Keep these coming, they make my brain satisfied.
@MartianGopnik
10 күн бұрын
3:47 to 4:00 reminds me of a banner I've seen recently, which reads: "We do this not because it is easy, but because we thought it would be easy". Lol
@fakesilver746
9 күн бұрын
this was so cool! I took a course in uni that included sat solvers and i always thought they were really cool but this is the first time I see someone using one in the wild. I didn't really understand how you encoded the pixels into numbers, with rules and everything, but i really liked the video! subscribed :)
@OvrcstYT
9 күн бұрын
Holy moley, this video was fascinating. Can't wait for the second part!
@johnreiland9180
10 күн бұрын
Around the 7:30 mark, when you are explaining Configuration Space, the music is quite loud, to the degree that I think it becomes an obstacle to cognition. Love your videos, not hating on you or them, just wanted to mention this small spot that I think can be improved.
@y00t00b3r
10 күн бұрын
grr, hate that
@StuartWoodwardJP
7 күн бұрын
Yep. music behind an explanation is really distracting. I didn’t enjoy that segment.
@zncon
9 күн бұрын
It took a while of watching for this to dawn on me, but the game of life is essentially a one-way hashing function. For the sake of all the worlds digital security I'm glad you didn't manage to conjure up a universal solution.
@acters124
10 күн бұрын
This is the best video on machine learning and how the LLMs work! AMAZING!
@DStageGarage
5 күн бұрын
About 10 years back me and my friend installed a light system in a building I worked that used each window as one pixel (16x6 windows on a corner of the building). We've actually made this for the first time in 2007 on a dormitory back in the university times but I digress. The later system, that run for a few years, allowed not only predefined animations but also plugins - small programs running the display for determined time like 20s or so. We even had a competition where people send their plugins and some where really good in visual terms. I contributed a few of my own and one of these was a game of life ;-) I think there was also one send by someone with some different colour scheme etc.
@MouseQueen7220
10 күн бұрын
This reminds me of trying to get a file from its hash.
@AlphaPhoenixChannel
10 күн бұрын
You wouldn’t believe how hard I got downvoted for saying that SHA isn’t reversible but people are trying after someone on Reddit told me GoL wasn’t reversible
@hammerth1421
10 күн бұрын
@@AlphaPhoenixChannel SHA is reversible - by brute force _lovingly slaps GPU compute server_ That's why you salt your strings. You can reasonably brute force one rainbow table, but you can't brute force all of them.
@foobar4938
10 күн бұрын
@@hammerth1421 Its not reversible. At best you can take a pick of any of the infinite amount of inputs that could have produced that SHA. Unless the input length is limited, but even then once you reach about half of the length of your hash output, you're very likely to hit a collision.
@ShankarSivarajan
10 күн бұрын
@@AlphaPhoenixChannel I expect your problem is that you use "reversible" like a _physicist,_ and math people hate that.
@scaredyfish
8 күн бұрын
When I think about this problem, I immediately go to things like Minesweeper, and Sudoku, where from your initial constraint/starting information, you gradually reveal new info based on what has already been revealed. I guess this is exactly what the SAT solver is doing, but to me this is a more intuitive way to think about it.
@xlerb2286
8 күн бұрын
Z3 sounds like a modern version of the genetic algorithm concept we covered in AI back when I took the course ~30 years ago. GA's were mighty slick. You needed to express the problem as a topography and then provide a function that given a point on the topography would indicate how good a fit it was to the desired solution. The GA did the work of traversing the topography and avoiding foothills. Mainly it started with a set of random guesses and then did a combination of "walking uphill" and creating new guesses by combining a couple of the more promising existing guesses (thus the "genetic" part of the name) to create new guesses that may be even more promising. It was at the time one of the best and most flexible ways to solve the foothill problem
@michaeltraynor5893
7 күн бұрын
My first software job was at the company that convinced Microsoft to open-source Z3 :) we used it to find bugs in aerospace designs
@asdfasdf-dd9lk
10 күн бұрын
I for one would absolutely love more on SAT solvers ! super interesting topic
@AlphaPhoenixChannel
10 күн бұрын
Check out the linked talk
@justindie7543
10 күн бұрын
Gotta love redditors. Never ask reddit for advice with anything if you want to be optimistic about it in any way.
@andreyzyablikov9891
9 күн бұрын
Спасибо за это увлекательное путешествие в мир NP-задач, теперь я стал понимать, в чём проблема NP. И ваше стремление найти решение в этой "тёмной комнате", где даже не известно, есть ли в ней "кошка", меня восхищает! Удачи и сил продолжать подобные поиски и спасибо за видео!
@Trainwreck1123
10 күн бұрын
I love your videos! Your channel is near the top of my list for new videos I get excited about :)
@cblair1353
9 күн бұрын
Wolfram has some great stuff along this same topic and dealing with computational complexity.
@amdphreak
Күн бұрын
Because something noisy devolves into something periodic and self-sustaining, it cannot be "undone" using an algorithm. It is similar to square-rooting a number: there are two possible answers to that one, but for this one, there could be an indefinite number of solutions.
@Susul-lj2wm
10 күн бұрын
fascinating video, very excited for the sequel!
@typeswitch
10 күн бұрын
Oh when I started the video I thought "I hope he's using a SAT solver" and I wasn't disappointed hehe :-) 24:35 NP-hard doesn't mean "not polynomial time" and NP-complete doesn't mean "it can be solved in exponential time". I know this isn't a CS channel but I wish you were a little more precise at explaining these concepts the first time for people who might not already be familiar with them. The visualisation of (CDCL) SAT solvers as crossing out whole swathes of solution space where only suboptimal solutions exist, is really good! Thanks for this insight.
@AlphaPhoenixChannel
10 күн бұрын
I know those aren't the rigorous definitions, but they are true statements. I went back and forth a LOT about that segment trying to say what needed to be said relevant to this video (and not too much), but not be incorrect. Edit: The verbiage I used to describe NP complete in the video was “at worst exponential time”, which is a very precise way to phrase it. Claiming that NP is “not polynomial time” in the graphic and saying “no known algorithm to solve in polynomial time” is also I think a very precise way to phrase it. The graphic annotation is practical and the part I said out loud was exact
@typeswitch
10 күн бұрын
@@AlphaPhoenixChannel Well, they're not entirely true, no. NP-hard doesn't imply "not polynomial time", it only implies "we don't know a polynomial time algorithm to solve this (and probably never will)". NP-complete does imply "can be solved in exponential time" but so does NP. So does P. etc. It just doesn't feel like a good explanation for why SAT in particular can be used to solve this problem. I think a better explanation would talk about how NP problems have easy to verify solutions, and how this problem has easy to verify solutions (just run the solution forward one step & check that it matches the desired output), and then link that to a brief discussion of NP-complete & SAT solvers (which you kinda already have in the video).
@ruroruro
10 күн бұрын
@@typeswitchmeh, I think that for all intents and purposes NP-hard does kind of imply "not polynomial time". Sure, it doesn't technically imply "we can prove that it's not polynomial time", but "there is no polynomial time algorithm" and "there is no known polynomial time algorithm and it's almost certain that there never will be" are basically equivalent in colloquial use (and I'd argue they are definitely equivalent in the Bayesian sense).
@theqwert3305
10 күн бұрын
I saw a *really* cool video recently that rephrased NP vs P as "Can you reverse every polynomial algorithm in polynomial time" The moment I saw the title I went "of course running it backwards is hard, it's NP!"
@AlphaPhoenixChannel
10 күн бұрын
@@typeswitch The verbiage I used to describe NP complete in the video was “at worst exponential time”, which is a very precise way to phrase it. Claiming that NP is “not polynomial time” in the graphic and saying “no known algorithm to solve in polynomial time” is also I think a very precise way to phrase it. The graphic annotation is practical and the part I said out loud was precise
@benjaminguo7559
9 күн бұрын
Both this video and Veritasium's video on QR codes involved some multidimensional hyperspace. Kinda cool coincidence that these two videos were released on the same day.
@Jellylamps
9 күн бұрын
I JUST had SAT solvers recommended to me recently concerning finding valid number arrangements on the stickers of a 4x4 rubiks cube such that every face and every ring follows sudoku rules from 1-16 instead of 1-9
@La4geas
9 күн бұрын
3:55 It shouldn't be easy, especially when you consider patterns that disappear into nothingness, meaning an infinite amount of patterns can lead to the exact same result.
@Bibibosh
10 күн бұрын
I got so good at this game. I created a "dna" configuration that was far smaller than after it finished evolving. 55milions tics/frames later, it created a calculator that can add and subtract and has user input
@GameJam230
9 күн бұрын
An interesting idea about the difficulty in determining patterns that lead to other patterns in the game of life I had is that it can sort of be thought of a higher dimensional correlation to the problem of finding the smallest convex polygon that contains every point in a collection of points on a grid. This is a rather slow process to do by just looking at all the points individually and comparing their coordinates, but for a human who can see all the points plotted with pins on a cork board at once, it’s extremely trivial to just grab an elastic band and place it around all the points so that it snaps to the shape of only the outermost points, solving the problem. The game of life is sort of a 3D extension of that, where two of the dimensions correlation to the XY plane for any given state, and the third dimension is for layering consecutive states on top of each other. For a computer to find a valid state from a previous point in time, it needs to painstakingly simulate the entire state, and if even a single point is off, it’s wrong. But, a 4D observer could probably see the entire system of points across all those dimensions at once, and could wrap a metaphorical 3D rubber band around the whole collection of states at once (a balloon I guess? It doesn’t matter, there’s no rubber band here, that’s an entirely different problem than the game of life lol). They could see and have an intuition about the lower dimensional world that our brains and computers cannot even comprehend. Do 4D beings have higher dimensional problems they can’t yet solve? Perhaps multiple timelines create the possibility that more than one starting state can lead to the same ending state, and so 4D encryption would require not just finding a VALID starting state, but a specific one? Maybe a 5D being would have a special intuition for doing that which we do not? It’s a neat thought for sure.
@poorgrammar3136
9 күн бұрын
Such an interesting problem I almost wanted to not click on the video and just do this myself
@josephgoldsborough9138
7 күн бұрын
bro's tryna navigate an infinite sea of infinite outcomes in a somewhat efficient manner and i respect that
@stanleydodds9
10 күн бұрын
Nobody knows that NP complete problems cannot be solved in polynomial time. It is generally considered unlikely that they could be, but we do not know any reason that NP complete problems cannot be solved in polynomial time; that is, NP may be no larger than P, which of course would make it equal to P (trivially all P problems are also non-deterministic P). All that "NP complete" or "NP hard" means is that it is a problem that can be solved non-deterministically in polynomial time (that is, it is in NP), and also it is maximally hard. A maximally hard NP problem is one where a solution to this problem can be reduced to a solution to any NP problem (with at most polynomial slow-down). The typical example of such a problem is, of course, SAT. It's no coincidence that we use SAT solvers to solve all NP problems - SAT being NP hard exactly means that a SAT solver can solve all NP problems without significant slow-down. We also know many other NP complete problems, i.e. many problems that can be reduced to all NP problems, including each other. It's just that SAT is quite probably the "simpl. Secondly (but similarly), EXP (algorithms that run in exponential time) is weakly larger than NP, and it is suspected to be strictly larger than NP. Or put another way, NP is closely related to polynomial time (it's about a more general idea of polynomial time than P); it is not really about exponential time per se, although it is trivial that NP problems can be solved in exponential time by the naive brute force algorithm of checking all possible solutions. But note that also P problems, or indeed any easy problems, can be solved in exponential time. It's trivial in the same way that solving NP problems in exponential time is trivial. That doesn't necessarily mean exponential time is the fastest we can do for NP problems, and it doesn't mean that all exponential time problems can be verified / solved non-deterministically in polynomial time (they probably can't all be).
@MikkoRantalainen
6 күн бұрын
I see reversing of Conway's Game of Life similar to reversing cryptographic hash such as MD5 and SHA-1. I would try similar methods that were used to crack MD5 and SHA-1. And note that we haven't yet solved even MD5 to have a working pre-image attack so that's a really hard problem. Of course, Conway's Game of Life has way less complexity for output bits than MD5 or SHA-1, so it might be possible to find a working pre-image attack for Conway's Game of Life, at least for small pictures. Since each pixel can be only white or black, the Conway's Game of Life is basically a hash algorithm that outputs enough bits to output the target image and you have to guess a suitable pre-image.
@DavidPHH
10 күн бұрын
I love this channel. Thank you for the effort you put into these videos
@timonix2
9 күн бұрын
We use SAT solvers for testing code. It allows you to make broad statements like, this code will never deadlock and it goes... Naah, it totally can, check this out; and it shows you how your code can deadlock. And a whole bunch of other things. Super powerful
@nicodeklerk1617
10 күн бұрын
This was a gooood watch thanks!
@ryangeorge346
2 күн бұрын
Something i think would be cooler is something that finds rules you can turn on or off to go from one on pixel to any given configuration in a certain number of steps
@theopoldthegamer4284
2 күн бұрын
The editing on this video is incredible
@sirmyself
4 күн бұрын
33:46 It's really reminiscent of how chess engines work. Most of them go to a certain depth of possible chess positions from the current one. Then they evaluate each positions, of each possible paths and outputs the next position with the path with the best overall evaluation.
@benjaminshropshire2900
9 күн бұрын
I'd be tempted to starts with a modest collection of random inputs, likely with random but uniform live/dead ratios, hill climb from each of them and use the per-cell statistics from the collection of dead-ends to inform future guesses. *Is that a known/named strategy?* This would let you quickly identify portions of the space that are well constrained (e.g. all the dead-ends look the same there) and focus the places that seem to be more chaotic. It might be even better to use some autonomous classification to identify clusters of similar but not identical solutions that can be partitioned off and considered in isolation.
@Pepesmall
9 күн бұрын
That's the best physical design of a hypercube ive seen.
@ricardasist
10 күн бұрын
This is super cool, man you make some really next level content😊
@triplebog
2 күн бұрын
A couple thoughts though, one is that the problem that you encounter at the end "iterating through multiple possible solutions for ones that give us more valid states" sounds a lot like a stock-fish esque chess rating algorithm, where they have to walk through the number of possibilities for outcomes that look or are more optimal. Tile solver is interesting too, like you wrote in your pinned comment. Because at that point you would just be running the Sat solver on a smaller possibility space, but with having way more complex rules to figure out. There is probably a tradeoff there and an optimal balance of "larger ruleset vs larger grid". I mean, if you really think about it, you are already doing a 3x3 tile solves. Just that the edges overlap, and the 3x3 logic exists in the ruleset handed to the tiler. If you were to do larger sections, say 4x4 or 5x5, you'd essentially have to just hardcode all that data into the ruleset. Which probably would be fine and could be a slight optimization, but you'd probably want to write a program that automatically writes the code for the python program logic for you.
@MarkEichin
9 күн бұрын
Excellent example of the "reduced to previously-unsolved problem" CS trope...
@danser_theplayer01
9 күн бұрын
Ah, reminds me of how QR code redundancy works. They have like 9 control bits or something close to that, and they create config space "distance" for other bits of code and so just a handful of these control bits map each byte read from a qr code to a super mega hyper cube thing. And that lets them guess what the intended message was even if you spill ketchup onto the code.
@rieduciumaratonas
10 күн бұрын
I worked on a similar problem, difference being that my solution did not have to be exact, just similar. I used genetic programing, but didn't get anything. Maybe I will revisit it with new ideas.
@a_commenter
10 күн бұрын
it was so funny to see you mention z3 bc i was watching this video while waiting for my own z3 toy example to finish
@Jack-vq9we
9 күн бұрын
Oh dear, what is an eden space?!? that sounds mathematically and existentially terrifying.
@speedyJ0hnny
10 күн бұрын
This is awesome, I always love your vids! looking forward to part 2 :)
@jordillullchavarria4082
9 күн бұрын
Cool project! Love seeing how you're tackling this. Ever thought about training a neural network to guess the previous state of the game? Might help with the search, and could be a fun experiment to see how well it learns the game's logic. Just an idea! Keep up the awesome work.
@MichaelKire
5 күн бұрын
Right away I saw a similarity to trying to reverse engineer a hashing algorithm and thus making it a very hard problem.
Пікірлер: 814