Module:Grind/opt

From Fallen London Wiki

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