25% performance boost by preallocating the search tree
No need to keep track of previous position anymore