minimax complexity tic tac toe


minimax complexity has an upper bound complexity of o(b^m), where b are the legal moves in the game and m the depth of the search tree.

For an unbounded tic-tac-toe search, the max depth would be 9, and the number of legal moves goes decreasing as the search deepens e.g. at depth 0 it’s 9, at depth 1 8 and so on. Thus the complexity should be o(m!).

However my current implementation gives 434746 iterations to the minimax function (for the first movement), which leads me to think that my previous analysis is wrong. Any hints/ideas?

9^9 > 434746 > 9!