Agreed. 

I wrote play() mostly to have something to show(), this is nowhere near final :)

I think building a new board is better for search algorithms, clearly. In the long run, it would be cool not to use tree, but directed graphs for search, as this would enable not looking at the same thing twice.