I''ve been toying with writing a chess program and have been having a little trouble thinking about how I''d accomplish something. Let''s say that I''m using a general search tree to search through positions to find the best one, like the one below. Let''s say that it is the computer''s turn to move, so he begins thinking and searching his search tree and this is how far he gets before he decides that he has run out of time and needs to make his move. So the computer decides that the first move in the tree was the best move, and so he makes that move, and now waits for his opponent to make his move. While the computer waits, it will continue to search until it''s opponent has made his move. Here''s my question. How do I avoid having to restart a new search of the new position everytime one side makes a move? If I have to restart the search everytime one of the players makes a move, then I will be ending up repeating a lot of the searching that I had already done during previous searching. Maybe this isn''t that hard and I''m just missing something obvious, but whatever the reason, I''m not getting how I should go about accomplishing this. I believe it would be much more advantageous in a chess game, or any other game that uses search as it''s method of intelligence, to avoid restarting the search from the new position everytime one side makes a move. It seems that after many moves into the game, that if you could keep a cumulative tree search going, that you would little by little increase the depth that you are searching farther than it would have been if you had restarted the tree search after every move, and with the added depth would come stronger play by the program (that''s my thinking anyway). If you have any ideas on how I should go about doing this please let me know.

Well, the obvious way would be to do a breadth first search keeping all the tree in memory. Then when someone makes a move cut off all the branches except the one that corresponds to that move. The top of that branch now becomes the root node and you can keep on searching from where you left off.

This technique uses an exponential amount of memory. But if you have more memory than time you might as well use it.

ro