Part 1: Sequential Processes
Challenge 1
The mazes the bots inhabit are now slightly more complex. As the bot travels around a maze it may lose or gain resources each time it visits a node. If a bot's resources ever reach 0% the bot dies. Clearly, a bot's resources can never exceed 100%. If a visit to a node would lead a bot's resources exceeding 100%, its resources will be capped at 100%.
You should implement a bot that finds the shortest safe route through a maze. Your bot will have access to a complete map of the maze, including the resource adjustments in place at each node. See the code documentation for details on how to access this map, and the information in them.
You will be provided with a number of mazes and associated tester software to test your bots.
Indicative code size: This challenge does not require any major change to the maze traversal algorithm of the bot provided. The additional code should be significantly smaller than the traversal code already provided.
Challenge 2
This is similar to challenge 1. Again visiting a node will affect a bot's resources. The difference is that a bot will no longer have access to a map of the maze. Instead the bot will need to explore the maze and build up a map. The bot can access information about its current location and the immediately neighbouring nodes. This includes information about the location names and the resource adjustments in force at those locations. The bot can use this information to build up its map. The bot can at any time leave a copy of its current map in the maze. This copy will be available throughout the maze, and will overwrite any previous map left in the maze. See the code documentation for details on how to access the information about the locations, and for details on how to manage maps.
A series of bots will be sent through the maze. You will need to implement a combination of bots. Earlier bots will need to explore the maze, building up a map of the maze for later bots to use. The later bots will be able to use the maps left by earlier bots, and will be similar, if not identical, to the bots from challenge 1.
You will be provided with a number of mazes and associated tester software to test your bots.
Indicative code size: This challenge requires the development of a new traversal strategy to implement the exploration phase of the bots. This is likely to require code of approximately the same order of size as the traversal code provided.
Challenge 3
This is similar to challenge 2. The only difference is that the bots will no longer have direct access to information about the resource adjustments in force at their current location, or at the directly neighbouring locations. The bots will need to deduce this information from observation of their own resource levels. See the code documentation for details on how to access this information.
You will again need to implement a combination of explore bots and challenge 1 type bots.
You will again be provided with a number of mazes and associated tester software to test your bots.
Indicative code size: This challenge should not require any major changes to the traversal strategy developed for challenge 2. The code additional to challenge 2 should be significantly smaller than the traversal code provided with the basic bot.
Challenge 4
In this challenge bots will only be able to leave copies of their maps at their current locations. This means that explorer bots may need to return to the maze's entrance node(s) in order to leave their maps there for the use of any future bots.
You will, of course, again be provided with a number of mazes and associated tester software to test your bots.
Indicative code size: This challenge will require an additional traversal strategy allowing the bot to return to the entrance node(s) to leave copies of its map. The code additional to challenge 4 is likely to require code of approximately the same order of size as the traversal code provided in the basic bot.
Part 2: Concurrent Processes
There will now be multiple bots in a maze, although these will now be the simple mazes, without any resource adjustment at the nodes. Instead, the bots' resources will be affected by deals between the bots. Whenever two bots meet at a node they will trade with each other. Each bot must decide whether or not to cooperate with the other bot. If both bots cooperate they will both have their resources increased by 10% (absolute - e.g. if a bot's resources were 60% they will be increased to 70%, not 66%). If neither bot chooses to cooperate (i.e. they both "defect") they will both be punished by having their resources reduced by 5% (absolute). If one bot cooperates and the other defects the one cooperating will suffer for its naïvety by having its resources reduced by 20% (absolute), and the defecting bot will be rewarded for its audacity by a 30% (absolute) increase in its resources. Again, resources will be capped at 100%, and a bot whose resources drop to 0% will die. This is summarised in the following table:
Challenge 5 -
Deals between bots are brokered by the nodes in the graph. A bot will, from its point of view:
- enter a node;
- if there is a bot waiting
then do a deal with that bot
else wait for a bot to arrive (and then do a deal)
end if;
- choose next node;
- go to next node;
From a node's point of view this same process is seen as:
- bot A arrives;
- if there is a bot, B say, waiting to do a deal
then broker a deal between A and B
else get A to wait at this node
end if;
For this challenge you must implement this behaviour for nodes. The bots will be independent threads, and you will have to use Java's concurrency mechanisms to manage these threads, ensuring that bots wait as necessary, and resume execution correctly. You must also ensure that the bots' resources are adjusted correctly according to the outcome of the deals. See the code documentation for details of how to ask bots whether they are going to cooperate or defect on a deal, and on how to adjust the bots' resource levels.
You will be provided with sets of bots to test your node and associated tester software to test your code.
Indicative code size: This challenge should be no more challenging than the tutorial exercises on synchronisation and communication between concurrent processes in Java. See the tutorial model answers for an indication of the complexity of code likely to be required.
Challenge 6
Challenge 6 is similar to challenge 5, but is made more complicated by the fact that bots may decide to completely distrust other bots. If one bot distrusts another it is not willing to trade with that other bot. Consequently if, for example, bot A is waiting at a node to do a deal, and bot B arrives, but either bot A distrusts bot B, or bot B distrusts bot A, then both bot A and bot B will have to wait for other bots to arrive before they can do a deal.
From the node's point of view the process is now:
- bot A arrives;
- if there is a bot, B say, waiting to do a deal
and B is willing to trade with A
and A is willing to trade with B
then broker a deal between A and B
else get A to wait at this node
end if;
For this challenge you must implement this behaviour for nodes, using Java's concurrency mechanisms.
Indicative code size: This challenge will probably require the use of some more advanced Java synchronisation tools and will probably result in code of the order of 2 to 3 times the length of the challenge 6 code.
Attachment:- Assignment_Files.zip