HighDiceRoller/icepool

Simplify `estimate_order_costs`

Closed this issue · 2 comments

This would look like having a priority of concerns rather than the full cost estimation as now. Possible ordering:

  1. Evaluator / expression order requirement (mandatory).
  2. More favorable mixed dice order. For the usual right-truncation case, this would favor popping from the top, i.e. ascending / backwards or descending / forwards.
  3. Skips. highest prefers popping from the top (ascending / backwards or descending / forwards), and lowest from the bottom (descending / backwards or ascending / forwards). (Should skips be added for decks?)
  4. Ascending / backwards if there are no other preferences.

For anything beyond constant factors I would tend to prioritize single-query performance over caching. So pool.lowest() might lose some cache hits when used with both mixed and homogeneous pools.

In a quick test:

from icepool import MultisetEvaluator, d4, d6, d8, d10, d12, Pool, Order
import cProfile

class TestSumEvaluator(MultisetEvaluator):
    def __init__(self, order):
        self._order = order

    def next_state(self, state, outcome, a, b):
        if state is None:
            state = 0
        return state + outcome * a + outcome * b

    def order(self):
        return self._order

evaluator_a = TestSumEvaluator(Order.Ascending)
evaluator_b = TestSumEvaluator(Order.Descending)
mixed_pool = Pool([d6, d8, d10, d12])

cProfile.run('evaluator_a(mixed_pool, mixed_pool)')
cProfile.run('evaluator_b(mixed_pool, mixed_pool)')

The backwards evaluation resulted in

69975 function calls (65244 primitive calls) in 0.024 seconds

while the forwards evaluation resulted in

722621 function calls (661263 primitive calls) in 0.235 seconds

Possibly the forwards evaluation scales more poorly with state count? In which case using the backwards algorithm would probably be more important than skips. In this case, we would have:

  • If mandatory order, select that one.
  • If dice are mixed and prefer one pop order, use that one even if it causes forwards evaluation due to mandatory order. Otherwise, pop to get backwards evaluation.
  • Otherwise, the dice are all the same. If there is a mandatory order, choose the backwards evaluation.
  • Otherwise, choose pop by which makes better skips.
  • Otherwise, default to ascending / backwards.