4 ms·

Have you ever written a Sudoku solver. It works like that. You start with an array where every tile is possible in every location. Then you pick a random cell

Have you ever written a Sudoku solver. It works like that. You start with an array where every tile is possible in every location. Then you pick a random cell and assign a tile to it. That tile implies some choices are impossible, so you set those possibilities to false. That further implies some other possibilities are false and so on. You propogate that as far as it goes, and when you are done, pick another random cell and assign a random possible tile to it. Because you are propogating information as much as possible before making the next choice, the algorithm very rarely needs to backtrack. You can run WFC without any backtracking at all and it'll still find a solution most of the time. Some animated examples I put together might illustrate things more: https://boristhebrave.github.io/DeBroglie/articles/gallery.html https://boristhebrave.github.io/DeBroglie/articles/gallery.h...

doubleunplussed 8y ago
As a physicist who works with quantum mechanics, I have to say, "wave function collapse", is an extremely apt name for what you're describing. Usually when quantumy things are used in names of things it's just 'cause it sounds cool, but this is spot-on.
- madhadron 8y ago
  As an ex-physicist, I would say "Markov random field sampling" would be the right name.
- BorisTheBrave 8y ago
  It's really not. There's no probability field (unless you count booleans as a scalar), no complex numbers, and no entanglement. It's just constraint propogation, optimized for certain conditions and given a fancy name. I guess you could call it a markov random field, but I don't think it does unbiased sampling.
  - doubleunplussed 8y ago
    There kind of is entanglement though! You 'measure' one cell, and then all the other ones 'collapse' to values consistent with the result, because they have a hidden relationship with the cell you measured. That's what happens in quantum mechanics. When you measure one thing, all the other things its entangled with collapse somewhat too - but not necessarily completely, it depends on the entanglement they had with the measured system. It's a metaphor, I'm just saying it's very apt, not that it's mathematically equivalent.
  - gus_massa 8y ago
    I agree. My main objection of the QM metaphor is that in QM you can have interference. For example in version more similar to QM if you have a 2x2 map like this 1) X ? 2) X Y 3) X ? 4) X Y ? ? ? ? Z ? Z ? The probability of some particular tile in the bottom right corner may be bigger in 2) and 3) because somehow Y and Z make this tile more probable, but perhaps in 4) the probability decrease. The trick is that you must calculate amplitudes, not probabilities. For example, Y may contribute an amplitude of .5 to the bottom right corner , and the probability is (.5)^2=.25. And Z may contribute an amplitude of -.3 to the bottom right corner , and the probability is (-.3)^2=.09. But when both are there the amplitudes must be added and the probability is (.5-.3)^2=.04. This is a case of destructive interference that reduces the probability of a particular tile when both are present, but if both have the same sign it can be a constructive interference and increase the probability of that tile. This type of interference is what produce the weird interference lines in the double slit experiment (and even in the single slit experiment). This project just add probabilities, without squaring the numbers, so it's more difficult to have quantum-like weird things. Anyway, I like the result very much. Nice project. Nice name.
srtjstjsj 8y ago
How is that different from regular constraint propagation?
- dkural 8y ago
  It's not.
JazzXP 8y ago
Thank you. This description is what cleared it all up for me. I totally understand how this works now.

doubleunplussed 8y ago

As a physicist who works with quantum mechanics, I have to say, "wave function collapse", is an extremely apt name for what you're describing. Usually when quantumy things are used in names of things it's just 'cause it sounds cool, but this is spot-on.

madhadron 8y ago
As an ex-physicist, I would say "Markov random field sampling" would be the right name.
BorisTheBrave 8y ago
It's really not. There's no probability field (unless you count booleans as a scalar), no complex numbers, and no entanglement. It's just constraint propogation, optimized for certain conditions and given a fancy name. I guess you could call it a markov random field, but I don't think it does unbiased sampling.
- doubleunplussed 8y ago
  There kind of is entanglement though! You 'measure' one cell, and then all the other ones 'collapse' to values consistent with the result, because they have a hidden relationship with the cell you measured. That's what happens in quantum mechanics. When you measure one thing, all the other things its entangled with collapse somewhat too - but not necessarily completely, it depends on the entanglement they had with the measured system. It's a metaphor, I'm just saying it's very apt, not that it's mathematically equivalent.
- gus_massa 8y ago
  I agree. My main objection of the QM metaphor is that in QM you can have interference. For example in version more similar to QM if you have a 2x2 map like this 1) X ? 2) X Y 3) X ? 4) X Y ? ? ? ? Z ? Z ? The probability of some particular tile in the bottom right corner may be bigger in 2) and 3) because somehow Y and Z make this tile more probable, but perhaps in 4) the probability decrease. The trick is that you must calculate amplitudes, not probabilities. For example, Y may contribute an amplitude of .5 to the bottom right corner , and the probability is (.5)^2=.25. And Z may contribute an amplitude of -.3 to the bottom right corner , and the probability is (-.3)^2=.09. But when both are there the amplitudes must be added and the probability is (.5-.3)^2=.04. This is a case of destructive interference that reduces the probability of a particular tile when both are present, but if both have the same sign it can be a constructive interference and increase the probability of that tile. This type of interference is what produce the weird interference lines in the double slit experiment (and even in the single slit experiment). This project just add probabilities, without squaring the numbers, so it's more difficult to have quantum-like weird things. Anyway, I like the result very much. Nice project. Nice name.

srtjstjsj 8y ago

How is that different from regular constraint propagation?

dkural 8y ago
It's not.

JazzXP 8y ago

Thank you. This description is what cleared it all up for me. I totally understand how this works now.