such that the teaching assistants can test them. It is not allowed to use code supplied by others. If we suspect plagiarism, the exam committee will immediately be notified!
Rules for submission
Grading Every session is graded by the teaching assistants. The grade of this lab assignment will count for 15% of your final grade. Note that the deadlines are strict: we subtract 2n−1 grading points for a report that is n days late.
A classic problem that lends itself for local search algorithms is the N-queens problem. In the first programming assignment, we try to tackle this problem using hill climbing, simulated annealing, and a genetic algorithm.
Download from Nestor the file nqueens.c. This file is the starting point for this exercise. The program uses a complete state algorithm, i.e. N queens are placed on an N × N chess board, one queen per row. We introduce the rule that a queen can only move horizontally within her row. The state is represented by the one-dimensional array queens. The number of queens is stored in the variable nqueens. We do not consider cases with N > 100.
#define MAXQ 100 int nqueens; /* number of queens: global variable */ int queens[MAXQ]; /* queen at (r,c) is represented by queens[r] == c */
The state is encoded as follows. The queen that corresponds with row r is in column queens[r]. Note that the rows and columns are numbered 0..nqueens-1.
Some functionality has already been implemented for you. Before you start, study the code in nqueens.c. Compile the program as follows:
gcc -Wall -o nqueens nqueens.c -lm
Implement yourself the hill climbing algorithm from the textbook. In the hill climbing process, you will often get in the situation that several neighboring states evaluate to the same best value. In that situation, you may choose randomly between the best choices. You can use the standard C-library function random() for this. This function returns an integer random number that is at least 0. So, if you want to choose a random value from the integer interval
[a,b), then you can do that by using choice=a + random() % (b-a).
Note that the random generator random() is a so-called pseudo-random generator. For every invocation of the program, the sequence of ’random’ numbers generated by random() is the same (but appears to be random). This is quite convenient, when you are debugging your program. However, in the ’production phase’, you want more random behaviour. You can do this by ’seeding’ the random generator with some initial value. A standard trick is to use the cpu-time (which will be different at each invocation of your program) as the seed for the random generator. You can do this with:
srand ((unsigned int)time(NULL));
Once you have implemented the algorithm, answer the following questions.
T(t) = ...
Here, T denotes temperature and t denotes time. As a first try, you may choose a linear function. What is the effect of this function on the quality of the algorithm? Implement your function in a C function called timeToTemperature(). Motivate your choices in your report.
Which of the three methods (Hill climbing, simulated annealing, and genetic algorithms) works best for the N-queens problem (for varying values of N)?
Nim is a simple two-player game. There exist many variations of the game. In this lab, we consider the following variation. We start with a pile of n matches, where n ≥ 3. Two players, Max and Min, take turns to remove k matches from the pile, where k = 1, k = 2, or k = 3. The player who takes the last match loses.
For example, consider a game with initially n = 7 matches. Max starts and takes two matches, so there are 5 matches left. Next, Min takes 3 matches, leaving 2. Now, of course, Max takes 1 match, and Min loses.
Make a negamax-version of the minimax algorithm that returns pairs (move + valuation). Make sure that your program plays the same strategy as the original program. Include the code in your report.
Extend your program with a transposition table (see textbook, Section 5.3). You may assume that the game is not played with initially more than 100 matches. Run the modified program again for n = 50. Did this help? Include the code in your report.