# Chopsticks game in Python

As a beginning project, I decided to code something that plays the game Chopsticks in Python 3. I'm using the Minimax algorithm, and exploring the tree using simple recursion. One of the main problems is performance. I can only search through about five moves deep; anything more takes too long. How can I improve my performance?

This is my first small to middle sized project, after doing some simple stuff (<20 lines). This is not homework, a challenge, etc. I'm just doing it for fun (which it is), also to finally beat my friend at chopsticks.

As of right now, this is pretty useless, at least in the beginning stages, because it can't think far enough ahead to actually reach some, or any, leaf nodes.

import itertools
from copy import deepcopy

class State:
def __init__(self):
self.person_left = 1
self.person_right = 1
self.computer_left = 1
self.computer_right = 1
self.is_computer_turn = False

def tap(self, is_to_left, is_from_left):
if self.is_computer_turn:
if is_to_left:
if is_from_left:
if self.computer_left != 0 and self.person_left != 0:
self.person_left += self.computer_left
else:
return False
else:
if self.computer_right != 0 and self.person_left != 0:
self.person_left += self.computer_right
else:
return False
else:
if is_from_left:
if self.computer_left != 0 and self.person_right != 0:
self.person_right += self.computer_left
else:
return False
else:
if self.computer_right != 0 and self.person_right != 0:
self.person_right += self.computer_right
else:
return False
else:
if is_to_left:
if is_from_left:
if self.person_left != 0 and self.computer_left != 0:
self.computer_left += self.person_left
else:
return False
else:
if self.person_right != 0 and self.computer_left != 0:
self.computer_left += self.person_right
else:
return False
else:
if is_from_left:
if self.person_left != 0 and self.computer_right != 0:
self.computer_right += self.person_left
else:
return False
else:
if self.computer_right != 0 and self.computer_right != 0:
self.computer_right += self.person_right
else:
return False

if self.computer_left >= 5: self.computer_left = 0
if self.computer_right >= 5: self.computer_right = 0
if self.person_left >= 5: self.person_left = 0
if self.person_right >= 5: self.person_right = 0
self.is_computer_turn = not self.is_computer_turn
return True

def put_together(self, sticks_on_left):
if self.is_computer_turn:
if sticks_on_left < 0 or (self.computer_left - sticks_on_left) < 0:
return False
if sticks_on_left == self.computer_right:
return False
if sticks_on_left == self.computer_left or self.computer_right == (self.computer_left - sticks_on_left):
return False
self.computer_right += (self.computer_left - sticks_on_left)
self.computer_left = sticks_on_left
else:
if sticks_on_left == self.person_right:
return False
self.person_right += (self.person_left - sticks_on_left)
self.person_left = sticks_on_left
self.is_computer_turn = not self.is_computer_turn
return True

def is_leaf(self, past_iter):
if past_iter > 5:
return True
if (self.person_left == 0 and self.person_right == 0) or (self.computer_left == 0 and self.computer_right == 0):
return True
else:
return False

def value(self, past_iter):
if (self.person_left == 0) and (self.person_right == 0):
return 5 - past_iter + 10
else:
if (self.computer_left == 0) and (self.computer_right == 0):
return -1 * (5 - past_iter + 10)
else:
return -2

def best_move(state, do_max, past_iter):
if state.is_leaf(past_iter):
return state
else:
child_nodes = gen_child_nodes(state)
child_node_values = [best_move(s, not do_max, (past_iter + 1)).value(past_iter) for s in child_nodes]
if do_max:
return child_nodes[child_node_values.index(max(child_node_values))]
else:
return child_nodes[child_node_values.index(min(child_node_values))]

def gen_child_nodes(state):
child_nodes = []

for arg in itertools.product(*((True, False), (True, False))):
testing_state = deepcopy(state)
if testing_state.tap(*arg):
child_nodes.append(testing_state)

for arg in range(0, 5):
testing_state = deepcopy(state)
if testing_state.put_together(arg):                                      #Does this call the function? Same with the thing above
child_nodes.append(testing_state)
return child_nodes

game = State()
move = ['','','']
while not game.is_leaf(0):
print game.person_left, " ", game.person_right, "     ", game.computer_left, " ", game.computer_right
if game.is_computer_turn:
game = best_move(game, True, 0)
game.is_computer_turn = False
else:
while not ((move[0] == 'split') or (move[0] == 'tap')):
string = raw_input('What would you like to do?\n'
'Type \'split\', then how many fingers you\'d like to have left on the left hand after splitting\n'
'Type \'tap\', whether you are tapping to the computer\'s left hand (True or False), and  whether your tapping hand is your left hand (True or False)\n'
'Examples: \'split 3\', \'tap True True\', \'split\' 1\', \'tap False True\'\n')
move = string.split()
if move[0] == 'split':
game.put_together(int(move[1]))
else:
if move[0] == 'tap':
game.tap((move[1])[0] == 'T', (move[2])[0] == 'T')
move = ['', '', '']


A better use of itertools

You wrote itertools.product(*((True, False), (True, False))) which shows knowledge of the itertools package which is good (because it is so awesome) and of the star-argument syntax (I ignore what the real name is).

However, this looks a bit cryptic and can probably be improved. Indeed using the repeat argument, you could simply write :

itertools.product((True, False), repeat=2)


Making code clearer

In the following code:

for arg in itertools.product((True, False), repeat=2):
testing_state = deepcopy(state)
if testing_state.tap(*arg):
child_nodes.append(testing_state)


You've used star-arguments again. I think that the code would be much clearer by using tuple unpacking so that you can give proper name to the values:

for to_left, from_left in itertools.product((True, False), repeat=2):
testing_state = deepcopy(state)
if testing_state.tap(to_left, from_left):
child_nodes.append(testing_state)


Having fun with chained comparisons

From the doc:

Comparisons can be chained arbitrarily, e.g., x < y <= z is equivalent to x < y and y <= z, except that y is evaluated only once (but in both cases z is not evaluated at all when x < y is found to be false).

In your case, things like :

self.person_left == 0 and self.person_right == 0


can be rewritten:

self.person_left == self.person_right == 0


Do not repeat yourself

In :

if is_from_left:
if self.computer_left != 0 and self.person_left != 0:
self.person_left += self.computer_left
else:
return False
else:
if self.computer_right != 0 and self.person_left != 0:
self.person_left += self.computer_right
else:
return False


it looks like we are doing the same thing twice but using a different value. You could easily rewrite this with less duplicated code (the variable name introduced is terrible):

value = self.computer_left if is_from_left else self.computer_right
if value != 0 and self.person_left != 0:
self.person_left += value
else:
return False


The same idea can be reapplied in different places at different levels.

Then, the whole tap functions becomes :

if self.is_computer_turn:
computer_value = self.computer_left if is_from_left else self.computer_right
if is_to_left:
if computer_value != 0 and self.person_left != 0:
self.person_left += computer_value
else:
return False
else:
if computer_value != 0 and self.person_right != 0:
self.person_right += computer_value
else:
return False
else:
person_value = self.person_left if is_from_left else self.person_right
if is_to_left:
if person_value != 0 and self.computer_left != 0:
self.computer_left += person_value
else:
return False
else:
if person_value != 0 and self.computer_right != 0:
self.computer_right += person_value
else:
return False


This could be reduced further but I am still thinking about the best way to do so.

• Good answer! I'm new to Code Review SE... should I accept this answer, or wait till someone improves on this even more? Also, should I copy your changes into the code in my question? Thanks Commented Apr 25, 2016 at 17:46
• @APCoding do not modify the code in your question as it would invalidate that answer. As for accepting an answer it's up to you, but it's not rare to get answers up to a couple of days after posting a question. Commented Apr 25, 2016 at 18:18
• @MathiasEttinger Will do, thanks for the help. Commented Apr 25, 2016 at 18:21
• "This could be reduced further but I am still thinking about the best way to do so." What do you think of getattr and setattr here? It makes the code smaller. (The variable names are really bad) Probably best if they make a 'user' class now that I think about it... Commented Apr 27, 2016 at 9:14
• @JoeWallis I am usually not a big fan of getattr and setattr as they tend to be used the solve wrong problem in the wrong way. In your case, the code does look better indeed. An alternative (which is pretty much identical) I had in mind was to use dict instead of individual variable (from your solution, it just changes the fact that instead of using self as a dict (which is what it is), we define another dict (of dict?) self.my_dict and write something like "self.my_dict[other] = other_value + turns_value". Commented Apr 27, 2016 at 17:11