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