Optimal decision in games with many (time)steps

[void4]

(How) is it possible to optimize problems like these: https://qewasd.com (https://github.com/void4/qewasd)?

https://www.reddit.com/r/CasualMath/comments/hvuw4w/optimal_cookie_clicker_strategies/

The most generalized case seems to mirror

• https://en.m.wikipedia.org/wiki/Busy_beaver
• https://en.wikipedia.org/wiki/Halting_problem
• https://en.wikipedia.org/wiki/Rice%27s_theorem
• https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

especially if there is some asymmetry involved (for example, when selling an item doesn't return the exact purchase price).

https://en.wikipedia.org/wiki/Operations_research, https://en.wikipedia.org/wiki/Job_shop_scheduling and https://www.itc2019.org/test-instances

This also has implications on real world financial decisions, since returns, depreciation or risks may compound over time.

Curiously, this seems to correspond to the impossibility of orbit/trajectory calculation https://en.wikipedia.org/wiki/Three-body_problem, https://en.wikipedia.org/wiki/Lyapunov_exponent which quickly gets into https://en.wikipedia.org/wiki/Chaos_theory territory.

Which systems have analytical solutions and which do not? What properties do (discrete) systems need to have in order to be at least computationally/brute-force optimizable?

Solution approaches:

• https://en.wikipedia.org/wiki/Brute-force_search
• https://en.wikipedia.org/wiki/Backtracking
• https://en.wikipedia.org/wiki/Dynamic_programming
• https://en.wikipedia.org/wiki/Integer_programming (how to represent the causal dependencies here is unclear to me)

Even more links:

https://en.wikipedia.org/wiki/Configuration_space_(physics)

https://en.wikipedia.org/wiki/Phase_space