Thanks a lot for the useful insight. I hadnt considered using only one gamestate with undo moves. I will definitely give it a try and see if this is a faster way to perform the search.
Update: Well, it turned out to be quite easy to implement. After editing my code, my program issued me the following response:
I visited 137257 nodes, of which 117649 are leaves, in 304 miliseconds which is 452 nodes/ms
Almost 400 times as fast Thanks a lot, it gave me a great insight in how memory is being used.