12/8: Class Notes

What did people think of 7 letter word?
Daniel: It was helpful to have previous reports, previous code less helpful
Neha: It was helpful to know the approach of previous years. Knowing what not to do helped to figure out what to do.
EPK: Maybe it would be interesting to repeat multiple projects
Dan: We wasted a lot of time getting an architecture together when we could have been writing the code.
Elba: It was helpful that the first project was text based (and not geometric)
Flavio: It was nice that we could get some basic results quick

Mosquito?
EPK: I liked that it was visual
Daniel: It was interesting that nobody got a good discrete solution
Everyone thought that the competition was fun

Push?
Elba: Everyone kinda plateaued
Yang: It was an interesting game, that models what we see in real life
Neha: The piling was terrible

iSnork?
General consensus - many variables, very complex, quite a bit of room for further work

Most people voted to extend project 4 for next year

12/6 Class Notes

Tournament parameters:

Group 4 will create an extra player that does just danger avoidance, and then comes back to the boat.

D:
30, 40
R:
5, 8, 15
N:
1, 2, 7, 20, 30
Maps:
Lochness
Mines and treasure
G2 benchmark
Lochness, but it's happy, not dangerous
Piranha
Lochness, plus 3 happy creatures of the same species
G5 VERY happy
1 or 2 static happy creatures
Piranha plus a few good creatures
More than 26 species

1 map with very dense wildlife many different species, d=60

We'll narrow this down to 8-10 boards

How many different random seeds?
~100-1000, depending on time it all takes (will maximize # seeds to fit in 4 hr run)

We'll use a different configuration today...
D=40, R=8,N=7, Seed=1,291,659,224,861

G1: 1023
G2: 1591
G3: 1330
G4: 702
G5: 1217
G6: 836
G7: 1153

What did we learn today?
John: Cover the board!
Daniel: We are overly conservative when estimating the number of creatures instantiated
Lauren: We are overly optimistic with the same thing!
Flavio: Better to be home early than to be home late!


Weds: Final code due by noon. Course wrap-up.
Mon: Presentation and report. and peer review

12/1: Class Notes

Schedule update: We are swapping the class wrapup and presentation days. So presentations on the 13th. Course wrapup on the 8th. Final players due at noon on the 8th.

We ran a d30 piranha map:
G5: -887,000; 13 didn't make it home
G1: 35,000
G2: 35,000
Lauren: We stay in the boat until there's no danger in the radius.
Flavio: This is going to keep you locked in the boat!
G3: -21,000
Jesse: We got the max, then we didn't go back, so we lost it all
G4: -1,347,000
Zach: We don't properly avoid danger due to a bug
G6: -71,000; 7 DSQ
You should have a fuzzy condition test to see if you have the max

Mines:
G5: 0
G1: 5740
G2: -156
Whats a good meta strategy to realize that your current strategy needs to be changed?
David: Make milestones, and see if it's taking too long to ge there

Neha: Do path finding through static dangerous creatures

G3: 20740
G4: 1740
Zach: We should be exploring... but retraced our steps for some reason
G6: 1740

Lauren: It's important to have different strategies for static/moving danger.

Lauren: Visiting all of the creatures will be NP-Hard (traveling salesman)
DFed: Just use simple heuristics (see the closest, etc. only need to see 3 of each creature)

G5: 5005
G1: 4785
G2: 5321
G3: 6275
G4: Crash
G6: 5853

11/29 Class Notes

Daniel: If there's something really valuable out there, and getting of the boat may give you some minor penalty, you shouldn't just stay on the boat

We ran on Lochness:

G6 - We have each player explore, left to right, then get stuck on the right. (6000, then -3000 after penalties)
G4: We are using the isnork, but not acting upon it. (3000)
G5: (Neha) - We have some big bugs with handling messages (-71000)
G1: 9000 points. They used the isnork to send messages, but not listen
DFed: Our snorkelers return home after they see everything
Dan: Actually, might be wise to stay out to help spot things
Lauren: But if there's a very high risk of danger, and not much to track, you should go home
G2: (John) - We go home early also. Sending out junk messages for the seaweed, shouldn't be bothering. 11,000 pts
G3: (David) - We use the isnork right, and we do a spiral exploration
G7: We are not using the isnork either. -13,000


G5 Happy trials:
G1: 3050. Mostly random wandering
G2: 3850.
G3: 4300
G4: 2645
G5: -(a lot). Still stuck in random pairs
G6: Still stuck on the right. -9150
G7: 3065

What have we learned?

John: There's a really steep penalty for not making it back on the time. Should we raise it?

We're changing it completely so that if you don't make it back to the boat, your entire score is DSQ'ed

Dan: Is there a "par" for each map?
Yes... 3 of every creature happiness

Eva: We are using huffman coding
Blake: We are sending this as numbers in base 26. 4 or fewer creatures fit in 2 chars, more fit in 3
DFed: You don't need to send the position if you know that the player is always following

EPK: How many divers you have is a very important variable when determining what to follow
Flavio: You need to follow at a distance to make sure you don't get hurt

Nitin: It can be really difficult to handle very dangerous creatures.
John: We should focus on board coverage
Daniel:

For Weds:
Send AND receive messages (and act on them ;))
Everyone gets back to the boat
Feel free to come up with t-shirt ideas. For $8 shirts, we will need to use only 1 color. Full color gets much more expensive (towards $20) and the quality goes down (you end up with iron-on transfers instead of silk-screening)

11/28

DFed will augment the simulator so that snorkelers will see the direction that observed things are facing.

G1 & 4 errored.

G5 had a bad danger avoidance code
g6 had some big bugs too

What have we observed so far?
PK: Avoid the danger
Nitin: Is there some complexity in avoiding dangerous creatures?
EPK: The best way to avoid a creature is to swim perpendicular to it (Blake's idea)

Can you compute an expected score?
Is it worthwhile to do a complete simulation on each turn?
Daniel: You could do this probabalistically
Should we jump in the water for short periods of time and come back, ever?
Daniel: Note that if there are a lot of static creatures, it's essentially a maze solving problem

Blake: Players might want to keep track of a map (particularly of static) creatures to help them return

Eva: We need to have some way of interrupting a full message to deliver something super important
Neerja: You could just follow what's so important for 1-2 moves while sending what you were already, and then send the important one
DFed: We have no problem fitting everything that we need in 3 chars.
Blake: We encode different things depending on how big R is
Jesse: If there are a lot of things, it's not useful to broadcast this

DFed: We're sending (species)(location)(etc)
Daniel: This is good because then you know what you are looking for, and it can be interrupted better.
DFed: Even if you send stale messages, we can infer when it was sent and from where
Arcahna: Snorkelers should permute themselves around the board to see different things

Daniel: The isnork is really only useful for things that are rare and/or high value

For monday:
Make it better. G1 and g4 certainly shouldn't crash again :)
Have thoughts about the iSnork vocabulary

11/22: Class Notes

G2 submitted a fairly sparse board, benchmark, which has a few high scoring items
Daniel: This is interesting because it forces you to have to spread out
Lauren: Boards with few creatures are "easy" in that you have less creatures to find to maximize your score.

We computed that the maximum ideal dimension is 80, after which point you'll get stuck at the edges
Blake: Bigger R's shrink the board
Daniel: R=D is a sanity check
Lauren: Why not use 2 way communication with the isnork?
DFed: How do you do that without interference? Maybe you have some sync time where everyone agrees to give some sort of state update.
Daniel: We don't need to have people tell us what they need if they are instead telling us what they have seen
Flavio: But we may need to know the ID of the creature too, not just what it is
John: In a dangerous environment, a conga line makes sure that you know a safe path back to the boat
What happens if your conga line is interrupted?

Did we miss discussing anything?
John: Whether creatures are helpful or just provide a minimal benefit

We'll make a map with 5-10 of each creature, filling at least half of the cells (all benign, same happiness)

Zach: Use something like huffman coding to make important messages come out faster, and less important ones take longer

What features would we want to encode in the isnork?
John: Add a 27th letter, the null character
DFed: We need to know the radius at which you saw something

For Weds:
Some players that respond to the boards we saw today.
Be ready to talk about how you are going to use the isnork.

11/17: Class Notes

Today we are starting project 4. Hooray!

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

DFed: We should use a 2 character message instead of a 1 character message
Lauren: If you have a buddy, then you can have 2 people sending out messages from the same observation.
DFed: Would it be smart for all of the snorkelers to go in the same direction?
Zach: It's high risk
Neha: We should be sophisticated with our coding to show the different kinds of sealife
Eva: We should come up with a good way to do path finding?
Daniel: Each player should have a long term goal of where they want to explore
Archana: We can pre-determine different roles for each snorkeler
Should one stand still?
Lauren: It may be more useful to hang out in the middle than get stuck in a corner
Zach: Depends on how many players you have.
DFed: Fanning out in all different directions isn't great because when you actually want to backtrack to see what someone else said, you have to go all the way over there

For Monday:
An interesting configuration for an ocean.
An initial player attempt.

11/10: Class Notes

Lauren: As piles get condensed, we become somewhat more eratic.
Daniel: Once there are no more single moves that can help you, it's really hard to tell who remains your partner
Lauren: You also have to make sure that if a player has only one move left, you don't hold it against them if they hurt you (or don't help) (or help)
Daniel: Many groups don't seem to have an endgame strategy implemented yet

Flavio: Making agreements at the start of the game does not seem appropriate because it's impossible to guarantee that it will be upheld.
Dan: The last move should always be to sabotage someone
John: When should you start sabotaging? Last, second to last?
Neerja: Interpreting moves at a statistics level misses a lot of nuance
Elba: It's really hard to interpret what a move means, so relying upon stats on that is not so great

What issues are still open?
EPK: If you are going to get 0 points, and your only possible move will help someone, maybe you should make an invalid move
We had a significant discussion over whether this is appropriate or not
In the interest of stability, we're not going to change anything. I'll try to get some extra helpful logging for when invalid moves do happen though

Dan: There is a cost of aggression: you're missing out on cooperation!
David: Sometimes it's better to be 2nd best near the end because people will go after the best.

Predictions for the tournament:
Eva: Some good cooperation
John: A lot of variance

Reminder: Players due by noon on Friday
Presentations and reports Monday

Expected tournament run times

Based off of a few anecdotal tests with only 1 core running, without overhead of logging the results:

# of rounds	expected run time (sec)
10	.35
25	.8
50	1.5
100	3

There will be:
8 choose 6 (28) configurations with 1 of each player (counting dumb player)
8 with 6 of each player (1 player playing against itself)
8 choose 2 (28) configurations with 3 of each player (2 players playing 3v3)

That's 62 player combinations and we had 7 round configurations, and assuming we do 1000 runs of each pair of player-round configurations, that's 434,000 executions.

I can conservatively run this across 300 cores, which puts us at 1445 executions per core, and if we round out the average run time to a highly conservative 2 seconds (counting overhead for logging and distributing batches), it should take just over 50 minutes to run the entire tournament.

11/8: Class Notes

We need to set the final code delivery date:
Friday by 12:00 PM

Tournament parameters?


DFed's group isn't observing betrayals and continues to help players that have helped it, ever.

What did we learn from today's simulation?
Co-operating with a player is a good idea, but you need to have a backup strategy
Andrew: Use a short term memory
Archana: When co-operating with a player, don't do the "best" thing, so that you can do something else bette rlater.
Blake: But our player would then ignore you because you're not really helping us as much as someone else who is helping us more

Perhaps we should vary the number of rounds in the tournament?

Run 1,000 runs for each tournament
We will do 8 combinations of players for each configuration of # of rounds [counting dumbplayer] (also, run so that we have 8 more tournaments, each with 6 of one player, also do a set of 3v3's with only 2 players).

10, 25, 26, 50, 51, 99, 100 number of rounds

I'll do a feasibility study before Weds to see how many we can run (I'm expecting to be able to do the above but scale up to 10,000 runs each instead of 1,000).

How much harder is it to form a 3 way partnership over a 2 way?
Zack: Are betrayals a good thing? (for the betrayer)

11/3: Class Notes

We ran G1,2,3,4,5,7 on a 100 round sim:

G4 strangely pushed directly away from itself
G7 is trying to co-operate with the player directly opposite from it, for the first 10 minutes

Is it possible to try to cooperate with everyone?
Jesse: This might appear to be non-cooperation for some
Elba: A tit-for-tat strategy will always help (if everyone is)

Can you help two players at the same time?
John: Yes, but it's very small.
Neha: We should try to only give small helping moves first, and then we can move to more later once we're sure that we're cooperating

Flavio: At the end of the game, co-operation can also include a "defense" strategy

When do we degrade how much we are valuing our cooperation 
Nitin: At first it might look like someone is helping you, but they may be actually just pushing through you to make it to another player
 Zack: Don't just keep a history of the past 10 turns, keep a weighted history of everything - both how much X has helped you ,but also how much you have helped X.
Daniel: It's important to keep track of *if* someone can be helping you, because if they aren't helping, and they can't, you shouldn't hold it against them.

What would make a neutral move?

Should we co-operate with immediate neighbors?
Eva: No, because there are fewer number of moves to make to help

Daniel: Opposite players will end up at end-game doing a defensive strategy for each other.
EPK: Breaking an alliance at the end of the game may be risky because it may alienate them
David: If two players team up against 1, that 1 would need to have 2 people protecting it, otherwise it will lose coins

Neha: The game has something of a bias towards randomness because as the game ends you will HAVE to push piles together

For next Monday:
Improve, improve, improve your players (nooo illegal moves)
Encourage: swap your players

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.

Class Notes: 9/29/10

Ideas for strategies?

Elba: Put 2 lights overlapping with the collector between them to guide the mosquitoes
David: When we have sub-areas, put the collector right near the gap to bring them to it
Yang Jian: Put lines along each obstacle
Neerja: Also need to focus heavily on the light frequency, not just the placement
Dan: Once you get the mosquitos in one area, it's easy to move them as a bunch, rather than moving them individually. The obstacles can be used to keep them in the bunch
Andrew: What if you have lights near each other and flick them really really fast, so that they go to some average location instead of to the light directly
Eva: As we have more and more lights, create an abstraction of light groups
Pilunchana: What if you had only one light?
Neetha: Place the lights in places that are less obscured by obstacles
Neerja: A lot of how long things take to run depends on the initial placement of the mosquitos
Archana: Place the lights in a zig-zag pattern to maximize the board coverage
Pilunchana: When there are a lot of obstacles, a zig-zag may be very useful
Neha: This doesn't work when you have very few lights
Nitin: Never put the collector out of the way
Elba: When you do the zig zag, they should overlap 100%


Deliverables for Weds:
1 - Come up with at least 1, preferable 2 boards per group, and a target number of lights for that board
2 - A player, which doesn't have to do anything super useful. Modify dumb player somehow interesting

Teams for Project 2:

Dan Iter	1
Zach Sheppard	1
Daniel Wilkey	1
John Graham	2
Jesse Bentert	2
Elizabeth Kierstead	2
Lauren Pully	3
Neetha Sebastian	3
Eva Sitaridi	3
Archana Balakrishnan	4
Neerja Pancholi	4
Flavio Palandri Antonelli	4
Dawei Shi	5
Neha Srivastava	5
Nitin Natarajan	5
Elba Garza	6
Andrew Shu	6
Pilunchana Kiatruangkrai	6
Blake Arnold	7
Yang Jian	7
Dan Federman	7

(Is there a bug causing the mosquitos to not fly straight? Can we add more contrast to the simulator?)

Project 2: Mosquito Simulator available

Simulator on CourseWorks (or GoogleCode). Instructions in GoogleCode

Class notes: 9/27/10

Tournament format:
Warning: If your player errors out during the tournament, it will be removed from the rest of the tournament

Do we include old players?
Neha: Include just G1
KR: Let's have 2 classes of tournaments - one with just new players, one with both
Daniel: Some have bugs
KR: OK, so we will use G1 as a representative of last year's players
KR: Note that we are optimizing for high score, rather than ranking

KR: Any ideas for a new tournament, not one that we did last year?
Nitin: Bring in more of LessStingyPlayer
DFed: Using LessStringyPlayer will hurt conservative players
KR: Is it interesting to run with 7 hidden letters?
Elba: Yeah, it's pretty interesting. People still get 1 letter. There is still some play
Nitin: With 7 hidden letters, LessStingPlayer should be there.
Yang Jian: 7 hidden letters means that we depend a lot more on luck
Eva: With 7 hidden letters, we should have more rounds
Daniel: Yes, we could do this and it wouldn't really take that long either
Neerja: Leave out group 1 when you start with 7 hidden letters
KR: But it actually shows an interesting baseline of what happens when you just use your 7 starting letters

Final format:
Number of rounds fix to 100
Vary number of letters 0-7 (for 7 hidden letters do 200)
We will include last year's Group 1 as a player in addition to this year's 7:
8 choose 2 2-player tournaments
8 player tournament
8 player tournament, with 2 of 4 players, done enough so that everyone plays as a duplicate player once
single player tournament, with 4, 8, and 12 of each player
8 choose 2 2-player tournaments, with 5 of each player, plus a "LessStingyPlayer" who always bids rand(0,3)

If we have time afterwords, run 8 players + LessStingyPlayer

Last year:
Vary number of letters 0-6
Vary number of players 2-14
Number of rounds fix to 50

5 choose 2 2-player tournaments
5 player tournament
5 player tournament, with 2 of each player
single player tournament, with 5, 10, and 15 of each player
5 choose 2 2-player tournaments, with 5 of each player, plus a "StingyPlayer" who always bids 0

I will make the results available only as a SQL database - no more text output. I'll send out a SQLite database, probably (might make a public MySQL instead)


We did a run with 7 letters...
What went well/wrong?
Daniel: We are bidding high on letters when we are close
Lauren: We didn't do so great - we were too conservative, which is a big problem on 7 hidden letters. When we get 7 letters for free, we should make sure that we're not that conservative

KR: What makes a successful player?
EPK: It's important to adjust your bidding range based on what everyone else is doing
Monica: It should, however, be largely based upon how you value the letters.
Elba: You need to STILL value the letters carefully on a low/medium/high range, but you must define what low/medium/high is from the market
Neha: Never bid on anything that doesn't help you (ie, don't try to bid to hurt people)

KR: How many of your players will really try to harm opponents in a small game?
(4-5 people raised their hands)

Blake: Being able to adapt to the game will be important.
Yang Jian: Same - having multiple strategies

KR: How many of you have multiple strategies that you switch between?
(about half)
Zach: Our player has 3 strategies, which it switches based upon how many letters we have. We switched based upon an early/middle/late game strategy
Dfed: We are focusing on getting one main strategy to work, otherwise things become much too complex
Neerja: Concentrate on the main strategy. Work on fine tuning various parameters
KR: Yes, for sure - work hard on figuring out how to set each parameter
David: Budget control in 2 player game - make sure that you always have points to rebound as necessary
Daniel: The bonus is very disproportionate, (jumping from 11-12 points to 60+), so it's sooo important to make sure you get a 7 letter word. Spending 30 points for a 6 letter is not OK, but 50 points for 7 letters is good. It's really, really hard to figure out all of the specific corner cases and account for them.

KR: What did you use from last year?
EPK: A priori algorithm
KR: Did anyone rely on last year's strategies, with or without using the code?
Zach: The early/middle/late idea
KR: How essential was it to use last year's players for background?
Eva: We were able to bootrstrap our own discussions
Dan: We already knew a lot of the issues
Zach: It was helpful to be able to play against last year's players as we were developing
Archana: I was in some ways constrained to thinking in previous ways
Dan: It was interesting to read from past group's mistakes

Class notes: 9/22/10

JB will be returning the score and/or word of each player at the end of the round

We did a run:
Dan (g6): We happened to bid 5 for a Q, which we think to be a relatively low bid, then 95 for an E. We are assuming that nobody else will bid high
Daniel: Highest scoring word without 7 letters is 32. 95 is way too much
Blake: Maybe getting something for 0 points and having a huge rack is a good thing this time

Flavio: We have a lot of letters right now, but we've been bidding pretty low. We plan to get as many letters as possible, hoping that we'll eventually get a 7 letter word.

KAR: So what have we learned so far?
Daniel: G1 from last year is really good.
Neha (g5): We have been bidding pretty close to the true value of the word, without thinking about the value to others (we're not getting things).
Zach: Hidden letters form a burden for last year's players, more so than for us
Neerja: We are trying to do more upfront
John: Everyone is driving up the cost of common letters more so than they should be
Eva: We should adjust bids based upon the frequency of letters remaining
KR: But a few people overbidding can still drive everything up

Monica: But some letters may not come up at all in the game
Daniel: An agressive/passive strategy will play differently in a game of different size. We need to take that into account.

KR: In a two player game, maybe you should never bid 0.

David: With 6 hidden letters, people should want different things, so maybe bids will be lower

Monica: Actually, you can pay a LOT now, because you only need 2 letters!

Deliverable for Monday

A player that is robust under these various kinds of configurations.

Final deliverable due at noon on Wednesday.

Class Notes: 9/20/10

KR: Last week we didn't really talk about HOW we should/will/are implementing our strategies. What kinds of data structures are appropriate? Are we happy with what happened last year? What kind of innovation can be made?

Jesse: For any hand of letters, calculate the expected value if you had these letters. You'd need the probability of getting each letter, and of what the cost may be. Use a linear scan, no special data structures
Nitin: In the beginning, compute the list of 7 letter words. Prune out the ones that you can't form with at least 50% of what's on your rack currently. Bid high, low, or medium based upon frequencies.

KR: Let's focus on how, rather than pure strategy.
Neeha: Need to adapt previous strategies to take into account how many bids are left.
EPK: We use the apriori algorithm. We can use this general algorithm to make strategy decisions. The interesting change is that we can look at subsets of our rack, because we can form a 7 letter word with more than 7 letters (rather than assume that all letters on the rack must be used to form a 7 letter word).
Daniel: We use an intersection to create a list of words with 1 A, 1 B, etc, 2 A's, 2B's, etc. We do a linear merge upon the sorted word list.

Zach: We take each word, and if it's possible, rebuilt them into a list of letters, sorted by the letters that they have.
DFed: Each node tells you how many words are reachable from each set of letters. (JB: Take a look at Group 2 from last year, we had this all in a SQLite database, plus some other stats too :P)
Eva: We do this all in a few hundred MB

Lauren: We are doing an intersection of both strategies. We have an alphabetical trie for word lookup at the end of the game, plus apriori to find what is reachable. We assume that we may get at least 8 letters, so that you can drop a letter if necessary.
Dan: Try to look at percentage of words that can be formed overall. Rather than counting the words that ARE possible, look also at the words that are form-able.

We ran a game and:
Andrew (g4): We bid 22 for an E. We did this because we are close to 7, and we really like E's.
John (g9): We bid 12 for a V, and that's because we can form a lot of 7 letter words with (A,I,R,V). Our max bid is 15
Aranchana (g1): Similar to John/G9's strategy here
Monica: We are planning to add more to infer others' bidding strategies
Group 6 bid 68 for an S (bug)

DFed: Everyone should be bidding high on S's because they should perceive that they form more 7 letter words.

KR: Did we learn anything about strategy from this?
Daniel: Everyone seems to be pretty conservative.
Monica: Group 3 took on way too many vowels. Only looked at letter frequencies, not looking at what words can be made.
Nitin: We were supposed to stop after a 7 letter word, but stopped at 7 letters. Try to figure out the value of a high bid for everyone before putting in a high bid.
Flavio: We computed the average score for a letter, but we should have come up with an expected score (using the probability of getting each letter)

KR: What's the next most important thing to get working?
DFed: Coming up with an approximation of a letter's value to other people, to adjust your bid.
Blake: If we do a strategy where we bid more than we really value it for, we can use a sliding "bank" for using to outbid others, limiting the damage.
Neeha: DFed & Blake's strategy sound good.

Deliverables, etc

For this Weds: Fix your bugs, etc. and improve your strategies! Let's see the implementation match the discussion, rather than a "we should be doing X but seem to be doing Y" discussion.

Note that the 27th will be the last discussion class for this project. Final code will be submitted on the 29th, and presentations/write ups on Oct 4.

Using my old SQLite database

If you want to play around with statistics, you should take a look at the seven.db file included in the simulator in src/g2/util. You can access it with the sqlite application (I believe one comes standard on Mac OS X, you can download one otherwise).

There are two tables:
lettercollections:

letters|oc_1|oc_2|oc_3|oc_4|oc_5|oc_6|oc_7|a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z

The first column is the set of letters, sorted alphabetically. Each oc_n column shows how many words occur with those letters of length n. The a-z columns show how many of each letter are in that word.

words:
word|letters|score

The first column is the actual word, the second the alphabetically sorted set of letters, and the 3rd the score you'll get for it.

SQLite supports standard SQL, ex, to find the most common letters in 7 letter words:

pazuzu:util jon$ sqlite3 seven.db
sqlite> select letters,oc_7 from lettercollections where length(letters)=1 order by oc_7 desc;
letters|oc_7
E|16068
S|13216
I|12154
A|12028
R|10727
N|9584
O|9426
L|8664
T|8382
U|6765
D|6627
C|5942
G|5338
M|4941
P|4711
H|4599
B|3996
Y|3298
K|2718
F|2563
W|2285
V|1623
Z|760
X|629
J|577
Q|360

Class notes: 9/15/10

We did a run, here's what happened:

Zach: Group 7 is bidding rand(0,20) for every letter.
Nitin (Group 4): Bids based upon the frequency of getting new 7 letter words
Shishir (Group 2): Calculate an average best-case points for using the letter, then bid it
Neetha (Group 8): Tries to bid a lot, but is underbidding relative to everyone else
Lauren (Group 3): Bid 1 by default. Bids more if it will give us a 7 letter word, plans to increase bidding to just overbid other people
EPK (Group 1): Multiply the face value of the letter by 3
Aditya (Group 8): Focus on letters that are frequent in words. When it's an uncommon letter, put out a random bid

KR: If you aren't bidding high and others are, should you be worried?
Daniel: No. The high bidding players will lose all of their points, while the low bidding players will do OK
Nitin: If there were very few players, the agressive bidder will prevail
Aniket: Conservative players will miss out on the letters they need
Dan: Eventually market values will go down, and the conservative players will prevail for their low investment

KR: What did we learn from this round?
Archie: It's OK to be offensive, as long as nobody else is.
Monica: There are other ways to be offensive, ex, bidding high early on OR just randomly bidding high to block others
John: You should decide when to be agressive based upon how many points are left/where we are in the round. If we are later in the game, then you'll probably pay less (via the Vickrey system)


KR: How does the Vickrey auction fit in with this all?
EPK: There's no advantage to bidding high if others are. Just let them pay as much as they want.
DFed: The value of a letter for each team is not really knowable if there are secret letters. In the relatively short period of time that this game runs on for, it's hard to guess what people might bid. Just bid whatever your own value is, plus some perturbation perhaps.
Neeha: How high you bid should also depend on your present score - you don't want to run out of points
Andrew: For a micro-strategy, still value letters after you have a 7 letter word, to bid low and prevent them from getting anything (or at least making them pay)
Archana: Should keep a history and infer the strategy of other players. Realize that if someone needs an A, avoid it, realizing that it will be cheaper
David: When we track bids, we're too conservative, because we are including stingy player.
Jesse: Nobody wants to waste the points to try to block someone else, because maybe someone else will. Limit blocking to small games only

KR: It might be a good idea to focus on our own strategies before working on counter and counter-counter strategies
Neeha: To really block other players, you might need to get 10-12-15 letters, and it will be costly
Aniket: Use a progressive bidding strategy, valuing letters more as they become less available
DFed: There will be deflation over the course of the game, so you should keep bidding something as you keep going

EPK: Should we bid based upon how many points we have?
Flavio: No, look only at what you spent so far on that word.
Monica: But if you have 60 points and everyone else has 100, it's worth trying to catch up.

KR: What about simulating your strategies... run them in parallel then decide which one to use

Neerja: Focusing on countering someone else always gets you into trouble
Daniel: If you are very close with someone else, you SHOULD try to kill them, if everyone else is far behind, because it won't really sacrifice your ranking
Archie: Separate tactics from strategy: Strategies are long term, but within a game you might have multiple tactics
Pilunchana: You might think that your bidding is high, but it might not actually be relative to others


Deliverable for Monday:
Revised player that is correct (doesn't claim it has letters it doesn't), and does something smart (doesn't just bid random, etc)

Class Notes: 9/13/10

Remember to register for the course if you haven't.

Project 1 Introduction

Q/A:
Daniel: Are letters carried over between rounds?
KR: No
Zach: If rounds are independent, do the number of secret letters remain constant?
KR: Yes
Jatin: How are starting points associated with the number of secret letters?
KR: You always start with 100 points no matter how many secret/starting letters you have, but in each game everyone starts with the same number of letters.

KR: What do you think were some important ideas identified last year?
Elizabeth: Using a strategy that values letters based upon how others are bidding as well.
Jesse: Valuing a letter more if it kept paths to getting 7 letters high
Aniket: Integrating the history - remembering that if it was hard to get an A before, it might be hard to get an A again
Monica: Microstrategies are helpful in creating refinements vs. a monolithic strategy

KR: Remember that you have access to last year's players. This can be good, or it can be bad, depending on how they were written and what you plan to do. Remember that if you take last year's player, tweak a few parameters, and submit it as yours, you will not be evaluated as highly as a team who brings in new, fresh ideas. Taking someone else's code as a starting base is fine, but make sure to implement NEW functionality as well, which you can clearly attribute as your own work.

KR: What else was interesting from last year?
John: Preprocessing over the wordset (offline)
Flavio: You also need to have something fast online (ex, the apriori algorithm)
(JB: paper here, Ben's original code here, original comments from Ben: "The ScrabbleMiner file has a demo/test program that builds the data structure and then looks up the set of letters passed on the command line--the other two have the actual logic.  The rest of the code has fewer comments than it ought to, but isn't *entirely* incomprehensible, I hope.  If you want to comprehend it in detail, the attached paper would probably be helpful, though.")
Yang-ziah (sp?): Some players gave a bonus for getting a letter that would complete a 7 letter word (typically 15 points). Also important to track letter frequency (as it decays from the starting scrabble frequencies)

KR: Remember, I strongly prefer that you are not using laptops during the class, unless you are, ex, submitting your code so that JB can run it, or doing something very very necessary (JB: Don't bother taking notes at all except for maybe jotting a few reminders to yourself, just read mine).

Monica: Data management was super necessary, ex, removing anagrams from the dictionary
Eva: Using a loss-based strategy - sometimes you should bid high just to block somebody else from getting something
KR: That wasn't that useful last year actually. Could it be more useful this year?
Neha: Since we have an unlimited rack size, even if we won a letter we didn't want, we won't get killed by it
Pranjal: If we've already gotten our 7 letter word, bid to block others (or make them pay) instead of bidding 0
Zach: You might still end up winning and losing points
Lauren: If you're in a small group of players it might be useful still, or if you are ahead by a lot.
Dan: Will we know how many rounds we are playing?
KR: Yes - it's 8p
Dan: Actually, if you are behind, you might want to take some risks. KR - Or, have a "meta strategy" to say "am I doing well?" and if not, "do something different
DFed: You might be losing a lot to get these letters, because if someone really needs them, they'll bid high
Nitin: If there are no hidden letters, you have perfect information, and you can stop it. And you should. If there ARE hidden letters, then you can only approximate if you are blocking a 7 letter word.
Elba: Alternatively, have a micro-strategy that changes when anyone gets 7 letters
Archy: Is "winning" by total points or total wins? KR - Total points. Archy - So don't always win, just do above average
Jatin: Maybe you should just always bid high at the start, since you'll be the only one taking this risk
Blake: This could be very, very bad if someone else does the same!
Aditya: In the first round, if people re bidding a lot, then hold out and wait to see who does what.

KR: What are some important differences we should look at?
Andrew: Sniping may not be as effective this year, since there will be more and more letters. The premium to get the 7th letter may be lower
Daniel: Hard to do a lot in 1 second
Bo: Pay more attention to other people's bidding and create strategies based upon that
Yang-ziah (sp?): Should focus more on ourselves

KR: How big a deal is it that there are more letters possibly?
Neerja: Do all of the letters have the same # of points? KR - No, they are scrabble scored.
Archana: These extra letters force you to bid more points
Claire: Different strategies for different games (2/3/4 etc person games)

Deliverable for Wednesday:
Submit a player. It doesn't have to be great. It doesn't have to win. It shouldn't crash, and it should have something that is building towards a final strategy.

Please make sure to name your players in the package:
seven.f10.g<groupnumber>.<yourplayername>

Project 1 Teams

Name	Group
Elizabeth Kierstead	1
Archana Balakrishnan	1
Blake Arnold	1
Lauren Pully	3
Elba Garza	3
Dawei Shi	3
Andrew Shu	4
Neetha Sebastian	4
Flavio Palandri Antonelli	4
Nitin Natarajan	4
Neerja Pancholi	5
Neha Srivastava	5
Jesse Bentert	5
Dan Iter	6
Pilunchana Kiatruangkrai	6
Yang Jian	6
Eva Sitaridi	7
Zach Sheppard	7
Dan Federman	7
John Graham	9
Daniel Wilkey	9
Monica Ramirez-Santana	9

Project 1 Simulator Available on CW

Please find the simulator for project 1 available on CourseWorks, with some brief notes on running it and implementing your own player on google code.

Getting started with SVN and Eclipse

Some people come into this class and haven't ever used SVN (or another version control system). With the super-fast deliverable schedule and intense team collaboration, you'll need to use a system for sharing your code with each other and managing revisions. If you've never done this before, take a look at this tutorial on using google code, eclipse, and svn for tips on getting started. If you get stuck, feel free to shoot me a note.

Update:
Some platforms don't have native SVN libraries available for subclipse to use:

If you are using a 64bit windows platform, you may need to install this:
http://www.sliksvn.com/en/download

If you are using a 64bit Mac platform, you may need to install this:
http://www.open.collab.net/downloads/community/

Welcome to PPS!

Welcome to the TA Page for the Fall 2010 edition of Programming and Problem Solving - Columbia COMS 4444.

First, about me: My name is Jonathan Bell ("Jon Bell" or "JB" most commonly). I'm a first year Master's student here, but did my undergraduate here and took PPS last year. As an undergrad, I specialized in the "Applications" track. As an MS student, I'm in the "Systems" track. I've interned at Sikorsky Aircraft (in CT), Codestreet (here in NYC), and have been working here for the Dean running and creating various software systems for the school. As of this summer, I have also become co-founder and CTO of RentPost, an online tenant-landlord relations system focusing on rent collection. As an undergrad I worked with Residential Programs for two years as a Community Adviser, creating programming for the 500 residents in the buildings that I oversaw. In my downtime, I enjoy cooking, riding my bike, and taking pictures. It's very poorly maintained, but I do have a flickr.

I'm very excited to be TA'ing this course: it was my favorite course by far last year, and probably top 2-3 courses ever. I've done my best this summer to get the simulators for this term's 4 projects (and make them as bug free as possible!) but please let me know immediately if you believe you have found any bugs or have any problems. I have created a Google Code as a repository for the simulators for your convenience, should we need to update the simulators. I will, of course, also be posting exports of the simulators on CourseWorks as well.

Contacting me:
I will be holding office hours tentatively on Mondays from 11:00-12:00 and Wednesday from 2:45-3:45 in 6LE1 CEPSR - the Programming Systems Laboratory. These hours are subject to revision within the next few weeks. I'm typically around campus a LOT though, so please feel free to ask to meet at another time. I'm available by email, at jbell at seas dot columbia, Jabber (GChat etc) at jon at jonbell (dot) net, or AIM at jonbellhasnoh. If you're stuck with something and want to just ask me a quick question, don't hesitate to ping me on GChat or AIM. If I'm busy I'll let you know, but more than likely I will be able to help you if I'm around.

I hope you enjoy your semester!
Jon