cmput 355 2022 assignment replacing quiz 3
计算机quiz代写 For this assignment, you can ask clarifying questions on eclass, but you cannot post answer hints or suggestions on eclass or anywhere else.
For this assignment, you can ask clarifying questions on eclass, but you cannot post answer hints or suggestions on eclass or anywhere else.
You can work on this assignment in groups of up to 5: within your group, you can discuss any questions, but you cannot copy answers. Each student must submit their own assignment. Discussing or copying with any student outside your group is plagiarism.
We might ask you later to explain your answers: if you are unable to do so, we might deduct some or all marks and report this to the faculty of science.
Submit each answer on eclass. 计算机quiz代写
Unless otherwise stated, each question is worth 3 marks.
- If you do not answer this question we will not mark the quiz and your quiz score will be 0.
(a) In at most 20 words, summarize the above plagiarism policy.
(b) Give the names and ccids of all members of your discussion group (including yourself). Explain how you worked together: e.g. discussed every question, discussed only questions 1 and 3 with group members X and Z, etc.For this assigment, your secret number is the sum (mod 3) of the number of digits in your name. E.g. if your name matches pattern ***** ******* *****, then your secret number is 17 (mod 3) = 2. E.g. if your name matches pattern **** **** ****, then your secret number is 12 (mod 3) = 0.
- a) Below from left are puzzles 0, 1, 2 respectively. Answer this question for puzzle n, where n is your secret number.
A strategy is winning if it wins against every possible opponent strategy. A move is winning if it is the fifirst move in a winning strategy. For this hex position with Black to play, give all winning moves. For one winning move, give a proof tree that shows how Black can win against any opponent move sequence.
b) For the puzzle below with Black to play, 1.Black[c2] is a winning move. Brieflfly describe a winning strategy, and give the number of nodes in a proof tree for this strategy (you do not have to draw the whole strategy tree).
3 Consider Pankratz’s visualizer http://webdocs.cs.ualberta.ca/~hayward/355/asn/hexviz/ of Yang’s winning 9×9 strategy. Below are move sequences 0, 1, 2 respectively. Use sequence n, where n is your secret number.
sequence 0 2.W[e4] 4.W[g2] 6.W[f2] 8.W[d7] 10.W[b8] 12.W[c7]
sequence 1 2.W[g1] 4.W[e2] 6.W[f4] 8.W[c3] 10.W[c9] 12.W[b8]
sequence 2 2.W[f4] 4.W[d9] 6.W[c8] 8.W[f2] 10.W[g3] 12.W[e8]
a) Against Black’s winning strategy, assume that White starts with your sequence. Give Black’s moves 1 to 13. 计算机quiz代写
b) Continue this game from move 14. Assume that White suddenly decides to lose as quickly as possible. Find a line of play so that the game ends soonest. Give all moves after move 13. Prove that your answer is correct (hint: shortest path).
c) Assume that a Hex game continues after a) with Black continuing to follow Jing Yang’s strategy and with White playing to prolong the game as long as possible. Give all moves (from 14 to the end) in such a game. (There are many correct answers.)
4. Consider Hex program hex-3×3.py from the class repo.
a) On my home machine, when I play x b2 and then ask it who wins (? o), it answers x can win, 677 calls. Using this program, fifind all winning fifirst moves for x, and for each give the number of calls.
b) 3×3-Hex is rotationally symmetric: if we rotate the board 180 degrees, it is identical to the original board. Why are the answers to a) not rotationally symmetric, e.g. why is the number of calls to solve the game after 1.B[a3] difffferent from the number of calls after 1.B[c1]?
c) When I ask the program who wins from the empty board if x plays fifirst (? x), it says x can win, 678 calls, so exactly 1 more call than after x b2, ? x. But if I change the move order (line 109) to the natural move order (108), ? x takes 5677 calls. With this move ordering, what fifirst winning move is the program fifinding for Black? Explain brieflfly. In your answer, give the number of calls made before it found the winning move, and the number of calls when it tried the winning move. 计算机quiz代写
d) Replace line 109 with a bad move ordering, i.e. a move ordering that you think might maximize the number of calls needed to answer the question ? x from the empty board. How many calls does your bad ordering achieve, and why do you think this might be the maximum (or close to the maximum)?
e) Program hex-3×3.py uses function has_win to check whether a player has won the game. Does has_win use breadth-fifirst search, depth-fifirst search, or neither? Explain brieflfly, and explain why I used this approach for this program.
f) Brieflfly explain the difffferences between program hex-3×3.py and program hex-vc3.py.
