TA’s word.

My name is Satyajeet Shaligram, and I’m the TA for PPS Fall-09. I’m a Master’s student at SEAS specializing in software systems. I took this course in Fall-08 and had a fabulous time ‘programming and problem solving’. I had the chance to work with some really amazing people and on four really cool projects. This year there are four new projects, and I’m sure you’ll have just as much fun as I did. But beware,  this course

is easily one of the toughest ones you’ll take here at Columbia and will require you to put in your 100%. This page will have updates on teams, simulators, projects and so on. You may write to me with doubts or questions at: sss2171@columbia.edu

Best of Luck,

Satyajeet.

28th October Class notes

Deliverables:

1. No extra mazes. (But you’re welcome to)

2. A player that does something to optimize the score.

Fully connected maze: Why?

Ben: Its easy to solve. No self loops.

Laima: This graph is easy because the chances of ending up in the new room are less.

Self loops are going to cause headaches for you.

Smriti: Self loops make it easier since you can discover them more quickly.

Colin: It makes no difference except the number of steps it takes to discover them.

Colin: on a fully connected graph a random traversal will give you a lot of coverage.

A monte carlo approximation allows us to calculate how well we could do with just a random traversal.

G3 map:

Is random traversal likely to work in general?

How many runs would you want to find out the reliability of your player?

Variance is map dependent.

Ben: Its an interesting map. Extremely low probability of making it to the treasure room or the shortcuts.

Monal: Too many deadends.

Self loops:

Shilpa: It wastes one turn from the number of turns that are available to you. They leave you at the same place, plus you dont increase your score a lot as well.

Dan: Self loops keep you local. Dont take you too far.

What could you do on this map with 10 objects?

Shilpa: If you’re lucky then the number of objects does not matter.

Jon: The connectivity is local, so there is high chance that you can map a fair bit of a small area (for which you do have enough number of objects)

Nipun: It depends on your strategy.

The number of moves will be atleast be (number of nodes x 10).

Dan: Every strategy is essentially random in some way.

g5 map:

Not quite fully connected.

Colin: Is there a way to maximize the variability of 10 numbers…basically the door sequences.

What if we had a large number of objects? Say equal to that of the number of nodes.

Jon: We generally are conservative, and hence we might not drop all the objects

Colin: There are some similarities between explorandum and maze.

Here you are competing for time, while there you were competing for place.

 

Project-3 Teams & 21st Oct Class notes

Deliverables for wednesday:

1. Submit a maze (based on the simulator specifications)

2. Come up with a player that does something interesting (Moving around, updating data structures etc).

The professor started of with a brief description of the original Adventure game of Crowther and woods, which provided the inspiration for this project.

[Class discussion about the project specification]

Group-1: Danny, Sean and Stuart.

Group-2: Jon, Green and Laima

Group-3:  Shilpa, Colin and Nipun

Group-4: Smriti, Ben and Yang

Group-5: Sharadh, Manuel and Monal

What would you do if you had just one object?

Manuel: Drop it as soon as possible.

Ben: Drop it in the start cell.

Jon: Establish the path into the start cell.

Green: Advocates dropping it in the start room.

Yang: Drop the object second room, since it gives you more information as its outside the scope of the exploration.

Ben: If you are exploring, its always random. You have no information unless you id both the ends.

Manuel: If you establish a cycle between 2 rooms you have some concrete information about the maze.

Colin: Start discovering lots of cycles – in order to avoid them in the future.

Can you merge the information about cycles?

Smriti: You have more information from cycles about the rooms that do not lead to the treasure room. (A way to eliminate doors)

Laima: If you drop objects in a sequence, then you can – as you traversing the room – start putting in label on the passages.

You can get some locality information by eliminating all possibilities in terms of passages from a particular room.

Sharadh: The length of the cycle is not going to be proportional to the actual number of steps that you have taken to get there.

Jon: There is a high chance of staying at the same place if you have a sparse graph.

What kind of data structures do you need?

Nipun: Its important to have both the history of the graph and the passages. It depends on the number of objects that you have at your disposal.

Do we need to fully reconstruct the graph to do well on the game?

Laima: If you dont have good information about the graph you will spend more time just going round and round without any gain.

How is the mapping going to slow you down? Can you come up with a graph where random exploration is much cheaper than systematic exploration?

Smriti: Use a strategy that uses pseudo-random exploration for the map.

Sean: You have no information to say that there are infact in self loops.

Shilpa: If there are no cycles then random will be advantageous over systematic.

Sharadh: Bigger cycles are just as much a problem as smaller cycles.

Colin: You can minimize the number of cycles in the first 10 turns, and then use that information later.

Green: Have some objects in reserve so that in case you discover a cycle you can use the additional objects to fully explore that cycle.

Sharadh: But you may not be able to collate the information until you get back to the cycle. So there is a trade-off or balance involved in making the decision about the number of objects in reserve.

Nipun: Explore a local area with all your objects, and once you are done – pick all of them up and move on to a new area.

There are infact many different trade-offs involved.

Ben: You could be many moves away but you may still be in the same locality of the maze.

Project-3 Simulator

1. Download the simulator from courseworks and create a New Java Project in Eclipse using the unzipped file.

2. Simulator code resides in maze.ui package, and your own players need to reside in their own packages as usual. Use the convention “maze.g4.Playername” as is the norm.

3. The rest of the simulator is fairly easy to use, and given how great UI development in Java Swing is, there are bound to be some quirks. On the other hand, if you notice a bug – either in the UI or in game logic please let me know and it shall be fixed right away!

Class Notes 14th Oct

People tend to bring personal experiences to the puzzle solving experience.

Laima: Its important to use the correct instructions and terms to help direct the users to the task correctly.

Danny: Obscure hints are good. It will help to keep them on the right track and yet keep things difficult.

What generic instructions do we need to give the puzzlers?

Colin: The word pattern needs to be used instead of puzzle. We could say find the patterns in the image.

Sharadh: Tell them that the pattern has a meaning, which is where the puzzle comes in.

Ben: Use a reference puzzle, and describe the kinds of things that you are doing – ‘puzzles may include but are not limited to..’ wording.

Nipun: Something about the grid? Tell them what the grid is?

Shilpa: Tell them that the puzzle could be anything from general knowledge to math. Need to provide some kind of context.

Green: Shapes? Graphic objects? Also that patterns may be multiple colored?

Laima: Use words like pictures, text, (Jon: Icons..)

Colin: I like Sharadh’s definition of puzzles with deeper meaning

Nipun: Don’t mention domains like GK, math etc. Instead just mention that there are text, shapes and pictures – which could have higher meaning and just finish it at that.

Monal: We could say that puzzles could consist of other puzzles.

Danny: Give a sample puzzle, with the solution to help people via example.

Many people liked Danny’s idea. Some disagreed.

Monal: Just one small image with one of the images from the original ‘Gal’ puzzle.

Laima: This might bias them, and it will affect their judgement and it affects the criteria by which we rate our puzzles.

People will rate puzzles based on their enjoyment.

Green: Training is a good idea, and it prevents the first puzzle being shown from acting as a training sample for the puzzles that follow.

Many people agree that Gal’s puzzle is a good sample puzzle.

Green: There are 2 categories – 1) arithmetic progression (with meaning) and 2) images (no additional meaning)

Nipun: Give an entire sample puzzle.

Smrithi: Smaller puzzles are easier to find.

Class Notes 30th Sep

The puzzles in the image are:

1. Secret
2. For Gal
3. Pi
4. XIII
5. My Uncle in Hebrew
6. Blue blobs = Water drops
7. Planets
8. Colors of the rainbow
9. GAL in morse code
10. Ken
11. The number 13
12. The family tree
13. Beethoven’s

Which of the puzzles did you think were appropriate?

Laima: It was easy to find  things like 13 and GAL since there was a reference.

People will not have context information, and hence how we deal with that is going to be important.

Sean: People will be inclined to find localized clusters of puzzles as opposed to something which spans the entire grid.

The background is very important, since it can confuse the onlooker.

Smrithi: Writing numbers and letters is a bit confusing since an I can look like a 1 and so on.

There is no obligation to follow a particular model, for example in the puzzle given here.

Jon: Some colors stand out better than other.

You have an option for choosing from the entire RGB palette.

Ben: Color blindness is also an interesting thing to watch out for.

Yang: Color blindness is not absolute, certain times there is just a difficulty to separate certain colors.

Shilpa: Black and white has a lesser capacity to hold puzzles.

A metapuzzle in the image is the 2 black dots that help us identify existing puzzles in the diagram.

Jon: There is trade off since with more colors you can have more puzzles but then it can always get confusing to have so many colors.

Laima: You can recruit people to analyze puzzles for them.

As you design the puzzles you will not be objective. So find others who can give you second opinions.

You can prefer to work in the CMYK color space since it has a nice separation, better compared to RGB.

Use the book by Tufte since it outlines principles of conveying information in an effective fashion.

Nipun: Size of the puzzle is an important factor since its easy to see bigger puzzles.

Laima: Looking at a distance and looking closely are 2 ways of solving different kind of puzzles.

Nipun: You can assume that puzzles are generally spread around the image.

Sean: Its a good idea to spread out your puzzles evenly.

Ben: Big lines give you a nice reference point to start looking for puzzles in the image.

Sharadh: Black lines can draw your attention to them, and it makes it easier to notice puzzles.

Most people agree that having a scaffold in your image/puzzle is a good idea.

You should have a balance of difficulty in your puzzle.

Nipun: Contiguous cells is a good way of finding puzzles.

How much value do you put on finding, and solving the puzzles? Finding can be easy and solving can be made difficult. Or vice versa.

Manuel: Finding should be easy so atleast you know what you trying to solve.

Shilpa: Finding some puzzles is the same as solving such as the secret word SECRET.

Monal: It depends on the kind of puzzlers you have available. So some times finding it can be a challenge for someone who cant solve it.

Green: Any pattern can be a puzzle. So looking for them depends on who hidden these patterns are?

Danny: To have some meta information about a puzzle is helpful.

You can use any common knowledge that can be expected of people. (Lay people).

Shilpa: In addition to the puzzle you give the puzzler a context for the puzzle.

Project-2 Teams

Deliverable for Monday: Project-1 presentation

Deliverable for Wednesday: A simple player that embeds a single puzzle.

Group 1: Jon, Nipun & Zang

Group 2: Danny, Shilpa & Smrithi

Group 3: Sharadh, Ben & Green

Group 4: Colin, Manuel & Sean

Group 5: Laima, Stuart & Monal

Project-2 Embuzzled Simulator Setup

Setting up Embuzzled is fairly simple and the steps are quite similar to those for the previous project. Just download the simulator from Courseworks and Setup a new project in Eclipse using the downloaded source code. You can refer to the tutorial for how to create your own player, and how to use the simulator.

Class Notes 28th Sep

Tournament Discussion:

Students suggested a bunch of maps for the tournament such as:

Large Islands 3, [8]

Bridges 5/10,[5]

“no water” 3, [5]

Small Continent 5, [9]

Temple of Doom 8 [3]

Beach Island 8 [2]

Students also suggested some of the features that they wanted for the unseen maps.

Unseen-1: tunnels, bridges, maze structures, range of 30,

Unseen-2:

The tournament results will be displayed in batches.  The tournaments will also have lots of permutations to make sure that there is no bias for a particular player.

Gray team seem to have a good cleanup strategy at the end.

Sharadh: The way you encounter footsteps is important.

Green: You may have a strategy that has a bias towards certain directions and this becomes obvious for certain maps. And in such cases the starting locations will make a difference.

Most players seem to have similar strategies.

Sean: Most of us are using some function that gives us a measure of openness.

Shilpa: Because we had last years code to look at, hence I chose to extend those ideas instead of implementing a radical strategy.

Sharadh: It was good to have previous years players to test against.

Nipun: Having last years code meant that we tended to think from a slightly narrow mind.

Monal: We wanted to compete against last years players, hence we avoided being too experimental. Since we were biased towards doing well in the tournment.

Colin: Group dynamics also has something to do with the way we take decisions. Someone could easily have come up with the idea inside a group.

There is always an incentive for coming up with a brand new idea, since its something that you get complete credit for.

Certain groups like to discuss mechanisms (How things need to be done?) and certain groups who like to discuss policy decisions (What needs to be done?)

Manuel: We started off without the openness function, but since we value the same things – we end up doing good as well.

Green: We could try and find patterns for the maps we know shall be in the tournament. (Not recommended since this does not seem so interesting from the point of view of reports/class grading)

Nipun: Too many footsteps makes it difficult to use the footstep information and can even lead to behavior that is not so advantageous for the player.

How to run tournaments for Explorandum?

Running tournaments for explorandum is fairly simple. Firstly you will have to RUN the tournament class instead of the gameEngine class. In order to do so, just select RUN CONFIGURATION and change the main class to “explorandum – tournament”.

Now just like the gameEngine class, this class also needs command line arguments which need to be provided from the RUN CONFIGURATION setting. In order to do so, just go to the tab titled ARGUMENTS and where currently you have something like:

“explorers.xml” gui

You should change that to follow the following format:

Tournament <config file> <board> <range> <num rounds> <num games>

where the variables all have appropriate meanings. Also sometimes you might get an error because the simulator is unable to find the board.xml in which case just copy the desired board to the root of the project (The “Explorer” folder)

As always, you may email me if you have any problems running this.

Class Notes 23rd Sep

CLASS ANNOUNCEMENT:

Final presentation for project-1: 5th Oct 2009.

Final Code Submission for project-1 deadline: 29th Sep 2009 7pm.

Final discussion class: 28th Sep 2009.

23rd sept Class notes

Its helpful to have a general loop detection strategy since with complex strategies its expected that you

You should be able to justify magic number. As such you should have a good explaination for why you chose a particular number or parameter.

Shilpa: Keep track of the step count for each cell. And if these are in arithmetic progression then its an indication that you are stuck in a loop.

Team1: Look for a coast unless you run into many footsteps in which case it will move randomly.

Team2: Emphasis on trying to find new territory.

Monal: You should try and claim water right away.

Jon: If the water is the outside coast, then you should continue exploring it.

The coast is a very big payoff.

Finding the edge of a map? How useful is it?
– High payoff for the water at the end.
– you might be able to find tunnels that lead you to new territory.

One heuristic is to just circumnavigate the map by using one edge of the coast/border.
This can be overwritten for short term gain.

Green: What happens if your range is low?

Jon: We try and find open spaces and move towards it.

Moving in a spiral is a slow way of trying to go to the outer regions of the map.

Green: Pick a random direction and then continue to walk along that direction.

Laima: You can revert back to the south, when you realize that it is now available for traversal.
[South being the original random direction that was chosen]

Ben: Pick 2 directions and alternate between them in order to move along the general direction that you wanted to go in.

Jon: If we see footsteps then we will not hug (double hug).

Ben: Else move one cell inwards and move along the coast. But why not move to someplace completely new.

Green: Even the half that you are getting, might not be completely claiming it since there could exist mountains.

There is a gamble involved since you are giving up a known score (coast) against something else.

Group 4: We know that we are stuck. Its difficult to predict where

Group 5: Add footstep detection to SynDiego where footsteps are used to modify the openness. The openness estimate is now more accurate since all the cells that have been seen [based on footstep] by someone else are decreased in value.

How many of you think your players are competitve with last year’s player?
[3 groups raised their hand]