Author: Hristo
Date: 14:26:48 04/07/99
Go up one level in this thread
On April 07, 1999 at 15:13:13, Dann Corbit wrote:
>I have seen some discussion on using linked lists for things.
>
>If you want to use linked lists, I would suggest skiplists.
>They use only about 1.3 pointers per element, give random access which is
>O(log2(n)), and are very simple. They were invented by Bill Pugh, and a web
>search will turn up code for one in most any language. Sequential access is
>still O(1) also. I have a C++ template I use for them. They should have been
>added to the STL. Shrug.
Thanks Dann.
http://www2.be.com/~dbg/src/skiplist/
seems to be a good source, but you were correct, there is many implementations.
I'm not sure if I can use this approach at the moment. I have to think about it!
The search part is great, but I'm not sure how to preserve the path(child-parent
relation) and implement key based indexing. The key reorders the elemnts and I'm
trying to have everything ordered using depth+move+eval(deep-eval), since nodes
get added after every successful move they(the nodes) are added at the right
place, and at the right time to begin with. Those nodes should stay
there(child-parent) relation! However every Node has a prev-next relation that
identifies all other possible moves in a given position. So the reordering is
done(at the moment) only in the prev-next relation. For instance:
let <np> = next-prev relation, and
<cp> = child-parent relation.
e2e4 <np> d2d4 <np> g1f3 <np> c2c4 <np> ...
<cp> <cp>
c7c5 <np> e7e6 <np> ... e7e5 <np> g8f6 <np> ...
... I hope this explains better what I'm trying to do. :) ("trying" is the main
word)
It might be easier to use hashing methods to speed-up the detection of already
evaluated positions.
regards.
Hristo
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.