1
\$\begingroup\$

I made a tic tac toe bot with the following rules (it's not unbeatable):

  1. If bot is about to win, it will find the winning move.
  2. If bot is about to lose, it will find a move that prevents the other player from winning.
  3. if none of rule 1 or 2 is found, then it will play a random move

I think it's highly inefficient, so if you could give optimization advice, that would be great!

class Cell(str): # a class for strings with unique ids, every time
    pass

def mediumbot_move(self, player):
    """
    medium level bot player - allows a bot with two rules to play
    1) If bot is about to win, it will find the winning move.
    2) If bot is about to lose, it will find a move that prevents the other player from winning.
    3) if none of rule 1 or 2 is found, then it will play a random move
    """
    print('Making move level "medium"')
    opponent = self.other_player[player]
    board = self.board.board # the board represented as an array like ["X", "O", " ", "O", ...]
    winning_three = set(itertools.permutations([player, player, " "])) # permutation for all the winning positions
    losing_three = set(itertools.permutations([opponent, opponent, " "])) # permutation for all the losing positions

    # the three across positions
    horizontals = [board[i:i+3] for i in range(0, 7, 3)] 
    verticals   = [board[i:9:3] for i in range(3)]
    diagonals   = [board[0:9:4], board[2:7:2]]

    # if a winning pattern found win
    for pattern in (horizontals + verticals + diagonals):
        pattern = tuple(pattern)
        if pattern in winning_three:
            for winning_pattern in winning_three:
                if pattern == winning_pattern:
                    position_id = id(pattern[pattern.index(" ")]) # storing the id of the empty spot to place player on to win
                    for i in range(9): # looping through the board (array) to find the stored id, to place player
                        if id(board[i]) == position_id:
                            self.board.board[i] = Cell(player)
                            return

    # if no winning patterns found, choose a move, that would not result in a loss
    for pattern in (horizontals + verticals + diagonals):
        pattern = tuple(pattern)
        if pattern in losing_three:
            for losing_pattern in losing_three:
                if pattern == losing_pattern:
                    position_id = id(pattern[pattern.index(" ")])
                    for i in range(9):
                        if id(board[i]) == position_id:
                            self.board.board[i] = Cell(player)
                            return

    # if no patterns found, choose a random move
    available_indexes = [index for index in range(9) if board[index] == " "]
    bot_index = random.choice(available_indexes)
    self.board.board[bot_index] = Cell(player)
\$\endgroup\$

1 Answer 1

Reset to default
1
\$\begingroup\$

First of all, this is too big for one function. You have 7 levels of indentation. Split it up, or remove levels.

Second, you say "I think this is inefficient". Why? Have you timed it? How long does it take? How long do you think it should take? It is a bad idea to try to speed things up before measuring — maybe there is no problem. Maybe some other part of your program is the slow part.

If you are trying to figure out how to make your program efficient, you normally only need to look at the for loops:

for pattern in (horizontals + verticals + diagonals):
    for losing_pattern in losing_three:
        for i in range(9):

It should take (8 * 3 * 9)=216 iterations. Actually less, because you have if branches, but that's the maximum. You could make this smaller, yes (both of the two inner loops can be removed). But also, 216 iterations is just not that many — your computer executes a billion operations per second.

You should remove your third for loop, and every use of id, because it is confusing and hard to read, not because it's a loop.

\$\endgroup\$