This article is translated by DeepL and fix a little.
simanman.hatenablog.com
Problem
www.topcoder.com
Strategy
- Organize the farmers into groups of two. If there is an odd number, only one group will have three members.
- Move the farmer.
- Evaluate the grid after the move to determine the best farmers placement.
Farmer groupings
We will need at least two people to catch the chickens, so build a group of two.（There are some patterns that can be caught by one person, but that's not many.）
If there is an odd number, there will be only one group of three.
Each group decides on a chicken to chase, and then tries to chase.
Move the farmers
As for moving farmers, there are five possible move candidates for each farmer: up, down, right, left, and wait. If you try to combine the moves of each farmer, you will get a pattern of 5 ** number of farmers.
In order to find the optimal placement from this vast of patterns, I used the direction of movement of the farmers as an array and SA (Simulated Annealing) the direction of movement to find the optimal placement.
The transition is select any one point and change direction.
This will make it easier to search for some effective patterns even if the number of farmers increases.
Evaluation of the grid
For the evaluation of the board, we focused on the following items for confirmation.
- Catching the chickens
- Check to see if the chickens are in a caught pattern.
- Whether you are able to get close to the chicken to be captured or not.
- Whether or not the candidates of movement of the chickens to be captured is being reduced.
The higher the likelihood of catching chickens, the higher the evaluation value.
Catching the chickens
If farmer reaches the same cell as the chicken that is the highest value. In some cases, it may be better not to dare to catch them, but I couldn't evaluate them that much.
A case where it's better not to catch them.
The best solution here will be to try to catch two chickens at the same time.
Patterns that can be caught
Condition of a chicken can be caught is the chicken cannot move and there is a farmer in the adjacent cell to the chicken. For each chicken, check if it is in this state, and if it matches the pattern, give it a higher value. The main patterns are as follows.
Leading to a catching pattern
For the patterns that can be caught, the prior state is only one candidate for chicken movement and a fence or farmer exists at the destination, so this state is also evaluated.
Patterns that can be caught with probability
Since both the order and direction of the chickens' actions are randomly determined, the order and direction of the chickens' movements may lead to a catching pattern, also evaluate those patterns.
A pattern that can be caught depending on the order in which the chickens move.
A pattern that can be caught depending on where the chickens are moved.
Approach the target chicken.
Approach the target chicken. When approaching, move in such a way that you can reach as many cells as possible before the target chicken.（Move the chicken so that its Voronoi area becomes smaller.）
Summary
I made a mistake in the design of the evaluate function because the content of the evaluation function to catch the chickens became complicated and produced some unintended behavior. As for the movement of farmers, I think it would have been more efficient to focus on a specific area rather than the whole area at once, but I didn't have time to implement it, so I gave up. I was a little put off by the randomness of the chicken movement, but I wish I had done a little more detailed research and incorporated it into my evaluate function.
