Author Topic: Inept question about probability  (Read 4942 times)

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 801
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Inept question about probability
« on: September 15, 2009, 05:46:53 PM »
EDIT: some crude testing suggests that my code works just as it should. Sometimes it's better to think things over twice before posting for help. Ah, well ...

Sometimes I'm feeling very stupid. Like ... just about now. Someone with a clearer mind should be able to help me out with this one.

I'm reworking the parts of my code that picks a random element from a set (of monsters, or items, or something else). First, the possible choices are put in a python dictionary, where the key is the name/identifier of the element, and the value is the relative probability of that element showing up. Something like this, in other words: {'sword':1, 'croquet club':2, 'knife and fork':4} In this example, croquet clubs should be twice as probable as swords, and cutlery four times as probable. Here's what I'm uncertain about:

Code: [Select]
def draw_lot(pd): # pd is the dictionary of stuff
    full_prob=reduce(lambda x,y : x+y, pd.itervalues()) # adds all values,
            # ie. sets full_prob to 7 in the example with the weapons
        choice=random.randint(1,full_prob) # a number between 1 and full_prob
        while 1:
            k=pd.popitem() # pops a random key+value from the pd dictionary
            if k[1]>=choice: # k[1] is the value, ie. 1, 2, or 4
                return k[0] # returns name of picked item
            else:
                choice-=k[1]

This works pretty fast, but I'm unsure as to whether it produces the intended effect. Will it actually return clubs twice as often as swords, and cutlery twice as often as clubs? I feel like I've a short circuit here somewhere, but I can't wrap my mind around it. So, any help regarding this would be appreciated.

As always,
Minotauros
« Last Edit: September 15, 2009, 05:59:04 PM by AgingMinotaur »
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: Inept question about probability
« Reply #1 on: September 16, 2009, 12:13:57 AM »
wow, where did you come up with that scheme?

I did something simular but mine is somewhat more basic. 
I have a list that I add things to multiple times, depending on its probablility.  I.e 'sword' will be added once, 'knife and fork' will be added 4 times.  Then I randomly choose an integer between 0 and size-1 of the list.
Then I select element at that place.

This works well if you know what is going in the list.  Before you add something you have to remember what is already in the list so you can set the probability correct.  But I guess all schemes have that problem.
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Inept question about probability
« Reply #2 on: September 16, 2009, 12:28:52 AM »
wow, where did you come up with that scheme?

I did something simular but mine is somewhat more basic. 
I have a list that I add things to multiple times, depending on its probablility.  I.e 'sword' will be added once, 'knife and fork' will be added 4 times.  Then I randomly choose an integer between 0 and size-1 of the list.
Then I select element at that place.

This works well if you know what is going in the list.  Before you add something you have to remember what is already in the list so you can set the probability correct.  But I guess all schemes have that problem.

You can do this with math, too. For instance, sword=1 knife=2 spoon=4, we can add together sword+knife+spoon and then pick a random number between 0 and this number. Then, 0 would be the sword, 1-2 the knife and 3-7 the spoon. If spoon+knife<what we picked, it must be sword. If spoon<what we picked and if spoon+knife>what we picked, it must be the knife, and so on.

But, I'd probably just use a list that gets added to multiple times, because that's easy :D

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 801
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: Inept question about probability
« Reply #3 on: September 16, 2009, 12:34:04 AM »
wow, where did you come up with that scheme?
I guess I'm just a natural 8)

I did something simular but mine is somewhat more basic. 
I have a list that I add things to multiple times, depending on its probablility.  I.e 'sword' will be added once, 'knife and fork' will be added 4 times.  Then I randomly choose an integer between 0 and size-1 of the list.
Then I select element at that place.
This is basically what I used to do, as well. It still seems like a natural approach. The reason I wanted to redo it, was that it ran slightly slow as my lists-of-stuff became bigger. I guess this has to do in part with the slowness of sorted lists in python, but mainly of course it's due to my subhuman coding skillz (my horns get in the way as I type). The new piece of code takes up less space in my source, and runs several times faster, sometimes knocking a few tenths of a second off of map building times.

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Inept question about probability
« Reply #4 on: September 18, 2009, 04:37:29 PM »
The approach with probability distributions given as numbers rather as repetitions generalizes to formulae. Thus, an elven sword might be very hard to find on low levels, popular on middle levels, and obsolete on high levels; abundant in elven-themed locations and avoided in orc-themed ones.

Also, repetitions are not very useful if you want some items to be extremely rare (in the given conditions) -- you would have to replicate the usual ones, say, thousands of times.

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 801
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: Inept question about probability
« Reply #5 on: September 18, 2009, 05:57:57 PM »
Also, repetitions are not very useful if you want some items to be extremely rare (in the given conditions) -- you would have to replicate the usual ones, say, thousands of times.

Yes, that's what started happening to my list-based scheme. Some of the lists would be several hundred thousand instances long ...

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

corremn

  • Rogueliker
  • ***
  • Posts: 700
  • Karma: +0/-0
  • SewerJack Extraordinaire
    • View Profile
    • Demise RogueLike Games
Re: Inept question about probability
« Reply #6 on: September 19, 2009, 10:25:47 AM »
Man, thats huge.

I choose random base types first then choose from the type that comes up. I.e First put in weapons, armour and misc items.  If weapons come up, I make another list with swords, axes, etc.  If swords comes up, I make another list with daggers, long swords.. and so on and so forth, thus eliminating creating massive lists of all items. 

So my lists only ever contain a few elements at a time.
corremn's Roguelikes. To admit defeat is to blaspheme against the Emperor.  Warhammer 40000 the Roguelike

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Inept question about probability
« Reply #7 on: September 20, 2009, 10:57:57 AM »
Yes, that's also a good idea because it is easy to maintain a balance between items of different kind. (So that if you decide to add a new weapon type, the balance won't be disrupted by reducing the chance of, say, obtaining potions of healing.)

Still, you need to put rare items somewhere in your tree (unless you use a different method altogether for them), and use a high multiplicity for your common path.