ignore-me weighted picking with unknown sets

For what's not in 'Top Priority Game Design'. Post your ideas, visions, suggestions for the game, rules, modifications, etc.

Moderator: Oberlus

Post Reply
Message
Author
Ophiuchus
Programmer
Posts: 3427
Joined: Tue Sep 30, 2014 10:01 am
Location: Wall IV

ignore-me weighted picking with unknown sets

#1 Post by Ophiuchus »

just have to dump something here, s'gonna get updated

You imagine your targets sorted, the primary targets on the left, the secondary targets on the right and you make a dice roll.
Lower numbers left, higher numbers on the right. Primary targets get three numbers instead of one.

But in reality you do not know the sets in advance and also do not know how big the sets are. And the sets are actually not sorted.

Also maybe imagine you know (more-or-less) how many targets there are in whole, but you read them as a stream.

So you start with a dice roll.

E.g. you have 100 targets and primary weight is 3, you roll a die 1-300 and if it rolls a 1 you take the first primary target you encounter.

So for the case you do not find what you look for (worst case first):
  • If you roll a 1-3, and there is actually no primary target, you search until you encounter target 100, then you take the last secondary target (i.e. 100th target).
  • the following 4-6 shows the optimisation trick for stopping search earlier
  • If you roll a 4-6, and there is actually no primary target (or one is rightmost), you search until you encounter target 99, then you take the second last secondary target (i.e. 99th) [optimisation]
  • If you roll a 4-6, and there is actually only 1 primary target (and it is not rightmost), you search until you encounter target 100, then you take the second last secondary target (i.e. 99th) [simple]
  • the following 7-9 generalizes the optimisation trick for stopping search earlier
  • If you roll a 7-9, and there are actually zero to two rightmost primary targets, you search until you encounter target 98, then you take the third last secondary target (i.e. 98th).
  • If you roll a 7-9, and there are actually N<3 non-rightmost primary targets, you search until you encounter target 98+N, then you take the third last secondary target (i.e. 98th).
  • ...
  • If you roll a 295-297, and there are actually N<99 non-rightmost primary targets, you search until you encounter target 1+N, then you take the second secondary target (i.e. the 2nd).
  • If you roll a 298-300, and there are actually N<100 non-rightmost primary targets, you search until you encounter target N, then you take the first secondary target (i.e. the 1st).
This is completely wrong, it is unclear though to make correct treatment of "gaps" though. E.g. if you have 1 secondary target it has actually the same chance as any primary target.

Or a heuristic. Breakpoint could be 50/50, so around 200 (50*3+50).

With that expected distribution you would roll a die 1-200 and for 1-150 take a primary target and for 50-200 a secondary target. That would not exactly be 3-to-1 weight, but that weight is anyway kind of arbitrary. Probably sampling of up lets say 20% of the targets is a lot more fair than that heuristic. Small target sets can correctly be completely evaluated.

Maybe one can "warp" the roll once you find that your distribution is very wrong. I really think moderate amounts of wrongness are totally fine for most cases.

...neeed to think more...


This one should work, be correct and give some(times) speedups:

So for the battle scanner case we either have primary or secondary targets and all targets are either primary or secondary. And we do a single pick

#primary=p, #secondary=s, #targets=t=s+p
Only t is known.

The boring option: After one pass of evaluating the condition on all targets one has two distinct sets and knows s and p and can decide by a weighted dice roll.

Or: For picking only one result one does a maximum-weighted dice roll in the beginning (the expectation all targets are primary), with the result N<=t*3 ; then you stop evaluating the primary conditions if you found the Nth primary match.

If that the roll is low enough N < p*3, you dont have to evaluate the condition for the whole set.

If the roll is high N > p*3, what a pitty, one rolled a secondary, and did the maximum amount of work and evaluated all targets. On the bright side one knows p and warps the dice roll to choose the right secondary (the (N-(p*3))/3 -th one).

If the roll is very high you can speed this up by expecting all targets to be secondary and doing the reverse trick.
Any code or patches in anything posted here is released under the CC and GPL licences in use for the FO project.

Look, ma... four combat bouts!

Post Reply