Author: KarinsDad
Date: 08:01:06 04/07/99
Go up one level in this thread
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. The main >point of hashing is surely to avoid searching the same position more than once >when it arises by transposition of moves, which would be lost using linked >lists, but at least errors due to repetition draws should be easier to avoid: >this is a major drawback with hashing that has caused problems for many of us >and has often been a topic of discussion. With hashing you always recognise the >same position, but know nothing about the p.v. from that position that lead to >the evaluation stored in the table. With your method you have much more >information about the move sequences, but lack a way of recognising when the >same position occurs elsewhere in the tree. It sounds like an interesting idea >though - I hope you persevere. Good luck, > >Roberto I am using a combined hash table / linked list. So far, it seems to work ok (but it is somewhat slow and I am still in early development). It has the advantages of both systems. It has the disadvantage that it uses up more memory (keeping a link to every parent and every child). It has another disadvantage in that everytime I drastically change a score (+/- a small delta), I must go back through all of the parents and update the nodes above them with the new score (I do not know how this is handled in a normal hash scheme). I haven't yet added in a "Next / Prev" set of links. I'm not sure yet if I need them. KarinsDad :)
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.