Author: J. Wesley Cleveland
Date: 18:16:58 05/10/01
Go up one level in this thread
On May 10, 2001 at 18:19:43, Dann Corbit wrote: >On May 10, 2001 at 18:14:02, J. Wesley Cleveland wrote: > >>On May 10, 2001 at 16:48:39, Dann Corbit wrote: >> >>>NO big-O stuff in here! I promise! >>[snip] >>> >>>Now the board positions is another matter. Let's suppose that there are only >>>10^50th distinct board positions, including halfmove clock, castle rights, etc. >>>We might store those in a linear list, and just have pointers from our tree to >>>the list. We would have to use 64 bit pointers because of the size of the list >>>(some other clever indexing method might conceivably reduce this). >>> >>>Even if we could use perfect move ordering and only store sqrt(5.28713e9320) >>>elements in the list, that's still a lot of pointers. >>> >>>Or have I missed something. >> >>Yes. Each position has the best move (or 1 of the n equal best moves) stored >>with it. > >You STILL have to store the whole tree! You won't be able to compute the best >move until you have analyzed the whole tree. > >IOW -- where does the best move COME from? > >The entire problem we are facing here is: >What is the best move from this position: >[D]rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - >The entire effort I am talking about is to find the answer to what is the best >move from here! > >How will you answer that question until you know all the others. > >Storing the best move doesn't help a thing. You do your standard alpha-beta search (which only needs O(maximum depth*branching factor) bytes memory (which is trivial in comparison). When you have a node with a result, you save it. When all nodes below a given node have a result, you can mark that node with a result and a best move. Continue, and eventually you will have a result for the starting position.
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.