Want to (wait for it) *pool* our resources? 😃

[posita]

Some explorations are best done solo, but I feel like there's at least room to ponder whether you and I should collaborate. I don't know precisely what that might look like, but it feels like our outlooks and skillsets are complimentary. If you're interested in exploring further, let me know. If not, no judgment whatsoever.

[HighDiceRoller]

Thank you for your considerate message. I'm happy to consider comments, questions, and requests you may have, as well as requests for the same in the other direction. To be frank, however, I would stop short of accepting direct contributorship at this time; as you allude to, this project is in part an outlet for my introversion.

Here are my objectives for the project within the next six months:

• I'm working on an extended and refined explanation of the pool algorithm. Hopefully this will help in understanding its operation.
• I'm hoping to settle on a version 1.0 feature set for this project and release it. Historically, finalizing anything has been devilishly elusive, but it's necessary for any practical use beyond a solo affair.

[posita]

Thanks for your thoughtful response and for the roadmap!

I'm working on an extended and refined explanation of the pool algorithm. Hopefully this will help in understanding its operation.

I think the real trick on this one is discovering ergonomics to lead to reinforcing intuitions. In this particular case, I think it's a challenge. A great and worthy one, to be certain, but a challenge nonetheless. If I think of anything that might be helpful, I'll definitely pass it along.

Historically, finalizing anything has been devilishly elusive, but it's necessary for any practical use beyond a solo affair.

I think you describe the experience of many a developer (including myself)! FWIW, I had a similar outlook to yours when I started dyce (as an outlet). Given other things competing for my attention, it has been hard for me to maintain momentum toward something worthy of the 1.0 moniker. That's still in an aspiration, of course. I have some fresh ideas and may even have the time to explore some of them. This is where I think you hit the nail on the head: Getting to a polished product is hard. Getting (and staying) there alone is even harder.

Thanks again for the care and attention. I'm happy to cheer from the sidelines as long as it remains helpful and welcome!

[posita]

Howdy again! I have a pending branch on dyce to advertise icepool in dyce's table of related libraries. Please let me know if you would prefer that icepool not be listed or if you think any corrections need to be made. Thanks, and my apologies for not getting to this sooner. 😊

[HighDiceRoller]

Much appreciated, go for it! I should come up with a list of related projects as well...

---

I've been working on turning the core dice pool algorithm into a paper, which will hopefully be more useful as an explanation. Here's a preprint, though if you wait a week I'll update it with a revised version. I've cited a couple StackExchange Q&As by Ilmari and yourself. It will appear in AIIDE 2022.

[posita]

Looks great! I look forward to the update.

FYI, the update to the dyce's README that includes a link to icepool will go out with its next release.

After reading the paper, I was wondering if you considered a mechanism by which to short circuit your callbacks (or if it's even necessary). I'm thinking of something like this:

class KeepHighest(icepool.OutcomeCountEvaluator):
    def __init__(self, num_highest: int):
        super().__init__()
        self._num_highest = num_highest
    def direction(self, *generators: icepool.OutcomeCountGenerator) -> int:
        # I'm not sure I understand this interface, but the intention is to get larger outcomes before smaller ones
        return -1
    def next_state(self, state, outcome, count):
        if state is None:
            state = ()
        state = (outcome,) * count + state
        if len(state) >= self._num_highest:
            raise NoNeedToLookAnyFurtherOnThisBranchWeCanStopNow(state[-self._num_highest:])
        return state  # Perhaps in case our pool doesn't have enough dice?

Where NoNeedToLookAnyFurtherOnThisBranchWeCanStopNow would recognized by the callback mechanism (currently, OutcomeCountEvaluator._eval_internal and OutcomeCountEvaluator._eval_internal_iterative, I believe) to stop delving and accept the raised state as final. The intention is that for KeepHighest(3)(icepool.d4.pool(4)) the callbacks might look something like:

state = None
state = next_state(state, 4, 4)
# done; final state is (4, 4, 4)

state = None
state = next_state(state, 4, 3)
# done; final state is (4, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 2)
# done; final state is (3, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 1)
# done; final state is (3, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 0)  # not sure if this call is actually made
state = next_state(state, 2, 2)
# done; final state is (2, 4, 4)

state = None
state = next_state(state, 4, 2)
state = next_state(state, 3, 0)  # not sure if this call is actually made
state = next_state(state, 2, 1)
# done; final state is (2, 4, 4)

# etc. …

The code's a bit hard to follow, but I think you could do something like this:

# <omitted>

UPDATE: Nope. I got the execution order wrong. I'll have to go back and think about how one might implement something like this.

Apologies if you already have something that performs that function and I missed it.

(By the way, I acknowledge that there are likely more efficient ways to perform something like "keep highest". I'm using it in this example because it's a useful vehicle for conveying the short circuit functionality I'm proposing.)

[HighDiceRoller]

Thanks for the suggestion! I've split it off to #81.

[HighDiceRoller]

I've uploaded the revised version of the paper, merged THANKS.md into README.md, and added a mention of dyce in it. Let me know whether this meets your approval.

[posita]

I've uploaded the revised version of the paper, merged THANKS.md into README.md, and added a mention of dyce in it. Let me know whether this meets your approval.

Love it! Thank you! ❤️

[bszonye]

Oh hi there! I mentioned in posita/dyce#10 that we'd strayed off topic from Lea. Perhaps this would be a good place to continue that conversation?

Last night I had the inspiration for how to improve my NdX drop/keep method. As I mentioned in the other discussion, I had developed a reasonably efficient algorithm for keeping dice at either end of a pool, but keep-middle/slicing had me stumped. I came up with a new approach last night. My insight was that you can enumerate all combinations of the kept dice, and for each such result there's enough information to efficiently count the all of the lower and higher dice.

For example, to find the PMF for 9d6km3 (keep middle 3):

1. First, determine the kept dice. In this example, it's the middle 3d6 out of 9.
2. Enumerate the kept 3d6: (1, 1, 1), (1, 1, 2), (1, 1, 3), ... (5, 6, 6), (6, 6, 6)
3. For each enumerated result, find the constraints for the higher and lower dice. In 9d6km3, there are always three dice <= the lowest kept die and three dice >= the highest kept die. For example, the result (3, 5, 5) has three dice <= 3 and three dice >= 5.
4. It's much easier to count "three dice <= 3" than it is to enumerate them. So, count the lower dice, count the higher dice, count stuff with the multiset permutation function, multiply stuff together.

My first attempt was hilariously bad. I had missed some subtleties around counting the boundary dice. Take the (3, 5, 5) example again. The math for counting the dice < 3 is different from the dropped dice == 3. I got it sorted out tonight, though, and even made it work for non-uniform dice. The new algorithm computes 600d6km1 in five seconds, whereas previously it could only handle about 40d6 in that time. I think the algorithm has polynomial complexity. Usually the bulk of the computation time goes to the enumeration of the NdX kept dice, which I think is is O(XN^something). However, it's also linear in the number of dice dropped at each end, O(H*L), so finding dice in the middle is a lot more expensive than at the ends.

I set up icepool for head-to-head comparison on the same machine. My new algorithm computes 600d6km1 in 5.1s whereas icepool does it in 2.4s with d6.pool(600)[300]. The two algorithms seem to scale similarly, with icepool consistently about twice as fast. That's impressive considering that your Pool class is also more general! I see that it can find arbitrary slices, whereas mine only finds contiguous dice in the results. I suspect that icepool benefits from its much more aggressive memoization.

(As an aside, does the NdXkM notation bother anybody else? It just seems wrong to interrupt the pool-counting bits with the die descriptor. I fooled around a bit with notations like MkNd6 that mimic the MkN shorthand from games like L5R. I really like how that alternative ends with the bit you're actually going to add up, like M-keep-Nd6. However, I couldn't find any other prominent notation system that grouped the dice-counting stuff together, so maybe it's just me?)

[HighDiceRoller]

Indeed, I took a similar approach in one of the early versions of this project, though I didn't get as far as central slicing before I moved away from this approach. In fact, for some problems it ran faster than modern Icepool due to its use of floats and numpy, though ultimately I decided that the exactness and flexibility of the current algorithm were more important.

The new algorithm computes 600d6km1 in five seconds, whereas previously it could only handle about 40d6 in that time. I think the algorithm has polynomial complexity. Usually the bulk of the computation time goes to the enumeration of the NdX kept dice, which I think is is O(XN^something).

The number of multisets of size N with X outcomes is binom(N + X - 1, N) = binom(N + X - 1, X - 1). If either N or X is kept constant, then the number of possibilities indeed grows only polynomially. Unfortunately:

• If both N and X are allowed to increase linearly, the number of possibilities grows exponentially (example proof). So it is not jointly polynomial.
• Even if X is held constant, we have X - 1 in the exponent. While this is technically polynomial, this can result in quite high orders, e.g. using d10s will result in O(N^9) possibilities. D&D-style ability scores and exploding dice (including your example of L5R) can generate even larger effective die sizes.

I suspect that icepool benefits from its much more aggressive memoization.

Memoization is indeed a big part of it. Another advantage Icepool has is that its state space is only the number of possible (partial) sums, rather than the possible number of multisets, which allows Icepool to remain polynomial with reasonable order even with increasing die sizes.

However, I couldn't find any other prominent notation system that grouped the dice-counting stuff together, so maybe it's just me?

My wild guesses:

• Maybe it's because of the sequential physical process of rolling NdX, and then selecting M of them?
• Or maybe it's due to Roll20's dominance of the VTT market?

[bszonye]

The number of multisets of size N with X outcomes is binom(N + X - 1, N) = binom(N + X - 1, X - 1). If either N or X is kept constant, then the number of possibilities indeed grows only polynomially. Unfortunately:

• If both N and X are allowed to increase linearly, the number of possibilities grows exponentially (example proof). So it is not jointly polynomial.
• Even if X is held constant, we have X - 1 in the exponent. While this is technically polynomial, this can result in quite high orders, e.g. using d10s will result in O(N^9) possibilities. D&D-style ability scores and exploding dice (including your example of L5R) can generate even larger effective die sizes.

Ahhh thanks for explaining this. I think you mentioned it in your paper too, but I didn't fully grasp the underlying math until you laid it out like this. My current algorithm iterates over those ((X, N)) = binom(X + N - 1, N) possible multiset combinations, so of course that's going to be a factor in the total number of operations. Now I understand how that leads to O(N^X) complexity when X is constant.

• Maybe it's because of the sequential physical process of rolling NdX, and then selecting M of them?
• Or maybe it's due to Roll20's dominance of the VTT market?

The NdXkM notation dates back to at least 1985, when Unearthed Arcana was first published for AD&D 1E. That book introduced an optional ability score system where you rolled 9d6k3 for your prime ability, down to 3d6k3 for your dump stat. (That's 7 ability scores total, because UA also added Comeliness to the 6 usual abilities.) I don't think UA itself introduced the k3 suffix, but it must have appeared somewhere prominent like Dragon magazine around that time, because we all picked up the notation pretty quickly in the '80s.

I agree that it's probably based on the actual procedure you follow when rolling and filtering dice, and through that lens it definitely makes sense for the filters to appear after the roll. I suppose you could make things more consistent by putting the die size first such that XdNkM means "roll X-sided dice in a pool of N, keeping M dice," but NdX is way too entrenched to change that part of the notation.

[bszonye]

I've been thinking a lot about how your algorithm works with mixed die sizes like in (2d6+2d8)kh2, where you can optimize mixed pools as long as all of the dice have a common subset anchored at one end of the range: 1..6, 1..8, 1..20, et cetera. That reminds me a lot of your optimization for selecting the highest/lowest dice. It's relatively easy to drop dice from one end of a pool, much harder to drop arbitrary dice. However, you've figured out a fast general solution via the count-list, dropping dice when the count-list is zero at either end.

I wonder if it's possible to generalize mixed pools in the same way? Instead of always popping outcomes from highest to lowest, perhaps it's possible to alternately pop from either end? It might lead to a more general optimization that doesn't require all of the dice to be aligned at one end.

[HighDiceRoller]

The NdXkM notation dates back to at least 1985...

Ah, I did not know that. My personal experience only dates back to the turn of the millennium, so I only know bits and pieces of the formative material. Thanks!

It's relatively easy to drop dice from one end of a pool, much harder to drop arbitrary dice. However, you've figured out a fast general solution via the count-list, dropping dice when the count-list is zero at either end.

To be fair, we only get to "fully" skip the zeros at one end of the count-list. We still have to go through the zeros on the other end explicitly, which does generate more intermediate pools. What the zeros on the non-skipped end do accomplish is halting the growth of the state space, so it does tend to be cheaper than keeping those dice, if not quite as cheap as a full skip.

Instead of always popping outcomes from highest to lowest, perhaps it's possible to alternately pop from either end?

We're on the same wavelength---I've considered this before; for example, it would lead to an efficient solution to this MathExchange question. Unfortunately, there are several issues that have kept me from seriously pursuing this so far:

• The gains in the MathExchange example don't generalize well. With the two classes of players, you can shave off the top and bottom "overhangs" and then everything left is homogeneous. However, with three classes, after shaving the top and bottom you're not getting any benefit from the choice.
• As you allude to, it's not possible to pop from the center and still make use of the count-list feature. So this reduces the number of possible pop choices at each step.
• At the same time, more choices can be bad in its own way---it can increase the number of intermediate pools, which hurts memoization.
• Monotonic iteration order is convenient for some evaluators, such as finding straights.

[bszonye]

I think I've found the first use of the "keep" notation: What are the Odds? Unearthed Arcana's “Method V” analyzed by Arthur J. Hedge III in Dragon #117 (January 1986).

When a number between 3 and 18 is generated using nine six-sided dice, I suggest using the notation “9d6s3” instead of “9d6.” The first digit represents the number of dice to be rolled, the second digit represents the type of die to be used, and the third digit represents the number of dice to be added together by selecting the highest rolled numbers.

Note that he actually suggests an s instead of a k!

[bszonye]

I'm tempted to experiment with PMFs implemented as multisets and subtyped from Set instead of Mapping. The Mapping API has a bunch of annoying quirks that get in the way when you want to use the keys as "values" and the values as weights, starting with the fact that Mapping is covariant in the value type but not the key type. I'm mostly hesitant because the Set API has its own quirks, and I'm not sure that they're any better.

[HighDiceRoller]

Now that's an angle I haven't considered before. A multiset would be quite natural for decks, since in that case each card is unambiguously a discrete element. For dice there is some equivocation between discrete physical faces, counting events, and abstract units of probability.

The big problem I see is iteration. If the multiset emits the same element multiple times to account for its quantity, then large denominators become completely intractable. If it only emits unique elements, then it's not "really" a multiset.

A lesser wrinkle: The Set interface implies (?) that these should be subset relations; on the other hand, if someone types d6 < d6 the natural interpretation is "will the first d6 will roll lower than the second?" One could support both at the same time using something similar to my implementation of == where the result of the comparator is a PMF that also has a truth value via __bool__, though this is a bit of a hack.

Other options I've been mulling over:

• Give up and just use Generic[T_co].
• Make __getitem__ and get accept Any, make the PMF a covariant Mapping, tell mypy to ignore the incompatibility in variance, and hope it doesn't cause mypy to choke.

[bszonye]

I tried out the multiset approach, and I think it has promise for representing sample space (outcomes) but not event space or probability functions.

As you noticed, the Set API has some semantics that map awkwardly to probability concepts. I looked closely at the spec and the stdlib implementation for the abstract Set class, and I concluded that an idiomatic multiset implementation would need __iter__ and __len__ to reflect element multiplicity (just like Counter.elements and Counter.total do). The ABC relational operators rely on it:

    def __lt__(self, other):
        if not isinstance(other, Set):
            return NotImplemented
        return len(self) < len(other) and self.__le__(other)

I think that works OK for things like cards in a deck or faces on a die, especially quirky dice with repeated numbers or symbols. (Small World, War of the Ring, and Star Wars RPG all come to mind.) I think the relational operators might even be handy for testing whether one sample space is a proper subset of another, like when setting up heterogeneous dice pools.

However, I don't think multisets have the right semantics for events or probability functions. Clearly they don't work for conventional probabilities (real numbers in the [0, 1] interval). I had the intuition that they might work for the kind of integer weights that we're all using under the hood, because those superficially resemble a multiset. However, those integers represent the numerator of a fraction, not the multiplicity of a multiset element, and that's an important semantic distinction. For one thing, the multiset iteration semantics just don't make sense theoretically or practically for a PMF, as you pointed out.

I still don't like the Mapping API for PMFs though, so I've been switching my code over to use Collection as the ABC instead. I'm tempted to use Sequence, because it makes a lot of sense for sample spaces and event spaces with an obvious total ordering (like most dice and cards). However, I have a bad habit of overengineering stuff, so I'm going to postpone that decision until later. The Collection API seems sufficient for now, plus the internal Mapping object provides stable ordering anyway.

One thing I have decided is that I'm going to reserve the __getitem__ API for that potential Sequence implementation. I'm moving the probability lookup over to the __call__ API instead because it's a probability mass function, and using the indexing operator for that always kinda bugged me. 😹 I haven't decided yet whether pmf(event) should return a probability (Fraction) or a weight (int). Currently I have the callable interface returning a Fraction and a separate PMF.weight method returning the int numerator.

[HighDiceRoller]

I've come up with a compromise on the Mapping side, which is to inherit from Generic[T_co], Mapping[Any, int]. This makes it both covariant and a Mapping, though not a covariant Mapping. I'll be curious to see what you end up with.

Small World, War of the Ring, and Star Wars RPG all come to mind.

For "symbol" based dice, one approach I've used is to make the outcomes tuples (which Icepool treats as vectors, i.e. most operators are performed elementwise) with one element per symbol type. Then the @ operator will give the total number of each symbol rolled. For example, here's a notebook regarding the Household RPG.

Edit: Though it looks like they ended up going back to the older Broken Compass mechanic in the latest Quickstart.

[bszonye]

I just learned that covariant types can't be parameters. I missed that the other day because I named my event TypeVar ET_co but forgot to actually make it covariant. 🤦‍♀️ I guess I will need my lookup methods to accept Any instead of restricting them to the event type. Not a huge problem because only the correct type can get into the PMF in the first place, but it does limit the possible static type checking.

[bszonye]

My project is currently in limbo while I try to settle a name dispute. I went to release an alpha version about a month ago & found that somebody was squatting on the bones name at PyPI. There's a matching repository on Github, but it looks like they never actually published any code to PyPI. Last activity on either was 2016, so I thought the author might be willing to cede the name & I reached out per the PEP 541 process. They left me hanging for five weeks before flatly refusing this morning.

Unfortunately, that completely blocks the PEP 541 process for abandoned projects. I might still be able to claim ownership if PyPI determines that the project is invalid because it's "name squatting (package has no functionality or is empty)." I guess I'll wait out the rest of the six-week notice period to see if the current owners actually bother to upload a package. If not, I might file an official PEP 541 request to declare the project invalid and transfer ownership to me.

In the meantime, I need to start thinking of alternate names. I've found a few possibilities that are still available, but nothing that I like quite as much as bones. Plus it's just a hassle to change all of the code & docs.

[posita]

Gah! bones would have been pretty good. How about dembones or clickclack? Maybe you could get hold of snakeeyes? Or maybe snekeyes? What about pips or pypips? Do any craps terms grab you (e.g., hardway, boxcars, etc.)? Is there a part of a skeleton that is unique to Pythons that has a cool name?

[bszonye]

Haha, you've hit on some of the same alternates I've checked out; dembones is on my short list along with dsix, oddly, and otter.

That's clever thinking about names that are both snake- and game-related. I originally picked bones partly because skulls are such a big thing in Warhammer, and a different Warhammer reference might work (e.g. dsix). Alternately, I might go in a more general direction so that deck & bag support don't feel tacked-on when I eventually get around to them (e.g. oddly). Hm, actually I quite like that last one, except that I'm tired of the fad of naming apps "whatever.ly," haha.

[bszonye]

I opened an issue with some of the leading suggestions: bszonye/ossuary#5

Thanks for the brainstorming assist. Please feel free to add more to the issue. So far, pippin and oddly are my two favorites. Gonna sleep on it before making any decisions, as renaming everything is going to be kind of a hassle, and I don't want to need to do it again, haha.

[bszonye]

I went to the trouble of changing everything from bones to oddly, tested on test.pypi.org, merged the change, and then pypi main rejected the name anyway. Getting pretty frustrated with this. Guess I'll try pippin next?

[bszonye]

Thanks to my wife's Medieval French degree, my toolkit now has a home on PyPI: https://pypi.org/project/ossuary/