Open HighDiceRoller opened 2 years ago
Great suggestion!
I'm not sure I understand this interface, but the intention is to get larger outcomes before smaller ones
That's correct, this controls whether the outcomes are seen in ascending order (1
), descending order (-1
), or it doesn't matter to the evaluator (0
). The 0
case has some extra room for optimization by dynamically choosing which side to pop from at each step, but I haven't gotten around to trying this out and thinking about the cache behavior.
Maybe I should use the word order
instead?
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".
At current I don't have a general-purpose short-circuit, though the thought has at least crossed my mind.
Currently there are two specific short-circuit mechanisms:
First, when next_state()
returns the special value icepool.Reroll
, that state / branch is immediately dropped from the computation. Though unlike the proposed short-circuit, this doesn't produce an outcome for that branch.
Second, the sorted_roll_counts
mechanism (currently called the count-list in the paper) does implement the short-circuit; when it sees that all of the remaining dice are counted zero times, it immediately dumps all the remaining dice in the pool in exchange for the remaining denominator, since these dice will not be visible to next_state
no matter what happens.
This is done on the pool side rather than the evaluator side; while not a general short-circuit mechanism, this does have some advantages of its own:
sorted_roll_counts
can be composed with any evaluator with no modification of the evaluator necessary.The explicit pool syntax would be
icepool.d4.pool(4)[-3:]
# or
icepool.d4.pool(4)[0, 1, 1, 1]
# or
icepool.d4.pool(4)[..., 1, 1, 1]
(Un?)fortunately, this does steal a good deal of the thunder of the general case. Though there are some cases that don't fall under this, e.g. Neon City Overdrive. The potential benefits seem to come in two aspects:
next_state
. This will have to be weighed versus adding the extra bit of complexity to the API.next_state
or would it be able to eliminate big parts of the computation?
- Performance. I haven't conclusively determined how much a general short-circuit mechanism would save; would it only save a few calls to
next_state
or would it be able to eliminate big parts of the computation?
This is probably the most significant factor. It very well could be that so few cases benefit from the complexity (and possible overhead, depending on implementation) of a short circuit like the one I propose that they deserve explicit specialization (e.g., Die.keep_highest
).
Regarding the use of exceptions to signal the shortcut case: I like that approach, although I think it a small tweak would make it more pythonic. The example code uses an exception as a sort of "long-distance return" statement, both signaling the end of iteration and returning the final value in the exception arguments. Contrast that with the Python generator protocol, which returns the final iteration on one pass and then raises StopIteration
to signal that you're past the end.
Here's an alternate example using that protocol:
def next_state(self, state, outcome, count):
if state is None:
state = ()
if len(state) >= self._num_highest:
raise StopIteration
return (outcome,) * count + state
This approach has advantages and disadvantages. On the negative side, it means that you get an extra level of fan-out in the traversal, because you'll be signaling one past the end, instead of signaling at the end. On the other hand, this iteration protocol is so common in Python that it may be the cleanest way to implement shortcuts, especially for cases that have an underlying generator, iterator, or sequence, because those are all cases that naturally lend themselves to a terminal StopIteration or IndexError at the one-past-end point.
Originally posted by @posita in https://github.com/HighDiceRoller/icepool/discussions/26#discussioncomment-3335032