Review Theorem I.1 in AC if you don’t remember the basic constructions.
Appendix A.1 and A.4 in AC. This goes over the cycle construction, but leaves
much to the reader. You don’t necessarily need to follow every step, but it
would be good to have an idea of where this is going.
Neil’s expanded write-up
of the cycle construction derivation.
Optionally take a look at the FLINT docs. I plan to
go over the core stuff of interest though.
Agenda:
Review basic definitions of combinatorial classes and fundamental
constructions.
Continue deriving the cycle construction, which we skipped when originally
visiting Theorem I.1. (Neil will be doing this one.)
Last time we left off after deriving Möbius inversion. We’ll do some review
and then continue from there.
Introduce the Thrill Digger challenge!
I’ll introduce the rules of this
mini-game from
Zelda: Skyward Sword. (Background motivation: this game is great for
grinding rupees.)
Exercise: Derive an exact to solution of conditional bomb/rupoor
distributions using classical counting techniques.
Preview: I’ve written a simulator and “solver” for the game. I’m introducing
it now to let people mull it over.
Competition: The goal is to eventually have everyone submit an agent to play
the game “optimally”.
Agents do not necessarily need to be “trained” in any way. After all, a
simple greedy/heuristic algorithm may actually be best!
Lots of ideas for different competition planes: rupees mined per hour,
rate of games “won” (or at least where you come out in the positive),
ultra compute-constrained, etc. I want to spend some time brainstorming
different competition classes.
The idea as of now is to run all these tests in a browser on my computer
to level the playing field. Depending on how people plan to implement
solutions, we might need to reshape the API/execution environment. Since
I’ll be running arbitrarily code, I do want it to be sanboxed…
If time allows, we’ll discuss “real-world” coefficient extraction with the
FLINT numeric library.
Notes:
We spent most of the time reviewing combinatorial classes and the OGF
abstraction since we had some new comers.
Reviewed Möbius inversion (derived last time).
Covered the next bit of cycle construction derivation—bivariate Möbius
inversion.
Introduced Thrill Digger and its basic rules.
Picked on
Thrill Digger Assistant
for getting the bomb/rupoor distribution “close”, but not quite correct. The
author makes an obvious mistake in not weighting the observed microstates
correctly (since it turns out that each visited solution state is actually a
partially-observed macrostate).
Solved a few states by hand and discussed how to implement a “brute force”
solver.
Talked about the agent competition. At “training” time, everybody will have
access to both the simulator and solver. Competition classes we’re considering
at the monent:
Efficient approximations of the exact solution function. (Computing the
exact solution is exponential in the size of the fringe of exposed cells,
even with heavy pruning.) This is the only non-agent competition class—the
goal is strict function approximation.
Maximize rupees mined per hour. We’ll need to come up with a “realistic”
cost function that accounts for how long it takes a real person to enter the
state into a solver app, run the solver, and then take the suggested
actions. Depending on the exact parameters, we might simplify this by just
seeking to maximize rupees earned per game.
Minimize the probability of going broke (given some number of
starting rupees). It’s quite painful to boostrap a big enough cash reserve
to start playing once you lose all rupees, so this is a scenario best
avoided in the first place. Alternatively: minimize the probability of not
breaking even in a single game instance.
Maximize rupees per hour in a “resource constrained” environment. We didn’t
discuss exactly what this would look like, but it could include strict
memory/latency bounds (per action, game, etc).