Project 4: Colorful Exploration of Leprechaun Land (CELL)

Leprechaun Land is a colorful place. It is made up of a hexagonal grid of side length d, something like the central region of a Chinese Checkers board, and every cell has one of six colors. You can explore Leprechaun Land by moving from cell to cell, but there is a cost to movement. You have a sack of colored marbles, and every time you step on a cell of a given color, a marble of the corresponding color disappears from your sack. If you don't have any remaining marbles of a color, you must avoid cells with that color. You must move on every turn, and if you cannot move your exploration ends. (This is the origin of the phrase ``losing your marbles.'')

You start with a bag of 6m marbles, m of each color. The only way to increase your marble count is to trade with one of L Leprechauns. (You were wondering why it's called Leprechaun Land, right?) Leprechauns occupy random cells on the map, and to trade with a Leprechaun you must move onto a Leprechaun's cell. When that happens, the Leprechaun will show you his exchange rate for marbles in the form of six floating point numbers (r,g,b,y,p,o), one for each of the six colors, where each of these numbers is randomly chosen uniformly in the range from 1 to 2. You get to submit some number of each color, and request some number of each color, with the requirement that the total value of what you request cannot exceed the value of what you submit. Also, you must have in your sack enough marbles to cover your offer. The Leprechaun executes the transaction, and disappears in a puff of smoke!

Actually, the Leprechaun re-appears in another randomly chosen previously-empty cell elsewhere in Leprechaun Land. If you get to visit this Leprechaun again later, the exchange rates will be different random numbers. You have complete information about the colors of all cells and the current locations of the L leprechauns. Additionally, players from other teams will be traversing the map at the same time, and you can see them too. It is perfectly fine for two players to be on the same cell at once. Beware, though, that when two players step on a Leprechaun's cell at the same time, the Leprechaun gets scared and disappears in a puff of smoke without giving either player an opportunity to trade.

To win this game, you must quadruple your counts of each type of marble, i.e., have at least 4m of each color. Winning players are taken to the end of the rainbow and no longer occupy Leprechaun Land. If after some large number of turns there are still players remaining that have not won, the simulator will terminate the game. Players are ranked as follows:

• Winning players, in the order that they won.
• Players remaining when the simulator stops the game, in descending order of total marble count.
• Players who lost their marbles, in reverse order of when that happened.

The color map of the cells of Leprechaun Land is not random. The simulator will read the value of d and the colors from a file, and so we will consider a variety of map types. In fact, one of the first deliverables for each group will be to come up with a handful of ``interesting'' color maps.

The key to the game is to make favorable trades with the Leprechauns. Some initial things to think about:

• How might your strategy adapt to the density of players and Leprechauns?
• How important is it to be the first to get to a Leprechaun?
• How should m scale with d and L to keep the game interesting?
• Why is this game like the ethernet protocol?