Module:Grind/opt
From Fallen London Wiki (Staging)
Documentation for this module may be created at Module:Grind/opt/doc
local p = {}
local util = require('Module:Grind/util')
local dist = require('Module:Grind/dist')
local GRON = require('Module:Grind/GRON')
local fml = require('Module:Grind/fml')
-- == GRON optimisation utilities ==
-- Evaluates a single challenge.
-- `quality` is the challenge quality name.
-- `level` is the challenge level. For Luck, it is the success probability in %.
-- `broad` is the boolean flag of whether the challenge is broad.
-- `step` is the narrow difficulty step.
-- `data` is a table containing player stats/items.
-- Success probability is returned ([0; 1]).
local function eval_challenge(quality, level, broad, step, data)
if quality == 'Luck' then
return level / 100
end
local actual_level = data[quality] or 0
if broad then
if level == 0 then
return 1
end
return math.min(1, 0.6 * actual_level / level)
else
return math.max(math.abs(step), math.min(1, 0.5 + (actual_level - level) * step))
end
end
-- Evaluates a challenge consisting of a number of stat challenges.
-- `challenge` is a table containing challenge information.
-- Its keys are challenge quality names.
-- The corresponding value is either:
-- * Challenge level
-- * A table of:
-- ** Challenge level
-- ** `broad`/`narrow` string
-- ** Narrow difficulty step in % (optional).
-- `data` is a table containing player stats/items.
-- Success probability is returned ([0; 1]).
local function eval_full_challenge(challenge, data)
local prob = 1
for quality, info in pairs(challenge) do
local level, ctype, step
if type(info) == 'string' or type(info) == 'number' then
level, ctype, step = tonumber(info), 'broad', nil
else
level, ctype, step = tonumber(info[1]), info[2], tonumber(info[3])
step = (step or 10) / 100
end
prob = prob * eval_challenge(quality, level, ctype == 'broad', step, data)
end
return prob
end
-- Converts the specified value or formula into a distribution table.
-- A formula is: (formula; <FORMULA>)
local function interpret_dist(gron, data)
if type(gron) == 'string' or type(gron) == 'number' then
if tonumber(gron) ~= nil then
return {[tonumber(gron)] = 1}
end
return nil, 'Cannot parse number: ' .. gron
elseif type(gron) == 'table' and gron[1] == 'formula' then
local s = gron[2]
if type(s) ~= 'string' then
return nil, 'Malformed formula'
end
local tree, err = fml.parse(s)
if err then
return nil, 'Error parsing formula (' .. s .. '): ' .. err
end
tree = fml.eval(tree, data)
if tree[2] ~= 'dist' then
err = fml.find_error(tree)
if err then
return nil, 'Error evaluating formula: ' .. err
else
return nil, 'Error evaluating formula ' .. s
end
end
return tree[1]
elseif type(gron) == 'table' and gron[1] == 'err' then
return nil, gron[2]
elseif type(gron) == 'table' then
return nil, 'Invalid value: ' .. GRON.encode(gron)
end
return nil, 'Invalid value: ' .. gron
end
-- Removes menaces from the effect, estimates action cost of subsequent recovery.
local function process_antiresources(effect, menaces)
local new_effect = {}
local a_extra = 0
for resource, d in pairs(effect) do
if menaces[resource] == nil then
new_effect[resource] = d
else
local a_cost = menaces[resource]
a_extra = a_extra + a_cost * dist.expected_value(d)
end
end
return new_effect, a_extra
end
-- Optimises GRON.
-- Returns:
-- * expected effect (as a distribution)
-- * optimal GRON
-- * boolean error flag
function p.optimise(gron, resource, data, menaces, optimisation_target)
local function err(text)
return util.complete_effect(0, {}), {'error', text}, true
end
local function eval_optimisation_target(effect, resource, optimisation_target)
local r = effect.effect[r] or 0
local rpa = dist.resource_per_action(effect, resource)
if optimisation_target == 'rpa' then
return rpa
elseif optimisation_target == 'r' then
return r
end
end
local gtype = gron[1]
if gtype == 'error' then
return util.complete_effect(0, {}), gron, true
end
if gtype == 'input' then
return err('Input not provided: ' .. tostring(gron[2]))
end
if gtype == 'nop' then
return util.complete_effect(0, {}), gron, false
end
if gtype == 'action' then
local challenge = gron['challenge']
local a = gron['a'] or 1
local success = gron['success'] or {}
local failure = gron['failure'] or {}
local alt_success_p = gron['alt_success_p'] or '0'
local alt_success = gron['alt_success'] or {}
local alt_failure_p = gron['alt_failure_p'] or '0'
local alt_failure = gron['alt_failure'] or {}
local optimal_gron = {
'action',
title=gron['title'],
link=gron['link'],
challenge=challenge,
a=gron['a'],
comment=gron['comment'],
success=gron['success'],
failure=gron['failure'],
alt_success=gron['alt_success'],
alt_failure=gron['alt_failure'],
alt_success_p=gron['alt_success_p'],
alt_failure_p=gron['alt_failure_p']
}
local e
local success_dist, success_a_extra = {}, 0
for resource, dist in pairs(success) do
success_dist[resource], e = interpret_dist(dist, data)
if e ~= nil then
return err(e)
end
end
success_dist, success_a_extra = process_antiresources(success_dist, menaces)
local failure_dist, failure_a_extra = {}, 0
for resource, dist in pairs(failure) do
failure_dist[resource], e = interpret_dist(dist, data)
if e ~= nil then
return err(e)
end
end
failure_dist, failure_a_extra = process_antiresources(failure_dist, menaces)
local alt_success_dist, alt_success_a_extra = {}, 0
for resource, dist in pairs(alt_success) do
alt_success_dist[resource], e = interpret_dist(dist, data)
if e ~= nil then
return err(e)
end
end
alt_success_dist, alt_success_a_extra = process_antiresources(alt_success_dist, menaces)
local alt_failure_dist, alt_failure_a_extra = {}, 0
for resource, dist in pairs(alt_failure) do
alt_failure_dist[resource], e = interpret_dist(dist, data)
if e ~= nil then
return err(e)
end
end
alt_failure_dist, alt_failure_a_extra = process_antiresources(alt_failure_dist, menaces)
local p_alt_s = tonumber(alt_success_p)
local p_alt_f = tonumber(alt_failure_p)
if p_alt_s == nil then
return err('(action): invalid alt_success_p')
end
if p_alt_s < 0 or p_alt_s > 100 then
return err('(action): alt_success_p should be in the 0-100 range, got ' .. p_alt_s)
end
if p_alt_f == nil then
return err('(action): invalid alt_failure_p')
end
if p_alt_f < 0 or p_alt_f > 100 then
return err('(action): alt_failure_p should be in the 0-100 range, got ' .. p_alt_f)
end
p_alt_s = p_alt_s / 100
p_alt_f = p_alt_f / 100
local prob = 1
if challenge ~= nil then
for q, q_data in pairs(challenge) do
if type(q_data) == 'table' and q_data[1] == 'formula' then
-- the formula was not evaluated; it contains a distribution
return err('(action): ' .. tostring(q) .. ' challenge contains a distribution')
end
end
prob = eval_full_challenge(challenge, data)
if prob == nil then
return err('(action): invalid challenge: ' .. GRON.encode(challenge))
end
end
local a_extra =
success_a_extra * prob * (1 - p_alt_s) +
alt_success_a_extra * prob * p_alt_s +
failure_a_extra * (1 - prob) * (1 - p_alt_f) +
alt_failure_a_extra * (1 - prob) * p_alt_f
local effect = dist.effect_sum_p(
dist.effect_sum_p(
dist.effect_mul_p(success_dist, prob * (1 - p_alt_s)),
dist.effect_mul_p(alt_success_dist, prob * p_alt_s)
),
dist.effect_sum_p(
dist.effect_mul_p(failure_dist, (1 - prob) * (1 - p_alt_f)),
dist.effect_mul_p(alt_failure_dist, (1 - prob) * p_alt_f)
)
)
optimal_gron['p'] = prob
local expected = dist.expected_effect(effect)
optimal_gron['expected'] = expected
optimal_gron['a_expected'] = a + a_extra
return util.complete_effect(a + a_extra, effect), optimal_gron, false
end
if gtype == 'seq' then
local optimal_gron = {'seq'}
local effect = {}
local a = 0
local e = false
for i = 2, #gron do
local effect_i, gron_i, e_i = p.optimise(gron[i], resource, data, menaces, optimisation_target)
effect = dist.effect_sum(effect, effect_i.effect)
a = a + effect_i.a
e = e or e_i
if type(gron_i) ~= 'table' or gron_i[1] ~= 'seq' then
table.insert(optimal_gron, gron_i)
else
for j = 2, #gron_i do
table.insert(optimal_gron, gron_i[j])
end
end
end
return util.complete_effect(a, effect), optimal_gron, e
end
if gtype == 'airs' then
local range = gron['range'] or '1-100'
local ranges = gron['ranges']
if type(ranges) ~= 'table' then
return err('(airs): invalid or missing ranges')
end
if #ranges ~= #gron - 1 then
return err('(airs): number of ranges not equal to the number of branches')
end
local rmin, rmax = util.parse_range(range)
if rmin == nil or rmax == nil then
return err('(airs): invalid range: ' .. range)
end
local optimal_gron = {'airs', range=range, ranges={}, target=gron['target']}
local effect = {}
local a = 0
local e = false
local last_item = nil
local last_range = nil
local all_equal = true
for i = 2, #gron do
local effect_i, gron_i, e_i = p.optimise(gron[i], resource, data, menaces, optimisation_target)
local range_i = ranges[i - 1]
e = e or e_i
local rmin_i, rmax_i = util.parse_range(range_i)
if rmin_i == nil or rmax_i == nil then
return err('(airs): invalid ranges[' .. (i - 1) .. ']: ' .. range_i)
end
local prob = (rmax_i - rmin_i + 1) / (rmax - rmin + 1)
effect = dist.effect_sum_p(effect, dist.effect_mul_p(effect_i.effect, prob))
a = a + effect_i.a * prob
if util.tables_equal(last_item, gron_i) then
-- merge ranges instead of adding a new branch, if possible
local last_min, last_max = util.parse_range(last_range)
if last_max + 1 == rmin_i then
if rmax_i ~= rmax_i + 1 then
range_i = last_min .. '-' .. rmax_i
else
range_i = last_min .. '-'
end
optimal_gron['ranges'][#(optimal_gron['ranges'])] = range_i
else
table.insert(optimal_gron, gron_i)
table.insert(optimal_gron['ranges'], range_i)
end
else
table.insert(optimal_gron, gron_i)
table.insert(optimal_gron['ranges'], range_i)
end
if all_equal and last_item ~= nil then
all_equal = util.tables_equal(last_item, gron_i)
end
last_item = gron_i
last_range = range_i
end
if last_item ~= nil and all_equal then
return util.complete_effect(a, effect), last_item, e
end
return util.complete_effect(a, effect), optimal_gron, e
end
if gtype == 'pswitch' then
local target = gron['target']
local ranges = gron['ranges']
local action = gron['action']
local optimal_gron = {'pswitch', target=target}
local effect_a, gron_a, e_a = p.optimise(action, target, data, menaces, 'r')
optimal_gron['action'] = gron_a
optimal_gron['ranges'] = {}
optimal_gron['p'] = {}
local effect = {}
local a = 0
local e = e_a
local total_p = 0
for i = 2, #gron do
local effect_i, gron_i, e_i = p.optimise(gron[i], resource, data, menaces, optimisation_target)
local range_i = ranges[i - 1]
local _rmin_i, _rmax_i = util.parse_range(range_i)
if _rmin_i == nil or _rmax_i == nil then
return err('(pswitch): invalid ranges[' .. (i - 1) .. ']: ' .. range_i)
end
local prob = dist.range_prob(effect_a.effect[target], range_i)
if prob > 0 then
e = e or e_i
table.insert(optimal_gron, gron_i)
table.insert(optimal_gron['ranges'], range_i)
table.insert(optimal_gron['p'], prob)
effect = dist.effect_sum_p(effect, dist.effect_mul_p(effect_i.effect, prob))
a = a + effect_i.a * prob
total_p = total_p + prob
end
end
for a_resource, a_dist in pairs(effect_a.effect) do
if a_resource ~= target then
effect = dist.effect_sum(
effect,
{[a_resource]=a_dist}
)
end
end
a = a / total_p
return util.complete_effect(a, effect), optimal_gron, e
end
if gtype == 'best' then
local optimal_gron = {'nop', avoid='yes'}
local effect = {}
local best_opt_data = -1 / 0
local best_a = 1 / 0
local e = false
for i = 2, #gron do
local effect_i, gron_i, e_i = p.optimise(gron[i], resource, data, menaces, optimisation_target)
local expected_i = dist.expected_effect(effect_i.effect)
local a = effect_i.a
local opt_data = eval_optimisation_target(
util.complete_effect(a, expected_i),
resource,
optimisation_target
)
if gron_i[1] ~= 'nop' or not util.s2b(gron_i['avoid'], false) then
if opt_data > best_opt_data or (opt_data == best_opt_data and a < best_a) then
e = e_i
effect = effect_i
optimal_gron = gron_i
best_opt_data = opt_data
best_a = a
end
end
end
return effect, optimal_gron, e
end
if gtype == 'gate' then
local target = gron['target']
if type(target) ~= 'table' then
return err('(gate): target undefined or invalid')
end
local action = gron['action']
if type(action) ~= 'table' then
return err('(gate): action undefined or invalid')
end
local resolution = gron['resolution']
local reset = gron['reset']
local must_succeed = gron['must_succeed']
local failure_cost = gron['failure_cost']
local preserve_progress = gron['preserve_progress']
local optimise = gron['optimise']
local g_a = 0
local effect_r = { a=0, effect={} }
local gron_r = nil
local e_r = false
if resolution ~= nil then
effect_r, gron_r, e_r = p.optimise(resolution, resource, data, menaces, optimisation_target)
g_a = effect_r.a
end
local g_resource, g_level = target[1], target[2]
if g_resource == nil or g_level == nil then
return err('(gate): target invalid')
end
-- g_level might be a distribution
local g_level_dist, g_level_e = interpret_dist(g_level, data)
if g_level_e then
return err('(gate): target level invalid: ' .. g_level_e)
end
g_level = dist.expected_value(g_level_dist)
-- failure_cost might be a distribution
local f_cost = 0
if failure_cost then
local f_cost_dist, f_cost_e = interpret_dist(failure_cost, data)
if f_cost_e then
return err('(gate): failure_cost invalid: ' .. f_cost_e)
end
f_cost = dist.expected_value(f_cost_dist)
end
local effective_g_resource = g_resource
local effective_opt_target = 'rpa'
if not util.s2b(optimise, true) then
effective_g_resource = resource
effective_opt_target = optimisation_target
end
local effect_a, gron_a, e_a = p.optimise(
action, effective_g_resource, data, menaces, effective_opt_target
)
local expected_a = dist.expected_effect(effect_a.effect)
local rpa = dist.resource_per_action(util.complete_effect(effect_a.a, expected_a), g_resource)
local r_needed = g_level
local attempts = 1
if util.s2b(must_succeed) then
local prob = 1
if type(gron_r) == 'table' and gron_r[1] == 'action' then
prob = gron_r['p'] or 1
end
attempts = 1 / prob
r_needed = g_level - f_cost + attempts * f_cost
end
local times_a
if effect_a.a ~= 1/0 and rpa >= 0 then
times_a = r_needed / (rpa * effect_a.a)
else
times_a = 1/0
end
if util.s2b(reset) then
times_a = math.ceil(times_a)
end
local a
if times_a ~= 1/0 then
a = g_a * attempts + times_a * effect_a.a
else
a = 1/0
end
local optimal_gron = {
'gate',
target=target,
action=gron_a,
resolution=gron_r,
reset=reset,
must_succeed=must_succeed,
failure_cost=failure_cost,
preserve_progress=preserve_progress,
optimise=optimise,
times=times_a,
attempts=attempts
}
local effect = dist.effect_mul(effect_r.effect, attempts)
local preserve_progress = util.s2b(preserve_progress, false)
for a_resource, a_dist in pairs(effect_a.effect) do
if (a_resource ~= g_resource or preserve_progress) and times_a ~= times_a + 1 then
local e = {[a_resource]=a_dist}
effect = dist.effect_sum(
effect,
dist.effect_mul(e, times_a)
)
end
end
return util.complete_effect(a, effect), optimal_gron, e_a or e_r
end
if gtype == 'filter' then
local target = gron['target'] or {}
if type(target) == 'string' then
target = {target}
end
if type(target) ~= 'table' then
return err('(filter).target invalid or undefined')
end
local action = gron[2]
if type(action) ~= 'table' then
return err('(filter)[2] invalid or undefined')
end
local target_set = {}
for _, target_resource in ipairs(target) do
target_set[target_resource] = true
end
local effect_a, gron_a, e_a = p.optimise(
action,
resource,
data,
menaces,
optimisation_target
)
for a_resource, a_dist in pairs(effect_a.effect) do
if target_set[a_resource] == nil then
effect_a.effect[a_resource] = nil
end
end
return effect_a, gron_a, e_a
end
if gtype == 'sell' then
local action = gron['action']
local optimise = gron['optimise']
local optimal_gron = {'sell', optimise=optimise, market=gron['market']}
-- TODO: filter possible sell options based on action outputs?
for sell_resource, sell_effect in pairs(gron) do
if type(sell_resource) == 'string'
and sell_resource ~= 'action'
and sell_resource ~= 'market'
and sell_resource ~= 'optimise' then
optimal_gron[sell_resource] = sell_effect
end
end
local function sell_optimising_for(a_resource_s)
local effect_a, gron_a, e_a = p.optimise(
action,
a_resource_s,
data,
menaces,
optimisation_target
)
local a = effect_a.a
local effect = {}
for a_resource, a_dist in pairs(effect_a.effect) do
if type(a_resource) ~= 'string'
or a_resource == 'market'
or a_resource == 'action'
or a_resource == 'optimise' then
-- do nothing
elseif type(gron[a_resource]) == 'table' then
for r, delta in pairs(gron[a_resource]) do
-- TODO: support distributions for `delta`
if tonumber(delta) == nil then
return err(
'(sell) effect for '
.. tostring(a_resource)
.. ' contains resource '
.. tostring(r)
.. ' with non-number delta '
.. tostring(delta)
)
end
delta = tonumber(delta)
effect = dist.effect_sum(
effect,
dist.effect_mul(
{[r]=a_dist},
delta
)
)
end
else
effect[a_resource] = a_dist
end
end
return util.complete_effect(a, effect), gron_a, e_a
end
if type(optimise) ~= 'string' then
local effect_a, gron_a, e_a = sell_optimising_for(resource)
optimal_gron['action'] = gron_a
return effect_a, optimal_gron, e_a
else
local best_effect_a, best_gron_a, best_e_a = sell_optimising_for(resource)
local best_opt_data = eval_optimisation_target(
best_effect_a,
optimise,
optimisation_target
)
local best_a = best_effect_a.a
for sell_resource, _ in pairs(gron) do
if sell_resource ~= 'action' and sell_resource ~= 'market' and sell_resource ~= 'optimise' then
local effect_a, gron_a, e_a = sell_optimising_for(sell_resource)
local opt_data = eval_optimisation_target(
effect_a,
optimise,
optimisation_target
)
local a = effect_a.a
if gron_a[1] ~= 'nop' or not util.s2b(gron_a['avoid'], false) then
if opt_data > best_opt_data or (opt_data == best_opt_data and a < best_a) then
best_e_a = e_a
best_effect_a = effect_a
best_gron_a = gron_a
best_opt_data = opt_data
best_a = a
end
end
end
end
optimal_gron['action'] = best_gron_a
return best_effect_a, optimal_gron, best_e_a
end
end
if gtype == nil then
return err('GRON object of unspecified type: ' .. GRON.encode(gron))
end
return err('Unknown GRON object of type ' .. gtype .. ': ' .. GRON.encode(gron))
end
return p
