10/27/2010 Class Notes

Last class we talked a lot about collaboration. There are a few basic solutions that we came up with - tit for tat, etc.

G7 came up with the name "PushyPushelkins"

Did we do what we were trying to?
G2: Tried to co-operate with opposite player
G3: Tried to co-operate with the player across diagonally from us

Should you try to co-operate early or later?
Daniel: You could have information if you wait, because you'll see how others are working together.
John: Waiting lets you see who has more coins, and who will be a better ally.
Daniel: When you have multiple clusters you will have more opportunity for collaboration.

Will we end up with many clusters or few clusters?
Dfed: Nobody wants to 0 out everyone's scores in the long term

Dan: It's possible that you get stuck where you have to create a big stack. Maybe you want to make sure that you're helping the ones who won't overtake you anyway.
Neha: There's a risk of trying to help someone who doesn't retaliate.
Blake: That's why you should wait to cooperate

What happens when we add a dumb player?
David: The smart players can take advantage of a dumb player, knowing that they'll never hurt you back

What if it's all dumb, and one intelligent?

What if we have short games?
Andrew: Focus on the center low value squares.
Dan: There will be in general an early/mid/late game strategy, and this will just launch you straight to end-game

For Weds:
Your player must always make legal moves. It should implement some aspect of the strategies that we talked about.

Class notes: 10/20/10

What are the main points for the game?

Jesse: Cooperation: You need to find a cooperative agreement with another player. Not sure how you would signal this cooperation though.
Jesse: This is kinda an iterative prisoner's dilema. A "tit for tat" strategy may be effective, where you do onto others what they do onto you.
Neha: What happens if we end up with just 3 pairs, where opposite players co-operate?
DFed: You want to make sure that not only your opposite player, but also everyone who can affect you is working with you.
Daniel: You definitely want to cooperate with as many people as possible. But you can only make one move at a time, so how can you make people favor you over the long term?
EPK: If you cooperate with your neighbors, you can move directly into somewhere with higher payoff.

Lauren: If Red and Yellow are co-operating, you are working against orange
Neetha: Maybe there is an advantage to letting other people pile up the coins, then move that one pile
Zach: The best alliance to make early doesn't make any enemies - just push a player's coins deeper into their territory
Blake: Make sure that when a medium sized pile is accumulating, make sure that they slowly drift towards you

KAR: There's another issue: You have discussed varying your behavior over score. Is it score within an individual game, or over many games?
Flavio: This is important because we can build a macro/micro strategy

Daniel: If we end up with a few big alliances, we may end up with a bad, but stable case where all of the coins are together and nto helping anyone
DFed: Getting a 3-way alliance will take a lot of time to get everyoen to agree to it

Team formations:
1: Elba, Lauren, Zach
2: John, Dan, Neha
3: Pilunchana, Archana, DFed
4: Flavio, David, Blake
5: Jesse, Daniel, Neetha
6: Eva, Nitin, Elba
7: Andrew, Yang Jian, Neerja

Deliverables:
Monday - Presentations!
Wednesday - A play from each group that does something towards a strategy

Class notes: 10/18/10

Reminder: Final submission - Weds at noon!

What's a good intermediate number of lights?
Lauren: 5 is pretty good, it's an average case
Daniel: You can easily cover 50% of the map with 5 lights

We did some runs with G5.H map
G1: 270
Daniel: We find the spot with the most area and place the lights iteratively
Zach: We can construct linear and branching chains. We build the lights in a graph, then find the one that has the lowest average distance to all of the other lights, and put the collector there. We have a formula that calculates how long the pulses will be by looking at the "depth" from the
G5: 2013
Nitin: We don't do so great with the shadows
G2: 649
Jesse: G1 put the lights right on the perimeter of each other, whereas we make them somewhat closer
John: We create a 2D array and assign an "openness" value to each point

Nitin: We are all using a different approximation, and it seems like the people that take a finer granularity do better.
G3: 3972
Elba: Even if your chaining is slow, it's wayyyy better than random drift
G7: 3950
Dfed: We We have a "dumb" approach where we do a lot of random tries, then do whatever works best
Zach: Depending on how we place the lights, we can scale linearly
Andrew: The chain computation doesn't blow up, but the time to run the actual simulation takes time

G4: 850
G6: Didn't terminate
Yang Jian: We should have been chaining

Tournament configurations?
How many lights should we expect?
3, 10 came out of a hat. What is reasonable?
What about if you had a maze?

Upper bound: 50/100

How many times do we need to run to reduce variance?
Lauren - 5
We will rewrite the simulator so that it will run multiple runs with the same light configuration. I'll pick a reasonable number of runs (on the order of 10, probably)

How many lights?
3, 5, 8, 13, 100

What's an OK upper bound for a max rounds? 15,000

Blank
Boxes & Lines
Cage
Caged
G5 H
Steps
W

We will come up with:
1 maze
2 more hidden ones

10/13: Class Notes

Deliverable today was an automated player. How did we do?

We ran on "Cage.xml" map:
Daniel: Group 1 put all of the lights clustered together in one spot. They found the biggest area and stuck all of their lights there.
G1: 6763
EPK: Group 2 also looked for a large open area to place the collector in, then use a spirograph strategy to place the rest of the lights. They will be chained inwards, but will not necessarily note locations of walls.
G2: 3473
Neetha: We had a lot of bugs, not 100% sure what happened.
G3: 10278
Flavio: We find the largest area, then move diagonally and then horizontally
G4: 1570
David (G5): We look at 10x10 grid units, so we don't necessarily see the obstacles. A local search isn't necessary, need something more global
G5: Doesn't seem like it would ever finish.
Pilunchana (G6): We had special cases, couldn't get one to work here, so we went randomly, but did very poorly.
G6: No termination
DFed (G7): Collector in most open area. Then place lights to have minimal shadow
G7: 799

Why are we limiting how many lights we use? (ex, only using 7 when we have 10)
John: We should add more branches, so that we don't increase timing difficulties but have more lights
Dan: Have extra auxilary chains that aren't directly working with the main chain, but are working as an extra funnel
Neerja: It's really hard to make the frequency work right
Eva: We can take advantage of the walls to break up our sets of lights so that we don't have interacting flows.

We did a central collector manually and collected almost 50% in 261 steps.
Is this strategy optimal?
Dfed: We haven't proven that there isn't a better way to do it on the side
Neerja: There is no particular advantage in where you put the collector (center or side), because it matters mostly where the obstacles are
Eva: Create a partitioned space, closing the gaps between walls with the shortest line. Then find the largest blob, then see how large the rest of the blobs are, then use that to inform your strategy
Daniel: Calculate the minimum distance that each mosquito would have to travel to get to the collector, then use that information
Nitin: If we could look at this as a graph, we could re-use a lot of network flow algorithms that already exist
Blake: You don't need a complete graph representation, just within the boundaries that you need

What's a good fallback strategy?
John: Just put one long chain
Archana: Putting lights in the corner is a good one
Neetha: Putting the lights near the corner is not good because you lose a lot of the light
Archana: We'd use the corners to build a chain inwards
Neerja: You should NEVER pick a position statically

Monday is our final discussion class. Code will be due Weds and we'll start project 3 then too, and have reports and presentations on the 25th

For Monday: Have a very, very robust player.

10/11: Class Notes

We ran the simulator on the 3 light blank map. Most layers
G6: 297
G5: 296
G4: 528
G3: 322
G2: 337
G1: 368
G7: 292

What did we learn from this exercise?
David: When we have limited lights, make sure to cover the area as much as possible, with slower cycles
Nitin: The diagonals are longer than the side, so it makes more sense to put the lights along a diagonal
Neerja: We don't really have enough evidence here to make a lot of conclusions
Andrew: How do we approach timing? We need to make sure that they get all the way across a flow before we turn off the lights. We determined 11.5 was an appropriate timing
Neha: It's most efficient to leave the lights on longer (we looked at 20-30 seconds)
Jesse: Our ideal timing was 30 seconds for a cycle - 18 on, 12 off
Daniel: We used 20/20, but it will be different for different maps and placements

KR: How will you determine these parameters?
Zach: I think it will be constant between maps
EPK: It varies by how much overlap there is between lights

We did the same with 10 lights:
G1: 50
G2: 53
G3: 140
G4: 130
G5: 54
G6: 65
G7: 84

What did we learn from 10 lights, no barriers?
Pilunchana: Only cover 50% of the space, don't worry about getting more.
Daniel: Only invest a light to do a rapid collection if you have a lot of lights
John: Get more than 50% of the mosquitos to the collector as quickly as possible, it's better to have 50.2% than 49.8%


With g2board2, 10 lights:
G1: 181
G2: 141
G3: 963
G4: 899
G6: 125
G7: 132


Deliverable for Weds:
Let's see automatic players. We'll challenge it with one from the collection that we haven't played a lot yet.

Class notes: 10/6/10

KR: Is there something about this project, or any other that makes it inherently NP?

The cross map was interesting. Where do you place the lights? What if you only had 1 light?
Dfed: Use 1 light to draw mosquitoes into 1 region, then put the collector in that region

Dan: If you put a collector at the very end of a line, then you may see it more likely that a mosquito will hit it directly.

Elba: It's very important to make sure that we are using as much of the light as possible (minimal shadow, maximal shine in bounds)

KR: Take the group2board2 map, and think about it with 3 and 10 lights. Manually, come up with the best 3 light and 10 light arrangements.

How can you prune the search space?
Eva: Find only the interesting parts.
EPK: How do you determine how much of the board is empty space? Could you just use a random walk?

KR: What kind of representation do you use?
Blake: Create "areas" as units of reasoning
Jesse: Close off the small gaps, then use that to define the areas
Zach: You couldn't just go end-to-end, you have to do line-to-line
Dfed: We store for each meter of granularity, what lines are closest and how far
David: You can observe the intended direction of flow through a channel, by looking at which directions the obstacles are

KR: In a map with no walls, what's the most efficient way to collect the mosquitoes

Deliverables:
No more maps. A few manual deliverables:
A 3 and 10 light version of an empty map, and a 3 and 10 light version of the group2board2.
Next week, come up with improved players that do something interesting and is informed by your thinking from the manual investigations.