Local Search Lab

Introduction

In this lab, you will construct a hill climber that will solve the NQueens problem. This is a well known problem where n queens are placed on a Chessboard where no queen can “attack” another queen. Queens can move horizonally, vertically, and diagonally for any distance.

Files

• SearchProblem.py a abstract class (well, as close as you can get in Python) that represents a search problem. Based on work from AIBerkley.

• nqueen_hillclimber.py (UNFINISHED) Implements the NQueensProblem class, which includes code to compute the conflicts (heuristics function), successor functions, and goal state tests. It also includes some code to plot your results.

Instructions

Gradescope

Complete the local search lab in Gradescope first, which discusses the size of the state space for this problem.

Argument Passing

The code in nqueen_hillclimber.py contains the function parse_arguments. This function utilizies python’s ArgumentParser object. It defines a command line argument named nqueens that can passed in to specify the dimension of the board.

python nqueen_hillclimber.py --nqueens 8

The parms object that is passed back will contain a variable for each parameter. You can access the argument in your code as parms.nqueens. There is also an argument called runs that controls the number of hill climbers that are executed.

Coding

Augment nqueen_hillclimber.py to utilize a steepest descent hill climber as discussed in the reading assignment and in lecture. We refer to this as the descent version since the problem wants to drive the number of conflicts to zero.

NOTE: If the successor function returns many states with the same number of conflicts, select randomly from the sublist of similar values.
Recall that you want to minimize the number of conflicts. When no state is better than the current state, you have reached an optimum value (and possibly a local optimum).

1. The starting state for this first test is with all the queens in the same column [0,0,0,0]. Does your program find a solution? Run your program 30 times and gather the number of attacking queens (the heuristic) when the optimum is reached and the number of moves/actions it took to find the optimum. What is this ratio of totalSuccess (when the number of conflicts equals zero) over the total number of attempts. Each run of your program should behave differently since you have a stochastic component of breaking ties when the heuristic function minimum has multiple values.

2. Change your program so that instead of starting at state [0,0,0,0], start at a random state. You can add a new function to the NQueensProblem class to support this.
   Run your program 30 times and compute the same ratio as in the prior step.

3. Determine the maximum value of n that your program can accept and complete within two minutes.

Python Tip

You can still use namedtuples here, and I would encourage that (although it is not requried here). If you want to unpack a function’s return value into a named tuple, you can use the _make function that is part of the namedtuple implementation.

State = namedtuple("State", "board hx")
current_state = State._make(qprob.getStartState())

Rubric

Submitting

Submit your completed version of nqueen_hillclimber.py through Gradescope to the Lab3 Coding problem. Your answers to the 3 questions above should be embedded in the top of your nqueen_hillclimber.py code as comments.