Memoization

[harpy eagle]

I have a question about how the memoization functions work in the game. So suppose I wanted to cache the number of inhabited planets the current empire has this turn, to avoid iterating through empire.planets to count them every time. Would the following work?

Code: Select all

EmpireProperty.inhabited_planet_count = weak_memoize_1_to_n | function(empire)
  local count = 0
  for planet ; empire.planets
    if planet.inhabited
      count += 1
    end
  end
  return count
end

How does the memoizer know when the cache has become stale and the function needs to be called again?

[sven]

I have a question about how the memoization functions work in the game. So suppose I wanted to cache the number of inhabited planets the current empire has this turn, to avoid iterating through empire.planets to count them every time. Would the following work?

Yes, that should work.

How does the memoizer know when the cache has become stale and the function needs to be called again?

SiS runs Lua with the automatic garbage collector turned off -- however, we do a manual garbage collection pass any time either 1) the player completes a strategic action or 2) the game window is resized.

Thus, when you're writing logic for the UI, most of the time you're interacting with variables that can be easily and safely cached inside a function memoization that persists until the next GC pass. That's exactly what all the 'weak_memoize' helper functions do*.

However; context really matters for memorization tricks. If you're planning to use it inside, say, a callback that's processed as part of the 'year end' strategic updates, weak memoization hacks aren't particularly safe**; most important values are likely to change a few times before the 'year end updates' function completes (and thus, the cache may not flush soon enough to ensure that your data is correct).

* editors note: This is technically a lie -- only the weak_memoize_1_to_n and weak_memoizeNN functions are guaranteed to be flushed with a GC pass. The single return value memoizers may not flush if they return tables or functions. Just to avoid confusing myself, I'll often default to using weak_memoizeNN -- even though it's technically very slightly slower than the other options, it saves the headache of worrying about return types.

** editors note(2): I recently got myself into trouble by calling the planet pop_and_habs property inside a year-end mechanic. It's an easy mistake to make.

[sven]

Would the following work?

If you're inside a situation where weak memoization isn't particularly safe you may need to use a different pattern. Because the AI executes inside a "throw away" temporary environment, you can actually use strong memoizers there to store temporaries that will only be valid for the current ai call. See, for example: navy_composition.lua:init_production_desire.ships().

But if you want to write new game mechanics that make use of data memoization, then you may need to write an explicit flush function to manage your memoization caches by hand. Right now, there's only a handful of game mechanics that need to do this; most of them involve food/starvation, and you can see the pattern I use for explicit flushes by skimming farming.lua*.

* editors note(3): The fact that I seem to push so many patches fixing bugs in the starvation mechanic is not unrelated ;(

[harpy eagle]

Ok. I guess my main concern with the memoization functions was how to approach the decision of whether or not the game's memoization mechanisms should be used for a particular computation. I guess memoization should be avoided unless you're absolutely sure that the result of the computation won't change until anyone makes a strategic action. Which is not the case for a lot of stuff during year end processing. But strong memoization is fine for stuff being used by AI code.

Since it sounds like all weak caches get flushed by the GC, what happens if a weakly memoized function returns a table that isn't discarded in time?

[sven]

Since it sounds like all weak caches get flushed by the GC, what happens if a weakly memoized function returns a table that isn't discarded in time?

Well, as long as any reference to the table is still around, it will still exist after the GC call. But (assuming you're using the n-return value memoization helpers), the function that created the table will create a new version of the same table the next time it's called.

[sven]

But strong memoization is fine for stuff being used by AI code.

Yeah. Basically, at the start of an AI function call, you can add anything you like to the _ENV, and be confident that the variables you've created will only exist until the AI call completes. This includes creating new strong_memoized functions, which you'll then be able to call from other AI helpers with confidence that the associated return value caches will only last until the top-level AI call completes (because the functions *themselves* will only last that long).

[harpy eagle]

Well, as long as any reference to the table is still around, it will still exist after the GC call. But (assuming you're using the n-return value memoization helpers), the function that created the table will create a new version of the same table the next time it's called.

Do they check if a table has been cached and only return copies?

[sven]

Do they check if a table has been cached and only return copies?

If you don't hit the cache, you'll rerun the whole function, which will generally create a new table from scratch.
However, if you get a cache hit, the memoizer will return exactly the same table it returned previously. Thus:

Code: Select all

local f = weak_memoizeNN | function(a) return {} end
local t1 = f(1) -- creates a new table for f(1)
t1.bar=2
local t2 = f(1) -- returns the f(1) table created previously
print(t2.bar) --> prints 2

This property of memoization can be used with memorized functions like lazy_word_render() to create additional UI assets for a given resource only as needed. (This is what's going on with the 'if not word.draw_shadow' logic in the example code I gave siyoa.)

It's also a potentially confusing behavior if you're not expecting it though (indeed, you can find epic arguments about the wisdom of this memoization semantic on the lua-users.org mailing list). But basically, given the way I've coded them up, when one of my memoized functions returns a table, it may be best to think of that function as a tool for "fetching a shared resource".

[harpy eagle]

Ok, so putting it all together, does this seem like a good use case for memoization?

I have a custom function to determine the combat value of a ship, and I want to plug it into the ship_power_score() that's used by the strategic AI. However, it requires the ship's design and it's hull specs. Since I figure ship_power_score() gets called a lot, it seems like memoization might be worth it here since getting a proper design from ship.source_design requires cloning the design. What I have looks like this:

Code: Select all

local get_ship_design = weak_memoize_1_to_1 | function(ship)
  return Design.clone(ship.source_design)
end

function ship_power_score(ship)
  local mult = 1
  if ship.empire == empire
    mult = 1 - ( (ship.armor_damage or 0 )+(ship.structure_damage or 0) ) / (ship.armor+ship.structure)
  end

  return mult*design_combat_value(get_ship_design | ship)
end

local design_to_specs = weak_memoize_1_to_1 | function(design)
  return design.update_hull_specs()
end

function design_combat_value(design)
  local specs = design_to_specs(design)

  -- other code...
end

These functions are called outside of AI context so I am not using strong memoization.

[sven]

Ok, so putting it all together, does this seem like a good use case for memoization?

Yup. That will avoid repeated calculations of Design.clone() and design.update_hull_specs() when ship_power_score is repeatedly called for the same ship.

That said, it does look suspiciously like you're expecting to be inside AI context when calling ship_power_score, as _ENV.empire wouldn't be defined otherwise.

[harpy eagle]

Hm, that's right, ship_power_score() is in AIContext. That line was copied directly from the original function. Not sure why I thought it wasn't... though I remember having issues with accessing AIContext variables the last time I messed with this function.

I guess I can just use strong memoization then?

[sven]

I guess I can just use strong memoization then?

Well, AIContexts can be tricky. Read the comment at the start of @AIContext.lua first, if you haven't yet. Then consider that the rules around accessing functions defined in AIContexts are actually dangerously permissive. When I write:

Code: Select all

_ENV = AIContext
function ship_power(ship) 
  return empire==ship.empire and 1 or 0 
end

ship_power is actually added to _G.AI, so it can be called in cases when SCOPE['temp AI State'] isn't defined (i.e., you can access it outside an AI call as AI.ship_power()). And when that happens (and right now, it does happen), the function will evaluate '_ENV.empire' as '_G.AI.empire', which will almost certainly be nil. As it happens, this behavior is not a bug, it just means that we consider our own ships to be less powerful in the special case that we're executing inside an AI call, and the ship has taken damage.

So... long story short, ship_power is a kinda bizarre function, but given that it gets called both in and out of AIContexts, using weak memoization here is probably the right call.

[harpy eagle]

I seem to be having a bit of an issue with memoization.

The code I am using:

Code: Select all

local get_ship_design = weak_memoize_1_to_1 | function(ship)
  return Design.clone(ship.source_design)
end

The issue is that sometimes it gets confused and returns a design for the wrong ship. For example, here it has confused a military transport for an outpost transport:



The test fixture:

Code: Select all

function ship_power_score(ship)
  local mult = 1
  if ship.empire == empire
    mult = 1 - ( (ship.armor_damage or 0 )+(ship.structure_damage or 0) ) / (ship.armor+ship.structure)
  end

  local design = get_ship_design | ship
  if design.design_name ~= ship.source_design.design_name
    local memoized = design_combat_value(design)
    local fresh = design_combat_value | Design.clone(ship.source_design)
    print(design.design_name, memoized, ship.source_design.design_name, fresh)
    if memoized ~= fresh
      error('possible memoization error?')
    end
  end
  local combat_power = design_combat_value(design)

  return mult*combat_power
end

[sven]

I seem to be having a bit of an issue with memoization.

Hmm. I usually avoid weak_memoize_1_to_1 because it can have weird caching behaviors (especially when used with objects, like ships). If you switch to weak_memoizeNN, does that fix the glitch?

[harpy eagle]

Hmm. I usually avoid weak_memoize_1_to_1 because it can have weird caching behaviors (especially when used with objects, like ships).

Huh, well I guess it's time to switch all of my instances of weak_memoize_1_to_1 then (It seems I'm only using it with either ships or empires).

If you switch to weak_memoizeNN, does that fix the glitch?

I'll have to wait and see if it pops up again, it's not exactly easy to reproduce. That said... the moment I changed it the fleet AI started behaving very differently, so... maybe?

EDIT: Yep, it's definitely fixed. I'm actually quite taken aback, I had been noticing issues with the AI's ability to attack or intercept coherently in my games. I didn't realize that this whole time it was because of my ship power code.

Talk about shooting yourself in the foot before you've even got started...