Traveling Salesman Problem

For this problem, you will be given some number of cities (N > 100) that must be connected by a route. The cities will be embedded in a plane, and the route must pass through each city exactly once, and must start and end in the same place. For more information on the traveling salesman problem, start here.

Write Up

Your write up should include:

1. Information about your baseline method (something naive-it can be the same as the one I used)
2. What you did to improve this method--this should include a well reasoned argument for why you think your new method will do better. Larger groups are expected to try more / more complicated approaches.
3. A discussion of the results, with charts where appropriate. I expect you to show how the method you implemented compares to the baseline. You should also show how they scale for larger problems. Your method doesn't have to do better than your baseline, but if it does worse you should explain why.

Interface

√Your program must take as a command line argument the name of a text file of x y coordinates separated by a space (each pair of coordinates is on its own line) and an output filename. Your program should read in this file and output a file in the same format with the cities ordered. Programs that don't produce a solution within the time limits will be disqualified from the competition.

Wumpus 2: This Time It's Personal

In this game, you have to find a path to a solution node in a graph. The goal is to find the shortest path to the solution. However, this is complicated by the fact that certain nodes are gates: your agent may only pass them if the agent posses a key of the same color.

Each pair of agents in the class will play 100 rounds in pairs. Each turn your agent may: move to a new node, and initiate a trade with another agent. The entire graph is searchable from any point.

Each time you move to a new node, you may propose one trade. Each trade may involve any number of keys for any number of keys. Each agent may decide whether they intend to actually follow through with the trade--agents may defect, choosing to not give the other agent the key. There is also a 2% chance a key will be lost each time a trade happens.

Interface

The players and the driver for this game will communicate over standard input, so simple scans and reads should be sufficent. The driver will write out the phrase "Start graph", followed by a series of pairs of strings seperated by spaces, indicating the edges, followed by "End graph". This will be followed by the keys in the format "Start keys", and then a series of numbers, where the nth number represents the number of the nth key the player posses (so the sequence 2 3 means the player has two of key one and three key twos.)

Once this information gets sent, agents can write the following strings:

Move nodeName
Trade keyOffered keyDesired (Cooperate | Defect)
Respond (Cooperate | Defect)

Agents may only propose one trade per round. They may also recieve messages of the format "Trade keyOffered keyDesired", too which they can issue a "Respond" message.

Report

You will be excepted to explain your strategy. You should explain your strategy for searching and your trade strategy, as well as if you are doing any opponent modeling.

Mastermind

Mastermind is a classic guessing game. One player (the "chooser") chooses a "secret code" and the other player (the "guesser") must guess the code within a certain number of guesses.

In the standard version of the game, the code consists of four pegs ("code pegs"), each of which is one of six different colors (white, orange, yellow, red, blue, or green). For each guess, the guesser chooses four pegs of these same colors. The chooser then gives feedback on the guess, using smaller red and white pegs ("key pegs"). One red peg is given for each correct color that is also in the correct location; one white peg is given for each correct color that is in the wrong position.

The game can be made arbitrarily more difficult by increasing the number of code pegs and the number of colors. Your job is to write a Mastermind guesser that can play any size game.

There are a number of different strategies that can be applied to reduce the number of guesses required to guess the code. The Wikipedia page on Mastermind gives a simple six-guess strategy (which always finds a standard mastermind solution within six guesses), and a five-guess solution by Donald Knuth. The five-guess approach exhaustively enumerates all of the possible codes, eliminating those that are inconsistent with the answers (red/white pegs) received so far. It then chooses a guess with the highest "minimax" score -- in this case, the guess such that [the minimum number of possibilities that could be eliminated by any of the possible red/white answers] is maximized. This sounds a bit confusing but it is relatively straightforward to implement.

Of course, this five-guess strategy isn't at all scalable: as the number of code pegs and the number of colors grows, the complexity of this approach increases dramatically. In fact, Stuckman and Zhang showed that the "Mastermind Satisfiability Problem" (choosing a set of guesses that taken together will determine the code unambiguously) is NP-complete (i.e., presumed to have a complexity that grows exponentially in the number of code pegs and colors).

The 1981 SIGART article by Rao gives a heuristic algorithm that seems unlikely to be optimal, but which would probably work for any size solution. (Whether it would scale efficiently is another question...)

Here are three simple strategies that aren't very scalable, but will always work:

Exhaustively enumerate all guesses, and try guessing each possible code, in lexicographic order, without paying any attention to the red/white peg responses. This method will take no more than c^p guesses (where c is the number of colors and p is the number of code pegs). Not very good, but it's a starting point.

Exhaustively enumerate all guesses, and try guessing each possible code, in lexicographic order, skipping any codes that are demonstrably inconsistent with any previous red/white peg responses. This will be at least somewhat better than strategy #1.

Use your first c-1 guesses to guess "all reds," "all whites," etc. - one "monochrome" guess per color, for all but one of the colors. At that point, you'll know how many code pegs there are of each color (namely, the number of red pegs associated with each guess). You don't need to actually guess the last color, since that color must have however many red pegs weren't allocated to other colors. Once you have this information, you can start generating only combinations that are consistent with the known color distribution. This approach has lower complexity than the first two strategies, since it "narrows in" on the right colors more quickly, and does less checking against the red/white responses. (Rao's approach is somewhat similar in spirit to this strategy, but adds other constraints to make it more sophisticated.)

These might be good starting points when you begin your implementation, as baselines to make sure you can get something working, and against which you can compare the performance of a more sophisticated strategy.

Points will be awarded based on how scalable your strategy is. All projects will be tested on a standard mastermind board, and the less guesses it needs to solve the answer, the better. Extra credit will be awarded on class rankings.

Report