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

Lecture 6 - Sep. 28

Simulator of Proj 1:

Two versions of simulator going to be used picked by each group

Proj 2:

Theoretical minimum of guess?

Case dependent?

Try to reduce possibilities

Guess everything at beginning. Good information retrival, but hard coded strategy may be abused by the mapper

Divide and conquer? Will that actually restrict the information we get from across queries?

Mapping of length 3 as example. Query of all numbers have 3 possible categories of returnings. They can reduce all possibilities from 27 to either 6 or 6 or 1.

Deliverable next Wednesday. At least a guesser to play with the dumb mapper shipped with the simulator.

(n/2, n] guarranteed algorithm given by Siyang

Related to problem of dropping 2 eggs from high?

Lecture 5 - Sep. 26

Talk about iSnork.

1. Summarize whole sight area instead of single high value creature. Calculate average happiness and quantize the value into 26 levels.

2. Send message every turn is not necessary given divers are not moving every min. Instead, send messages every 3 mins containing 3 letters (1 per min).

3. Average or most interesting? Especially when you don't have time to see everything.

4. Preference on static creatures in dense map.

5. Use marginal happiness instead of absolute happiness.

6. Spend bits on specifying the position within the sight.

7. Strategy for reaction to messages. Whether it worthes to follow. Assumption of a uniform distribution of species of creatures could be very helpful. But how confident it can be?

8. Map depends on listener

Tracking valuable creatures for others' reference.

Tourament configuration:

Boards: 8 boards

5 seen: Pirhanna, Hidden Treasure, Starwars, Diversity Day, Very Happy

3 unseen: One large creature; one high value, verying many low value dangerous creatures; very many species; order of many scales of happiness

D: 23, 12, 30, 100

R: 6, 3, 15, D * 3

N: 7, 19, 2, 28, 100

Average on ranks.

Disqualification: bottom of rank

Lecture 4 - Sep. 21

Anouncement:

Proj 1 final deadline after one week. Presentation 8 mins for each group.

Starwar map used. Size 15, R, N unchanged. Max happiness: 36,750. Random seed: 1,316,624,910,655

Question: statice creature on board.

G2: 17350. Lots of divers come back to boat early. Danger avoidance stategy can be improved to avoid penalty, especially in early game.

G9: -101600. take 1 hour to explore. ingore and step over dangers in early game based on map danger evaluation. then divers cluster and stay close to corner and edge. Confidence transmitted in messaging. All divers back.

C&Q: How is message from others change the behavior? (message value decay along time).

G8: 34450. spend 7 mins for planning and avoid dangers at beginning. using isnorkle. After seen everying, divers back to boat.

C&Q:

G7: 17,550. Same as G8 in early game. Try to keep a spiral track and avoid danger at the same time result in some clustered divers. Go around a danger then try to go back to the closest point on the spiral. All divers back to boat. But losing points on the way back.

C&Q: what if the danger is too dense for the divers to keep track on spiral. will it result in stuck at local minimum? (suggestion from other group: set time out limit. if wait too long, just random walk.)

G6: -85,450. Jump into the sea right away. But not avoiding danger enough. Hurt and followed by some really dangerous creature. All back to boats at 5h, but returned to the sea again. All back finally.

C&Q: cases that back to boat and come out again may benefit.

G5: -136,750. no avoiding danger due to heapmap bug. all divers back to boat though.

G4: have bug :(

G3: -120,550. Try to merge two strategy. Points not explored yet or place others suggest to go. Not appearing to avoid danger. Divres do not go back to boat.

Deliverables 4: next Monday. Last deliverables.

Lecture 3 - Sep. 19

G2 demo: all divers step south by one step and stay given that they have seen all the species. OutOfMemory error in later stage. Diagonal moving strategy.

C&Q: why all divers head to the same direction? more randomness needed? whether diagonal moving is a good way or actually a limitation, especially given the truth that it takes longer to move diagonally.

G3 demo: good inner and outer circle. half of the divers not back to the boat. the radius is determinded by the dimension.

C&Q: more circles.

G4: avoidance of the mines. some divers see the treasure. but iSnorkle is not implemeted yet to let others know. show a little confusion when exploring for the treature.

C&Q: strategy effect is map dependent. randomness gives good covering. but maybe only suitable for relatively small map. better random scattering by keep record of visited place. can it work with moving dangerous creatures? (Yes if estimating the probability of creature moving directions).

G6: Preset path. then switch path to avoid the danger when encounter. Danger avoidance results in group splitting. divers might be tracked by the dangers. 4 of the divers not back to boat.

C&Q: more efficient way than back tracking when switching? Walk along the edge is not efficient for information collection by seeing only one side. Is not coming back really a choice? (Ken's bias is to enforce coming back to the boat. You voted for disqualification)

G7: good two spirals and divers switching. Has some danger avoidance strategy, but don't have time to show in class.

G8: Stay in boat for 2mins for planning. Good work on danger avoidance. not using iSnorkle.

C&Q: Strategies could be strengthened benefitting from iSnorkling. What if the dangers are really dense? how to balance the need of danger avoidance and the enforcement of getting back to the boat in late game?

G9: Try to use spiral strategies. But haven't been able to give each diver a different spirals.

C&Q: Grouping up divers and send group message with more bits per message.

(It seems that I confused the comments between G4 and G5 by mixing them together or missing one of them. Sorry guys :| )

Lecture 2 - Sep. 14

Discussion and comments on the submitted maps, Whether it is necessary to give special algoritm for extreme cases which can be evaluated by overall map information? :

All except one creature are dangerous. Do the divers really want to jump into the sea or just stay on the boat staying away from all the dangers?

Tons of species

Some really dangerous creatures

Empty map, nothing interesting but engery cost

Offline learning

What to do before Monday (suggestions):

Danger avoidance

Path planning

Map overal analysis and evaluation

Infrastructure that allows new strategy to be plug in (time consuming)

Deliverables for Monday:

Working player, shows some strategies on some preferred the boards. Due by 12:00pm next Monday. Additional maps are welcome. No presentation or report required.

Project 1 Team Assignment

G2: Riddhi, Afreen, Tao, Siyang

G3: William, Hans, Moses, Andrew

G4: Kannapiran, Erik, Alex G.

G5: Alex B. , Colleen, Ben, Siddharth

G6: Jonecia, Elliot, Erica

G7: Dhaval, Ashish, Jonathan

G8: Orestis, Nathaniel, Najaf

G9: Sandeep, Neil, Chris, Yufei

Lecture 1 - Sep. 12

Brought up ideas from last year.

1. 1 hr simply walk around then try to optimize

2. spiral search strategy

3. dangerous creature avoidance

4. get back to the boat in time!

5. evaluate the worth of the message depending both the creature and distance (more details need to be discussed about the distance)

6. assign diver to follow really valuable creature to update with other coming divers. then they choose to switch following and browsing roles.

7. Divers' happiness are not shared. But it can be estimated basing on each one's message history

8. dynamic parameters of Divers

Suggestions:

1. Divide divers into explorers and browsers

2. Chain the divers and let them follow others

3. Sample the map and guess the whole picture?

4. Take advantage of the unlikihood of the creature makeing a turn

5. Explicit message for "seeing nothing" or "no danger"

Clarifications:

1. Euclidean distance, from square center to center

2. Boat can be used as shelter from dangerous creature

3. No credit for observation when in boat

4. Overlap on the same square is allowed (divers, creatures)

Anouncement:

1. Deliverables this Wednesday, dumb players that can correctly call the API as well as some rough description of potential strategies. Think about a new map. One submission each team.