Author: Roberto Waldteufel
Date: 16:06:37 04/07/99
Go up one level in this thread
On April 07, 1999 at 12:08:45, Hristo wrote: >On April 07, 1999 at 10:40:35, Roberto Waldteufel wrote: > >>On April 07, 1999 at 10:23:44, Hristo wrote: >> >>>Has anybody tried to use linked lists instead of hash tables. >>>I'm currently using a Quad linked list, i.e. Node(prev, next, parent child) to >>>store the evaluated positions. The prev-next relation identifies all possible >>>positions at a certain ply, and the parent-child relation is used to store the >>>different ply-depths. For instance NodeC = Node->child->child->child would go to >>>a position 3 plys away from the current evaluated position. Then the child will >>>have NodeC->next ... with all possible moves within this position. >>>What I can see is: >>>Linked lists: >>> -keep the order(paths) of moves static(you always know how you get to a >>>certain position). >>> -use memory more efficiently(?). One can discard a particular branch, >>>completely, in a middle of a search and reclaim the unused memory. >>> -gives you the ability to traverse more easily. One can widen the tree >>>without losing the currently evaluated position and the path to it. >>> -No random access to the tree. >>> -No or very little detection of move reordering. i.e. one can end up >>>evaluating the same position more than once ... nasty(!) >>> -Generally slower performance. However, in some cases the performance seems >>>to be quite good! >>> >>>What are your thoughts(experience) on this topic? >>> >>> >>>regards. >>>Hristo >>> >>>p.s. >>> Thanks Dan C. :-) >> >>I would have thought that hashing would be faster than linked lists. > >Hash is much faster(most of the time) method for getting the information you >describe bellow. However my main problem is the usefulness of the data stored in >the tree vs hash. I beleive tree style yelds better information handling .. >I can easily recognize transposition within 2 plys, but going deeper is very >slow ... :( I wonder, what is the percentage of transpositions 2,3,4,5 plys away >from the current position? (How often do we have transposition 5 plys away as >supposed to 2 plys away?) > >regards. >Hristo > I think that the deeper you go, the more possibilities for transposition there will be. I have not experimented to test this, but mathematically I would expect the number of transpositions to increase exponetially with search depth. Maybe a combination of both methods could work well though. Best wishes, Roberto
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.