6
\$\begingroup\$

Background
I am currently participating in a tic-tac-toe coding challenge. During their move, each participant is given the board state and their team, X or O. The blank board is:
[[' ',' ',' '],[' ',' ',' '],[' ',' ',' ']]
With 'X' and 'O' being added to the board, for example:
[[' ',' ',' '],[' ','X',' '],[' ','O',' ']]
I have developed a minimax algorithm with alpha-beta pruning in Python 2.7 and it plays perfectly (Please see code).
Link to challenge rules: https://ccpc.codecraftworks.com/python

Problem
The algorithm will always win or tie. In the event of a tie, the winner is determined by the computation time. I need to decrease the average time taken per move from 0.195 seconds to less than 500,000 nanoseconds (0.0005 seconds)

Possible Reasons for the Problem

  1. Incorrect implementation of minimax algorithm
  2. Incorrect implementation of alpha beta pruning.

Possible Solutions
I have tried to separate the min and max functions and apply them separately, however that didn't work. I searched stack overflow for other possible ways to decrease computation time in my program, but I couldn't find anything.

Code
Note 1: getGameState(), getTeam(), and submitMove(row, col) are predefined functions provided by the back end of the coding challenge . You can test the code by uploading the file here: https://ccpc.codecraftworks.com/

team = getTeam()

value_dict = {
    "X": 1,
    "tie": 0,
    "O": -1
}

def winner(board):
    for i in range(len(board)):
        if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
            if board[i][0] == "X":
                return "X"
            if board[i][0] == "O":
                return "O"

    for i in range(len(board[0])):
        if board[0][i] == board[1][i] and board[1][i] == board[2][i]:
            if board[0][i] == "X":
                return "X"
            if board[0][i] == "O":
                return "O"

    if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
            if board[0][0] == "X":
                return "X"
            if board[0][0] == "O":
                return "O"

    if board[2][0] == board[1][1] and board[1][1] == board[0][2]:
            if board[2][0] == "X":
                return "X"
            if board[2][0] == "O":
                return "O"

    for row in board:
        for cell in row:
            if cell == ' ':
                return "continue"
    return "tie"

def minimax(board, depth, is_max, n, alpha = float('-inf'), beta = float('inf')):
    check_winner = winner(board)
    if check_winner != "continue":
        return value_dict[check_winner]
    if is_max:
        best_score = float('-inf')
        for i in range(n):
            for j in range(n):
                if board[i][j] == " ":
                    board[i][j] = "X"
                    score = minimax(board, depth+1, False, n, alpha, beta)
                    board[i][j] = " "
                    best_score = max(score, best_score)
                    alpha = max(alpha, score)
                    if beta >= alpha:
                        pass
        return best_score
    else:
        best_score = float('inf')
        for i in range(n):
            for j in range(n):
                if board[i][j] == " ":
                    board[i][j] = "O"
                    score = minimax(board, depth+1, True,n, alpha, beta)
                    board[i][j] = " "
                    best_score = min(score, best_score)
                    beta = min(beta, score)
                    if alpha >= beta:
                        pass
        return best_score

def calcMove():
    board = getGameState()
    if team =="X":
        score = - 2
        x = -1
        y = -1
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == ' ':
                    board[i][j] = "X"
                    curr_score = minimax(board,0,False, len(board))
                    board[i][j] = ' '
                    if curr_score > score:
                        score = curr_score
                        x = i 
                        y = j
    elif team =="O":
        score = 2
        x = 1
        y = 1
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == ' ':
                    board[i][j] = "O"
                    curr_score = minimax(board,0,True, len(board))
                    board[i][j] = ' '
                    if curr_score < score:
                        score = curr_score
                        x = i 
                        y = j
    submitMove(x,y)
\$\endgroup\$
  • 1
    \$\begingroup\$ Is there anything in the rule that prevents a lookup table? \$\endgroup\$ – Hagen von Eitzen Nov 18 at 20:15
  • \$\begingroup\$ There is not, that is why I made the value_dict lookup table at the beginning of the program. \$\endgroup\$ – DapperDuck Nov 18 at 21:28
  • \$\begingroup\$ Is that average time of yours for when you start the game or for when the opponent starts the game or did you average both cases? (And same question about that average time of the opponent.) \$\endgroup\$ – superb rain Nov 19 at 0:27
  • 1
    \$\begingroup\$ Geez again... out of curiosity, I just submitted a solution that always just simply makes a random possible move. And ... I won! So they don't even play perfectly. And it even only took me four moves. At the end they report my average time as "1063544". Yeah, without unit. And my individual times were 1829389, 2224877, 1873029, and 1517514 ns. How come my average is much lower than all of those, you ask? Because they divided the sum by 7. And there's pretty much no way my solution took anywhere near that much time unless they're running it on a pocket calculator. OMG that site is so bad. \$\endgroup\$ – superb rain Nov 19 at 0:43
  • \$\begingroup\$ Indeed, the site has some weird ways of calculating the average time. I just used the time at the very bottom of the "console window" as the average time. \$\endgroup\$ – DapperDuck Nov 19 at 0:51
2
\$\begingroup\$

There are a few thing you can do to speed up your code.

len(...)

There are several places where you have loops like:

    for i in range(len(board)):
        for j in range(len(board[0])):

It looks like you are trying to write code which will work for a variety of board sizes, like 3x3, 4x4, 3x4, 7x9. But ...

if board[0][0] == board[1][1] and board[1][1] == board[2][2]:

... your board will only ever be 3x3, and you've got that hard-coded in your winner() logic. Accept that you aren't writing general purpose code, and use the number 3, or a constant N defined as 3. You'll save the overhead of a function lookup, function call, and argument passing.

Chained comparison operators

    if board[i][0] == board[i][1] and board[i][1] == board[i][2]:

This looks up the value of board[i][1] at least once, and possibly twice. It is not going to change, so there is no need to look up the value for the second comparison. Simply use Python's chained comparison operators:

    if board[i][0] == board[i][1] == board[i][2]:

Repeated lookups

for i in range(len(board)):
    if board[i][0] == board[i][1] and board[i][1] == board[i][2]:

How many times is board[i] looked up in this loop? Maybe four times? In order to do that, board must be looked up in the local dictionary, then i must be looked up in the local dictionary, and then board[i] must be evaluated. Again, it doesn't change.

When you have a loop for idx in range(len(thing)): and you only ever use thing[idx] inside the loop, you're better off looping over the object itself:

for row in board:
    if row[0] == row[1] == row[2]:

Don't test for return values, then return those values:

You've determined that all three cells contain the same value. Now, if the first cell is an 'X', you return an 'X'. Otherwise, if the first cell is an 'O' you return an 'O':

        if board[i][0] == "X":
            return "X"
        if board[i][0] == "O":
            return "O"

That is a lot of indexing, lookups, and comparisons. Instead, how about:

        if row[0] != ' ':
           return row[0]

Remove unnecessary work

Consider:

                board[i][j] = "X"
                curr_score = minimax(board,0,False, len(board))
                board[i][j] = ' '

and

def minimax(board, depth, is_max, n, alpha = float('-inf'), beta = float('inf')):
    check_winner = winner(board)
    ...

The winner(board) function checks all 3 rows, all 3 columns, and both diagonals to determine the winner, if there is one.

If the move board[i][j] = "X" is at i=0, j=1, it is only necessary to check 1 row (row 0) and one column (column 1); checking all 3 is wasted effort. If i == j, then the down diagonal needs to be checked. If i + j == 2, then the up diagonal needs to be checked. You've gone from exhaustive 8 directions to check down to 2, 3, or 4. That should save you a bit of time. But you'd have to pass the location into the minimax function.

Useless code

This code does nothing.

                if beta >= alpha:
                    pass

If the condition is true, a statement which does nothing is executed. In other words, time got wasted. You probably meant to code something else...

PEP 8

The Style Guide for Python enumerates coding conventions that all Python programs should follow.

These include:

  • One space after each comma (violated in minimax(board,0,False, len(board)))
  • snake_case should be used for variable and function names. calcMove() violates this. (getGameState(), getTeam(), and submitMove(row, col) also violate this, but as you've pointed out, they're predefined from the coding challenge, so they're excused.). Oh, never mind, calcMove() is not predefined, but it a required name for the challenge framework.

Available moves

You are spending a lot of time searching for available moves. You search the entire board looking for a space where you can make a move. When you find one, you tentatively make a move, and call minimax, which again searches the entire board looking for a space where you can make a move. With 9 possible moves, this translates to \$9^9 = 387,420,489\$ checks for whether a cell is a space!

Instead, in calcMove, you could build a list of available moves:

valid_moves = [(i, j) for i in range(3) for j in range(3) if board[i][j] == ' ']

With this list of moves, you would select one, and pass a copy of that list of valid moves to minimax with that move removed. Then you would select the next one, and again pass a copy of that list of moves to minimax with this new move removed instead, and so on. The minimax function would do the same: for each move in the list of valid moves, make that tentative move and pass a copy of the valid moves without the current move. For 9 possible moves, this translates to \$9*8*7*6*5*4*3*2*1 = 9! = 362,880\$ move tests, an improvement of 1000-fold over the exhaustive enumeration of each move and testing for the space.

Tie

With the valid_moves list, checking for no valid removes remaining is simply len(valid_moves) == 0, or equivalently, not valid_moves. No need to search all 9 cells looking for a space.

Obvious moves

Similarly, len(valid_moves) == 9 means you’ve got an empty board, and can make a fast good move, like claiming the centre spot, or picking a random corner.

Also, len(valid_moves) == 8 would mean your opponent has made the first move. If board[1][1] == ' ' is still available, it is probably your best move. If their first move was the centre, then you could pick a random corner.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It's not \$9^9\$ but less than \$9!*9\$ (less because of early wins). \$\endgroup\$ – Heap Overflow Nov 19 at 16:08
  • \$\begingroup\$ @HeapOverflow D'oh. I mucked that up, didn't I? I should have questioned that 1000-fold improvement. A 9-fold improvement (9! * 9 / 9!) would be closer to the truth. I'll have to run a test to get the actual numbers, and correct my answer. \$\endgroup\$ – AJNeufeld Nov 19 at 16:32
  • \$\begingroup\$ Thanks for your answer! This was really helpful! \$\endgroup\$ – DapperDuck Nov 21 at 19:19
4
\$\begingroup\$

Here's a simple way to make it about 10 times faster and better: If the board is empty, make a random move instead of your search.

It's faster because the trees for subsequent moves are smaller than for the first move. And it's better because... well, if your perfect player plays against another perfect player, then it doesn't matter. But if your opponent is not perfect, then you'll still have to come across its weakness if you want to win. And you're more likely to come across it if you don't always do the same.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I tried this, and it decreased the first move's time by a lot. I then made the program submitMove(0,0) without any randomness, and it decreased the time further. However, the average time with this implemented is still greater than the average time of the opponent. I gave this answer an upvote, and will give accepted answer, if there are no other answers. Thanks for the help! \$\endgroup\$ – DapperDuck Nov 18 at 23:45
  • \$\begingroup\$ Could I apply heuristic pruning? \$\endgroup\$ – DapperDuck Nov 18 at 23:51
  • \$\begingroup\$ @DapperDuck Don't know about heuristic pruning, it's been a long time since I last wrote some alpha-beta minimax. If you want a very fast solution, maybe try this strategy? \$\endgroup\$ – superb rain Nov 19 at 0:19
  • \$\begingroup\$ Oh and I'd suggest to really wait for other answers, as I'm not really reviewing much. \$\endgroup\$ – superb rain Nov 19 at 0:24
2
\$\begingroup\$

Use numbers

Comparing strings is slow and expensive, numbers are what computers love the most. Comparing numbers will much much faster in this case. So instead of using X and O, use 1 and 0.

I prefer using an enum in scenarios like this.

class Player(Enum):
    o = 0
    x = 1

Player.x.value == 1
Player.o.value == 0

The same applies to your return values, don't use tie and continue, assign them to numbers, and use them instead. Again, the comparison of strings is slow and expensive. Comparison of integers is a single instruction.

If you are getting the board in the form of a string array, I suggest you convert it to an integer one.


Optimzing winner()

Your original code

def winner(board):
    for i in range(len(board)):
        if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
            if board[i][0] == "X":
                return "X"
            if board[i][0] == "O":
                return "O"

    for i in range(len(board[0])):
        if board[0][i] == board[1][i] and board[1][i] == board[2][i]:
            if board[0][i] == "X":
                return "X"
            if board[0][i] == "O":
                return "O"

    if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
            if board[0][0] == "X":
                return "X"
            if board[0][0] == "O":
                return "O"

    if board[2][0] == board[1][1] and board[1][1] == board[0][2]:
            if board[2][0] == "X":
                return "X"
            if board[2][0] == "O":
                return "O"

    for row in board:
        for cell in row:
            if cell == ' ':
                return "continue"
    return "tie"

Algorithm for checking winner

I'm afraid that this will disappoint you, but hard-coding the 8 directions is going to be significantly faster.

Following the previous two suggestions, which is two use a single-dimensional array of numbers to represent the board

def winner(board):
    if board[0][0] == board[0][1] == board[0][2] != Color.empty.value: return board[0][0]
    if board[1][0] == board[1][1] == board[1][2] != Color.empty.value: return board[1][0]
    if board[2][0] == board[2][1] == board[2][2] != Color.empty.value: return board[2][0]
    if board[0][0] == board[1][0] == board[2][0] != Color.empty.value: return board[0][0]
    if board[0][1] == board[1][1] == board[2][2] != Color.empty.value: return board[0][1]
    if board[0][2] == board[1][2] == board[2][2] != Color.empty.value: return board[0][2]
    if board[0][0] == board[1][1] == board[2][2] != Color.empty.value: return board[0][0]
    if board[0][2] == board[1][1] == board[2][0] != Color.empty.value: return board[0][2]

    
    for row in board:
        for elem in row:
            if elem == Color.empty.value: return None

    return TIE 

Benchmarks

I'll measure thee execution time of the winner() function

Old

#      Iterations      |     Time taken(s)
#  -----------------------------------------
#        10 ** 6       |         1.823
#        10 ** 7       |         18.843

New

#      Iterations      |     Time taken(s)
#  -----------------------------------------
#        10 ** 6       |         0.855   ( previously 1.823 )
#        10 ** 7       |         8.277   ( previously 18.843)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ How "much much faster" are such int comparisons? I get about 30 ns for string and about 27 ns for int. I don't think that deserves a "much much". \$\endgroup\$ – Heap Overflow Nov 19 at 13:10
  • \$\begingroup\$ What do your benchmarks measure? I guess calls of the winner function? With what board? \$\endgroup\$ – Heap Overflow Nov 19 at 13:14
  • \$\begingroup\$ @HeapOverflow The older one uses string, the new uses int \$\endgroup\$ – Aryan Parekh Nov 19 at 13:20
  • \$\begingroup\$ @HeapOverflow In my tests, working with a string board proved to be much slower, because every win call itself would have 8 comparisons, and a few more in minimax \$\endgroup\$ – Aryan Parekh Nov 19 at 13:21
  • 1
    \$\begingroup\$ Thanks for your answer! This was really helpful! \$\endgroup\$ – DapperDuck Nov 21 at 19:19
1
\$\begingroup\$

If you want speed, sacrifice memory. Precompute the best move for each of the 765 positions (exploiting symmetry) and dump into in a dict, probably using a bitboard to represent a position (for example, you can encode an entire game position into a single 32 bit integer 0b00000000ooooooooo000000xxxxxxxxx where o and x are nine bits for each square that can be occupied1). Look up the best move per turn in your data structure.

After this, it's all micro-optimizations. Eliminating branches and loops are generally good ideas with side benefits for increased readability and reduced cyclomatic complexity (fewer bugs).

There's no need to check for wins until at least the 5th move was made. Draws are pointless to check until the board is full. With a bitboard, moves and win/draw state check operations can boil down to masks and shifts. Then again, if you've precomputed everything, you can store the outcome in a couple of bit flags per state.

All of these optimizations are minor relative to the precomputation and table lookup, though. Writing a domain-specific implementation with a bunch of branches should also be pretty fast, but still seems likely to be slower than the hash table lookup and a lot more fuss.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ While interesting ideas, this answer does not even attempt to provide review comments on the code the OP provided. All answers on Code Review must actually provide a review of the existing code, or are invalid answers, off topic for the Code Review site, and subject to deletion. \$\endgroup\$ – AJNeufeld Nov 22 at 1:30
  • \$\begingroup\$ That's a bit surprising--this answer remarks less directly on OP's code but I don't see any comments to this effect there and it has three upvotes. I'm addressing OP's code on a high level and reviewing their overall design (reliance on branch-heavy code, checking win/draw conditions even when they're impossible, fundamentally using minimax) but not digging into a line-by-line analysis. How detailed do I need to be to qualify as on-topic and why is the other answer acceptable? \$\endgroup\$ – ggorlen Nov 22 at 3:12
  • 1
    \$\begingroup\$ I feel this answer is good and there shouldn't be an issue with it. If applied with @AJNeufeld's logic, then even superbrain's answer would be off-topic, but it isn't. \$\endgroup\$ – Aryan Parekh Nov 22 at 3:15
  • \$\begingroup\$ BTW, don't recommend bitboards in python. The bitwise operations are very slow \$\endgroup\$ – Aryan Parekh Nov 22 at 3:17
  • \$\begingroup\$ Thanks for that. You'd have to benchmark against the alternative which is representing a position with tuples or other hashable objects as keys to the move lookup dict--OP's 2d lists won't work. Manipulating these complex structures has a cost as well and even if bit operations are slower than you'd expect, I'd be surprised if they can't compete with typical object ops. The point is that you need something hashable and integers are just great for that. As my review points out, the critical part is that everything is precomputed so it's sort of splitting hairs either way. \$\endgroup\$ – ggorlen Nov 22 at 3:37

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.