introduce a database of mazes with descriptive metadata, for example number and length of dead-ends, etc.

[otizonaizit]

No description provided.

[otizonaizit]

Looking at #852 , we need to discuss what to store in the layout database. This depends in my opinion on how we plan to use that information. I envision something like this:

pelita --trapped-food 0.3 bot1.py bot2.py

where --trapped-food represent the (maximum) proportion of food which is located within dead-ends, tunnels and/or chambers. This would replace the current --dead-ends switch.

The way it would work should be the following:

• if a layout is explicitly specified and the layout contains no food, food is distributed randomly but according to --trapped-food in a "soft" way, i.e. if the layout does not have enough trapped squares it won't error our but just do that best it can
• if layout is explicitly specified and the layout already contains food, a warning is issued and the --trapped-food switch is ignored
• if layout is not explicitly specified, a random layout is selected among those in the database that allow us to satisfy --trapped-food and food is distributed randomly according to --trapped-food. For this to work, the layouts will be stored without food in the database.

What do you think @Debilski ? If we agree on this use case, we can design the database to make this the privileged and optimized use case. Given that the database is private, I think we can change it later with not too much trouble should the need arise, given that #852 is optimized as hell and tuns in ~10 seconds on 1600 layouts.

[Debilski]

Couple of thoughts:

• I suppose this would mean that we also get rid of the mazes with/without dead ends distinction? Mazes can have all the dead ends/chambers that they like, because who cares if we do not put food in them?
• Without the need for this distinction and with an algorithm that finds all chambers in a maze in 1/160 seconds, we might not need a maze database at all (at least not yet). We use the --trapped-food (name feels a bit weird) option and the food is arranged according to specification.
• Not having a db will make life a little easier. (Less to think about, fewer moving parts to maintain.)
• The food relocation algorithm will need to be aware of the desired trapped food ratio.
• I think mazes that contain food should (/could) also be reshuffled. For development situations, it could be easier, if the food in a maze does not reshuffle each time one uses it, but this can simply be done by not using the --trapped-food flag.
• For a tournament, the food should absolutely be reshuffled. (Although I do not see any problem with not reshuffling it. I kind of doubt that there is any real danger in knowing the food locations in advance.)
• I guess we could also decide to use a specific pre-defined, pre-generated set of mazes for the tournament instead of relying on any maze database or live-generation. But live-generation is also fun, so I have nothing against it.
• (This probably goes to far but we could now also vary how much food is on a maze.)

Going forward, my suggestions would then be something like:

• Rename create_db.py to layout_tools.py or something.
• Make the find_chambers, find_tunnels methods public api along with a distribute_food method. (Public in the sense that game.py uses them.)
• Instead of having a database, we could have a script that prints out the stats for each layout, which we could use for our own analyses.
• The tournament should make use of --trapped-food or use a new set of mazes that are generated when running tournament setup.

[otizonaizit]

* I suppose this would mean that we also get rid of the mazes with/without dead ends distinction? Mazes can have all the dead ends/chambers that they like, because who cares if we do not put food in them?

this is not strictly necessary, but we can of course re-generate all layouts without using the code that removes dead-ends and chambers

* Without the need for this distinction and with an algorithm that finds all chambers in a maze in 1/160 seconds, we might not need a maze database at all (at least not yet). We use the `--trapped-food` (name feels a bit weird) option and the food is arranged according to specification.

Well, not really. Imagine I set --trapped-food 0.33. This means I want to trap 10 food pellets, i.e. I need to select a maze among those that have at least 10 trapped squares. If I don't have the database I would need to parse all the layouts every time I start a game. With the database, I know which layouts fit my requirements without the need of parsing anything. Given that the algorithm to get the list of trapped squares is fast, this only means that we do not need to store this list in the database, but we need to store the number, so we can select the right mazes and then, once one maze has been chosen at random, with the algorithm we can get the list of relevant squares.

* Not having a db will make life a little easier. (Less to think about, fewer moving parts to maintain.)

See above, I don't think we can avoid it.

* The food relocation algorithm will need to be aware of the desired trapped food ratio.

I am not sure I agree. A defender may decide to "guard" the entrance of a chamber for too long and then the food will be relocated at random, so it may be relocated outside of the chamber. This is fine in my opinion. The --trapped-food thing is in my vision just a starting condition.

* I think mazes that contain food should (/could) also be reshuffled. For development situations, it could be easier, if the food in a maze does not reshuffle each time one uses it, but this can simply be done by not using the `--trapped-food` flag.

For development situation, if you want to replay on the same maze with the same food you just use --seed. I think that it is a more intuitive API if the food is distributed at random only if not explicitly specified in the layout. If the layout comes with food, I want it to be exactly there. the --trapped-food switch is only to make the proportion of trapped food configurable. We could even start without that switch and just hard-code the proportion. The distribution of food at start is a different thing, that we are here doing at the same time, but logically it is a different thing.

* For a tournament, the food should absolutely be reshuffled. (Although I do not see any problem with _not_ reshuffling it. I kind of doubt that there is any real danger in knowing the food locations in advance.)

For me it is not about danger, but if we want --trapped-food to be configurable, then we need distribution at start, or we may not have enough layouts that match the requirements.

* I guess we could also decide to use a specific pre-defined, pre-generated set of mazes for the tournament instead of relying on any maze database or live-generation. But live-generation is also fun, so I have nothing against it.

* (This probably goes to far but we could now also vary how much food is on a maze.)

OK, OK, but that is something else, we can talk about it later. Note that live maze generation is not doable at the moment: it is too slow.

Going forward, my suggestions would then be something like:

* Rename `create_db.py` to `layout_tools.py` or something.

* Make the `find_chambers`, `find_tunnels` methods public api along with a `distribute_food` method. (Public in the sense that `game.py` uses them.)

Sure.

* Instead of having a database, we could have a script that prints out the stats for each layout, which we could use for our own analyses.

See above, I don't think this is feasible.

* The tournament should make use of `--trapped-food` or use a new set of mazes that are generated when running tournament setup.

I don't think it is feasible. Generating the mazes takes too long.

[Debilski]

I think I have been slightly misunderstood: I never meant to parse and analyse all mazes before a match instead of using a database. No matter how fast the algorithm gets, this would break down on a slow file system. However, my approach assumes that this is not necessarily needed.

• I suppose this would mean that we also get rid of the mazes with/without dead ends distinction? Mazes can have all the dead ends/chambers that they like, because who cares if we do not put food in them?

this is not strictly necessary, but we can of course re-generate all layouts without using the code that removes dead-ends and chambers

• Without the need for this distinction and with an algorithm that finds all chambers in a maze in 1/160 seconds, we might not need a maze database at all (at least not yet). We use the --trapped-food (name feels a bit weird) option and the food is arranged according to specification.

Well, not really. Imagine I set --trapped-food 0.33. This means I want to trap 10 food pellets, i.e. I need to select a maze among those that have at least 10 trapped squares. If I don't have the database I would need to parse all the layouts every time I start a game. With the database, I know which layouts fit my requirements without the need of parsing anything. Given that the algorithm to get the list of trapped squares is fast, this only means that we do not need to store this list in the database, but we need to store the number, so we can select the right mazes and then, once one maze has been chosen at random, with the algorithm we can get the list of relevant squares.

My approach was: Draw any layout fitting the size from our pre-generated layouts and then place the food according to the requested (or hard-coded) specification. If the maze doesn’t have enough dead-ends or chambers to place food: bad luck. (Or good luck!)
If we want to have --trapped-food 0, we can still use mazes with chambers/dead-ends. The important part is that no food is placed in a dead-end, no?

(The only problem would be if this breaks down too often. Then a db could help with pre-selecting.)

Aside: Please let’s not invent something that needs to use a number like 0.33 as a default. That number doesn’t look right. :) Perhaps --trapped-food 10:30 or so, which also specifies the total food.

• Not having a db will make life a little easier. (Less to think about, fewer moving parts to maintain.)

See above, I don't think we can avoid it.

• The food relocation algorithm will need to be aware of the desired trapped food ratio.

I am not sure I agree. A defender may decide to "guard" the entrance of a chamber for too long and then the food will be relocated at random, so it may be relocated outside of the chamber. This is fine in my opinion. The --trapped-food thing is in my vision just a starting condition.

The idea was more: If --trapped-food is 0, then relocated food should also not be placed in a chamber.

• I think mazes that contain food should (/could) also be reshuffled. For development situations, it could be easier, if the food in a maze does not reshuffle each time one uses it, but this can simply be done by not using the --trapped-food flag.

For development situation, if you want to replay on the same maze with the same food you just use --seed. I think that it is a more intuitive API if the food is distributed at random only if not explicitly specified in the layout. If the layout comes with food, I want it to be exactly there. the --trapped-food switch is only to make the proportion of trapped food configurable. We could even start without that switch and just hard-code the proportion. The distribution of food at start is a different thing, that we are here doing at the same time, but logically it is a different thing.

But our own selection of mazes would not have the food pre-set? Then I think I misunderstood it.

• For a tournament, the food should absolutely be reshuffled. (Although I do not see any problem with not reshuffling it. I kind of doubt that there is any real danger in knowing the food locations in advance.)

For me it is not about danger, but if we want --trapped-food to be configurable, then we need distribution at start, or we may not have enough layouts that match the requirements.

That’s why I am more in favour of a who-cares algorithm that takes any maze and just places the food as good as it can. With the database you now have to figure out a selection algorithm.

• I guess we could also decide to use a specific pre-defined, pre-generated set of mazes for the tournament instead of relying on any maze database or live-generation. But live-generation is also fun, so I have nothing against it.

• (This probably goes to far but we could now also vary how much food is on a maze.)

OK, OK, but that is something else, we can talk about it later. Note that live maze generation is not doable at the moment: it is too slow.

Yes, that’s why I meant, pre-generated: They will be generated when the yaml file for the tournament is created, during tournament setup.

Going forward, my suggestions would then be something like:

• Rename create_db.py to layout_tools.py or something.

• Make the find_chambers, find_tunnels methods public api along with a distribute_food method. (Public in the sense that game.py uses them.)

Sure.

• Instead of having a database, we could have a script that prints out the stats for each layout, which we could use for our own analyses.

See above, I don't think this is feasible.

• The tournament should make use of --trapped-food or use a new set of mazes that are generated when running tournament setup.

I don't think it is feasible. Generating the mazes takes too long.

During tournament setup time it should work.

[otizonaizit]

yes, so I think we agree on almost everything. The plan would be this: #856 (comment) . If maze generation is fast enough, we can really get rid completely of the hard coded mazes.