Project 3: Skittles

You are a part of a group of n friends who have each bought a packet of Skittles. Skittles are sweet candies that come in a variety of colors, each with a particular flavor. The yellow skittles taste like lemon, for example. Each packet contains p individual skittles. (There are small, medium and large bags in practice, ranging from 50 to 400 skittles per bag; there are about 400 skittles per pound.) The skittles can be one of c distinct colors/flavors. (The standard 5 colors are purple, red, orange, yellow and green. There have also been special editions with pink, blue, light-green and lavender, among others.) See this candyblog for more information about skittles.

Each of you and your friends has different tastes. Since this is your first time tasting skittles, you don't yet know which ones you like and which you dislike. Each person can find out whether they like a skittle by eating one (or more than one). You will find out (details below) how much you like/dislike this particular flavor. The rules for eating skittles are that you can consume as many as you like at once as long as they are all the same color, and as long as you have at least that many left in your bag.

Each skittle flavor will have a preference score s between -1 and 1. A score of -1 means you hate the skittle and a score of 1 means you love it. The distribution of preferences will be biased towards positive scores, since the manufacturer is trying to make popular flavors.

If you eat k skittles at once, and that flavor has a score of s, you get an enjoyment score of sk². That means that eating double the number of skittles at once multiplies the enjoyment by 4. When s is negative, the enjoyment is negative too. It thus pays to eat the skittles you like in large batches, while eating the ones you dislike one at a time. You must eat at least one skittle on each turn.

You might even be able to avoid the ones you don't like by trading with your friends. On each round, you get to eat a mouthful of skittles, and then offer to trade some of your remaining skittles with other group members. Since they have different taste preferences from yours, a trade could benefit both of you.

A trade is specified as follows. You offer a set of skittles represented as a c-component vector. For example, if c=4, you might offer (1,0,1,3) corresponding to giving away 5 skittles: three of the fourth color, and one of the each of the first and third colors. You can offer any number in a trade, but must have enough skittles of the specified colors in hand to be able to complete the trade. The offer also includes what you desire, specified as a vector, such as (0,5,0,0) which says that you would like to get five of the second color skittles. The total number you offer must match the total number you request.

Each player submits their offers in parallel, without seeing any other offers. Note that nobody has access to the color counts or preferences of other players. The offers are resolved as follows:

• The simulator will order the players randomly. The order will change for each round of the game.
• For each player in turn, that player will be asked for one of the remaining offers they would like to accept. (A player can choose to not accept any offers.) To accept an offer, the player must be able to supply the skittles requested.
• Once the simulator validates that the accepted offer is feasible, it executes the offer, changing the balance of colors in each player's packet. The accepted offer is withdrawn from the list of offers for the remaining players.
• If by accepting an offer, a player can no longer satisfy the offer he previously made, the previous offer is withdrawn.

At the end of the resolution phase, all players are informed about which offers were made, which were accepted, and by whom they were accepted. The game then progresses to the next round when more skittles can be consumed, etc. Players also see their own updated enjoyment score, so that they can figure out their s value for that color.

Since you care about your friends as well as yourself, your overall score is the sum of two components: your personal overall enjoyment, and the average of all your friends' enjoyment. In other words, you care primarily about your enjoyment, but you also have some incentive to help the others in the game. (The game will be part of a tournament in which many games are played among different subsets of players, so a player that is helpful to others without hurting their own enjoyment may do better than one that does not care about the others' enjoyment.)

Your job is to program a player to play the game well, maximizing the overall score.