6
\$\begingroup\$

I'm writing a Discord bot for an online 7th Sea campaign. Players will type something like

roll finesse 4 + weaponry 3 + 1

and the bot will spit out something like

3 raises (9+2, 8+3, 6+4, leftover 5)

The hard part is grouping the dice into raises. I would like to do this automatically. Is there a known optimal algorithm for this? I played around with a straightforward greedy approach, but I'm not convinced that it is optimal in all cases. The algorithm I'm using now is:

  1. Add the largest die.
  2. Repeatedly add the largest die that will not make the group exceed 10 (or 15, if applicable).
  3. If the group isn't 10 yet, add the smallest die.

I've found cases where this “almost” doesn't produce the optimal outcome, but no actual failures. Still, I'm not completely convinced. Is there any existing research on this?

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Please don't use code formatting for quotes. I know we've got a meta on this, but basically it 'reads' it wrong for those using screen readers and should only be used for actual code. \$\endgroup\$ – NautArch Apr 23 '20 at 17:09
  • 2
    \$\begingroup\$ @NautArch it is an actual code, isn't it? A command for the bot, written in specific syntax \$\endgroup\$ – enkryptor Apr 23 '20 at 17:12
  • 3
    \$\begingroup\$ Here is the meta on the reasoning behind this. But thank you for your understanding! \$\endgroup\$ – NautArch Apr 23 '20 at 17:14
  • 1
    \$\begingroup\$ I'll need to think about this more, but it sounds like you'll want a recursive algorithm that passes an array of remaining dice, sorted ascending in value that checks for all pairs that are exactly ten first, then move on to what you're doing. I haven't try to code it out yet \$\endgroup\$ – CatLord Apr 23 '20 at 18:46
  • 1
    \$\begingroup\$ I believe I have a counterexample for your greedy algorithm: (8, 3, 3, 3, 3, 3, 3, 3, 1, 1). You can get three raises out of those dice by grouping them as 8 + 3 = 11 and two groups of 3 + 3 + 3 + 1 = 10, but your algorithm would instead first group up 8 + 1 + 1 = 10 and then be left with seven 3s that cannot make two raises. \$\endgroup\$ – Ilmari Karonen Apr 23 '20 at 22:56
7
\$\begingroup\$

Your problem appears to be an instance of the maximum set packing problem:

Given a (multi)set of positive integers, how many disjoint subsets with sum ≥ 10 can be formed from them?

(Allowing subsets with sum ≥ 15 to count as two raises turns it into a weighted maximum set packing problem instead, with subsets summing to 15 or more having twice the weight of those with sum between 10 and 14.)

In general, the maximum set packing problem is known to be hard to solve, and I suspect that even this specific instance of it may be difficult to solve exactly for large inputs. Fortunately, the limited number of dice available to players means that a (smart) exhaustive search of the solution space is probably tractable.

In particular, the maximum set packing problem can be represented as an integer linear program, and solved (or approximated) using any software package designed for solving such programs. You don't say what language you're writing your bot in, but e.g. for Python a quick Google search turns up several possible libraries such as Python-MIP. (To be honest, most of those tools are probably way overkill for this task, but since they exist already, it may be easier to use them than to try to come up with an algorithm from scratch.)


Also note that there are some preprocessing steps you can do to simplify the problem, and in some cases even solve it completely:

  • Any roll of 10 (or more, with bonuses) can be set aside as its own group.
  • Any pair of dice that sum to exactly 10 can also be safely set aside as a group: there's no situation where breaking up such a pair could increase the number of possible raises. (At least, I have a proof sketch of this that I'm pretty sure is correct.)
  • The maximum number of additional raises that can be obtained from the dice remaining after the simplification steps described above is bounded by their sum divided by 10. In particular, if this sum is less than 20, the problem is trivial.

Unfortunately, the simplifications above assume that the skill rank 4 bonus that allows counting any groups summing to 15+ as two raises is not in play. If it is, you could obviously still safely set aside any single rolls of 15+, but I'm not sure those can ever arise. And I'm not even really sure whether setting aside pairs summing to 15 is guaranteed to be optimal in that case.

Still, at the very least, you can obtain a lower bound on the number of possible raises using e.g. your greedy solution algorithm, and an upper bound by multiplying the total sum of the dice with 1/10 (or 2/15). If those bounds match, you'll know that your greedy solution is optimal. If they don't, you could either try a more complicated exhaustive search or just display the greedy solution accompanied by a warning to the player that a better grouping might exist.


Actually, thinking about this a little more, you probably don't need anything like a full ILP solver for this; a simple recursive search with memoization ought to be more than sufficient for, say, less than 20 dice. In pseudocode, it could look something like this:

cache = map(multiset of integers -> integer)

function max_raises_for(rolls: multiset of integers) -> integer:
    if rolls in cache: return cache[rolls]

    upper_bound = round_down(sum(rolls) / 10)
    if upper_bound ≤ 1: return upper_bound

    max_raises = 0
    for each group in feasible_groups_for(rolls):
        raises = 1 + max_raises_for(rolls - group)
        if raises > max_raises: max_raises = raises
        if max_raises = upper_bound: end loop

    cache[rolls] = max_raises
    return max_raises

where the helper function feasible_groups_for(rolls) generates every distinct subset of rolls that sums to at least 10 and has no extra dice that could be removed without bringing the sum below 10.

Note that, for efficiency, you'll definitely want to store the multiset rolls in some canonical form, at least for the cache lookups, so that e.g. looking up (4, 5, 4, 3) will find an existing cache entry for (3, 4, 4, 5). Simply sorting the list of rolls before looking it up in the cache will work, but you could also represent the multiset e.g. as a (sorted) map of dice values to counts, so that e.g. (3, 4, 4, 5) would be represented as {3:1, 4:2, 5:1}. Also, you'll probably want to apply the preprocessing steps I suggested above to simplify the problem before running this algorithm on it.

I'll leave modifying the pseudocode to handle the "double raise on 15" rule as an exercise; basically you'll just need to consider more feasible groups (i.e. those that sum to 15, with no extra dice) and adjust the upper bound calculation to something like round_down(sum / 15) + (1 if sum % 15 ≥ 10 else 0) (and return early if it's at most 2). Also, if you want to return the actual groups of dice in the optimal solution and not just how many of them there are, you can do that easily enough by storing the actual list of found groups in the cache (and returning it from the function) instead of just its length.

\$\endgroup\$
1
  • \$\begingroup\$ The moment I saw this question I knew who'd be answering it x) \$\endgroup\$ – kviiri Apr 24 '20 at 19:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.