Yes, but in this case the algorithm would need to figure out the constraints from preexisting examples and so would you not need to program complex constraints rules with probabilities by hand?
I read this months ago, and the impression I was left with is that this technique is simply a fancily-named variant of any normal tree-based search algorithm. You have constraints which can be represented on your search, and then you attempt to navigate the hyperspace finding a configuration which matches.
I really can't see how this isn't "wavefunction collapse" and is rather just, "search."
But I feel like I must be missing something. If this isn't right, can someone explain to me why it's not right?
As I commented on the other thread on this article going right now, this is better known as sampling from Markov random fields. There is a sizeable literature dating back to the 1960's under that name.
Somewhat off topic, but one of my absolute favorite YouTube videos is this https://youtu.be/p7bzE1E5PMY one by Udiprod that shows visualizations of wave function collapse, with bite sized, iterative explanation of all the concepts involved.
Very nice and clear write up. Looks like I know what I’m going to be programming today. I particularly liked your example of how to sample existing tiles to generate rules.
I’ve been wanting to work on a 2d game world generated off similar constraint algorithms. But also allow some tiles with high entropy states to be able to occasionally “flip” and propagate around, thus changing the world dynamically as you’re walking around.
And I shall name it Wave Function Collapse since it’s clearly not controversial.
Am I being a pedant if I think this algorithm has been misnamed for the purposes of PR? It just looks like constraint satisfaction. What's quantum about this? There's no constructive/destructive interference, which to my mind is the crucial distinction between quantum and classical systems.
It's simply named only for the analogy with the Copenhagen Interpretation -- everything is in a 'superposition' (all options possible) until a single 'observation' is made, which causes a reduction in the available possibilities, which propagates across the space/structure. That's as far as the analogy goes.
This sort of loose analogy is a perfectly reasonable way to name things IMHO.
I don't hear anyone complaining that bubble sort doesn't consider buoyancy and surface tension, or that the flood fill algorithm doesn't involve any actual fuid dynamics.
I have my own theory on why people like to complain about this particular analogy, but for the sake of not causing offence I will leave it there ;p
I think people are saying that the algorithm isn't cool enough for its name.
Bubbles aren't cool, so bubble sort must be rightly chided. /s
Quantum physics? Now that's cool, regardless of how much one knows about it.
I don't think the reason gets much deeper than that, barring any disagreements that it is just plain misleading.
I guess you could argue to some degree that a name should be usefully informative to an outsider or newbie. But that doesn't really apply to things that have already established their cool factor, like 'deep learning', 'crypto', 'agile', 'serverless', etc..
I would object to the name on the basis of it influencing a misleading association. A person's brain will jump from one idea to the next based on familiar recall, and when people can't 'jump' to the correct association because their brain is filled with bad ideas that have nothing to do with the topic, then we all suffer for having to defend against it.
I’m complaining about it because when I first heard about it, I tried to look up information to understand the algorithm and.. it turns out that “wavefunction collapse” is not useful, at all, as search terms or a starting point to learn anything about this algorithm. The name is completely useless to understanding it or finding out any more about it.
You could say the same about bubble sort or whatever, sure, and a case might have been made about the name when it was first introduced, but now they’re established names where “bubble sort” are good search terms that will help you find lots of information about the algorithm, but “Wavefunction collapse” isn’t a widely used algorithm and the name has a lot of existing publications that are not related (because they’re to do with actual quantum physics, not this algorithm). Even searching “wavefunctoin collapse algorithm”, when I last did it, only found quantum physics result (that seems to have changed though, as I just did a google search and the entire first page is about this algorithm, but I see most of the results are quite recent: within the last few months)
>> but I see most of the results are quite recent: within the last few months
I think you've answered your own question. I don't know how long this has been around and I'm not sure how long people have been calling it this. Regardless of any of that, it is now getting a name and recognition under that name. The world changes, and you're seeing a little of that here.
On a related note, I wrote some code to take a piece of music and output guitar TAB. I'd print a number on every string where it was playable, and this left me to manually search for optimal fingerings (some notes have 5 or 6 options). Wave Function Collapse is exactly the type of thing I had been trying to devise to reduce the TAB to something easy to play. You could even change the constraints for different picking styles.
The original WFC github project was posted in 2016, so it took approx. 2 years before it became searchable. It’s fine now, but it was incredibly frustrating for me when I tried to look into it around January or February of this year.
The WFC algorithm itself is very interesting to me and now that I can find more information and code, I’m eagerly planning to play with t myself in the coming weeks. :)
We need to lower the noise floor or raise our attenuation level to valuable ideas, but yes this is a valid point. On a larger scale with population levels rising and our rate of dicovery/creation happening at idk... really fast, it behooves us crate diggers of good ideas is to step up our game. My only helpful suggestion to aid in this is read The War of Art[1]
I understand what you're saying but I'd like to push back a little. The loose analogy of superposition applies to a very large number of algorithms just as much as it applies to this one. You could likewise apply it to sorting - a "Wave Function Collapsing Sort" considers all elements of a set to be in superposition, then gradually "collapses" each index to the element which matches. It does this iteratively until it either sorts incorrectly and must start over, or until it produces the correct sort.
In other words, this isn't actually a superposition. You could definitely say there's entropy involved, but really this is replacing the word "uncertainty" with "superposition." If you do that, an extraordinary number of algorithms suddenly fit the template of wave function collapse. Basically anything that has a probability distribution and iterative reduction, because that's what this is (and not a wave function).
I'd also say that flood fill actually looks like a flood filling a room if you see a 2-dimensional visual of it pathfinding around obstacles. Personally I don't really care about how algorithms are named, but I think flood fill is a bad example because it actually looks like a flood filling a room.
> I have my own theory on why people like to complain about this particular analogy, but for the sake of not causing offence I will leave it there ;p
Why even mention it then? "I'm thinking something that might be offensive so I won't say anything"; sort of undoes the whole not saying anything bit, doesn't it?
> In other words, this isn't actually a superposition.
Obviously. That was my point: it is but a simple analogy. There are no actual bubbles in bubble sort, either.
As for my theory -- I suspect that whenever quantum physics is mentioned, a certain brigade of users like to take the opportunity to look smart by showing off their (in this case largely irrelevant) knowledge of quantum physics. (While simultaneously showing how they fail to grasp the concept of simple analogies, and so actually appearing the opposite. But then I'm zero_iq, so what do I know...!)
> until a single 'observation' is made, which causes a reduction in the available possibilities, which propagates across the space/structure
wavefunction collapse is a singular event not an iterative process, results are not equiprobable, alternative probabilities become 0, there is no undo/traceback etc etc. the analogy doesnt make sense, it's just a fancy name
To my knowledge, this depends on the interpretation. Some interpretations consider wave function collapse an actual physical process, some don't, so I don't believe it is possible to make an absolute statement such as yours. There is still some debate about whether or not the process occurs over finite time (at least there was 2-3 years ago -- perhaps things have moved on since then and I haven't caught up. If there have been new developments along these lines, I'd be interested to see it).
Regardless, it can be computed as a process, and this is where I believe the analogy in question arises. Is a perfect analogy? Of course not -- no analogies are. Bubble sort has no bubbles and involves no liquids or gravity, or buoyancy, etc. etc. the analogy still works despite that IMO.
It is almost comical. But it seems to be working, since it got a lot of attention. I should call my latest paper about finding integer solutions to LP relaxations something with quantum.
I agree that the crucial property of quantum systems is interference, specifically "negative probabilities". Just having a dead/alive ambiguity does not make "wavefunction collapse" a reasonable name.
Not only that, but “wavefunction collapse” makes it sound a lot more complex and makes it more daunting to understand. A simple description of the simple tiled model algorithm in the article is basically “pick a candidate at random and prune remaining lists to remove now-invalid candidates” or something similar. Building the rules is simply “list all of the pairs in the example and store how frequently they occur. The frequency count prioritises more common pairs and pairs not encountered in the example can’t occur in the output”. No “quantum” or “wavefunction” or anything here. A list of candidate items isn’t a wavefunciton.
When I first saw this technique, I was interested in replicating it. So I started reading about wavefunction collapse on wikipedia. It had a bunch of complex quantum math and I gave up thiniking the technique was beyond me. But now I see it was also completely irrelevant. Thanks to the bad name, I gave up on it (until now, at least, when I see that its a lot simpler).
The name is not so bad as you two think. The act of measurement of a quantum state can be thought of as a filtering procedure after which a normalization operation is applied. This is the same protocol that occurs when conditioning on an observation in regular probability. If you take away normalization and stop propagating weights, that same operation corresponds to applied constraints or guards, which trigger backtracking operations, in logic programs for example.
This algorithm is actually an instance of constraint propagation: https://en.wikipedia.org/wiki/Local_consistency and constraint satisfaction algorithms generally, that find use in say, computing graph homomorphisms.
If it had been called something around constant propagation then I would have had a starting point to learn more when I last attempted to (January or February of this year). Luckily thanks to this article and other recent articles/github projects, it seems that it’s more searchable now than it was then.
Yes, it should really just be called "Random Field Collapse" or even just "Random Field Generation".
The simple case is a naive way to sample a Markov field in 2 dimensions, estimating transition probabilities from global overall adjacency frequencies.
"PDF collapse" is usually known as "random sampling".
Of course, random sampling can be quite non-trivial. The Lovasz local lemma comes to mind as something that's similar (but more general) to what the algorithm here achieves.
I certainly understand how people can get annoyed by this kind of marketing. Randomized algorithms have a long tradition, including randomized rounding of fractional relaxations which somebody alluded to, and nobody who worked on those felt the need to mislead with quantum allusions.
Take the Mersenne twister algorithm for instance. It is a non secure pseudo random number generator that is found everywhere even though there are alternatives that are better IMHO. I'm sure it's success comes from the fact that it is good enough and that it has a cool name.
I also think it is the rationale behind named vulnerabilities like heartbleed and spectre. Grabs attention.
Hah, I just wrote a similar question. It seems like it's simply an application of a search technique where the constraints are an NxN matrix.
It's a good trick, to be sure, but it doesn't seem "quantum". I suppose you could argue that there are often many valid solutions to the system, and you're just selecting a superposition.
I haven’t looked at the algorithm so I can’t comment on your specific question, but I just want to warn you, if the bastardization of wave/particle theory annoys you, you are in for a world of hurt over the next few decades.
I believe the notion of waves and their relationship to observations is the new “megameme” for western intellectualism. The progression as I see it:
Everything (including us) is a clock/machine
Everything (including us) is a computer/information processor
Everything (including us) is a wave/field
This metaphor will get dragged just as hard as the clock and information metaphors got dragged
For how simple WFC seems to be portrayed, the only reference I can find is for use in other code. Is there any simple, but still code, examples of this? Or is it always quite a bit of work to get going?
I wrote an post with a short and (hopefully) understandable implementation a while ago: https://terbium.io/2018/11/wave-function-collapse/. There's a Jupyter notebook you can download at the bottom of the page.
The algorithm for the first example reads just like an implementation of a SAT solver. Set a variable, propogate clauses, backtrack on conflict (learn new 'rule' from conflict).
Neat. I wrote an algorithm very much like this... I mean, sure, it's just a greedy search over a contraint-satisfaction problem... but I love the name and I'm gonna use it.
The algorithm is not related to quantum mechanics, although is is very cool. Technically, before "collapse" what is there is a probably distribution function, not a wavefunction.
https://inst.eecs.berkeley.edu/~cs188/fa18/assets/notes/n2.p...