Chopsticks Game in Python (Version 2)

Question

This is another iteration of my previous question.

This program plays the game Chopsticks using the Minimax algorithm. I search the tree using recursion. The problem, however, is that it is just too slow. I can only search with a depth of about six; otherwise, it just takes too long. How can I improve my code for performance?

I'm writing this for 1) fun and 2) to beat my friend at Chopsticks. The latter is very important.

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:
            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

        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_right + (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_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 < 0 or (self.person_right + (self.person_left - sticks_on_left)) < 0:
                return False
            if sticks_on_left == self.person_right:
                return False
            if sticks_on_left == self.person_left or self.person_right == (self.person_right + (self.person_left - sticks_on_left)):
                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 > 6:
            return True
        if (self.person_left == self.person_right == 0) or (self.computer_left == self.computer_right == 0):
            return True
        else:
            return False

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

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

def gen_child_nodes(state):
    child_nodes = []

    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)

    for arg in range(0, 5):
        testing_state = deepcopy(state)
        if testing_state.put_together(arg):
            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_value(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 = ['', '', '']

Thanks for letting me know that the game is called Chopsticks, ever since I played it for the first time last year, I've been wondering what it's called. — Simon Forsberg♦, 2 days ago
Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. — Simon Forsberg♦, 2 days ago

zondo · Accepted Answer · 2016-04-30 11:35:30Z

You have many != 0's for conditions. It just so happens that 0 has a boolean value of False, and any other number has a boolean value of True. That means that you can change

if computer_value != 0 and self.person_right != 0:

to

if computer_value and self.person_right:

Yes, it is faster.

Your if and else blocks in tap() are quite similar. I might create a class for a player and have left and right attributes of that class. You could then have self.computer = Player(1, 1) and self.player = Player(1, 1). Then, you could keep track of the current player instead of if it is the computer's turn. That way, tap() could have something like current = self.current_player; opponent = (self.player if current is self.computer else self.computer) (on two lines, preferably). Since you now work with current and opponent instead of player and computer, you could take out the if and else, and make slight changes to what used to be in them to match your new logic. Your put_together() method would also benefit from this. It probably isn't faster, but it's cleaner.

if past_iter > 6:
...
    return 6 - past_iter + 10
    ...
        return -1 * (6 - past_iter + 10)

Where did all of these numbers come from? What are is_leaf() and value() doing? At the least, leave comments to explain the numbers. It would be better if you didn't use magic numbers.

Whenever you have if ...: return True else: return False, you can change it to return ... or return bool(...). In is_leaf(), you have such a pattern. I'll give an example:

if x:
    return True
else:
    return False

If x is True, we return True. If x is False, we return False. Do you see a pattern, we are just returning whatever x is. You might need to use bool(...), however, if x is not either True or False, but is Truthy or Falsey. That is, if x is 4, we don't want to return 4; we want to return True. Similarly, if x is 0, we want to return False.

return child_nodes[child_node_values.index(max(child_node_values))]

Here we go. I can finally tell you something to improve efficiency. You are iterating through child_node_values twice: first to find the maximum value, and second to find where that maximum value is. I would change it to:

return max(zip(child_node_values, child_nodes))[1]

I'll give an example:

>>> from itertools import izip
>>> x = (4, 5, 6, 4)
>>> y = (2, 3, 1, 2)
>>> izip(x, y)
<itertools.izip object at 0x7f5b30c56a28>
>>> list(izip(x, y))
[(4, 2), (5, 3), (6, 1), (4, 2)]
>>> max(izip(x, y))
(6, 1)

A tuple works similarly to a number in comparisons. Let's say you have a two-digit number. The first digit (in the tens place) is the most important. If it is higher than the first digit in a different two-digit number, it is the higher number regardless of the second digit. If the first digit of the two numbers is the same, the second digit is checked. In a tuple, the first value (in child_node_values) is the most important. If it is the same in both tuples (if child_node_values has duplicates), the higher one is the one with a higher second value (the corresponding value in child_nodes). Once we find the maximum tuple, we get the child_nodes value in it by accessing max(...)[1]. Since child_node_values no longer needs to be a list (we aren't using .index() anymore and we are iterating only once), its definition can be more memory efficient by using (...) instead of [...]. That is because we are now creating a generator expression instead of a list comprehension, so only one value at a time is stored in memory. Similarly, gen_child_nodes() can use yield testing_state instead of child_nodes.append(testing_state). That makes it return a generator object instead of a list. Again, it saves on memory use.

while not ((move[0] == 'split') or (move[0] == 'tap')):

You are finding move[0] twice. I would change it to:

while not (move[0] in ('split', 'tap'):

I would add some more conditions in there. Don't assume that the user doesn't make mistakes. He might not type anything (in which case move[0] would raise an IndexError); he might type split Yahoo (in which case int(move[1]) would raise a ValueError); etc.

I'll accept this answer soon, just waiting to see if anyone else has anything else to add. — APCoding, 2 days ago
@APCoding Don't explain magic numbers. Put them in a variable with a meaningful name instead. — Mast, 2 days ago
@APCoding Not the function names. But the numbers in a variable. Preferably a pseudo-const. — Mast, 2 days ago

asked	3 days ago
viewed	55 times
active	2 days ago

current community

your communities

more stack exchange communities

Chopsticks Game in Python (Version 2)

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged python beginner python-2.7 time-limit-exceeded or ask your own question.

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Chopsticks Game in Python (Version 2)

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged python beginner python-2.7 time-limit-exceeded or ask your own question.

Linked

Related

Hot Network Questions