Storing nodes in state space search I'm taking an introductory course in AI and we've been given the assignment to solve a puzzle using different search algorithms on a state space (BFS, DFS etc). I understand the theory and everything, but I'm not sure what information I should store in the nodes of the tree.

Assume that I have a matrix to represent the game board. Should each node in the tree contain the entire board? For example, in the case of 19x19 Go, would each node consist a matrix of size 19x19 (the problem I'm trying to solve is a 1 player game, and not Go or chess or anything like that, however)? If this is the case, even with pruning, it sounds to me like this would take up an insane amount of space. For example, at depth 1, a state space of the game of Go would have 19*19 nodes each containing a 19*19 matrix (correct me if I'm wrong here). At the same time, I can't find a better option. 

What is the general approach to storing these kinds of states?

Any help is greatly appreciated. 
Please let me know if the question is in any way unclear.
The common answer to "What to store?" is "As much as you need and nothing more."

You can instead store a reference to the previous state and the move(s) you made on the previous state to get to the current state. 

This is more compact that a full copy of the state in each node but less convenient to work with because you'd need to reconstruct the state by following all the moves made since the last known full state node. 

The next option is to throw away parts of the graph that you aren't looking at at the moment and instead recreate it later when needed. 

Both of these options trade space for time.