Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

STUDENT INSTRUCTIONS

1. Read all instructions carefully. We recommend you read through the entire paper at least once before writing.

2. There are three questions. All candidates should attempt every question.

3. You should not submit answers to more than the required number of questions.

4. All parts of every question count equally.

5. Where handwritten answers are permitted, please ensure you write legibly, preferably in dark blue or black ink. If you use a pencil, please ensure it is not too faint to be captured by scan or photograph. It is your responsibility to ensure your work can be read.

6. If uploading photographs or scanned copies of your work, please check for legibility before uploading. It is your responsibility to ensure your work can be read.

7. Add your student number to all uploaded files.

8. You are permitted to access module materials, notes, resources, references and the internet during the online assessment.

9. You must not communicate with any other candidate during the assessment period, unless instructed to do so as part of the assessment requirement(s).

10. By starting this assessment, you are declaring yourself fit to undertake it. You are expected to make a reasonable attempt at the assessment by answering the questions in the paper.

IMPORTANT INFORMATION

• We strongly recommend you use Google Chrome or Mozilla Firefox to access the Alternative Exams Portal.

• You must have completed and uploaded the assessment within the period of time provided.

• You are granted an additional 45 minutes beyond the stated duration (2 hours) of this assessment to allow for downloading/uploading your assessment, your files and any technical delays.

• Late submissions are not accepted. Once started, you must complete the assessment within 2 hours and 45 minutes.

• If you are unable to submit your assessment, you can record Mitigating Circumstances and the Board of Examiners will consider your case.

• Students with approved Alternative Exam Arrangements (Reasonable Adjustments) that permit extra time and/or rest breaks will have this time added on to the stated duration.

SUPPORT DURING THE ASSESSMENT

Operational Support

• Use the Alternative Exams Portal to seek advice immediately if during the assessment period:

o you cannot access the online assessment

o you believe you have been given access to the wrong online assessment

Operational support will be available between 09:00 and 17:00 UK Time for each examination (excluding Sunday)

Technical Support

• If you experience any technical difficulties with the Alternative Exam Portal please contact [email protected]

• If you experience technical difficulties with Moodle please contact [email protected]

• If you experience technical difficulties with Questionmark Perception (QMP) please contact [email protected]

• If you experience technical difficulties with myWBS, please contact [email protected]

Technical support will be available between 09:00 and 17:00 UK Time for each examination (excluding Sunday)

Academic Support

• If you have an academic query, contact the invigilator (using the ‘Contact an Invigilator’ tool in AEP) to raise your issue. Please be aware that two-way communication in AEP is not currently possible

Academic support will normally be provided for the duration of the examination (i.e. for a 2 hour (+45 min) exam starting at 09:00 UK Time, academic support would normally be provided between 09:00 and 11:45 UK Time). Academic support beyond this time is at the discretion of the department

Other Support

• Write to your department immediately if you cannot complete your assessment for the following reasons:

o you lose your internet connection

o your device fails

o you become unwell and are unable to continue

o you are affected by circumstances beyond your control

[Question 1][Combinatorial Games]

a) Using any theory you like, as long as you say what it is, find ALL winning moves in the game of Nim played with five piles of sizes 9, 20, 12, 10 and 20. Explain your analysis.           [25 marks]

b) Suppose we have a game of Nim with three piles of sizes b, 2b and m. If , what does m have to be for the game to be losing? The answer depends of course on n, so first try n=3. [25 marks]

c) Consider the games OddNim and EvenNim, which are like regular Nim except that you can take away, respectively, only an odd or even number of chips. Let o(m) and e(m) denote respectively the Nim value of a single pile of m chips in these games. Evaluate o(m) and e(m). For partial credit take m=0,1,…,6.            [25 marks]

d) Who wins in the sum of the games OddNim[5,6] and EvenNim[5,6]? Explain and give a winning move if it is the first player, an optimal response to removing 2 from the pile of 5 in EvenNim if it is the second player. [25 marks]

[Question 2] [Combinatorial Games / Mazes]

Combinatorial Games

a) Consider the game on the board drawn below where players alternate in moving the Queen. In this game the Queen can move at most one square up or left but as many squares as she likes along the up-left diagonal. The Queen has five moves (options) from the pictured square. Calculate the Nim value of the game where the Queen starts in the pictured square. Show your calculations.        [25 marks]

b) Who wins the game where there is an additional Queen (with same movement as above) placed in the white square (0,2), two squares to the right of the upper left corner square? (When a player moves he can move either Queen.)

What are the optimal moves?  [25 marks]

c) Apply the RTA to the maze network pictured below, starting from the node at the right side of arc C. When there is a choice of how to leave a node, choose the passage with highest number. The arcs are labelled so that they go right, for example B goes along the top of the circle from left to right. Indicate by B* the part of a path that goes along the same arc to the left.  [25 marks]

d) Assume all arcs have unit length. Starting at the left end of arc A, and following the Randomized Tarry Algorithm, what is the expected time (number of traversed arcs) to reach the right end of arc C?

What is the probability that arc B will be traversed twice before the right end of C is reached? Explain. [25 marks]

[Question 3] [Alternating Search and Search Games]

a) An object is hidden in box i at location 1 with probability pi, i = 1,2,3 and in box j at location 2 with probability qj, j = 1,2,3,4, where p = (30,15,5), q = (2,38,2,8). The probabilities are given as percentages for simplicity. At each location, the boxes must be searched in increasing order but the searcher can switch between locations at will.

Find all optimal search strategies and the least expected search time, by dynamic programming. What is the total number of possible strategies? [25 marks]

b) Consider a more general search problem of the same type. Using the forward looking strategy, describe the optimal search strategy when:

i) both the pi and the qj are decreasing.

ii) the pi are increasing and the qj are decreasing. (To make this more particular assume five boxes at each location and q3 > P > q4 , where P denotes the average of the pi.) [25 marks]

c) Let V(x) denote the value of the search game played on the network drawn below, left, consisting of three circles and three lines, with the searcher starting at the node A.

Find bounds on V(x), as a function of x.           [25 marks]

d) Next, find the value of the game played on the network drawn above right, where the left network has been cut at A and the line separated from the circle. Searcher starts at A.           [25 marks]