Thursday, April 2, 2009

The advantages of O(b^d)

The punch line is that the advantages of exponential time complexity is that even small improvements in performance are not so small.

For instance; When I finely got the alpha-beta pruning correct (I think) on my Connect 4 AI and it's effective complexity went from O(70.7 d) to O(70.6 d). For d = 13 that's 49 million leafs to 3 million leafs.

This is the same principle that make this idea reasonable

No comments:

Post a Comment