CSE 3500: Algorithms and Complexity (Fall 2019) Programming Assignment #3: Chopsticks In this programming assignment, we practice dynamic programming and write Python code to implement a game named chopsticks. The description of the chopsticks game can be found at the following link. https://www.wikihow.com/Play-Chopsticks Do not worry about the details of different rules. This part is already taken care of by the starter code. In our implementation, there are two players. The first player is player A, and the second player is B. A user can choose whether he or she wants to be player A or player B. And the computer will be the other player, as shown in the following code. moves = 10 print(“The chopsticks game.”) print(“The game will end within”, moves, “moves.”) answer = input(“Do you want to go first?”) if answer in [“Y”, “y”, “Yes”, “YES”, “yes”]: chopsticks_game(moves, 0) else: chopsticks_game(moves, 1) The above code shows that the maximum number of moves each player can take is 10. If the user choose to be player A, then the function chopsticks_game(moves, 0) is called; otherwise, chopsticks_game(moves, 1) is called. The good news is that the function chopsticks_game is given in the starter code, as shown below. def chopsticks_game(moves, index): depth = 2*moves d = best_move_dp(depth) w = ((1, 1), (1, 1), 0) display(w) moves_left = moves turn = 0 while w[0] != (0, 0 ) and w[1] != (0, 0) and w[2] < depth: # computer will use d[w] to decide its move if (turn + 1) % 2 == index: result, v = d[w] if (result == 1 and index == 1) or (result == -1 and index == 0): print("I will win.") else: print("I may not win.") w = v moves_left -= 1 1 else: all_next_moves = next_moves(w) num = len(all_next_moves) print(moves_left + index, "moves left.") print("Choices:") for i in range(len(all_next_moves)): print(i, ’:’, all_next_moves[i][:2]) while True: s = input("Your move:") while not s.isnumeric(): s = input("Your move:") choice = int(s) if choice >= 0 and choice < num: break v = list(w) v = all_next_moves[choice] v = tuple(v) w = v display(w) turn = turn +1 if w[0] != (0,0) and w[1] != (0,0) and w[2] == depth: print("It is a tie.") elif w[0] == (0, 0): print("B wins.") else: print("A wins.") As shown in the code, we use w to represent the current game state. w is a 3-tuple, which include the state of player A, the state of player B, and the level of this state in the game tree. To understand the game tree, please read from the following link https://www.cs.cmu.edu/~adamchik/15-121/lectures/Game%20Trees/Game%20Trees.html At the beginning, we have w = ((1, 1), (1, 1), 0) indicating that player A has 1 finger on each hand, player B has 1 finger on each hand, and the current level is 0. Note that the game will end when either player A or player B has the state (0, 0) or the level reaches depth. Also notice that the computer is using the dictionary d with key w to obtain the game result and the best move assuming the user will play the game perfectly. The dictionary d is obtained as follows d = best_move_dp(depth) Note this function is only called once before the game starts. We focus on finishing only the function best_move_dp, as shown below. This function returns a dictionary. A key of this dictionary is a game state, and a value of this dictionary is the game result and the best move for the current player given both player play their game perfectly. In order to better understand our implementation. Please read about game trees from the following link. 2 https://www.cs.cmu.edu/~adamchik/15-121/lectures/Game%20Trees/Game%20Trees.html In particular, read the section titled "Minmax" very carefully. def best_move_dp(depth): assert(depth % 2 == 0) d = {} # base cases for i in range(0, 5): for j in range(0, 5): for k in range(0, 5): for l in range(0, 5): if i == 0 and j==0 and k == 0 and l == 0: d[((i, j), (k, l), depth)] = (0, []) elif i==0 and j==0: d[((i, j), (k, l), depth)] = (-1, []) elif k==0 and l==0: d[((i, j), (k, l), depth)] = (1, []) else: d[((i, j), (k, l), depth)] = (0, []) for h in range(depth -1, -1, -1): # fill in code below return d Note that the number of game states at each level is bounded by 54 = 625. This is because each hand can only show from zero finger up to four fingers. This leads to 5 possibilities for each hand. And there are four hands in total for both players. Therefore, we can have 54 = 625 possible finger configurations. The idea here is to use the dictionary to save minmax algorithm results without physically creating a game tree. This is feasible because at each level of the game tree, there are at most 625 unique game states. And we bound the depth of the game tree by limiting the number of moves each player can make. Note at the same level of a game tree, a game state node could appear multiple times. The game tree ap- proach is like the recursive approach, which is very time consuming since it involves repetitive computations from these same game states. The dynamic programming approach we use here does not have this problem. The starter Python files is provided. The file name is chopsticks.py. The following function returns the list of next game states from the current game state v. That is, all the possible moves that the opponent can take. This function will be used to fill the missing code above. For curiosity, infer from the code below the exact rules we used in the chopsticks game. def next_moves(v): L = [] # if the game is already over, return the empty list if v[0] == (0, 0) or v[1] == (0, 0): return L 3 # the following depends on whose turn it is l0, r0 = v[0][0], v[0][1] l1, r1 = v[1][0], v[1][1] h = v[2] #print(l0, r0, l1, r1, h) if h % 2 == 0: s = set() # to make sure that we do not add zero with other numbers if l0 > 0 and l1 > 0: item = ((l0, r0), (overflow_sum(l0, l1), r1), h + 1) s.add(item) if l0 > 0 and r1 > 0: item = ((l0, r0), (l1, overflow_sum(l0, r1)), h + 1) s.add(item) if r0 > 0 and l1 > 0: item = ((l0, r0), (overflow_sum(r0, l1), r1), h + 1) s.add(item) if r0 > 0 and r1 > 0: item = ((l0, r0), (l1, overflow_sum(r0, r1)), h + 1) s.add(item) #move fingers from the left hand to the right hand for i in range(1, l0 + 1): l = l0 – i # to make sure we do not overflow if r0 + i < 5: r = overflow_sum(r0, i) #print(l, r, l0, r0) if (r, l) != (l0, r0): item = ((l, r), (l1, r1), h + 1) s.add(item) #move fingers from the right hand to the left hand for i in range(1, r0 + 1): l = overflow_sum(l0, i) r = r0 - i #print(l, r, l0, r0) if l0 + i < 5: if (r, l) != (l0, r0): item = ((l, r), (l1, r1), h + 1) s.add(item) else: s = set() if l1 > 0 and l0 > 0: item = ((overflow_sum(l0, l1), r0), (l1, r1), h + 1) s.add(item) if l1 > 0 and r0 > 0: item = ((l0, overflow_sum(r0,l1)), (l1, r1), h + 1) s.add(item) if r1 > 0 and l0 > 0: item = ((overflow_sum(l0, r1), r0), (l1, r1), h + 1) s.add(item) 4 if r1 > 0 and r0 > 0: item = ((l0, overflow_sum(r0, r1)), (l1, r1), h + 1) s.add(item) for i in range(1, l1 + 1): l = l1 – i r = overflow_sum(r1, i) if r1 + i < 5: if (r, l) != (l1, r1): item = ((l0, r0), (l, r), h + 1) s.add(item) for i in range(1, r1 + 1): l = overflow_sum(l1, i) r = r1 - i if l1 + i < 5: if (r, l) != (l1, r1): item = ((l0, r0), (l, r), h + 1) s.add(item) for item in s: L.append(item) return L For completeness, below are the other two functions used in the the implementation. def overflow_sum(a, b): if a > 5 or b > 5: print(“input error.”) return if a < 0 or b < 0: print("input error.") return if a + b >= 5: return 0 else: return a + b # display the game state def display(w): print(“***********************”) print(“A:”, w[0]) print(“B:”, w[1]) Sample outputs from my implementations. The chopsticks game. The game will end within 10 moves. Do you want to go first?n *********************** A: (1, 1) B: (1, 1) I may not win. 5 *********************** A: (1, 1) B: (2, 1) 10 moves left. Choices: 0 : ((2, 1), (2, 1)) 1 : ((1, 3), (2, 1)) 2 : ((3, 1), (2, 1)) 3 : ((1, 2), (2, 1)) 4 : ((1, 1), (0, 3)) 5 : ((1, 1), (3, 0)) Your move:5 *********************** A: (1, 1) B: (3, 0) I may not win. *********************** A: (1, 1) B: (4, 0) 9 moves left. Choices: 0 : ((0, 1), (4, 0)) 1 :
((1, 0), (4, 0)) 2 : ((1, 1), (2, 2)) 3 : ((1, 1), (1, 3)) 4 : ((1, 1), (3, 1)) Your move:4 *********************** A: (1, 1) B: (3, 1) I may not win. *********************** A: (1, 1) B: (3, 2) 8 moves left. Choices: 0 : ((3, 1), (3, 2)) 1 : ((1, 1), (1, 4)) 2 : ((1, 3), (3, 2)) 3 : ((4, 1), (3, 2)) 4 : ((1, 1), (4, 1)) 5 : ((1, 4), (3, 2)) Your move:5 *********************** A: (1, 4) B: (3, 2) I may not win. *********************** A: (1, 4) B: (0, 2) 7 moves left. 6 Choices: 0 : ((1, 0), (0, 2)) 1 : ((3, 4), (0, 2)) 2 : ((1, 4), (1, 1)) Your move:2 *********************** A: (1, 4) B: (1, 1) I may not win. *********************** A: (1, 4) B: (2, 1) 6 moves left. Choices: 0 : ((2, 4), (2, 1)) 1 : ((1, 4), (0, 3)) 2 : ((3, 4), (2, 1)) 3 : ((1, 4), (3, 0)) 4 : ((1, 0), (2, 1)) Your move:3 *********************** A: (1, 4) B: (3, 0) I will win. *********************** A: (1, 4) B: (0, 0) A wins. 7 Guidance for Turning in Programming Assignments Please include the following (please put them in a directory and then submit it to HuskyCT): ● Source code with in-line documentation. Uncommented code will be heavily penalized. ● A separate (typed) document describing the overall program design, a verbal description of “how it works”, and design tradeoffs considered and made. Also describe possible improvements and extensions to your program (and sketch how they might be made). The format of the description file should be as follows (If your turn-in does not follow the above format, you’ll get 10 points off automatically). ○ Description: describe the overall program design and “how it works” ○ Tradeoffs: discuss the design tradeoffs you considered and made. ○ Extensions: describe possible improvements and extensions to your program, and describe briefly how to achieve them. ○ Test cases: describe the test cases that you ran to convince yourself (and us) that it is indeed correct. Also describe any cases for which your program is known not to work correctly. I should emphasize the importance of designing appropriate test cases. In general, thorough test cases of a program should contain both special cases and normal cases. The description of your test cases should follow the following format: ■ First, describe your overall design for the test cases. ■ Then, for each test case: ● (1) Describe your test case, ● (2) Describe why you choose this test case, and ● (3) Describe the output of the test case. Please provide screen-shots. Grading policy Java Source Code ● works correctly 50 points (shown by testing results) ● in-line documentation 10 ● quality of design 10 Design Document ● description 5 ● tradeoffs discussion 5 ● extensions discussion 5 Thoroughness of test cases 15 Total 100 points
