7
\$\begingroup\$

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 = ['', '', '']
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – APCoding Apr 25 '16 at 17:46
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Mathias Ettinger Apr 25 '16 at 18:18
  • \$\begingroup\$ @MathiasEttinger Will do, thanks for the help. \$\endgroup\$ – APCoding Apr 25 '16 at 18:21
  • \$\begingroup\$ "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... \$\endgroup\$ – Peilonrayz Apr 27 '16 at 9:14
  • \$\begingroup\$ @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". \$\endgroup\$ – SylvainD Apr 27 '16 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.