On Sat, 2007-01-20 at 10:19 +0100, Heikki Levanto wrote:
> That also means that you have to keep enough data in each node to
> recalculate the hash keys from, for example the board position etc.
> Maybe it would be enough to keep the zobrist hash of the position, and
> use different bits of it for
On Fri, Jan 19, 2007 at 10:46:07AM -0500, Don Dailey wrote:
>
> On Fri, 2007-01-19 at 12:00 -0200, Mark Boon wrote:
> > What ticked me off with the cuckoo method is apparently it can loop
> > and a rehash is needed. Ouch, that better not happen very often!
>
> The whole point is that this cost
I seriously doubt any of this makes a difference for a huge data
structure.
I'll check it out though.
- Don
On Fri, 2007-01-19 at 17:49 -0600, Jim O'Flaherty, Jr. wrote:
> Don,
>
> You wrote:
> > Does it matter?...
>
> While I am not totally up-to-date on C++ compiler optimizers, it seems
> l
Don,
You wrote:
> Does it matter?...
While I am not totally up-to-date on C++ compiler optimizers, it seems
like locality of reference compiler optimizations might be influenced if
you were to specify allocation on the stack as opposed to the heap. And
aren't stack based values much more li
On Fri, 2007-01-19 at 17:19 -0600, Jim O'Flaherty, Jr. wrote:
>
> Don,
>
> So could you elaborate on where you are allocating space for big_array
> in your code snippet below?
>
Does it matter? I just declare it as a global but I will probably
eventually
just place it on the heap via malloc -
I don't think Don was clear about whether he was using stack, heap or static
allocation of that structure. I am just saying that it could be done in
such a way that any code anywhere can know where that object is without
having to pass around a pointer to the structure which is a really nice
feat
Nick,
I am not sure I follow. Are you implying the following
"...&(big_array[1300])" an strong indication that big_array is stack
based, as opposed to heap based? It is possible to do such a thing as
stack based in Java, although quite uncustomary and require special
start-up parameters to
This is a very good design in my opinion. I was about to ask why you used
an index instead of a pointer until I saw that you were using a pointer
actually. Using global data like this highlights one of the ways that C++
can blow away Java's requirement that everything must be allocated on the
he
On 1/19/07, Mark Boon <[EMAIL PROTECTED]> wrote:
This seems to be only a small variation of hashing methods I was
taught at university in the 80s.
The method I always used was simply putting the new value and key in
the place of the old one, with one simple addition. In case the spot
is filled i
On Fri, 2007-01-19 at 12:46 -0500, Chris Fant wrote:
> Are there more experimental results coming? Have you tried going
> higher than 100 yet? How much memory do you need at 100 during the
> course of a 30 minute game?
I don't have the computing resources to test everything I would
like to. Bu
Are there more experimental results coming? Have you tried going
higher than 100 yet? How much memory do you need at 100 during the
course of a 30 minute game?
On 1/19/07, Don Dailey <[EMAIL PROTECTED]> wrote:
I'm not sure it matters, because as I reported earlier you
can delay node expansion
On Fri, 2007-01-19 at 16:51 +, Eduardo Sabbatella wrote:
> Sorry, I didn't understand the big table but It sounds
> promissing. I don't understand how do you access to
> different variations ... it seems like a merge-sort
> array but not sure.
It forms a tree in memory, but it's just a huge a
Sorry, I didn't understand the big table but It sounds
promissing. I don't understand how do you access to
different variations ... it seems like a merge-sort
array but not sure.
--- Don Dailey <[EMAIL PROTECTED]> escribió:
> I'm not sure it matters, because as I reported
> earlier you
> can dela
I'm not sure it matters, because as I reported earlier you
can delay node expansion with hardly any effect on the strength,
and I'm requiring 100 hits before expansion.
Pruning out moves from the tree WILL weaken the program -
the question is how much? There is a tradeoff of course.
What I am d
I see your point.
I was thinking that after X simulations, transposition
table could be made 'persistent'. Not before that.
So this will avoid a lot of 'garbage', not so 'useful'
board states.
I have to think a lot about it. But I suposse as my
transposition table implementation, it should have
On Fri, 2007-01-19 at 11:45 +0100, A van Kessel wrote:
> My personal summary: it is very hard to be more clever
> (at replacement) than "always replace when hitting an occupied slot".
> (this is very similar to beating a LRU-replacement-sheme for
> disk-blocks;
> but totally different ;-)
You can
On Fri, 2007-01-19 at 11:33 +, Eduardo Sabbatella wrote:
> If this ratio becomes tooo low (ex, win ratio below 1%
> with 10 games confidence), you can be sure you can
> delete all the game tree after this move. All the
> transposition tables following this move.
I think you can win, but
On Fri, 2007-01-19 at 12:00 -0200, Mark Boon wrote:
> What ticked me off with the cuckoo method is apparently it can loop
> and a rehash is needed. Ouch, that better not happen very often!
The whole point is that this cost is extremely tiny when amortized
over the run time of the whole algorith
Worst case on "classical" hash is lineal. Never
happend, but on heavy loaded hashes, you can get
lineal times which is bad, very bad.
Using Cuckoo method, with a hash table the double the
size of the expected items, it ensures you that the
collision is almost null.
It seems strange the "loop infi
On Fri, 2007-01-19 at 07:17 -0300, Eduardo Sabbatella wrote:
> Hello,
>
> Did someone try to store the transposition tables of
> the first n plys in order to reutilise them?
This is probably a good idea. Since the tree in UCT
is deep and narrow, you should probably not reset it
between moves,
This seems to be only a small variation of hashing methods I was
taught at university in the 80s.
The method I always used was simply putting the new value and key in
the place of the old one, with one simple addition. In case the spot
is filled it would look at the next 'n' spots until it
I have just understood the algorithm.
Quite interesting, the collision prob decreases in the
power of two on every step. Nice.
Also quite new, I like to see new, basic and simple
algorithms. Not common this days.
Thanks!
--- £ukasz Lew <[EMAIL PROTECTED]> escribió:
> Take a look at
> http://e
Take a look at
http://en.wikipedia.org/wiki/Cuckoo_hashing
also.
Lukasz
On 1/19/07, Eduardo Sabbatella <[EMAIL PROTECTED]> wrote:
Right now my two main concerns are about:
1) feasability, perhaps even prunning with UCT for
storing usefull games, no more than 5 ply can be
stored on nowadays mem
Right now my two main concerns are about:
1) feasability, perhaps even prunning with UCT for
storing usefull games, no more than 5 ply can be
stored on nowadays memory constraints.
2) techniques for prunning gametree on big "databases"
of game configurations. This thing by itself its a
quite big
I believe that clustering algorithm is algorithm is both more
practical and elegant, than
two big, and other multilevel schemes.
- It uses memory in more efficient manner effecting in reduction of
collision rate.
- It allows for more than 2 entries on the same hash before loosing
the information
On 1/19/07, Eduardo Sabbatella <[EMAIL PROTECTED]> wrote:
> interesting question may be how to efficiently free
> memory from
> entries that become irrelevant in the continuation
> of a game (after
> the actual moves made have ruled out portions of the
> full game-graph),
> but this is probably
I'm talking about a transposition table storing
win/played values (MC interested values.).
If this ratio becomes tooo low (ex, win ratio below 1%
with 10 games confidence), you can be sure you can
delete all the game tree after this move. All the
transposition tables following this move.
I wi
> interesting question may be how to efficiently free
> memory from
> entries that become irrelevant in the continuation
> of a game (after
> the actual moves made have ruled out portions of the
> full game-graph),
> but this is probably not an issue in the context of
> the original
> poster's que
> No it wasn't. I think you're confusing me with Dennis Breuker.
I stand corrected.
> Yes, "new" does quite well
At least I remembered the conclusion.
Remembering the Authors name should be next on my list...
AvK
___
computer-go mailing list
computer-g
On 1/19/07, A van Kessel <[EMAIL PROTECTED]> wrote:
Erik van der Werf's thesis was mainly about
transposition table replacement algorihtms, IIRC.
No it wasn't. I think you're confusing me with Dennis Breuker.
see: http://www.xs4all.nl/~breukerd/thesis/index.html
I have some knowledge on trans
> UCT could help to tiddy up the transposition table
Erik van der Werf's thesis was mainly about
transposition table replacement algorihtms, IIRC.
My personal summary: it is very hard to be more clever
(at replacement) than "always replace when hitting an occupied slot".
(this is very similar to
Hello,
Did someone try to store the transposition tables of
the first n plys in order to reutilise them?
I mean, at least the first 5 or 10 plys.
We are talking about a lot of GB.
UCT could help to tiddy up the transposition table
after a degree of confidence is gained. This could
save a lof of
32 matches
Mail list logo
