Author: J. Wesley Cleveland
Date: 10:48:25 05/11/01
Go up one level in this thread
On May 10, 2001 at 21:23:49, Dann Corbit wrote: >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) No. We are evaluating, not playing, and there is no reason to continue evaluating a line that could be called a draw by either side. >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. Exactly. > 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? I never said "easy". Take tic-tac-toe as an example. The principles are exactly the same, but the numbers are small enough to work with. The tree has an upper bound of 9! or 362880 nodes. The transposition table has an upper bound of 9!/(5!*4!) + 9!/(4!*4!) + 9!/(4!*3!*2!) + 9!/(3!*3!*3!) + 9!/(3!*2!*4!) + 9!/(2!*2!*5!) + 9!/(2!*6!) + 9!/(7!) + 9!/(8!) +1 or 6046 entries. If you do an alpha-beta search of the tree, you will visit only a few hundred nodes and have a proof that with best play, it is a draw. >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. Again, not for evaluation.
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.