1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ You might be interested in Bitboards $\endgroup$ – adrianN Sep 21 '17 at 14:07
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer! I actually thought of just storing the changes but implementation seems difficult, and, as you say, at the cost of time. Just out of curiousity; how do they store the nodes in like AlphaGo and DeepBlue (I know DeepBlue is old but that makes it even more interesting, even though pruning made a huge difference)? $\endgroup$ – Lobs001 Sep 21 '17 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.