randomizers and bias (1/N)
So for the randomizer, I wanted to add a mode ("full") that assigns orbs to lands as close to 1:1 as possible. Some pairings of orbs/lands are not allowed, and there are a lot of special cases in this logic. I wanted to place them such that they are unbiased, i.e. every possible placement has equal probability. That is surprisingly difficult.
randomizers and bias (2/N)
The naive algorithm would be to shuffle the orbs completely at random. If this results in an invalid configuration, try again until it works. That would be unbiased, but in this case, certain lands and orbs accept only a few pairings, so there'd be a lot of retries.
randomizers and bias (3/N)
One could adjust that by checking pairs during the process and rerolling any invalid pairs. However, this would introduce bias. Early on, each pairing is equally likely, but these pairings eliminate different numbers of possibilities later. If I place a more "restricted" orb that can go in only a few lands, that eliminates relatively few possibilities for it, compared to other orbs that could go anywhere.
randomizers and bias (4/N)
And this algorithm can still hit dead ends, if an orb or land has no valid pairings left.
randomizers and bias (5/N)
The algorithm I settled on is.. maybe more understandable if you start from the end.
Let's say I have N orbs left to place in N lands. Naively, I could check all N permutations, store the valid ones, choose one at random, and I'm done. Of course, there are N! permutations, and I start out with N = 60, so this would take an impossible amount of computation and memory.
randomizers and bias (6/N)
Except, if I check the permutations in a random order, I don't have to test all of them. I can just choose permutations until I find one that works. That's my naive algorithm from earlier that rerolls way too often and takes too long. But we can build off of that.
randomizers and bias (8/N)
There's one critical difference though: this allows me to interrupt the process early. If I find an invalid orb placement, I can stop right there and start over. I don't have to calculate the rest of the permutation.
That helps, slightly, but I still expect a lot of retries.
randomizers and bias (9/N)
What I'm trying to do is build this by induction. If I solve the problem for N, I can solve it for N+1. I need a problem statement where that works and is somewhat efficient.
So here it is:
PlaceOrbsInLands(list of lands remaining, list of orbs remaining)
This either returns a list of pairs of lands and orbs, or "failure". Each valid permutation has equal probability, and probability of failure is proportional to the number of invalid permutations.
randomizers and bias (10/N)
The base case (N=1) is simple. If that 1 orb is valid for that 1 land, return a single pair of that land and that orb. If not, return failure.
randomizers and bias (11/N)
So, for the induction step, we try to place 1 orb.
We have to first account for permutations that fail at that step: we should have an M/N probability of failing outright, where M is the number of invalid orbs for the first land, and N is the total remaining.
So, we can try the orbs in a random order. If the first one fails, we know M is at least one, and so we should randomly return failure 1/N of the time.
randomizers and bias (12/N)
If we move on to trying a second orb after a failure, and that one also fails, we should return failure a total of 2/N of the time. But we already did the 1/N check, so at this stage we should return failure 1/(N-1) of the time, to increase the total probability to where we need it.
randomizers and bias (13/N)
OK, so what if an orb placement succeeds? We still have to place the rest of them. For that, we call PlaceOrbsInLands for our remaining set of lands and orbs. If it succeeds, great. We add the one pair placed in this step, and return the list.
If it fails, we need to decide whether to stop at this step. We want to do that in such a way that the overall probability of returning failure is proportional to the number of valid permutations given our input state.
randomizers and bias (14/N)
This is actually easy. The probability of stopping based on this specific orb that we placed should be 1/N * (probability of a valid combination based on having placed that orb). Well, the probability of PlaceOrbsInLands failing is equal to the second term in that multiplication, so we can treat this the same as an invalid pairing. It doesn't really matter that there might be some valid ones.
randomizers and bias, bad end (15/N)
And now I have to rewrite my placement algorithm because I realized while writing this that I took some shortcuts that may not be valid.
randomizers and bias, bad end (15/N)
Turns out I do not understand this as well as I thought. PlaceOrbsInLands in this example (even though that's not quite how I actually wrote it) has a probability of failure that's proportional to the ideal failure probability, for one step, but it's lower than that ideal. For it to be the same, we'd have to stop everything immediately after encountering any failure. But, if it is the same, we end up with an equivalent of trying every permutation.
randomizers and bias, bad end
The naive algorithm is not as slow as I expected, in this case. I suspect that in other cases we'll have a problem.
So, I still have no good solution. I guess we go naive for now.
viridian
re: randomizers and bias (6/N)
@madewokherd 🐍 ooh! how many orbs are restricted in what ways? (we remembered that we like math puzzles)
re: randomizers and bias (6/N)
@viridian Here's the function that decides it: https://github.com/zenorogue/hyperrogue/blob/master/orbgen.cpp#L216
Orbs that are useless, forbidden, dangerous, or burn are not allowed.
re: randomizers and bias (6/N)
@viridian Oh, also, olrPNever is not allowed.
re: randomizers and bias (6/N)
@madewokherd so, functionally, for each orb/land combination there is exactly one orb-land-relationship, and at this stage we only care about "allowed" vs. "not allowed" (and later logic determines whether the orb gets placed as a "collect 25" thing or a prize or just laying around somewhere or something?)
my thought is — I don't know if this has a name, but it's an algorithm that I've used before to great success — is to build out a tree where at each node you branch off of whichever orb / land has the fewest options*, until you get to a point where you can calculate the number of remaining legal combinations (as n! or something), then sum those back up the tree as total number of combinations under each branch (so if orb 1 going in land A leaves 10 legal combinations and orb 1 going in land B leaves 23 combinations, choose A1 10/33 times).
*which is kind of getting at "whichever choice locks in the most information"
(maybe) a key to this being computable is to recognize equivalence classes — if every [remaining?] orb that can go into A can also go into B, C, and D, then treat A-D as a group & say an orb that can go into A-E as having two options of {A-D, E} ? or just treat A-D as a zone that accept 4 orbs and has combinatoric mass 4!= 24?
or possibly more important is identifying subgraphs were placing orb A can't affect the placement of orb B, b/c then you can do those separately & just multiply… if group M and group P are mostly disjoint except that orb Z can go into either, choosing orb Z as either M or P as your next pic
once you get down to "these n orbs go in these n slots, these k different orbs can go into these k different spots, etc" you can compute that weight as n! * k!
there's probably a lot of things like that that don't help in the general case but might in the specific case depending on the shape constraints
my real answer is to start with a very restricted subset of your orbs, write test cases for "how many possibilities remain given these selections so far?", and TDD your way through it by adding orbs with more kinds of restraints; that should guide you to the most relevant optimizations / simplifications.
re: randomizers and bias (6/N)
@viridian Is this approach still going to work when I start randomizing land unlock requirements (which means I have to calculate reachability)?
randomizers and bias (7/N)
Let's say N is sufficiently small that that algorithm works. Can I make it work for N+1? Yes, here's how:
I need to decide what orb to place in my first land. In order to eliminate bias, I must weigh the probability of each orb by the number of valid permutations with that orb in the given land. I can't calculate that value, but I can just try a random permutation. If it doesn't work, I reroll the first orb. Easy.
Except that's equivalent to the bad naive algorithm.