sorting move before alpha beta pruning - tic tac toe - python

Question

I have the negascout or principal variation search algorithms working fine to solve tic tac toe. I have read somewhere that for these algorithms to be most efficient it is important to sort the moves such that the search starts with what is likely going to be the best move.

Assume the heuristic that in tic tac toe, the center square is better than a corner square, which is better than a side square.

I represent a square in tic tac toe by an integer between 1 and 9, as ordered on a numerical keypad. In Python3, I am currently doing:

def sort_candidate_move(candidate_move):
    # center > corner > side
    move_dict = {1: 'b', 2: 'c', 3: 'b', 4: 'c', 5: 'a', 6: 'c', 7: 'b', 8: 'c', 9: 'b'}
    to_sort = [(move_dict[move], move) for move in candidate_move]
    to_sort.sort()
    return [tup[1] for tup in to_sort]

where candidate_move is the list of candidate moves, for example:

candidate_move = [2, 5, 9]

The code returns:

[5, 9, 2]

It seems that ordering moves that way does not give any benefit in terms of computing time to solve tic tac toe.

Is there a more efficient way (in terms of computation speed) to code the function sort_candidate_move()?

Maiki Bodhisattva Maiki Bodhisattva · Accepted Answer · 2018-11-16T15:27:02

Tic-tac-toe game is at most 9 steps, giving less than 9! different games. For a problem of this scale all sensible algorithms will be superfast, so comparing their times will not show much difference. The algorithms' time-complexity estimates ("big O") are asymptotic, which means they are apparent only for problem of large to very-large size.

sorting move before alpha beta pruning - tic tac toe - python

1 Answers