Best data structure for an N-ary tree

I need to represent a tree with multiple branches per node. What structure should I use? It's for computing chess game states. It explodes exponentially so memory will be a concern. I'm using C++11 but am open to other standards. Also, pruning should be O(1).