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 = ['', '', '']
