Food-filling algorithm has a tendency to overfill chambers

[Debilski]

When chance generates a maze with not enough chambers, the filling algorithm always fills the chambers first, giving a somewhat uneven experience (sometimes other corners of the maze appear completely empty). I’m not completely against these mazes, I just think that they are generated too often.

We should maybe adapt the algorithm such that we don’t start with the filling of the chambers but assign the chamber nodes a different priority according to chamber nodes/non-chamber nodes ratio. That way we would at least not fill them up all the time. (rng.sample can take a counts= argument, so this could be easily tested out.)

On top of that, we may want to use an algorithm that leads to less clustering of the food pellets but that’s secondary.

(Maybe we should even have different filling algorithms and every time a different one is selected.)

[otizonaizit]

Well, it is not a "tendency". It is baked in on purpose. The idea being that if I say --food 10:30 I mean that I want 1/3 of the food trapped. The algorithm is best-effort based. If there are not enough trapped tiles, than you won't get as many trapped food as you requested, obviously. But if you have enough trapped tiles, you get what you asked for.

The intent here was to make it harder to gather food and making it more worth it to invest some time in coding a good defender, because now you have a good chance to kill.

I am not sure what would be the intent of implementing your proposal, except for a more visually appealing layout?

Regarding "clustering" of food pellets. The algorithm right now is a completely unspectacular uniform random distribution with two forbidden zones: the border of the homezone and the bots initial positions. I am not sure I see a reason to deviate from that, except to have a more visually appealing layout again?

[Debilski]

But if you have enough trapped tiles, you get what you asked for.

I guess my problem is with the ‘you get what you asked for’ because in practice no-one asks and the 10:30 setting is basically hard-coded.

Maybe we should work on an outline for what our end-goal is with the maze-redesign, because while we did some great and good changes to the algorithm, the original plan was to have a maze database which would have had vastly different mazes that would have been selected with a certain percentage each. What we have now is that all mazes are more uniform in how the food is distributed than they ever were in some sense. If there are further plans to the food distribution, then we might not need to change the actual algorithm. It is just that I lost track of what is the plan here.

Just so that it doesn’t get lost, here is a naive version of a weighted algorithm. (It tends to generate rather similar patterns actually.)

def distribute_food(all_tiles, chamber_tiles, trapped_food, total_food, rng=None):
    rng = default_rng(rng)

    if trapped_food > total_food:
        raise ValueError(
            f"number of trapped food ({trapped_food}) must not exceed total number of food ({total_food})"
        )

    if total_food > len(all_tiles):
        raise ValueError(
            f"number of total food ({total_food}) exceeds available tiles in maze ({len(all_tiles)})"
        )

    free_tiles = all_tiles - chamber_tiles

    def weighted_sample_without_replacement(population, weights, k, rng):
        v = [rng.random() ** (1 / w) for w in weights]
        order = sorted(range(len(population)), key=lambda i: v[i])
        return [population[i] for i in order[-k:]]

    all_tiles = list(all_tiles)

    # statistically, there should be trapped_food pellets in len(chamber_tiles) and
    # total - trapped pellets in len(free_tiles)

    chamber_weight = trapped_food / len(chamber_tiles)
    rest_weight = (total_food - trapped_food) / (len(free_tiles))
    weights = [chamber_weight if tile in chamber_tiles else rest_weight for tile in all_tiles]

    food_nodes = weighted_sample_without_replacement(all_tiles, weights, k=total_food, rng=rng)
    return food_nodes

Regarding "clustering" of food pellets. The algorithm right now is a completely unspectacular uniform random distribution with two forbidden zones: the border of the homezone and the bots initial positions. I am not sure I see a reason to deviate from that, except to have a more visually appealing layout again?

Less clustering means the bots have to do more work and visit more spots on the maze rather than just having to find the quickest path to the gold chamber and get there before the enemy. But of course I also want it to be visually appealing.

[otizonaizit]

Just for the record, let me write down here the background of #867 and #856 :

• When we started (b169497), the mazes were generated by removing dead-ends, which was quite slow and for that reason we decided to create a collection of 100 pre-computed layouts of normal size. This has been thee status-quo for a long time
• In 2019 (Refactor maze generation, do not create mazes with chambers #649) we decided to change the code that generated mazes to be able to remove chambers too. The rationale was that it is easy to detect the entrance of a chamber and that it was too easy to camp in front of it, making camping a winning strategy. This was also the moment where the algorithm to generate mazes became really slow.
• In Aug 2024 (New and enlarged collection of layouts #812) we discovered that students would manually go through all layouts, find the optimal spots to do camping and hard-code those positions in the code. To counter that we enlarged the collection of layouts up to 1000 layouts of normal size
• In the meantime (Discourage camping: Food relocation and ghost shadow #811) we also decided to make camping less attractive by introducing food relocation
• After ASPP2024 (Reduce default shadow distance to 1 #821) we decided to reduce the bot-shadow used for food relocation, as we saw that a shadow of 3 makes defending too hard and attacking too easy
• At the same time (Add a collection of layouts with dead ends #824, Use dead ends #825) we added a collection of layouts with dead-ends and made them to be chosen with a probability of 25% when running a game. The reasoning was that attacking needs to become a bit harder and we want it to make it worthwhile to spend some time implementing a defender

After all of the above, we still had some problems:

• layouts who claimed to have "dead-ends" did not necessarily have dead-ends, because in the generating algorithm we simply refrained from removing dead-ends if any were present. So a layout that was created without a dead-end by the generating algorithm would still be filed as a layout with dead-ends
• to make attacking harder and defending worthwhile, what matters is not the mere presence of dead-ends, but the fact that you have food in these dead-ends/chambers. If a dead-end does not contain food, there's no reason to go there ever

The first approach we tried (#852) was to write some code to analyze the existing mazes and create a database with their properties: how many dead-ends? How much food in each dead-end? ... and the same questions with chambers.

At the same time, @jbdyn spent some time (#856) looking at the maze generating algorithm and improved in such a way that it became feasible to think about generating the maze live and get rid of the pre-computed mazes, which have been a pain since the beginning of history. Also, we could now distribute the food such that it would land in the dead-ends/chambers. This solution addresses the issues above and also makes the idea of the database obsolete. We do not need to know how maze looks like to choose the ones we need, we just generate right away the maze exactly as we want it.

Finally, with #867 we integrated #856 into the pelita CLI, so that live maze generation can be used.
We have made attacking a bit harder and we have made it worthwhile to spend time coding a defender. The exact parameters can be adjusted after having a try-run in my course in the summer semester 2025.
If a proportion of 1 to 3 between "trapped" food and free food is a good one remains to be seen, but it is now easily changeable. If the bot-shadow used for food relocation needs to be increased again, now that you can camp in front of a chamber that you now know will contain some food, well, this also remains to be seen. But both parameters are just two numbers and we can change them before ASPP2025 after seeing how they work in my course.

So to me, except for the experimental test of these two parameters, the work seems to be a great success. @Debilski : is this the outline you wanted to see? Does it answer your concerns?

[Debilski]

This is a great resource for the Pelita historians. :)

[Debilski]

What I don’t understand is as follows. We have this as the starting point for the TU redesign:

we added a collection of layouts with dead-ends and made them to be chosen with a probability of 25% when running a game

and apparently, this had some implementation/execution problems as stated:

layouts who claimed to have "dead-ends" did not necessarily had dead-ends, because in the generating algorithm we simply refrained from removing dead-ends if any were present. So a layout that was created without a dead-end by the generating algorithm would still be filed as a layout with dead-ends
to make attacking harder and defending worthwhile, what matters is not the mere presence of dead-ends, but the fact that you have food in these dead-ends/chambers. If a dead-end does not contain food, there's no reason to go there ever

So, our problem was that we did not reach the 25% of dead ends and decided to do something about it.
However, now with the --food 10:30 default, it turns out we have 100% [*] of dead ends, which seems to vastly overshoot what we had in mind. I don’t necessarily have a problem with that, but for me this result does not follow from our initial goals and problems.

[*] Actually we have less, since the algorithm is still capable of accidentally producing mazes without dead ends (but it has become more unlikely I guess).

Of course, if our plan is now to make that --food X:30 number variable, then this seems to be a doable fix. I am just curious if this is still on the agenda.

[otizonaizit]

The overall goal is to make attacking a bit more challenging and defending a strategy that is worthwhile to implement.

All the historical changes I have explained above (the dead-ends at 25%, the food 10:30, the removing of chambers) are all just moves to reach that balance. So no, our missed goal was not that we didn't reach 25% dead-ends. The problem was that attacking was still too easy and defending still not worth it. In the past it was the opposite. We want to find a good balance.

We will experiment now if the chosen parameters for --food and bot-shadow are pushing us towards the overall goal. If they don't, we now just need to change the defaults, by either reducing the number of trapped food (in the extreme case to 0) or by increasing/decreasing the bot-shadow. By changing these two parameters we can dynamically adjust the worthiness of spending time implementing defense and attack. This is in my opinion exactly what we were missing until now.