Author: Roberto Waldteufel
Date: 07:40:35 04/07/99
Go up one level in this thread
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
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.