Shannon entropy - Githubissues

subdgtl / WFC

Prototype tools for playing with Wave Function Collapse

The Unlicense

5 stars 1 forks source link

Shannon entropy #15

Closed yanchith closed 3 years ago

yanchith commented 3 years ago

Fixes #13

I will post some exemplary runs on the Mondieu data set soon.

yanchith commented 3 years ago

So these are the results for various seeds in the Mondieu ruleset (EDIT: with the initial world state). As we can see, Shannon entropy is not doing very well either. Might be a mistake in my implementation, or we could try more rulesets.

Seed | Attempts Linear | Attempts Shannon
-----------------------------------------
   0 |           1000+ |            572
   1 |            105  |            994
   2 |            764  |           1000+
   3 |            735  |            162
   5 |            436  |           1000+
   8 |           1000+ |           1000+
  13 |           1000+ |            565
  21 |            305  |            971
  34 |            162  |           1000+
  55 |           1000+ |            995

yanchith commented 3 years ago

Oh, so when I try without the initial state, the ruleset is suddenly very easy to solve.

janper commented 3 years ago

Oh, so when I try without the initial state, the ruleset is suddenly very easy to solve.

but of course. the elements connect mostly in the Z direction (everything else is indifferent) and there is a hole in the middle of the world. also only certain modules are allowed to be on top and bottom. anything that is outside the envelope is out. so indeed the solution is easy without the hole and with anything allowed on top and bottom ;)

yanchith commented 3 years ago

so indeed the solution is easy without the hole and with anything allowed on top and bottom ;)

Now that you say this, this makes perfect sense. We shouldn't have been expecting any improvement here. What makes this specific Mondieu world hard to solve is its shape. And the way we compute weights is not informed by the world shape at all.

A couple of thoughts on this:

To measure if this is better, we should be using simple, nonrestrictive worlds with potentially difficult rules. Do we have any projects like that?
We should think, if there is a useful way of computing weights such that it takes the world into account. If we already had an already solved world, we could use that, but that is a chicken & egg problem.