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