Question 1

 

(a) Nim is a two-player game The rules are as follows.

 

The game starts with a single stack of 7 tokens. At each move a player selects one stack and divides it into two non-empty, non-equal stacks. A player who is unable to move loses the game.

 

Draw the complete search tree for nim.

 

(10)

 

(b) Assume two players, min and max, play nim (as described above). Min plays first.

 

If a terminal state in the search tree developed above is a win for min, a utility function of zero is assigned to that state. A utility function of 1 is assigned to a state if max wins the game.

 

Apply the minimax algorithm to the search tree to assign utility functions to all states in the search tree.

 

(3)

 

(c) If both min and max play a perfect game, who will win? Explain your answer.

 

(3)

 

(d) Given the following search tree, apply the alpha-beta pruning algorithm to it and show the search tree that would be built by this algorithm. Make sure that you show where the alpha and beta cuts are applied and which parts of the search tree are pruned as a result.

(9)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Question 2

 

a) Given the following parents, P1 and P2, and the template T

 

 

 

Show how the following crossover operators work

uniform crossover

order-based crossover

 

with regards to genetic algorithms

 

(8)

 

 

Use this problem description for parts b to e.

Assume we have the following function

 

f(x) = x3 - 60 * x2 + 900 * x +100

 

where x is constrained to 0..31. We wish to maximize f(x) (the optimal is )

Using a binary representation we can represent x using five binary digits.

 

b) Given the following four chromosomes give the values for x and f(x).

 

 

(2)

 

c) If P3 and P2 are chosen as parents and we apply one point crossover show the resulting children, C1 and C2.  Use a crossover point of 1 (where 0 is to the very left of the chromosome)

Do the same using P4 and P2 with a crossover point of 2 and create C3 and C4

 

(6)

d) Calculate the value of x and f(x) for C1..C4.

 

(2)

 

e) Assume the initial population was x={17, 21, 4 and 28}. Using one-point crossover, what is the probability of finding the optimal solution? Explain your reasons.

 

(7)

 

 

Question 3

 

 

Simulated annealing is an algorithm that always accepts better moves but also accepts worse with some probability

 

a)

 

Show a simulated annealing algorithm

 

(7)

 

What the probability of accepting the following moves? Assume the problem is trying to maximise the objective function.

 

 

 

(5)

 

b)

 

One aspect of a simulated annealing cooling schedule is the temperature. Discuss the following

 

What is the effect of having the starting temperature too high or too low?

 

(4)

 

How do you decide on a suitable starting temperature?

 

(6)

 

How do we decide on a final temperature?

 

(3)

 

 

 

Question 4

 

a) Briefly describe the Turing Test

 

(6)

 

b) Briefly describe the Chinese Room Experiment

 

(6)

 

c) Do you agree with the Chinese Room argument that if a computer passes the Turing Test then it does not prove that the computer is intelligent? State your reasons.

 

(13)

 

 

 

Question 5

 

a) John Conway’s Game of Life and Craig Reynold’s Boids are, arguably, examples of artificial life. What, in your opinion, would constitute artificial life and what problems would it cause if we ever created artificial life?

 

(10)

 

b) A simplified version of blackjack can be described as follows.

Blackjack is a two player game comprising of a dealer and a player. The dealer deals two cards (from a normal pack of 52 cards) to the player and one card to himself. All cards are dealt face up. All cards take their face value, except Jack, Queen and King which count as 10 and Aces which can count as one or eleven.

The aim for the player is to draw as many cards as he/she wishes (zero if they wish) in order to get as close as possible to 21 without exceeding 21.

 

Outline how you would develop a computer program that was capable of learning how to play blackjack, the aim being that it improves its play over time.

 

(15)

 

 

Question 6

 

 

a) Describe how ants are able to find the shortest path to a food source.

 

(4)

 

b) Using the travelling salesman problem as an example, define the following terms with relation to ant algorithms

 

Visibility

Evaporation

Transition Probability

 

(9)

 

c) Many of the search methods presented in the lectures had as their basis some aspect of the real world. Propose an idea for a search algorithm based on some natural process or animal behaviour. Discuss how your method could be realised in a computer implementation in solving, say, the TSP.

 

 

12 marks

 

ComputerScienceExpert

(11)

Status NEW Posted 23 May 2017 03:05 AM My Price 8.00

-----------

Attachments

file 1495510570-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer