CSc 244

Project 2 -- Queen's Lament
Due: Tuesday, February 17, 2004

Objectives

To implement, compare, and contrast local search algorithms

Your Mission

In this project, you'll apply several local search algorithms to the n-queens problem, where you try to place n queens on an n X n chessboard in such a way that no pair are in the same row, the same column, or the same diagonal. In class, we saw how several local searches could be implemented for a specific n, say n=4 or n=8. You'll be testing your code to see how well the algorithms perform over a wide range of n.

The Details

You are to implement the following local searches:

Hill climbing with random restart.
Simulated annealing. You will have to come up with a suitable way of mapping time to temperature.
Local beam search. You may experiment with the value of k=the number of states you keep in memory

For the purposes of this project, we will say that a valid state is any chessboard where there is 1 queen per column. That way, you can use the same successor function that we used in class; namely, that a single queen can move anywhere in her own column.

For each search, your agent should be able to take a size n as input (the size of the board). It should then be able to create an initial random valid state and use the search to locate the goal. Your agent should then output the number of moves it took to reach it. Note that for local beam, there will be k moves per generation.

Which is better?

Once all three searches are working, run tests to compare the effectiveness of the three algorithms for various n. To do this, start n at a small number (4 is good), set a fixed k for local beam, and find out the average number of moves it takes for the three searches to find the goal at that n. (You should run each search a fixed number of times to find an average.) Then, increase n by a predetermined amount and repeat. Remember, as n goes up, your algorithms may get "stuck" on local maxima/minima. Hill climbing may keep restarting, simulated annealing may stay in a current state seemingly forever if the probability of accepting a worse state gets really low, and local beam may not get enough diversity in its states to break out of local maxima/minima if k is picked badly. So you should also have a way of stopping the search in case it takes too long (say, 1 minute). We'll call that a failure. Once you've reached an n where failures are common, you should stop. That probably won't happen on all the searches, though. Run the experiment on enough values of n to be able to estimate its general behavior.

Once you've collected your data, display the results as a graph with n on the horizontal axis and the average number of moves on the vertical axis. Answer the following in your write-up:

Is one of the searches clearly more effective than another? Why or why not?
What value(s) of k worked best for local beam search? Does it depend on n?
What temperature mapping(s) worked best for simulated annealing? Does it depend on n?

Grading

This project is worth 50 points. I'm looking for:

correct implementations of your search algorithms
prudent discussion of your test results in your writeup

I'm not looking for:

mistakes or inefficiencies in the design of your code. This isn't a programming class, after all. However, if an error is so egregious that I catch it anyway without even looking for it, points may still be deducted.

Please hand in both an electronic copy of your project on BlackBoard and a paper copy.

Administrative statement

Programming assignments, like homework assignments, are individual projects. I encourage you to talk to others about the general nature of the project and ideas about how to pursue it. However, the technical work, the writing, and the inspiration behind these must be substantially your own. If any person besides you contributes in any way to the project, you must credit their work on your homework. Similarly, if you include information that you have gleaned from other published sources, you must cite them as references. Looking at, and/or copying, other people's programs or written work is inappropriate, and will be considered cheating.

Return to Project Index