159.271程序代做、代写Python程序设计、Python编程调试

日期：2021-05-27 10:44

159.271 Computational Thinking

Assignment 2

This assignment will be a piece of cake. That is, you need to smarten up the computer player for

a game we shall call “Piece of Cake”.

Piece of Cake

The game works as follows: We have a cake that is cut into pieces which can differ in thickness.

Players take turns in choosing a piece of cake. But they need to be polite: After the first piece of

cake has been removed, only one of the two pieces adjacent to the gap can be taken. Once the cake

is gone, the player who ate the most wins.

A simple implementation for a 2-player version of the game (computer vs human, human goes

first) is provided on the course website (if you see gaps in the cake border, that’s a bug in the graphics

library). The cake has 32 pieces (an even number ensures some measure of fairness), with thickness

ranging from 5 to 9.

Tasks

Currently, the computer player is using a simple greedy heuristic, choosing the bigger of the two pieces

available (this is done in cake picker.py - your implementation should modify this class). A better

strategy is to maximize the total amount of cake you can get regardless of how your opponent plays.

That is, you assume that your opponent always picks the piece which minimizes the overall total you

can get (and maximizes theirs).

(a) Give an example to show that the simple greedy heuristic used by the template is not optimal,

i.e., that it does not maximize the total amount of cake the computer will get when taking the

minimum among all possible choices for the human player. [2 points]

Note: The number of pieces left is always odd when the computer choses. A minimal odd-sized

example showing the non-optimality of a greedy strategy has 5 pieces.

(b) Implement an algorithm which maximizes the computer player’s guaranteed overall total in each

step (as described above). This algorithm should run in polynomial time. [6 points]

Hint: Use dynamic programming techniques.

(c) Analyze the time complexity of your algorithm, as a function of the number of pieces. [1 point]

(d) Describe briefly how to modify your algorithm if the computer player were to start. [1 point]