Reference no: EM132653283

CSE2AIF Artificial Intelligence Fundamentals - Latrobe University

Question 1 - Game of the Amazons

Game of the Amazons is a two-person strategy game played on a chessboard. Each player has a specified number of amazons, which are placed on the board in some predetermined configuration. Usually the amazon pieces are represented by chess queens. The typical default position is on a 10x10 board as follows:

Each turn consists of two separate movements:

1. A player first moves one of their pieces any number of spaces in any one direction (horizontally, vertically, or diagonally), but it may not cross or enter a square occupied by an amazon of either colour or an arrow.

2. After moving, the amazon shoots an arrow to another square, in any direction from the place where it has landed. Just like movement of the amazon, the arrow cannot cross or enter a square occupied by another piece.

Once an arrow has been fired, the square it lands in is blocked off and can no longer be used. The arrows are represented on the boards below using solid circles.

The goal of the game is to "trap" the opposing player: if a player cannot make a move on their turn, they are the losing player.

A video about the Game of Amazons with mathematician/computer scientist Elwyn Berlekamp

For this question, you will be investigating a simplified version of the game using two pieces on a smaller board. An example showing two possible moves starting with the configuration below is on the next page.

A possible starting configuration. A losing position for player 1 (white) - a victory for player 2.

Instructions
You have been provided with the following two files for this problem:
• minimax.lisp, which contains LISP code for the minimax algorithm, and
• amazons.lisp, which contains a working LISP implementation of the simplified Amazons game. The following LISP interaction show you how to play a game. Try it.

[1] > (load 'minimax)
;; Loading file C:\CSE2AIF\minimax.lisp ...
;; Loaded file C:\CSE2AIF\minimax.lisp T
[2] > (load 'amazons)
;; Loading file C:\CSE2AIF\amazons.lisp ...
;; Loaded file C:\CSE2AIF\amazons.lisp T
[3] > (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 given player, is currently defined as follows:
(defun static (pos player) (- (random 20) 10)
This means that each board configuration is given a random score between -10 and 10 inclusive. The result is that the program plays completely at random.
Your task for this question is to develop and implement a better heuristic for the Amazons game by following the steps below.

Functions that have been provided for you
The included file amazons.lisp includes a parameter and two functions which you can (and should) use in your code. The parameter/functions you can use are:
- *directions*
o A list of the directions a piece can move:
(defparameter *directions*
'(up down left right up-left up-right down-left down-right))
- get-element(board coordinates)
o The function get-element returns the piece on the board which is in the position specified by the coordinates. If the square is empty, it returns nil.
- locate(board player)
o The function locate will return the coordinates on board of the piece player.
- range-in-direction(coordinates direction)
o The function range-in-direction will return all the coordinates in the given direction relative to coordinates. The value of coordinates is not included in the list. The list is sorted in order from closest to farthest relative to coordinates.
You do not need to write code for the functions described above. They are already provided for you. Examples are shown on the next page.

Implementing the heuristic
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 pieces-in-direction (board coordinates direction) that takes as input a board, coordinates representing a position on the board, and a direction. The direction should be one of: 'up, 'down, 'left, 'right, 'up-left, 'up-right, 'down-left, 'down-right.
The function returns the contents of the board in the given direction from the given coordinates, not including the contents at coordinates. Using *test-board* defined above, the function should behave as follows:
[1] > (pieces-in-direction *test-board* '(0 0) 'right) (NIL NIL @)
[2] > (pieces-in-direction *test-board* '(1 2) 'up-right) (NIL @)
[3] > (pieces-in-direction *test-board* '(2 3) 'up-left) (X NIL)
[4] > (pieces-in-direction *test-board* '(0 3) 'down) NIL
Reminder: you can (and should) make use of the functions that have been provided for you on page 4.

Part (ii)
Write a function count-until-not-nil (lst) that takes a list as input and returns the number of elements in the list before the first non-nil element. If lst is an empty list, it should return 0. The function should behave as follows:
[5] > (count-until-not-nil '(nil nil @ nil x)) 2
[6] > (count-until-not-nil '(nil @ nil nil @)) 1
[7] > (count-until-not-nil '(@ nil @)) 0
[8] > (count-until-not-nil nil)
0
Part (iii)
Write a function number-of-movements-in-direction (board player direction) that takes a board and player as input and returns the number of possible places the player can move their piece to in that direction. (Note: this is not the same as the number of available moves, as this heuristic is not counting the number of arrows that could be fired.) You should find it useful to use count-until-not-nil as a helper function. Using the same test board state as defined above, the function should behave as follows:
[9] > (number-of-movements-in-direction *test-board* 'x 'up) 2
[10] > (number-of-movements-in-direction *test-board* 'x 'down) 1
[11] > (number-of-movements-in-direction *test-board* 'o 'up) 0
[11] > (number-of-movements-in-direction *test-board* 'o 'up-left) 2

Part (iv)
Write a function board-value (board player) which takes a board and player as input and returns the number of possible board spaces the player can move their piece to in all directions.

The *directions* parameter and your number-of-places-in-direction function will be useful.

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.1 Experiment with some of the following:
• Changing the parameter *max-depth*. This affects the quality of the game play. Make sure that you include a *max-depth* value of 1 as one of your cases.
• Changing the starting player. You can give the program the first move by running (play t).
• Changing the size of the board. The file amazons.lisp has a function change-board-size(n)
which allows you to play the game on different board sizes. To play on a 5x5 board:

[1] > (load 'minimax)
[2] > (load 'amazons)
[3] > (change-board-size 5)
[4] > (play)

Note: if you load the amazons.lisp file after defining parameters, they will be over-written.

Write a short paragraph summarising your findings and include it as a commented section at the top of your source code. Include discussion about the smallest value of *max-depth* for which it is difficult to beat the algorithm, including a *max-depth* value of 1 as one of your cases.

Question 2 - LISP implementation of finite state machines

Implementation details
You will be implementing a finite state machine which will be defined by:
• An alphabet, which will be represented as a list. The alphabet will not necessarily be single letters - look at the machines.lisp file for some examples.
• A transition table, represented as a list of rows of the transition table. The elements in the table are indices, representing the index of a state.
• An integer which is the index of the initial state of the FSM.
• A list of accepting states, represented as a list of integers.

The number of states can be derived from the number of rows in the transition table.
States will be referenced by an index from 0 upwards, so (for example) states S0, S1 and S2 will be referenced by 0, 1 and 2 respectively.

A transition sequence will be represented as a list of atoms. For example, the word 10010 will be represented as the sequence '(1 0 0 1 0). The empty sequence is permitted, and will be represented by '().

The file machines.lisp has the following code, which defines a struct called fsm with 5 fields.

(defstruct fsm
(alphabet '(a)) (table '((0) (0)))
(initial 0)
(accepting '(0)))

This allows you to create a finite state machine by using the make-fsm function. The values listed above are the default values, so calling (make-fsm) will generate the following (rather uninteresting) finite state machine:

To instantiate a finite state machine, each field can be specified with a :field key like so:

(defparameter *test-machine* (make-fsm
:alphabet '(a b)
:table '((2 1) (0 2) (1 0))
:initial 0
:accepting '(2)))

This code binds the finite state machine shown on the previous page to the parameter *test-machine*. Accessor functions for each field are defined automatically by LISP in the format(fsm-field fsm); e.g.:
[1] > (fsm-alphabet *test-machine*) (A B)
[2] > (fsm-initial *test-machine*)
0
[3] > (fsm-accepting *test-machine*)
(1)

The Task
You are required to write the following LISP functions, together with any helper functions that they require. Load the file machines.lisp first to make use of the fsm struct.

• table-element (table row column)
Function table-element takes a table containing a list of rows (a transition table, for example). It returns the element of the table in the given row and column. Indices start at 0.

[1]> (table-element '((0 2 1) (1 2 1) (2 0 2)) 2 1)
0
[2]> (table-element '((0 2 1) (1 2 1) (2 0 2)) 1 2)
1

• transition-function-index(fsm state-index transition)
Function transition-function will take an FSM (as defined by the previous section), a transition (which is assumed to be an element of the alphabet of fsm), and state-index, which is the index of the current state in the list of states. It returns the index of the state obtained by following the transition from the state indexed by state-index when transition is received.

[3] > (transition-function *test-machine* 0 'a)
2
[4] > (transition-function *test-machine* 0 'b)
1
[5] > (transition-function *test-machine* 2 'b)
0

Tip: the built-in function position will return the index of an element in a list if that element exists. For example, (position '3 '(1 2 0 2 3 5 6)) will return 4. Note that though the alphabet for the test machine is '(a b), in machines.lisp there are other machines with different alphabets.

• extended-transition-function (fsm state-index transition-sequence)
Function extended-transition-function takes as input: fsm, the designated finite state machine; state-index, which is the state to begin from; and transition-sequence, which is the sequence of transitions. It should return the sequence of states visited while processing the transition sequence, including the starting index state-index.

[6]> (extended-transition-function *test-machine* 0 '(a b b a b))
(0 2 0 1 0 1)
[7]> (extended-transition-function *test-machine* 0 '(b b a b))
(0 1 2 1 2)
[8]> (extended-transition-function *test-machine* 1 '(b b a b))
(1 2 0 2 0)
[9]> (extended-transition-function *test-machine* 2 '(b b a b))
(2 0 1 0 1)
[10] > (extended-transition-function *test-machine* 1 '())
(1)

• accepted? (fsm transition-sequence)
The function accepted? takes two inputs: fsm, the designated finite state machine, and
transition-sequence, which is a list of transitions to be processed in the given order.
If transition-sequence leads to an accepting state, it should return the sequence of states visited while processing the word. Otherwise, it should return nil.

[11] > (accepted? *test-machine* '(a b b a b)) NIL
[12] > (accepted? *test-machine* '(a b b a)) NIL
[13] > (accepted? *test-machine* '(a b b b)) (0 2 0 1 2)
[14] > (accepted? *test-machine* '(a b b a b b)) (0 2 0 1 0 1 2)

• filter-accepted-sequences (fsm list-of-sequences)
The function filter-accepted-sequences takes two inputs: fsm, the designated finite state machine, and list-of-sequences, which is a list of words to be tested.
It should return the elements of list-of-sequences which are accepted by fsm.

[15] > (filter-accepted-sequences *test-machine*
'((a b b a b b) (a b b b) (a b b a))) ((A B B A B B) (A B B B))

• all-accepting-sequences-up-to-length (fsm n)
The function all-accepting-words-of-length takes two inputs: fsm, the designated finite state machine, and n, which is the maximum length of sequences. It should return the list of sequences accepted by fsm which have length up to and including n.

[16] > (all-accepting-sequences-up-to-length(*test-machine* 3)) ((A) (B B) (A A B) (A B A) (B A A))

For this part, you can and should make use of the function all-sequences-of-length defined for you in machines.lisp. Read the comments and experiment with the function to see precisely how it works.

Question 3 - Resolution Refutation
Consider the following information:
"Joe is Murray's tennis trainer. Joe will be at the park whenever the weather condition is dry. If it is wet on a weekend, then Joe will be at the sports centre. Murray is enthusiastic, and all enthusiastic trainees will be with their trainer on a dry weekday. If it is not a dry weekday then an enthusiastic trainee will be at the sports centre. On Wednesday it is dry."

(a) Represent the above information, as well as any relevant background information, in full predicate form (i.e., you must show any existential or universal quantifiers). You must use ONLY the following predicates and constants:
trainee(X) X is a trainee
enthusiastic(X) X is enthusiastic
weekday(X) X is a weekday
trainer(X,Y) X is the tennis trainer of Y
conditions(X,Y) The weather conditions on day X is Y
e.g., conditions(mon, wet) location(X,Y,Z) The location of X on day Y is Z joe Joe
murray Murray
wet wet (assumed to be a weather condition)
dry dry (assumed to be a weather condition)
mon Monday (a day)
tue Tuesday (a day)
wed Wednesday (a day)
thur Thursday (a day)
fri Friday (a day)
park park (a location)
centre sports centre (a location)

(b) Convert the predicate calculus expression you wrote in part (a) to clause form. This means that each individual clause in the database must be a disjunction of literals, where a literal is an atomic expression or the negation of an atomic expression.
(c) Using your database of clauses from part (b), manually use resolution refutation to extract the answer to the question "Where is Murray on Wednesday?". Make sure that you show all steps, and show clearly the substitutions required in order to answer the question.

Question 4 - River crossing in Prolog

Consider yet another variation of the river crossing problem:

Three monsters and three humans must cross a river using a boat that can carry at most two people. For each side of the river, if there are humans on that side of the river, then they cannot be outnumbered by the monsters (as otherwise, the monsters would eat the humans).
The boat cannot cross the river by itself - it must have at least one human or monster on board. The three monsters and humans are initially on the east side of the river. How can all the monsters and humans get to the west bank alive?
Your task is to write a Prolog program to solve this problem. You should model your code based on the solution to the Farmer, Wolf, Goat and Cabbage problem from the Week 8 labs.
Represent the state of the program as a relationship state, so that state(M, H, S) represents the state with M monsters and H humans on the east, and the boat is on side S.
You will need to create predicates for unsafe states and valid movements. To help you, here is one example of a valid movement relationship in English:
A west state can be obtained from an east state IF
There is at least one monster on the east, AND
The number of monsters on the west is one more than the number on the east, AND
The west state is not safe.
Of course, this is not the only way that new states can be obtained - you will have to think of the remaining ones yourself.

Question 5 - An expert system rule base

Your task for this question is to develop a small rulebase that can be used in the CLIPS expert system shell. You may choose any appropriate domain for your system; however, it should be in an area in which you have some expertise. Suitable domains may include:
• recommending a movie to watch (you might want to focus on a particular genre);
• recommending a suitable pet (e.g., you might want to focus on a specific breed of dog);
• real estate advisor;
• etc.
but there are hundreds of others. Hopefully you will develop something that is both useful and fun!
The system that you develop should be engineered to return a single result (e.g., which restaurant to dine at, which movie to watch). As a rough guide, there should be approximately 3 or 4 outcomes (e.g., restaurants or movies to recommend) but this will depend on your particular domain.
Remember that the expert system approach is most appropriate when using ‘deep' knowledge, and inferencing involves several layers of intermediate-level hypotheses. While many real expert systems can contain hundreds of rules, for the purpose of this exercise, approximately 15 to 20 rules (not counting helper rules, whose purpose, for example, might be solely to obtain input) should be sufficient. It is usually a good idea to use some rules which are more general (i.e., only one or two conditions in the antecedent), and some which are more specific (e.g., three or more conditions in the antecedent. Obviously, with such a small number of rules, the expert system will not work well in all consultations. Try to engineer your system so that it performs well in a couple of particular cases (i.e., one or two particular restaurants; one or two particular movies).

Testing the system
Create at least three test scenarios, each corresponding to a different set of facts to be presented to the system when prompted. The scenarios should be carefully selected to test your system and to demonstrate the quality of its inferencing. Select two scenarios to demonstrate when your system works well, and at least one scenario to show when your system works poorly (i.e., gives bad advice). You will need to submit runs of these test scenarios, so you must capture the sessions to a text file. Instructions on how to capture input into a text file in CLIPS, see the Appendix).

Attachment:- Artificial Intelligence Fundamentals.rar