Gunnar

Class of worlds

This agent is much more complex than Einar. This complexity makes it handle worlds with the following properties quite well:

All interior tiles are walls or clear and some of them have items or homes.
The border tiles are walls.
There are no enemies.

Strategy

Gunnar's basic principle is to always explore the nearest unknown tile. Near is defined as low cost to reach it. But there are exceptions to the basic principle; the right-rule and groups. When no more unexplored tiles can be reached, Gunnar finds the cheapest way to a home, if one is reachable. If that way is cheaper than the reward for shutting off at a home, he goes there to shut off. Otherwise he just shuts off where he is.

Right-rule

The right-rule means that if the tile to the right of Gunnar is unexplored (and belongs to a group with the highest priority, se below about groups), Gunnar will explore that tile immediately.

If the right-rule is not used, Gunnar will move in the direction he is facing when he is exploring, and only turn when he has bumped into something. That behaviour tends to make him leave tiles behind, so he has to return later, thus making him less efficient.

When the right-rule is used, Gunnar will not always explore the tile he is facing if it is unknown with highest priority just because it is the cheapest tile to explore. Instead he will spend an extra amount, Turn_Cost, to explore the tile to the right first instead.

A test in a particular world of the size 60×52 with no homes, determined with the wall probability 0.3 and the item probability 0.1, Gunnar achieved the score 13691 with the right-rule and only 12983 without it.

Excercise. Test the effect of the right-rule yourself. Use a world similar to the one described above, a much larger world is not necessary to see the effect and may take unnecessarily much time.

Caution

There is an important detail; Gunnar must avoid getting stuck in an infinite rotation because of the right-rule. If he is surrounded by unknown tiles with the highest priority, he could be tempted to turn right to explore the tile to the right of him. But the next turn he is facing the same situation and would turn right again, and so on. This is particularly likely to happen at the beginning of the simulation. Therefore Gunnar will skip the right-rule in that case.

Groups

Even with the right-rule in place, Gunnar would leave many unexplored tiles behind until later, if it was not for groups. Gunnar does not just consider every unexplored tile by itself, he can also think of them in terms of contiguous unexplored areas, which are equivalent to groups of unexplored tiles. When exploring a tile, it can happen that such a group of unexplored tiles is divided into 2 or even 3 groups. This is called a split. It seems wise to explore the smallest groups first to get them done instead of wandering away while exploring a large group and then spend a lot of movement to return to the small group. This is why Gunnar searches for tiles belonging to the smallest groups.

Map

Obviously gunnar needs a world map to store and use the information he has gathered. It is a 2-dimensional array indexed with relative (to Gunnar's starting location) coordinates.

Searching

When Gunnar wants to find a tile to explore or a home to return to he has to search for a way to it. He uses a breadth-first search, which is optimal.

Speed optimizations

This section is about optimizations whose purpouse is not to achieve a higher score, but to make Gunnar decide faster which action to perform.

Note

Even the design of the simulator, where agent and client communicates over internet sockets, was developed with performance in mind. It makes it possible to run simulator and agent on different computers, for example the simulator on a workstation and the agent on a remote supercomputer.

Chosing Ada as a language for developing agents enables the relatively easy use of tasking and distributed computing on the agent side.

Irrelevant tiles

As stated in About agents, Gunnar uses a quite complex algorithm to find irrelevant tiles. See the file doc/gunnar/tunnels in the source distribution.

Note

This is such an obvious optimization that a large fraction of agents are expected implement it. Therefore the simulator has special support for debugging it. The agent can send a map symbol when it marks a tile as irrelevant, and the simulator can show it on the map. This makes it easier to debug the agent code for finding irrelevant tiles.

More excercises

Excercise. Improve Gunnar to handle enemies. He should be able to infer that a tile is safe when possible. He should also be able to neutralize without wasting ammunition and cost. But most important, he should make sure to stay alive.

Tip

If an agent comes in a situation where it has explored all tiles it could prove to be safe it may not know how to continue. But if it can neutralize and there is a tile where it percieves hostility, it can try to neutralize in one of the directions where an enemy could be. This could waste ammunition by not neutralizing an enemy, but it gives something else; the agent can be certain that there is no enemy in the tile it faces (and maybe the tiles beyond that, depending on the circumstances). So it can continue exploring. If it is lucky it might get a Neutralize_Reward. It is even nicer for the agent if it also no longer percieves hostility after the neutralization, because that means that there was only 1 adjacent enemy and that all adjacent tiles are now free from enemies.