AI代写：CMPT317 N-Queens Problem|留学生CS代写|代做Java编程|C作业|C++程序|Python代码

代写AI作业，用Minimax Search, Alpha-Beta Pruning等算法解决N-Queens问题。

Overview

The N-Queens problem is to put N Queens on a board (N * N) so that no queen attacks any other queen. (A queen can attack any square on the same row, same column, or same diagonal.) The following is a diagram of a game state with 2 queens on the board:

We will make a 2-player game of the N-Queens problem as follows: Players alternate putting a piece on the board, and can only place a queen on a square that is not being attacked, i.e., there is no queen already on the board in the same row or column or diagonal. In the N-Queens game, the objective is to be the last player to have a legal place to put a queen. We will work with two variations of this game, which differ in 2 aspects: how players can play, and how the score is counted.

Variation 1a

The players must place a queen on the left-most unoccupied column: Player 1 plays on Column 1, Player 2 on Column 2, Player 1 on Column 3, etc). For example, in the above diagram, it’s Player 1’s turn to move, and Player 1 must place a queen somewhere in column 3 (counting from the left, starting at 1). The winner is the last player to put a queen on the board. For example, if it’s Player 1’s turn to play in Column 5, but all squares in Column 5 are being attacked, then Player 1 loses, and Player 2 wins. The utility function would return 1 for a win for Player 1, or -1 for a win for Player 2. For example, Player 1 can place a queen in the above position, but Player 2 would be unable to play after that, so Player 1 would be the winner. There are no draws.

Note: If all N queens are on the board, then the last player to move is the winner: if N is even, then Player 2 wins, and the utility is 1 1, and if odd, Player 1 wins, and the utility is 1 1.There are no draws.

Variation 1b

This variation is identical to Variation 1a, except for the score of the game. The utility value is calculated by counting how many queens are on the board at the end of a game: if there are k queens on the board, and it’s a win for Player 1, the utility is k (positive, odd number); if there are k queens on the board, and it’s a win for Player 2, the utility is k (negative, even number). For example, the win for Player 1 (after playing one more queen on the board position above) counts for 3. There are no draws.

Note: If all N queens are on the board, then the last player to move is the winner: if N is even, then Player 2 wins, and the utility is N , and if odd, Player 1 wins, and the utility is N .

Notes

The purpose of this assignment is not to implement a real game, but to understand the game-tree search algorithms.
These variations are games, but may not be interesting games to play as humans.
Some of the variations of this game may not seem fair or balanced, and that’s okay for our work.
For N < 3, the game is quite boring.
Draw out the game trees for N ≤ 4 before you start coding. You’ll need these trees to debug your code.

Programming

As in previous assignments, it’s advisable to separate the game-specific code from the game-search code.
The interface between your game-search code and your game-specific code is as follows:

is_terminal(state): returns a Boolean, True if the given state has no more legal moves.
utility(state): returns a numeric value. The state must be a terminal state.
actions(state): returns a list of actions (i.e., moves) that are legal in the given state. The function needs to examine the state to determine whose turn it is to move.
result(state, action): returns a new game state which is the result of taking the given action in the given state.
Optional: is_maxs_turn(state): Returns a Boolean value, True if it’s Player 1’s turn (Max) in the given state.
Optional: is_mins_turn(state): Returns a Boolean value, True if it’s Player 2’s turn (Min) in the given state.

Implementing the optional methods may not be necessary for all the questions, though it would be useful if you wanted to play the game interactively. We saw the use of these optional functions in Lecture 18.

None of the coding is difficult, though finding a bug may be difficult. As always, you should write enough tests for your methods and functions that you can debug them using a test script. Debugging a whole application is more of a waste of your time than writing a test script.

You’ll be developing a code base throughout this assignment, and we only want to see it once to grade it. Each question will ask you to hand in a script that performs a task; this script can import the code you’re developing, but don’t hand everything in multiple times.

Execution instructions

The markers may or may not wish to run your program, to verify your results. To help them, you should provide brief instructions on what to do to get your program running. Include:

Programming language used (including version, e.g., Java 8 or Python 3)
A simple example of compiling and/or running the code from a UNIX shell would be best.

Keep it brief, and name it with the question number as the following example: a4q1_EXECUTION.txt. If your assignment uses third party libraries, they have to be included in your submission.

Clarification: You’ll submit one file documenting the execution instructions for all your scripts.

Clarification: What to Hand in instructions

The first version of this assignment required separate hand in files for questions 1-7,9. This pushes against Moodle’s very hard limit of 20 files maximum. To remedy this, the new requirements collect the requirements for these questions into 2 files:

A4_output.txt will contain tables output from your scripts for questions 1-7,9. Please mark each Question’s output clearly, so markers can easily identify which data belongs to which question.
A4_EXECUTION.txt will contain execution instructions for all your scripts for questions 1-7,9. Please mark each Question’s information clearly, so markers can easily identify which information belongs to which question.

You should not hand in separate output and execution instructions!

Question 1

Purpose: To implement Minimax Search for Variation 1a.
Degree of Difficulty: Moderate. Minimax is easy; the game will be the only tricky part.
Textbook: AIMA Chapter 5.1, 5.2
Implement Minimax search (with no bells or whistles) and apply it to Variation 1a, for game sizes N ∈ {1, ..., 10}.

Clarification

In the above output, which is literally copy/paste from my computer, the Best Opening Move is represented by a pair (WHO, ROW); in my implementation, I used the symbol ‘X’ to represent player 1 (answering WHO), and for ROW, I give an integer value. There is no need to imitate my output, as long as it’s clear.

Your output should go all the way up to 10 (or 11, if that amuses you). Your output should have the correct Minimax values, though there may be more than one opening move to achieve that value; it does not matter which of the equally good opening moves your script returns. Your times will vary, but reasonably you should expect your implementation to take only a few seconds at most. Try a few larger sizes, e.g. N = 11, 12, and observe the exponential nature of the search problem (again).

What to Hand In

A file named a4q1.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q1.LANG containing a script/app which, if executed, would produce the output submitted in a4q1.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q1_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this file.

Do not submit your entire codebase multiple times. Your script/app a4q1.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).

Clarification

You’ll be developing your code-base as you work on Questions 1-9. You will hand in your whole code base in Question 10. Your script for Question 1 will import modules/classes/libraries from (or include, or compile with) your code base, of course! But you don’t need to hand in the game code or the search code in Question 1. Just hand in the script that creates the data above. When the marker runs your script, it should import or compile with the code you submit in Question 10.

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q1.
1 mark: Your file a4q1.LANG contains a script/app that produces the output in A4_output.txt.

Question 2

Purpose: To implement Minimax Search for Variation 1b.
Degree of Difficulty: Easy. Minimax is done already; you have to modify the utility function for the new variation.
Textbook: AIMA Chapter 5.1, 5.2
Implement Minimax search (with no bells or whistles) and apply it to Variation 1b, for game sizes N ∈ {1, ..., 10}.

What to Hand In

A file named a4q2.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q2.LANG containing a script/app which, if executed, would produce the output submitted in a4q2.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q2_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information.

Do not submit your entire codebase multiple times. Your script/app a4q2.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q2.
1 mark: Your file a4q2.LANG contains a script/app that produces the output in A4_output.txt.

Question 3

Purpose: To implement Minimax Search with Alpha-Beta Pruning for Variation 1a.
Degree of Difficulty: Moderate. Your implementation of Variation 1a is done; you have to implement AlphaBeta pruning.
Textbook: AIMA Chapter 5.3
Implement Minimax Search with Alpha-Beta Pruning and apply it to Variation 1a, for game sizes N ∈ {1, ..., 10}.

Your output should have the the same Minimax values as Question 2, though there may be more than one opening move to achieve that value; it does not matter which of the equally good opening moves your script returns. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N . Try a few larger sizes, e.g. N = 11, 12, and observe the exponential nature of the search problem (again).

What to Hand In

A file named a4q3.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q3.LANG containing a script/app which, if executed, would produce the output submitted in a4q3.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q3_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information.

Do not submit your entire codebase multiple times. Your script/app a4q3.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).
Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q3.
1 mark: Your file a4q3.LANG contains a script/app that produces the output in A4_output.txt.

Question 4

Purpose: To implement Minimax Search with Alpha-Beta Pruning for Variation 1b.
Degree of Difficulty: Moderate. Your implementation of Variation 1b is done; you have to implement AlphaBeta pruning.
Textbook: AIMA Chapter 5.3
Implement Minimax Search with Alpha-Beta Pruning and apply it to Variation 1b, for game sizes N ∈ {1, ..., 10}.

Your output should have the the same Minimax values as Question 3, though there may be more than one opening move to achieve that value; it does not matter which of the equally good opening moves your script returns. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N . Try a few larger sizes, e.g. N = 11, 12, and observe the exponential nature of the search problem (again).

What to Hand In

A file named a4q4.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q4.LANG containing a script/app which, if executed, would produce the output submitted in a4q4.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q4_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information.

Do not submit your entire codebase multiple times. Your script/app a4q4.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q4.
1 mark: Your file a4q4.LANG contains a script/app that produces the output in A4_output.txt.

Question 5

Purpose: To implement a depth-cutoff and a heuristic evaluation function for Minimax Search, to allow play in Variation 1a larger than N = 10.
Degree of Difficulty: Easy. You have to modify your search algorithm, using the interface for imperfect real-time decisions.
Textbook Chapter: AIMA 5.4

Implement a depth-cutoff and heuristic evaluation function for Variation 1a. Apply your implementation with a cut-off at depth 4, for game sizes N ∈ {1, ..., 10}.

Since the cut-off is at depth 4, the first 4 rows in your output should have correct minimax values; after that, the minimax values will reflect your evaluation function, and probably won’t be optimal. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N . In particular, you should expect to run all examples in a few seconds at most.

Additional functions for your interface

The textbook recommends that you

Replace your test for a terminal state with a function that determines whether to cut off search.
Replace the utility function with a function that estimates utility for any given state.

I recommend otherwise! Add two new methods/functions to your Variations, as follows:

cutoff_test(state, depth): returns a Boolean, True if the search should be terminated at this state and depth.
eval(state): returns an estimate of the Minimax value of the given state.

By introducing these two new functions into the interface, your search algorithms need to be modified as well. Use the cutoff test and the evaluation function in combination, but only check for the cut-off after you’ve determined that the state is not an actual terminal state. This arrangement adds a few lines to the search algorithms, but helps keep your utility and estimated minimax functions independent, which is good for development.

The heuristic evaluation function

Such a function might be difficult to invent for this game. You are welcome to try. You should remember that your estimate should return a value in the range of your utility function; a confident estimate should be close to the true minimax value, and you can express uncertainty by producing estimates that are between the extremes, perhaps using fractional (floating point) estimates within the range. Alternatively, your evaluation function can return a random utility value. This is easy to start with, in any case.

What to Hand In

A file named a4q5.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q5.LANG containing a script/app which, if executed, would produce the output submitted in a4q5.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q5_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this file.

Do not submit your entire codebase multiple times. Your script/app a4q5.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).
Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q5.
1 mark: Your file a4q5.LANG contains a script/app that produces the output in A4_output.txt.

Question 6

Purpose: To implement a depth-cutoff and a heuristic evaluation function for Minimax Search, to allow play in Variation 1b larger than N = 10.
Degree of Difficulty: Easy. You have to implement a cutoff and evaluation function for Variation 1b. Your changes to Minimax from Question 5 should already be finished.
Textbook Chapter: AIMA 5.4

Implement a depth-cutoff and heuristic evaluation function for Variation 1b. Apply your implementation with a cut-off at depth 4, for game sizes N ∈ {1, ..., 10}.

Since the cut-off is at depth 4, the first 4 rows in your output should have correct minimax values; after that, the minimax values will reflect your evaluation function, and probably won’t be optimal. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N. In particular, you should expect to run all examples in a few seconds at most.

The notes about the interface, and the evaluation function, from Question 5, apply here as well. If you’ve adopted a good design, you may only need to over-ride the evaluation function from Question 5.

What to Hand In

A file named a4q6.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q6.LANG containing a script/app which, if executed, would produce the output submitted in a4q6.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q6_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this file.

Do not submit your entire codebase multiple times. Your script/app a4q6.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q6.
1 mark: Your file a4q6.LANG contains a script/app that produces the output in A4_output.txt.

Question 7

Purpose: To implement a depth-cutoff and a heuristic evaluation function for Minimax Search with AlphaBeta pruning, to allow play in games larger than N = 10.
Degree of Difficulty: Easy. You’ll need to adapt your Alpha-Beta search algorithm similar to the way you adapted Minimax in Question 5.
Textbook Chapter: AIMA 5.4
Adapt your Alpha-Beta search algorithm from Q4 similar to the way you adapted Minimax in Question 5. Apply your implementation with a cut-off at depth 4, for game sizes N ∈ {1, ..., 10}.

What to Hand In

A file named a4q7.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q7.LANG containing a script/app which, if executed, would produce the output submitted in a4q7.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q7_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this file.

Do not submit your entire codebase multiple times. Your script/app a4q7.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q7.
1 mark: Your file a4q7.LANG contains a script/app that produces the output in A4_output.txt.

Question 8

Purpose: To compare the output gathered in the previous questions.
Degree of Difficulty: Easy. You’ll need to understand why the output is the way it is.
Textbook Chapter: AIMA 5.1-4

Answer the following questions with a brief comment for each.

Compare the Minimax values for A4Q1 and A4Q2. The minimax value used a different scale (-1,1) versus a count of the number of queens, but did this change which player won the game?
Compare the runtimes for A4Q1 and A4Q2. Which variation seemed to be faster? Explain why.
Compare the Minimax values for A4Q1 and A4Q3. Were they the same?
Compare the runtimes for A4Q1 and A4Q3. How much faster was the search, for games with larger N?
Compare the Minimax values for A4Q2 and A4Q4. Were they the same?
Compare the runtimes for A4Q2 and A4Q4. How much faster was the search, for games with larger N?
Compare the Minimax values for A4Q1 and A4Q5. Were they the same? Explain.
Compare the runtimes for A4Q1 and A4Q5. How much faster was the search, for games with larger N?
Compare the Minimax values for A4Q5 and A4Q6 (Minimax with cut-off, two variations) with the results from A4Q7 (Alpha-Beta with cut-off, two variations). Were they the same? Explain.
Compare the runtimes for A4Q5 and A4Q6 (Minimax with cut-off, two variations) with the results from A4Q7 (Alpha-Beta with cut-off, two variations). How much faster was the search, for games with larger N?

None of these questions is difficult. This is more about requiring you to consider what you’ve done, than it is about understanding anything deep or complex.

What to Hand In

A file named a4q8.txt containing your comments to the above questions.

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

10 marks: Your file a4q8.txt contains plausible responses to the above questions.

Question 9

Purpose: To implement an interactive script/application that plays N-Queens.
Degree of Difficulty: Moderate. You’ll need to return actions, not just values, and you’ll need to distinguish between the scripts that plan moves for a single player (Q1-6), and scripts that take turns making moves in a real game.
Textbook Chapter: AIMA 5.1-4

This is the fun part. Implement an interactive script/application that plays N-Queens. Make use of your implementations from the previous questions.
Make sure you understand the difference between what the search algorithms are doing (planning a single choice), and what you need to do here (allow two planning agents to take turns making moves). You might start by implementing human vs. computer (or computer vs. human), so that you can figure things out, then replace the human player with the computer.

You should allow each player to use its own search algorithm, so you could play (plain) Minimax against Alpha-Beta, using equal depth cutoffs, or different depth cutoffs. You can model a weak player using a shallower cutoff, and a stronger player using a deeper cutoff. Play around with the cutoffs, so that the first few moves of the game do not take longer than a minute or so (shorter is better for experimentation though).

Try the following scenarios:

Try N = 10, equal cut-off value 4. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4).
Try N = 10, equal cut-off value 5. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4). Were these the same as when the cutoff was 4?
Try N = 10, Player 1 cut-off 5, Player 2 cut-off 3. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4). Did the deeper cutoff result in better decisions?
Try N = 10, Player 1 cut-off 3, Player 2 cut-off 5. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4). Did the deeper cutoff result in better decisions?
Repeat the above scenarios with N = 20.

If you are using a random evaluation function, be sure to run each scenario a number of times (you don’t want to draw a conclusion about random effects based on one example)! If you are using a deterministic evaluation function, then there is no point to repeat the scenarios more than once.

What to Hand In

A file named a4q9.txt containing your table, as above.
Revised: Your table, and any accompanying explanation, in your file A4_output.txt, which is a single file that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this file.
A file named a4q9.LANG containing a script/app which, if executed, would produce the output submitted in a4q9.txt (except the timing information which will differ). Use the file extension appropriate for your choice of programming language, e.g., .py or .java.
A file named a4q9_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.
Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the file A4_EXECUTION.txt, which is a single file that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this file.

Do not submit your entire codebase multiple times. Your script/app a4q9.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others).

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

Revised:

3 marks: Your file A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q9.
1 mark: Your file a4q9.LANG contains a script/app that produces the output in A4_output.txt.

Question 10

Purpose: To obtain grades for your implementations.
Degree of Difficulty: Easy. Just make sure your code is well-documented, well-organized, and hand it in. Nothing new here!
Textbook Chapter: AIMA 5.1-4

Hand in your code. All the scripts from the previous questions should be based on this code, by importing or compiling as necessary. All the scripts from previous questions must run using these files.
Your code should be documented internally so that a reader can make sense of it.

What to Hand In

Files named a4q10.LANG containing the code for your variations, and your search algorithms. If you have more than one file to submit (a good idea), you can name them appropriately, using a4q10 as a prefix.

Do not submit your entire codebase multiple times. This is the only place where your variations and search algorithms are submitted.

Be sure to include your name, NSID, student number, and course number at the top of all documents.

Evaluation

2 marks: Your implementation of Variation 1a includes functions/methods for the interfaces described throughout this assignment.
2 marks: Your implementation of Variation 1a is well-documented.
2 marks: Your implementation of Variation 1b includes functions/methods for the interfaces described throughout this assignment.
2 marks: Your implementation of Variation 1b is well-documented.
2 marks: Your implementation of Minimax Search makes use of the interface described through the assignment.
2 marks: Your implementation of Minimax Search is well-documented.
2 marks: Your implementation of Minimax Search with Alpha-Beta Pruning makes use of the interface described through the assignment.
2 marks: Your implementation of Minimax Search with Alpha-Beta Pruning is well-documented.

Work for the ambitious

We worked with two variations of the N-Queens game. There is a third, which I removed from the assignment.

In Variation 2, the players are not restricted in their choice of column, but can play a queen in any rowcolumn position, so long as it is not currently attacked by any other queen already on the board. For example, in the above diagram, it’s Player 1’s turn to move, and Player 1 can place a queen in either of the two unoccupied columns. The winner is the last player to put a queen on the board. The utility function would return 1 for a win for Player 1, or -1 for a win for Player 2. There are no draws.

Implement this variation, and try out your search algorithms on it. The branching factor is much higher, and moves are more strategic. This variation is a good opportunity to employ a transposition table, which stores board positions and utility values so that if the board position appears more than once in a search, the full search is not repeated. Use a hash table!