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
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
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 question.
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
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 not an
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
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
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
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
On Fri, 2007-01-19 at 14:04 +0900, Darren Cook wrote:
My point being that a top pro will find a high quality move in the time
it takes him to move the mouse from one side of the board to the other.
But still it's *WAY* below his normal tournament playing strength to
play so quickly...
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, but
for what it's worth, strong players often spend enormous amounts of time
on moves. professional tournament games are not generally of the
2-second-per-move variety. historically, they have taken days, but i'm not
sure what the standard is now. perhaps someone who has seen a web
simulcast of a
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
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 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
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
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 delay
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
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 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. But
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 it
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
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
At 08:45 PM 1/18/2007, you wrote:
On Thu, 2007-01-18 at 20:05 -0800, Ray Tayek wrote:
yes. i would easily give my opponent *much* more time than a few
handicap stones. the effect of time making someone (or thing) play
better (or worse) is non-linear and probably only effective over some
24 matches
Mail list logo
