Internet Problem Solving Contest

IPSC 2009

Solution to Problem H – Hunt!

The hunt as such was not that difficult. A human player can easily win the game in less than 30 moves. We will now describe one possible strategy. The basic idea of our approach is to move only a few of the wolves in every round.

First we start by moving a majority of wolves to partially “surround” the sheep. If these moves are performed well, the sheep will start to run away in such a way that they create small groups. After such small groups are created (which is a matter of 3-4 rounds) we choose a few (usually 2-3) wolves that are close to some groups. In the following rounds each chosen wolf is used to catch all sheep from one particular group. Using this approach, we make these few wolves much faster than the sheep, so they are able to catch all the sheep before they run away too far. The remaining wolves are used only as scarecrows (well, scaresheeps, to be precise :-) ) When a group is caught, we pick new wolf and attack the nearest group. Once all large groups are eaten, we can just greedily pick off the remaining sheep.

Using this strategy, one can usually catch the first 10 sheep in the first 7 rounds, and finish the game after 25 to 30 rounds.

Another nice strategy was to start by making empty moves during the first hour. This requires no thinking and it has the nice effect that the sheep will form nicely edible clusters.

However, the hardest part of this task was not the strategy. The hardest part was time management. Finding the time to make each move distracts the player from solving the other tasks. It may be a better strategy to implement a simple player (e.g., “always move two wolves greedily”) and let it play automatically. If you run the program early enough, you can easily get over 50 moves, and this should be enough even for a simple strategy to succeed.