Project 4 First Lecture

Group for Proj 4

Riddi, Ashish, Andrew

Siyang, Dhaval, Elliot

Nei, Tao, Najaf

Afreen, Sandeep, Nate, Jonathan

Akiva, Erica, Erik

Yufei, Sid, Jonecia, Hans

Kanna, Orestis, Chris

Find the exit first. Look back the track to see whether it is easy to let two out together.

How to use the obstacles to align two players.

Related to regular expression.

How to take advantage of obstacles is dependent on the locations of both of the players

Some maps are impossible to get out together.

Align too early may be weakened by obstacles on the way moving to the exit. It might be more reasonable to find obstacles near the exit and use them to align.

What if we know the whole map.

Moving diagnolly can see more unexplored area.

Search from the exits to see their common "back moves".

When there is enough information, exhaust search is theorecially fine to solve the proble.

When do you know you have enough information to start the very time consuming exhaust search.

How to explore more efficiently, taking consideration of both map.

Diagnoal search could be fast, but could also leave lots of wholes behind.

Think it as one puzzle instead of solving two individual puzzles together.

Deliverable 1:

Two maps, and one initial player

Might be limit on turns related to the size of the map

Lecture 14 - Oct. 26

Don't need to know every color's happiness, given the bias towards positive happiness. Keep in mind the happiness could be really random. Another reason is seeing other groupo is requiring that color a lot, which means we can benifit a lot from trading with that color without know the happiness of that color. The initial number of each color should also be considerated.

As long as know one color is of 1.0 happiness, you don't care whether there is

other color of 1.0 happiness since focus on one good color gives optimal result.

When it is hard to pick between two colors, hold on both. Later on, when one color accumulates more and more, the decision will be more apparent given the quadratic happiness curve.

Luck also counts. How early can you discover the best color to hold?

Given the quadratic dependence on the number, the difference between happiness contributes less.

Possible for the players to cooperate to follow a certain communication strategy such that all the players have a better knowledge of others' preference and everyone achieves global optimization? Is this kind of cooperation stable? How to assure your own benifit during a cooperation? Keep in mind that the communication is really limited. This may ruin the cooperation even everyone is trying to be nice. (Think about prisoner lemma)

Think in a bigger scale. The tournament score is sum over many games. Second rank every game may give you the champion after all games.

You are only one among many people giving offers. Does it worth to scrifice a little to make sure your offer has higher possibility to be picked?

Multiple games among the same group of players such that people have time to learn each other.

Lier could be identified by inconsistent behavior. Punish the lier hard and hide yourself harder. (You guys are really sophisticated...)

What if there are just too many colors that each color will not have number large enough to feed one single player? Even if there are less colors than players, there will still be some pathetic players have to eat more than one color.

Keep record of former trades, see what others like and dislike. Could be a count matrix.

Deliverable:

A little sophisticated player.

Offer and desire for the same color means something.

Lecture 12 - Oct. 21

Group for project 3:

Dhaval, Kann, Tao, Erica

Sid, Hans, Elliot

Ashish, Siyang, Akiva, Orestis

Sandeep, Erik, Riddi

Chris, Afreen, Najaf

Jonathan, Yufei, Andrew

Jonecia, Nate, Neil

G1: 0.3+0.5+1+0.7+0+0+400+161.8 = 564.3

G2: 1-0.5+0.3+0+0.7+157.5+324+67.5+all Pu left = 550.5

G3: 1-0.5+0.7+0.3+0.3+7.5+2.7+984.7 = 996.7

B: Blue, P: Pink, Pu: Purple, G: Green, R: Red

Round 1:

Eat:

G1: 1G 0.3

G2: 1G 1

G3: 1B 1

Offer:

G1:

G2: 1P <-> 1G

G3: 3G <-> 3B

Pick: G1, G2, G3

G3: 3G <-> 3B :G2

Round 2:

Eat:

G1: 1P 0.5

G2: 1B -0.5

G3: 1Pu -0.5

Offer:

G1: 3P <-> 3G

G2: 3B <-> 3G

G3: 2Pu,2G <-> 4B

Pick: G3,G1,G2

G2: 3B <-> 3G :G3

G3: 2Pu,2G <-> 4B :G2

Round 3:

Eat:

G1: 1Pu 1

G2: 1Pu 0.3

G3: 1P 0.7

Offer:

G1: 1G,3P <-> 4Pu

G2: 2B <-> 2G

G3: 4Pu,2G <-> 3B,3P

Pick: G2,G1,G3

G3: 4Pu,2G <-> 3B,3P :G2

Round 4:

Eat:

G1: 1B 0.7

G2: 1P 0

G3: 1R 0.3

Offer:

G1: 2G,2P <-> 3Pu,1B

G2: 2B,2P <-> 3G,1Pu

G3: 4Pu,2G <-> 2B,4P

Pick: G1,G2,G3

G3: 4Pu,2G <-> 2B,4P :G1

G1: 2G,2P <-> 3Pu,1B :G2

Round 5:

Eat:

G1: 1R, 0

G2: 1R, 0.7

G3: 1R, 0.3

Offer:

G1: 4R,1P <-> 3Pu,2B

G2: 3Pu,1B <-> 3R,1G

G3: 4R,2G <-> 6B

Pick:

G2: 3Pu,1B <-> 3R,1G :G1

Round 6:

Eat: at least 5 together

G1: 5R, 0

G2: 15R, 157.5

G3: 5R, 7.5

Offer:

G1: 4R,2P <-> 4Pu,1B,1G

G2: 2P,2Pu <-> 4G

G3: 2G,2R <-> 2B,2P

Pick:

Round 7:

Eat: eat whole color

G1: 20Pu 400

G2: 18G 324

G3: 3R 2.7

Offer:

G1: 2P <-> 2G

G2: 3P <-> 3Pu

G3: 2G <-> 2B

Pick:

G1: 2P <-> 2G :G3

Final Round:

Eat:

G1: 4G, 10R, 1P, 15B 161.8

G2: 15Pu, all P 67.5+all P

G3: 26B, 21P 984.7

I missed the number of Pink skittles G2 swallowed in the last round. If G2 still keeps the record, please let me know such that I can update.

Lecture 10 - Oct. 17

Tournament:

Mapper will be appointed. Randomly pick from multiple models and mix (pick of 4-8 mappers).

Guesser:

n, the length of the mapping: 2, 3, 5, 10, 20, 100, 1000, 10^4, primes, 10 repetition. 1 cpu second per guess.

penalty of the making wrong guess

Bug: query the same till cut off, but get score of 0.

Mapper: part of the mapping binary and the rest not.

For binary mapping, should narrow down gradually or jump to pair query after a couple of big group query. For narrowing down strategy, the decision tree grows exponentionally.

Grid query. Try never query two numbers together more than once.

Wednesday lecture new place at the open meeting room.

Lecture 10 - Oct. 12

Final deliverables of project 2 next Wednesday.

Submit guesser and we pick mappers randomly (might not seen by you before) since there is hard-for-sure strategy of mapping.

Test every guesser on binary mapper

What if mapping 1-20 -> {1,2}, 21-40 random

Whether spend first couple of queries on large fracture of the mapping to learn the big picture of the mapping?

For small N, exhaustedly search in the space? For large N, cut into sub mappings that are small enough for exhautedly searching.

Deliverable On Monday, bug free guessers, debugging message disabled.

Lecture 8 - Oct. 5

G3: 13 queries for all 3 random mapping. Could be improved by choosing different group size.

Comments: Optimal strategy should be dynamic, according to the information learnt from query feedbacks. Following a fixed strategy is not likely an optimal one. Or switch between several fixed strategies?

G5: How to calculate the size of the search space? Whether strategy that minimize search space size greedily result in missing the glocal optimal strategy? Try to find orthoganal questions and query them together. How to update former rules when new information is learnt (something like intersection with former rules)?

G2: Boolean vector for each index, then take orthoganal vectors (vectors sharing the least possibility overlap)

G7: Quickly go through all numbers (random decide how to split in half). Then repeat this recursively while shrinking the query size. What is the best shrinking rate? How many to overlap with former queries?

(Didn't follow the discussions over all the groups since helping G2 set up. Sorry...)

For pairwise query strategy, try this: [1,2,2,1,1,2,...]

Things to work on:

How to calculate the search space. How to shrink it most.

Best strategy so far: "BE LUCKY" :)

Next deliverable:

Implement a mapper. Improve the guesser.

Group for Project 2

Kann, Sandeep, Ashish

Chris, Elliot, Jonathan

Siyang, Erik, Jonecia

Afreen, Dhaval, Yufei

Tao, Sid, Nath,

Hans, Akiva, Najaf, Riddhi

Andrew, Erica, Neil, Orestis