Uniformly calculating Random Point Buy numbers

Question

In several popular tabletop games, there exist a series of 6 statistics (Also known as Attributes or Ability Scores.) They are integers. For the purposes of this problem, their numbers range from 7 to 18.

To keep things fair, there is a system by which people "Purchase" higher stats. This is called Point Buy. People start out with all of their attributes at some minimum (in this case 7) and a pool of points, which they can then spend to increase their Attributes. However, it is not a 1-1 ratio. An 18 is significantly more expensive than a 17, etc.

What I would IDEALLY like to do, is be able to write code that given a number of points, and a cost for each attribute, provide me with a random Attribute set (6 ints between 7 and 18) that makes use of the point total provided. Ideally I'd like the results to approach uniformity.

In the interest of making the problem easier to think about, I can provide an example example taken from the Pathfinder gaming system. (Note that those of you familiar with the system may notice that things aren't quite the same. I simplified it to make more sense as a computer science problem.)

All attributes start at 7, and cannot go any lower. You have 44 points to spend. The costs to raise an attribute by 1 are as follows: 2,1,1,1,1,1,2,2,3,3,4 Or, if you'd prefer the total cost, 2,3,4,5,6,7,9,11,14,17,21.

Also any links/resources to similar problems would be appreciated.

Answer 1

Another way of asking this question, using your example values, is: How many ways can you draw 6 numbers, with replacement, from the set {0,2,3,4,5,6,7,9,11,14,17,21} such that the sum is 44.

Once you have those answers you can select one uniformly, shuffle them into your attributes and add 7 to each one.

Some example answers:

{21, 21, 2, 0, 0, 0} {21, 17, 6, 0, 0, 0} {21, 17, 4, 2, 0, 0}
{21, 17, 3, 3, 0, 0} {21, 17, 2, 2, 2, 0}

etc.

So you select one of these, say {21, 21, 2, 0, 0, 0}. Shuffle it into your 6 attributes (A to F) for example {21, 0, 0, 2, 21, 0}. Map it back to your values {18, 7, 7, 8, 18, 7}.

Note, shuffling is not as easy as it sounds, there are discussions here on stackoverflow about it, and there is this interesting article: http://www.cigital.com/papers/download/developer_gambling.php

Here is correct (I believe), but not necessarily efficient (or pretty), C++ to calculate your sets:

#include <vector>
#include <iterator>
#include <iostream>

typedef std::vector<int> Costs;
typedef std::vector<int> Attrs;
typedef std::vector<Attrs> Choices;

void gen(Choices& c, Attrs a, int sum, Costs costs, int attrs) {
  if (sum < 0) { return; }
  if (attrs < 1) {
    if (sum == 0) {
      c.push_back(a);
    }
    return;
  }
  auto cc = costs;
  for (auto cost : costs) {
    a.push_back(cost);
    gen(c, a, sum - cost, cc, attrs - 1);
    a.pop_back();
    cc.erase(cc.begin());
  }
}

Choices genChoices(int sum, const Costs& costs, int attrs) {
  Choices allChoices;
  gen(allChoices, Attrs(), sum, costs, attrs);
  return allChoices;
}


int main(int, char*[]) {
  const Costs costs { 21, 17, 14, 11, 9, 7, 6, 5, 4, 3, 2, 0 };
  const int sum = 44;
  const int attrs = 6;

  auto choices = genChoices(sum, costs, attrs);

  std::cout << choices.size() << "\n";
  for (auto c : choices) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<Attrs::value_type>(std::cout, " "));
    std::cout << "\n";
   }

  return 0;
}

Compile with g++ 4.7.3: g++ -std=c++0x -Wall -Wextra attrs.cpp

There are 280 of them for the example you give.

Answer 2

The easiest way to do this is to just generate all values at random and then check whether the result is feasible with the given amount of points. If it is not start again.

This might seem very inefficient and in a certain way it of course is, but for real applications this is totally fine. For example, if the chance of picking a feasible solution is 1/6, the expected number of tries is 6 and the chance that you need more than 40 tries is less than 1 in 1000.

So unless you need to do this a massive amount of times (at least > 1000), I would recommend this method. It is easy to code, short and works for any parameters.

Two speed ups:

1. If you have a low number of available points, only generate attributes in the range of what could be bought with extreme placement of the attributes. So if you have 10 points, only generate attributes in the range of 7-14.
2. You can check whether the current result is feasible while you are generating the attributes. So you can already discard the current result if more than the possible points have been spend on the first two attributes. It is important to discard the current configuration and start anew. If you try to somehow fix it, you will end up with a skewed distribution.

**edit: just realized that I missed the “all points spend” condition you stated. That makes the problem a lot harder and this method very inefficient since only a very small portion of the possible configurations is feasible. The exact dynamics depend on your parameters, so if you only need a small number of samples, you could just try this method and see if it’s fast enough.

Answer 3

For the general theory involved here: The possible configurations are a modification of the knapsack problem. To sample uniformly you could iterate all feasible configurations and pick then uniformly pick one of those. I would expect the number of feasible configurations to be rather small, so if you have a fast way of finding them all, that could work just fine.

If there are too many possible configurations so can’t enumerate or count them, you have the standard problem of sampling from a distribution about which you have some information, but not all. I think the standard way to solve this problem is to use the a Metropolis-Hastings algorithm or some other kind of Markov Chain Monte Carlo (see also Propp-Wilson Algorithm). But to use those methods, you will have to construct a transition function between the feasible states that has certain properties. I tried a little bit, bout couldn’t think of one.