Author: Dann Corbit
Date: 18:23:49 05/10/01
Go up one level in this thread
On May 10, 2001 at 21:16:58, J. Wesley Cleveland wrote: >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. 1. The tree is infinitely deep (see posts on draw rules) 2. If it were not infinitely deep, you still have to store the pointers to the nodes. The value at the node is just a data element of that node. You won't know for sure what the value of any node is until you have either processed the whole tree or found terminal status for all subtrees underneath of it. Not as easy as it sounds. Remember, the above position is one instance of a position in the tree. When will you know what it's worth? 3. As demonstrated elsewhere, it is at times advantageous to ignore certain draw rules and continue playing. It is well within the rules to gather a win instead of a draw in such circumstances.
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.