Author: Robert Hyatt
Date: 09:19:56 11/27/01
Go up one level in this thread
On November 27, 2001 at 01:58:05, Russell Reagan wrote: >I'm trying to decide between constructing a tree with the root node being the >current position, and it's children being the positions that result from legal >moves, and their children being the same, etc. But this seems like it would take >a large amount of memory to store all of this information. > >Here's my thinking... > >On an engine that searched 1 million positions per second, you could store only >the moves that get you from position to position in your tree, and let's say for >the sake of discussion that you stored the move in 1 byte. So for a 60 second >search, that's 60 million bytes that you now have to store. So your program >would have to have approximately 60 MB of memory for every minute the program >searched. > There is a problem here. The approach you are taking is generally applied to a breadth-first or best-first type search, where the tree grows as the search progresses. Unfortunately, alpha/beta is a depth-first strategy that eliminates a huge part of the tree. But every now and then you have to search (on the next iteration) parts of the tree you pruned away last iteration. So you are going to end up with a _huge_ memory requirement that is going to totally kill you. Remember that storing the whole tree, a 5 ply search will have 38^5 nodes in it, not counting any sort of extensions or anything. That would be all you could reasonably store, and it isn't _near_ enough to play real chess. :) >Obviously this is far less memory than a recursive search would do, because it >doesn't save each and every node of it's search. > >Am I thinking about this correctly? The search tree method would take a ton more >memory than the recursive method, correct? > >Any other advantages or drawbacks to either method? The memory complexity of your approach is exponential. The memory complexity for depth-first is linear. Exponential is a problem. > >Thanks, >Russell
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.