# Your task for this question is to write a heuristic for the two-player game Connect-4 You are required to write various LISP functions which will be used to define the heuristic.

INSTRUCTIONS TO CANDIDATES

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

• > (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

(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

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)

## Related Questions

##### . Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

##### . The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

##### . Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

##### . SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

##### . Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Hire Me