ion/n/random.py

   1 """
   2 Random selection.
   3
   4 Summary:
   5     * OHRRPGCE/FF6 style random item selection (percentage probability based)
   6     * Weighted sampling of a sequence (choose one element, likelihood
   7       determined by weights)
   8     * Box-filling weighted sampling (virtual guarantee that each of
   9       the entire set of options will be given exactly once before
  10       repeating)
  11     * Dispensing items from a stock. (absolute guarantee that each of
  12       the entire set of options will be given exactly once before
  13       repeating)
  14     * Simple dice roll (as in '2d4' - 2 4sided dice.)
  15     * DiceRoll object: d = Diceroll(2,4); print d prints a random
  16       value in the range 2d4.
  17     * Simple throw from origin. V -/+ (random() * W)
  18
  19 """
  20
  21 # hackery so 'import random' imports the systemwide random, not us.
  22 from __future__ import absolute_import
  23 import sys
  24 selfpath = sys.path.pop(0)
  25 from random import randint, sample, gauss
  26 sys.path.insert (0, selfpath)
  27
  28
  29 #  How to use numpy.random.multinomial to pick from a list according
  30 #  to probability weightings:
  31
  32 import numpy
  33
  34 def choices (probs, size = 1):
  35     """ For a sequence of length N, along with a probability array of length N,
  36         return an array of shape SIZE containing random indices 0..N-1
  37         selected according to the given probabilities.
  38
  39         If you want actual samples rather than their indices, see samples()
  40         """
  41     # take 1 trial
  42     tmp = numpy.random.multinomial (1, probs, size)
  43     # multiply ([0,0,1,0,0] -> [0,0,3,0,0])
  44     tmp *= range (1, len(probs) + 1)
  45     # sum ([0,0,3,0,0] -> 3
  46     return tmp.sum (-1) - 1
  47
  48 def samples (items, probs, size = 1):
  49     """ Given a probability list totaling to 1.0, and a list of items, return
  50         1 or more of the items in list, per the probabilities."""
  51     c = choices (probs, size)
  52     a = items
  53     # only adapt it if not already adapted.
  54     try:
  55         assert a.dtype == numpy.object_
  56         a = numpy.array (items, dtype = numpy.object_)
  57     except:
  58         pass
  59     return a.take(c)
  60
  61
  62
  63
  64 # useful for eg. choosing which algo to demonstrate in a demo,
  65 # choosing which item reward to give in an RPG,
  66
  67 def boxfill (seq, status, weights = None):
  68     """Fill weighted boxes in a roughly even way.
  69
  70     If status is None, it is initialized.
  71
  72     Then...
  73
  74     status is used to inversely weight weights. status is a sequence of matching length to seq.
  75     Weighting is ((1.0/statusval) * weight)
  76     Thus, the more times something has been chosen relative to its siblings,
  77     the less likely it is to be chosen.
  78
  79     If you pass a status array, it should be filled with integers.
  80
  81     As a choice falls behind the others in amount-of-times-chosen, its likelihood to be chosen
  82     approaches infinity (but is never actually infinite.
  83     for instance, if choice A has been picked 4million times and choice B has been picked 10 times, there
  84     is a 1 / 400001 chance of A being picked next.
  85
  86     Another nice property is the auto-leveling. If the choices weren't made evenly (deliberately, say,
  87     like when a type of enemy can only drop one particular item), then you can still even out the
  88     spread using this when the option to drop one of several is available.
  89
  90     Returns an element from seq; Updates status in-place.
  91
  92     See also
  93     --------
  94     dispense
  95     """
  96     # could optimize this using digitization
  97     if weights:
  98         _w = [(1.0 / s) * w for s, w in zip(status, weights)]
  99     else:
 100         _w = [1.0 / s for s in status]
 101     total = sum(_w)
 102
 103     #elect a partition
 104     n = randint  (1, total)
 105     for i in xrange (len (weights)):
 106         n -= _w[i]
 107         if n <= 0:
 108             status[index] += 1
 109             return seq[i]
 110     return None
 111
 112 # boxfillIter goes here
 113 class boxfillIter (object):
 114     def __init__ (self, seq, status, weights = None, loop = 1):
 115         # infinite looping is done with loop = inf
 116         self.seq = seq
 117         self.status = status
 118         self.weights = weights
 119         self.loopcounter = loop
 120
 121     def __iter__ (self):
 122         return self
 123
 124     def next (self):
 125         nextrval = boxfill (self.seq, self.status, self.weights)
 126         if nextrval == None:
 127             self.loopcounter -= 1
 128         if self.loopcounter == 0:
 129             raise StopIteration()
 130         return nextrval
 131
 132
 133 # XXX same as samples (seq, weights)!
 134 def weightedSample (seq, weights):
 135     """Randomly choose an element from seq according to weights. example:
 136     seq = ("Red","Green","Blue")
 137     weights = ( 20, 10, 5)
 138     weightedsample(seq, weights)
 139
 140     returns "Red" ~20/35 of the time, "Green" ~10/35 of the time, and "Blue" ~5/35 of the time.
 141
 142     Sorting the choices so the most likely come first will speed things up.
 143     """
 144
 145     #calculate total
 146     total = sum (weights)
 147
 148     #elect a partition
 149     n = randint (1, total)
 150     for i in range (len (weights)):
 151         n -= weights[i]
 152         if n <= 0:
 153             return seq[i]
 154
 155     return None
 156
 157
 158 # 2007-05-17 further optimizations (just fill and empty status, using sample)
 159 # DODO use generator instead
 160 def dispense (contents, status, n = 1):
 161     """Dispense the contents of a box.
 162
 163     Parameters
 164     ----------
 165     contents: sequence
 166               Collection of items to dispense
 167     status: list
 168               Which items have not been dispensed already.
 169               If you pass ``status = []`` it will be automatically initialized to all of the contents.
 170               Status will be modified in-place during calls to ``dispense()``
 171     num: integer
 172               Number of items to dispense
 173
 174     Returns
 175     -------
 176     items: sequence
 177            Collection of items dispensed. May include None, when there are
 178            not enough items remaining in the box to dispense ``num`` items.
 179
 180     Notes
 181     -----
 182     Save the contents of ``status`` if you want to persist the state.
 183     ``contents`` is never modified.
 184
 185     """
 186     if len(status) < 1:
 187         # init
 188         status.extend(sample (contents, len (contents)))
 189     realn = min (n, len (status))
 190     tmp = status[:realn] + ([None] * (n - realn))
 191     # off with it's head!
 192     status[:realn] = []
 193     if len(tmp) == 1:
 194         return tmp[0]
 195     return tmp
 196
 197 def affinitySample (items, data, samples = 1):
 198     """Sampling weighted by affinity.
 199
 200        Parameters
 201        ----------
 202        items: sequence
 203               Group of 1 or more items which are related, represented as IDs
 204        data: map
 205               Intimacy data.
 206               Keys are item IDs, values are sequences of related item IDs
 207               All item IDs referenced must have an entry in ``data``.
 208        samples: integer
 209               Number of related items to find
 210
 211        Returns
 212        -------
 213        sampled: sequence
 214                 sequence of item IDs of length ``samples``
 215
 216        Notes
 217        -----
 218        Good for selecting partially or entirely themed sets.
 219
 220        Sparse matrix might work better here.
 221
 222        The first sample is picked randomly, if items[] is empty.
 223        Subsequent samples are required to be related increasingly intimately with the other samples.
 224
 225        data should hold intimacy data.
 226         {
 227           key : (relation, relation, relation),
 228           key : ...
 229           ...
 230         }
 231
 232         Each relation item should match a key in data.
 233         They can and should be repeated: for example:
 234
 235         {
 236           'gauntlets' : ('small shield', 'buckler','tower shield','leather gloves','leather gloves')
 237           'leather gloves' : ('small shield', 'buckler','tower shield','gauntlets','gauntlets')
 238           'buckler' : ('small shield','small shield', 'tower shield', 'tower shield','leather gloves','gauntlets'),
 239           'small shield' : ('buckler','buckler','tower shield', 'tower shield','leather gloves','gauntlets'),
 240           'tower shield' : ('buckler','buckler','small shield','small shield','leather gloves','gauntlets'),
 241         }
 242
 243         here, you can see the way that shields are more apropos to each other than handwear, though they both are apropos to each other, being armor, and vice versa.
 244
 245         Normally, intimacy data would be autogenerated from something like:
 246
 247         {
 248            'armor': ('buckler','small shield','tower shield', 'leather gloves','gauntlets'),
 249            'shields': ('buckler','small shield','tower shield'),
 250            'handwear': ('leather gloves','gauntlets'),
 251         }
 252
 253         Which suggests the straightforward algorithym of: 'intimacy == number of categories shared' - thus, all armor is apropos at least 1 point, and the contents of the specific categories are apropos 2 or more points.
 254
 255         (the real data would probably be numeric object ids, for efficiency; this works too, though.)
 256
 257
 258        Less than samples samples may be returned.
 259     """
 260
 261 def gotItem (info):
 262     """ Illustrates my theory of OHRRPGCE's behaviour giving items after battle.
 263     Pass a tuple (item, item %, rareitem, rareitem %) as the info parameter.
 264
 265
 266     Returns
 267     -------
 268     item : object
 269            One of (item, rareitem, -1) (where -1 indicates nothing dropped)
 270
 271     Notes
 272     -----
 273     equivalent to::
 274
 275       tmp = chain (((item %, item), (rareitem %, rareitem)))
 276       if tmp:
 277         return tmp[-1]
 278       return -1
 279
 280     """
 281
 282     if percent (info[1]):
 283         # rareitem's chance to drop:
 284         # (100% - item%) * rareitem%
 285         #
 286         # eg. item% == 50, rareitem% == 50
 287         # drop item 25% of the time,
 288         # rareitem  25% of the time,
 289         # nothing   50% of the time.
 290         #
 291         # with rareitem% == 25:
 292         #  item     37.5%
 293         #  rareitem 12.5%
 294         #  nothing  50%
 295         #
 296         if percent ((info[3] * (100 - info[1])) / 100 ):
 297             return info[2] # rareitem
 298         else:
 299             return info[0] # item
 300     else:
 301         return -1 # nothing :(
 302
 303     # expressed in weighted sampling:
 304     #
 305     # remainder = float (100 - info[1])
 306     #
 307     # return weightedSample ((info[0],info[2], -1), (info[1],
 308     # (remainder / 2.0) * (info[3]/100.0), remainder / 2.0)
 309
 310     # In more general, weighting is like:
 311     #     item @ item%
 312     #     item2 @ remainder
 313     #     item3 @ i2remainder
 314     #     item4 @ i3remainder
 315     #     None  @ allremainder
 316     #
 317     # With remainders weighted into the previous remainder space.
 318     #
 319     #
 320     # say, 50% 40% 30% 20%
 321     #
 322     # then..
 323     # 50% chance of 1
 324     # 20% (40% * 50%) chance of 2
 325     # 8% (30% * (100% - (50% + 20%))) chance of 3
 326     # 4.2% chance (20% * (100% - (50% + 20% + 8%)) ) of 4
 327     # 16.8% chance (20% * (100% - (50% + 20% + 8% + 4.2%)) ) of None
 328     #
 329     # to be precise (percentages expressed like 1.00 == 100%)
 330     #
 331     # weights = []
 332     # weights.append (factorlist[0])
 333     # factorlist.pop(0)
 334     #
 335     # for fac in factorlist:
 336     #     weights.append ((fac / 100.0) * (100.0 - sum(weights)))
 337     #
 338     # weights.append (100.0 - sum(weights))
 339     #
 340     # examples:
 341     #
 342     #
 343
 344
 345 def cumulative_to_simple_weights (factors):
 346     """ Convert a list of weights in terms of:
 347         M% chance of A, ((100%-Achance) * N%) chance of B,
 348         ((100% - (Achance + Bchance)) * O%)  chance of C,
 349         (whatever percentage remains in 100%) chance of Nothing.
 350
 351         To absolute weights.
 352         ie. [50.0, 50.0] becomes [50.0, 25.0, 25.0]
 353         ( 50% chance of A, 25% chance of B, 25% chance of nothing/ default.)
 354
 355         Thus, your default option should be the last choice - choices[-1]
 356
 357         There is not always a chance of Nothing being chosen. If the last factor is 100%, it will
 358         serve as the default itself, with 0% chance of Nothing.
 359
 360         Specifying 0% chance for anything is as good as commenting it out. It's perfectly harmless
 361         and may be useful during testing.
 362         """
 363     weights = []; factors = list (factors)
 364     weights.append (factors.pop (0))
 365     for fac in factors:
 366         weights.append ((fac / 100.0) * (100.0 - sum (weights)))
 367     weights.append (100.0 - sum (weights))
 368     if weights[-1] <= 0.00000000001:
 369         weights.pop() # 0% chance is silly.
 370     return weights
 371
 372
 373 def percent(p):
 374     """Return True p% of the time,
 375
 376     Parameters
 377     ----------
 378     p: integer
 379        Percentage chance
 380
 381     Returns
 382     -------
 383     success: bool
 384              Whether the percentage roll succeeded
 385     """
 386     if randint (1, 100) <= p:
 387         return True
 388     else:
 389         return False
 390
 391 def angbandDiceRoll (d, s):
 392     """Angband style dice roll - D rolls of an S-sided dice.
 393
 394        angbandDiceRoll (2,16) averages 17.4
 395        angbandDiceRoll (16, 2) averages 24.
 396
 397
 398        Examples
 399        --------
 400
 401        .. plot::
 402
 403           >>> rolls = [angbandDiceRoll (3,6) for v in range(100)]
 404           >>> import matplotlib.pyplot as plt
 405           >>> plt.plot (range(100), rolls, 'o')
 406     """
 407     from numpy.random import randint
 408     return randint (1, s + 1, d).sum()
 409
 410 def newDiceRoll(d, s):
 411     "Newstyle dice roll"
 412     return int (gauss ((d + d * s / 2), (d * s) / 5))
 413
 414 ## Choice tree goes here:
 415 #
 416 # idea is:
 417 #
 418 #
 419 #  a10.
 420 #  +  |
 421 #  |  +-- b1
 422 #  |  +-- c2 +-- d5
 423 #  |         +-- e2
 424 #  +         +-- f1
 425 #  k10.
 426 #  +  +--- l1
 427 #  |  +--- m1
 428 #  |  +--- n2
 429 #  +
 430 #  t20.
 431 #     +--- u5
 432 #     +--- v1 +-- w1
 433 #             +-- x1
 434 #             +-- y1
 435 #             +-- z1
 436 #
 437 #  numbers show weights.
 438 #  Each iteration picks an option from the current level, then moves
 439 #  to the next level. Iteration terminates when an item has no
 440 #  subitems.
 441 #
 442 #
 443 # The above tree might look like (lispish):
 444 #
 445 # (10, (1, 'b', 2, (5, 'd', 2, 'e', 1, 'f')), 10, (1, 'l', 1, 'm', 2,
 446 # 'n'), 20, (5,'u', 1, (1, 'w', 1, 'x', 1, 'y', 1, 'z')))
 447 #
 448 # You can use this as the governing data for an AI, for instance (if
 449 # you recognize that the opponent is mounting a strikingly effective
 450 # offensive, adapt the weightings to emphasize defense..)
 451 #
 452
 453 #2007-05-22 added ChainIter
 454
 455 # xx use a XDigraph for the above system
 456 # (point, (action, cond, chaincond), point)
 457
 458 def chain (pairs):
 459     """Iterates over (chance, value) pairs until a trial fails.
 460
 461     Parameters
 462     ------------
 463     chain : iterable
 464         (chance, value), (chance, value), (chance, value)...
 465         sequence or iterable.
 466         chances are specified as percentages.
 467
 468        Not to be confused with itertools.chain(), which returns an
 469        iterator chaining sequences end-to-end
 470        (a1,a2,a3..alast,b1,b2,b3..blast,..) with no random factor
 471        involved.
 472
 473     Examples
 474     --------
 475
 476     50% chance of 'bb', 25% chance of 'bb' and 'cc', 25% chance of Nothing::
 477         for a in chain (((50, 'bb'),(50, 'cc'))):
 478             #use the value of a here
 479
 480     See also
 481     --------
 482     percent
 483     """
 484     index = -1
 485     for chance, value in pairs:
 486         if percent (chance):
 487             yield value
 488         else:
 489             raise StopIteration()
 490
 491 def diceroll (dice, sides):
 492     """Roll dice infinitely
 493
 494     Parameters
 495     ----------
 496     dice: integer
 497           Number of dice to roll
 498     sides: integer
 499           Number of sides on the dice
 500
 501     Returns
 502     -------
 503     value,...: integer
 504           Values in the range [``dice``..``dice*sides``]
 505
 506     Notes
 507     -----
 508     Normally used in combination with ``ion.limititer()``
 509     """
 510     minval = sides
 511     maxval = dice * sides
 512     while 1:
 513         yield randint (minval, maxval)
 514
 515
 516 def throw (origin, distance):
 517     """ see also gauss(), normalvariate() which sometimes produce
 518     values beyond bounds."""
 519     return randrange (origin - distance, origin + distance)
 520
 521
 522
 523
 524
 525
 526 # TESTING STUFF FOLLOWS! MOVE OUT DAMN YOU!
 527
 528 # test diceroll
 529
 530 #a = DiceRoll(1,16)
 531 #print a
 532 #print a.d,a.s
 533 #for i in xrange(64):
 534 #    b = a + 0
 535 #    print 16 * b
 536
 537
 538
 539
 540
 541
 542 #test weightedsample
 543
 544 #f = 1.0
 545 #n = int(56 * f)
 546 #seq = (1,2,3)
 547 #weights = ( 32, 16, 8)
 548
 549 #l = []
 550
 551 #for i in xrange(n):
 552 #    l.append(weightedSample(seq,weights))
 553
 554 #>>>
 555 #print "R,G,B| %f,%f,%f" % (l.count(1) / f ,l.count(2) / f ,l.count(3) / f)
 556
 557
 558
 559 # a dictionary mapping number -> name
 560 #lut = {
 561 #    -1: "Nothing",
 562 #    0: "Item",
 563 #    1: "Rareitem",
 564 #}
 565
 566 #give item, never rareitem or nothing:
 567 #for i in xrange(8):
 568 #    print lut[ gotitem( (1, 100, 2, 100)) ]
 569 #
 570 #give item 50% of the time, rareitem 25% of the time,
 571 #or nothing 25% of the time:
 572 #
 573 #for i in xrange(16):
 574 #    print lut[ gotitem( (1,75,1,33) ) ]
 575
 576 #l = []
 577 #for i in xrange(800):
 578 #    l.append( weightedSample ( (-1,0,1), (1,2,1) ) )
 579
 580 #f = 8.0
 581
 582 # >>>
 583 #print "%f %f %f" % (l.count(-1) / f, l.count(0) / f, l.count(1) / f)
 584
 585 # XXX move to pixlab
 586 # XXX support even number of divisions, so it can be used for
 587 #     palette spread calculation.
 588 def plasma_color_gradient (divisions, initcolors, bounds = None):
 589     """
 590         Fills in randomish colors between colors A and B in the
 591         following manner:
 592
 593         A           B
 594         A     C     B
 595         A  D  C     B
 596         A  D  C  E  B
 597         AE D  C  E  B
 598         AE DF C  E  B
 599         AE DF CG E  B
 600         AE DF CG EH B
 601         AEIDF CG EH B
 602         AEIDFJCG EH B
 603         AEIDFJCGKEH B
 604         AEIDFJCGKEHLB
 605
 606         Parameters
 607         ----------
 608         divisions : integer where size % 2 == 1
 609         initcolors : array [X][CHANNEL]
 610         bounds : tuple of tuples, optional
 611                  Specifies acceptable randomization ranges for each
 612                  channel, on the range 0(start) to 1 (end)
 613
 614         Examples
 615         --------
 616         Limit the randomization of L to central 50%,
 617         the other channels are completely free.
 618         >>> plasma_color_gradient (3, [[100,-4,-10], [20,3,98]],
 619         ...                        ((.25,.75), (0,1), (0, 1)))
 620
 621     """
 622     # loop
 623     # find the first unfilled midpoint
 624     # fill it
 625     # check for complete fill -- if so, return.
 626     pass
 627
 628 __all__ = ('angbandDiceRoll', 'cumulative_to_simple_weights',
 629  'affinitySample', 'boxfill', 'chain', 'DiceRoll', 'dispense',
 630  'gotItem', 'newDiceRoll', 'percent', 'throw', 'choices', 'samples',
 631  'plasma_color_gradient')
 632