Feature Request : Optimize Kittens assignment

[oliversalzburg]

Original issue oliversalzburg/cbc-kitten-scientists#129 by @wilfriedwoivre

Optimize job assignments of kittens and add more smart method to produce ressources

Prevent Kittens starving
Remove farmer when you have enough catnip
...

[Zirak]

IIUC the problem of kitten assignment is actually two problems:

1. Identify when an assignment is (un)necessary
2. Identify which assignments are liquid

To give an example:

• Science is at its maximum; reassign scholars (1). But, where do they move to? (2)
• Science is lacking; we need more scholars (1). But, where do we take scholars from? (2)

These feel like orthogonal problems. I'll try to propose one possible concrete solution for each.

Necessity: Capped vs. uncapped jobs

Most jobs don't really have a cap on their assignments, or have one which is difficult to analyse. For example, woodcutters are always nice to have. Even if wood is ever at its max, workshop automation (with or without scientists) means wood can always be used for something. However, there is such a thing as too few woodcutters: A point where wood production is negative (because of e.g. smelters).

We can identify several jobs which do have a clearer cutoff point:

• Farmers: Too few farmers means kittens die, too many and we're moving production away from more profitable jobs
• Scholars: No scholars means no science, but once science is sitting at max, they're on the toilet playing Kittens themselves
• Woodcutters, miners: Too few is negative production, too many and no special harm done

Therefore, I propose a fairly simple heuristic for when a reassignment is needed:

• Farmers are needed when catnip production is negative; unnecessary when it's positive
• Scholars are needed when science is not at capacity; unnecessary when it's at capacity
• Woodcutters and miners when production is negative; unnecessary when it's positive
• Hunters, priests, engineers, and geologists are never "required"

This is something which can be both explained and understood without many "but what if"s.

A job that I feel is left behind are the hunters. Their heuristic could be when furs/ivory hit 0, but that might happen due to deliberate player intervention. So maybe when both furs/ivory are 0 for a portion of time? Considering some edge cases, I thought it better be left off for future iteration.

It can also be argued that geologists are neglected. I haven't personally seen where they're necessary, but they're definitely incredible when in large quantities.

Liquidity: Use the settings

We've identified when a certain job is required, and when it is no longer so. Now we have to answer: When we need a farmer, who do we take it from? And when the farmer is no longer needed, where do we move it to?

Once we've established that pretty much every non-essential job is nice to have, let's try to establish a few base assumptions:

1. We only ever touch jobs which are enabled in the settings
2. A poor assignment is better than having a free kitten
3. The "max" value is not a hard limit on either end; ok to go over, ok to go under
4. We should never make things worse than they currently are

3 feels like the biggest leap, but we'll get there.

What's our algorithm then? I propose something like the following:

function takeFrom(allJobs, destJob) {
    // We will only take from jobs which are:
    // a. Different from destination job
    // b. Enabled
    // c. Are not necessary (see Necessary section above)
    const candidates = allJobs.filter(
        (j) => j !== destJob && j.disabled && isCurrentlyNecessary(j)
    );

    // We freely take from jobs with no defined max
    const infinities = candidates.filter((j) => j.max === Infinity);
    if (infinities.length) {
        return randomFrom(infinities);
    }

    // We take from jobs that are above their maximum
    const overflowing = candidates.filter((j) => j.current > j.max);
    if (overflowing.length) {
        return randomFrom(overflowing);
    }

    // As a last resort, take from any ol' job
    return randomFrom(candidates);
}

This hits assumptions 1, 3, and 4 of the above. We never touch disabled or necessary jobs, so we don't leave things off worse than they were.

Note that this doesn't solve when such a reassignment is impossible. For example, the only enabled job is the farmer. During a catnip crisis, only farmers are managed, so nothing can be done. That is up to the caller to detect and handle. There's also a priority problem, discussed in "Why this is bad".

We've only solved half the problem. We figured out how to get another farmer, but what do we do when that farmer is no longer necessary?

I think we can employ a similar algorithm, sort of in reverse:

function whereTo(allJobs, sourceJob) {
    // We only give to jobs which are:
    // a. Different from the source job
    // b. Enabled
    const candidates = allJobs.filter(
        (j) => j !== sourceJob && j.enabled
    );

    // Give to jobs which haven't yet hit maximum
    const underflowing = candidates.filter((j) => j.current < j.max);
    if (underflowing.length) {
        // Sort underflowing by just how much they're missing
        const byMissing = underflowing.sort(
            (j0, j1) => (j1.max - j1.current) - (j0.max - j0.current)
        );
        // Return the most missed one
        return byMissing[0];
    }

    // Distribute to any ol' job
    return randomFrom(candidates);
}

This hits points 1-4 above. We only touch enabled jobs, we respect the max value, and we do whatever when we don't have a stronger heuristic.

Note that we don't need to check for necessary jobs, since we assume those are filled by the core loop (described just below). That may be something that could be done in addition to the existing logic.

Also note that if multiple jobs are uncapped (i.e. max === Infinity) we may not do the smart thing, either always assigning to one job, or assigning at random (which is kinda ok).

Core loop

The core loop for this decision making might look roughly like the following:

function loop(jobs) {
    let direNeed = jobs.find(isCurrentlyMissing);
    if (direNeed) {
        const to = direNeed;
        const from = takeFrom(jobs, to);
        if (from) {
            reassign(from, to);
        }
    }

    let extra = jobs.find(canDoWithout);
    if (extra) {
        const from = extra;
        const to = whereTo(jobs, from);
        if (to) {
            reassign(from, to);
        }
    }
}

This gives us a heuristic that, I think, isn't too difficult to follow. At least I think so at first glance. Over several loops, all necessary jobs will be filled, and all extraneous jobs will be voided. We have to be careful that isCurrentlyMissing and canDoWithout won't ever cancel each other out, creating a cycle like assigning poor Cassie Silk from Farmer -> Miner -> Farmer -> Miner endlessly, or something to that end.

I feel like there are some devils in the details of isCurrentlyMissing and canDoWithout, but this comment is already long enough and I didn't want to make it book-length.

Why this is bad

There are two big things that I feel are lacking in this proposal, but I didn't want to visit before getting feedback first. These are:

1. There's no priority, and kittens will die. At times of negative catnip production, farmers are clearly more important than anything else. This is not represented in the above algorithm. Given that only farmers and scholars are enabled, and science is not yet at its max, kittens will die.
2. Scholars are over-allocated. The heuristic of "science isn't at max" is relatively dumb, and it might lead to too many scholars. This feels either like something that needs tuning (e.g. "will reach cap in reasonable time", whatever that is), or that it's fine and will even out over time.

Neither is a hard problem to solve, and I think the rest lays the groundwork for the rest. 1 is adding a priority to jobs and filtering based on that, 2 is seeing how things go and benchmarking. Something to that end.

This suggestion also assumes no changes to scientist settings. There's always the possibility of adding a user-set priority; e.g. prefer assigning to geologists over priests over woodcutters, however that might work. Or maybe ratios. Or cutoff points. It's possible to workshop many improvements.

Sssooo uuuhhhh whadya think?

[oliversalzburg]

Those are definitely some good ideas, but I still feel like this is doomed to never result in a solution without edge cases.

In general, to implement more ideal kitten assignment, we need:

1. The ability to assign more than 1 kitten per tick
2. Removal of kittens from jobs (those over the max would be good candidates)

If we have those two components implemented, that would gives us room to experiment.