Question 1 – A heuristic for Connect-4 (15 marks)
Connect-4 is a two-person game played on a board that has seven columns, with six spaces in each column. The board is initially empty. Two players take turns dropping one piece (red or yellow in the diagram below, but X or O in our game) in a column. The piece falls into the lowest unoccupied row. A player cannot place a piece in a column if the top-most row of that column already has a piece in it. The first player to get four of their counters in a line (either horizontally, vertically, or diagonally) is the winner.
Your task for this question is to write a heuristic for the two-player game Connect-4.
You have been provided with the following two files for this problem:
lisp, which contains lisp code for the minimax algorithm, and
connect-4.lisp, which contains a working LISP implementation of the Connect-4 game. The following LISP interaction show you how to play a game. Try
> (load 'minimax)
;; Loading file C:\CSE2AIF\minimax.lisp ...
;; Loaded file C:\CSE2AIF\minimax.lisp T
> (load connect-4)
;; Loading file C:\CSE2AIF\connect-4.lisp ...
;; Loaded file C:\CSE2AIF\connect-4.lisp T
> (play)
The program plays poorly because it has a poor-quality heuristic. The function static, which evaluates a position from the point of view of a particular player, is currently defined as follows:
(defun static (board player) 0)
This means that each board configuration receives exactly the same evaluation; i.e., 0.
Your task for this question is to develop and implement a better heuristic for the Connect-4 game.
Instructions
You are required to write various LISP functions which will be used to define the heuristic. Parts (i) to (iv) ask you to define various helper functions. You will define the actual heuristic in part (v). The code that you write should be in a file named q1.lisp. Do not include any other code in this file other than any helper functions required by the functions below.
Part (i)
Write a function get-element (board coords) that takes a board and a pair of coords representing a board position as input. The first element of the pair represents the column number and the second represents the row number (indexing starts from 0). The function returns the contents of that board position, which can be either X, O or NIL. Using the following test board state
(defparameter *test-board* '((nil nil nil nil nil nil)
(O nil nil nil nil nil) (X nil nil nil nil nil) (X X O nil nil nil) (O O X nil nil nil) (nil nil nil nil nil nil) (nil nil nil nil nil nil))) the function should behave as follows:
|
[1]> NIL |
(get-element |
*test-board* |
‘(0 |
0)) |
(column 1, row 1 contains NIL) |
|
[2]> |
(get-element |
*test-board* |
‘(1 |
0)) |
|
|
O [3]> |
(get-element |
*test-board* |
‘(2 |
0)) |
(column 2, row 1 contains O) |
|
X [4]> |
(get-element |
*test-board* |
‘(4 |
2)) |
(column 3, row 1 contains X) |
|
O |
|
|
|
|
(column 4, row 3 contains O) |
Part (ii)
Write a function getline (board player line) that takes a board, a player and a line as input, and returns a list of length 3, where the first element of the list is the number of empty places in the line, the second element is the number of pieces that player has in the line, and the third element is the number of pieces that the opponent has in the line. You should find it useful to use get-element as a helper function. Using the same test board state as defined above, the function should behave as follows:
[5]> (getline *test-board* ‘X ‘((3 0) (3 1) (3 2) (3 3)))
(1 2 1) (line contains 1 NIL, player has 2 pieces in line, and opponent has 1)
[6]> (getline *test-board* ‘O ‘((3 0) (3 1) (3 2) (3 3)))
(1 1 2) (line contains 1 NIL, player has 1 piece in line, and opponent has 2)
You may wish to use the built in function count that takes and element and a list as arguments, and returns the number of occurrences of the element in the list; e.g.,
[7]> (count 1 ‘(3 2 1 4 3 1 1 3))
3
[8]> (count ‘a ‘( c a a a b a)) 4
Part (iii)
Write a function line-score (board player) that takes a board and player as input, and returns the line score for player. The line score is determined as follows:
if there are no pieces in the line the line score is 0;
if player has 1 piece in the line and the opponent has no pieces in the lines, the line score is 1;
if player has 2 pieces in the line and the opponent has no pieces in the lines, the line score is 2;
if player has 3 pieces in the line and the opponent has no pieces in the lines, the line score is 4;
if player has 4 pieces in the line, the line score is
You should find it useful to use getline as a helper function. Using the same test board state as defined above, the function should behave as follows:
[9]> (line-score *test-board* ‘X ‘((3 0) (3 1) (3 2) (3 3)))
0 (both players have a pieces in the line)
[10]> (line-score *test-board* ‘O ‘((3 0) (3 1) (3 2) (3 3)))
0 (both players have a pieces in the line)
[11]> (line-score *test-board* ‘X ‘((2 0) (3 1) (4 2) (5 3)))
4 (player has three pieces in the line and opponent doesn’t have any)
Part (iv)
Write a function board-value (board player, which takes a board and player as input, and returns the sum of line scores for player, summed over all 69 possible winning lines. To assist you, the code you have been supplied with contains a parameter *all-c4-lines* which is a list of all of the 69 possible ways to win in Connect-4. You should find it useful to use line-score as a helper function.
Part (v) – the actual heuristic function
Finally, write the function static (board player, which accepts a board and player as input arguments, and returns the board value of player, minus the board value for opponent. This is the function that will be used as the heuristic. You should find it useful to use board-value as a helper function.
Part (vi)
Play some games against the algorithm, experimenting with how the parameter *max-depth* affects the quality of the game play. Make sure that you include a *max-depth* value of 1 as one of your cases. What is the smallest value of *max-depth* for which it is difficult to beat the algorithm? Write a short paragraph summarising your findings, and include it as a commented section at the top of your source code.
Submit the following:
Electronic copy of a file lisp. This file should contain definitions of the functions described above, as well as any helper function required by these. Do not include any of the code from minimax.lisp or connect-4.lisp in this file. Make sure that your name and student number appear in the header documentation. Don’t forget to include a short summary of your findings as a commented section at the top of your source code.
Note on assessment:
Your code will be tested using the following test function
(defun q1test() (load 'minimax) (load 'connect-4) (load 'q1)
(play)
)
It is your responsibility to ensure that your code loads correctly, and that all required functions are present.
Your solution will be marked according to the following criteria:
Functioning code that operates as specified above
Programming style
Code displays good functional programming style with appropriate use of local variable definitions, higher-order functions,
Appropriate documentation and indentation. Documentation should be concise, but clear. Indentation should reflect the logical structure of the
Question 2 – LISP functions for a simple IR system (15 marks)
Your task for this question is to write LISP functions for a simple Information Retrieval (IR) system.
Background – a crash course in Information Retrieval (IR)
Information retrieval is most commonly carried out using the vector space model—a common method of representing text documents. Under this model, a document dj is represented as a vector
d j = (wj1, wj 2 ,..., wjt ) ,
where each of the t dimensions of the vector corresponds to a separate term (i.e., word). The dimensionality of this vector is usually very high, since most languages contain a large number of words. The components of the vector indicate the weight that the word has in the document. For example, wj1 represents the weight of the word 1 in document dj, wj2 represents the weight of the word 2 in document dj, and so on. There are many different ways of computing the weights, most of which are based on term frequency; i.e., the frequency with which that word appears in the document.
Since a query is just a collection of terms, queries can be represented in the same way as documents; i.e.,
q = (wq1, wq2 ,..., wqt )
Since we now have two vectors represented in the same space, we can try to come up with some measure of the similarity between these vectors. A widely used measure is cosine similarity. The cosine similarity between the above two vectors is defined as
cosq = d j × q
d j q
where
d j × q =å wjiwqii=1
So, to find which, of a collection of documents, is most similar to some query, we simply need to calculate the similarity between the query and each of the documents, and then rank the documents according to this similarity (i.e., most-similar to least-similar).
Suppose that we had a very small vector space comprising just the three words apple, banana and carrot. Following are examples of how three documents and a query could be represented in this space.
Document Vector space representation
d1: “apple banana carrot” (1, 1, 1)
d2: “apple carrot carrot” (1, 0, 2)
d3: “carrot apple carrot” (1, 0, 2)
Query Vector space representation
q: “apple” (1, 0, 0)
The cosine similarity between d2 and q would be calculated as
cosq =(1´1) + (0´ 0) + (2´ 0)= 0.447
The Task
You are required to write the following LISP functions, together with any helper functions that they require.
· create-word-list (corpus)
Function create-word-list takes a list containing lists of words as input. It returns the list resulting from appending these lists together.
> (create-word-list ‘((the ides of march) (the big game))) (THE IDES OF MARCH THE BIG GAME)
· filter(word-list words-to-filter)
Function filter should take two lists as input: word-list and words-to-filter. The function should return the list containing all members of word-list, excluding those contained in words-to-filter. For example:
> (filter '(fred barney wilma betty bambam) '(barney betty)) (FRED WILMA BAMBAM)
· create-dictionary (corpus stopwords)
Function create-dictionary takes two parameters as input: corpus, which is a list of lists of words, and stopwords, which is a list of words. It should return a sorted list of all of the words appearing in corpus, omitting those that appear in stopwords. Each word should appear only once. For example:
> (create-dictionary '((flintstones meet the flintstones) (a midsummer nights dream)) '(a the in at))
(DREAM FLINTSTONES MEET MIDSUMMER NIGHTS)
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
