> I was also hoping to use my DAG as a transposition table,
> so I could use the Zobrist hash of the current position
> to find where the child node would be if it existed. If
> the space was already occupied (by a node at the right
> depth), I would have a transposition.
>
> If each "node" might r
I was also hoping to use my DAG as a transposition table, so I could
use the Zobrist hash of the current position to find where the child
node would be if it existed. If the space was already occupied (by a
node at the right depth), I would have a transposition.
If each "node" might really
Okay, so I created a FastSloppyBoard class that works like a Board
but doesn't maintain ko or Zobrist information. Not all the wires are
plugged in yet (e.g., I'm not incorporating the results into the
tree), but this got me about a 20% improvement in run per second. For
those of you keepin
On 12/7/06, Don Dailey <[EMAIL PROTECTED]> wrote:
Probably one of these would suffice:
http://www.lns.cornell.edu/spr/1999-01/msg0014148.html
- Don
Wow, very cool page on fast RNGs. Thanks.
___
computer-go mailing list
computer-go@computer-
Yes, there are fast little generators that would probably serve our
purposes, however I don't want to have to spend too much time checking
them out so I found one that was known to be quite fast, the Mersenne
Twister.
But what you say is now a consideration based on what I've learned about
the spe
> So it's
> quite possible that
> this sequence dominates the call to rand().
on another note, if the only reason that you
need random numbers is to choose a number from
a list (<82, or <362), and the depth is being
constrained to something reasonable, then what
you need is not a super-duper rand
By the way,
I'm amazed that the code for playing random games is fast enough that
getting random numbers is actually a bottleneck and it's worthy of a
discussion on optimization.
One of the fastest chess programs a few years ago in terms of nodes per
second was Fritz. It heavily used a common te
I will test it with a table derived mask and see what happens. I would
like the table to be large enough to encompass 19x19 GO too, but I'll
test it with a small table first.
- Don
On Fri, 2006-12-08 at 00:39 +0100, Antoine de Maricourt wrote:
> Last time I checked MT was under 20cc per call (I
Yes I used such a representation, not in the context of MC, but for
experimental algorithms where I needed to know all paths that could lead
from the root to a given node. I used a representation that I found
later to be described under the name 'twin node' (in someone's thesis I
guess, but
> Is anyone storing a search DAG (as opposed to a tree) and
> using the firstChild/nextSibling representation?
> When you traverse children (e.g., in UCT) you have to
> know which move is associated with which child node. If a
> node might have more than one parent, the node can't store
> its last
Last time I checked MT was under 20cc per call (I assume it's inlined).
On a P4, the shift operator is supposed to have a 4 cc latency. The
dependency chain to get the mask yields to 25 cc latency before the mask
can be used (4 per shift + 1 for OR) * 5. So it's quite possible that
this sequenc
I see. I only recently had this realization that the within-tree and
purely-random parts of the search were deeply different. I'll take a
shot at this.
Thanks,
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 3:21
Peter,
I also want to point out that I DO do full KO testing, but it's just in
the tree search - it's the Monte/Carlo part that's a waste of time.
I say that because monte/carlo is a RANDOM search, it's not going to
deal with any positional finesses and such. It's too expensive even to
mainta
On Thu, 2006-12-07 at 14:09 -0800, Peter Drake wrote:
> > In the search tree part of the game, (not the random simulation
> > part) I
> > make state copies, do Zobrist hashing and full repetition checks and
> > other stuff - the tree part is cheap.
>
> Agreed -- the playing of moves is the expe
I'm pretty sure the time of this function is dominated by the call to
rand(), but it never occurred to do a table lookup for the mask,
interesting idea.
- Don
On Thu, 2006-12-07 at 22:36 +0100, Antoine de Maricourt wrote:
> If this randint routine is critical, you can save some calls to rand()
I can avoid the ko problem by storing the depth of each node and
never creating a link from a node at depth d except to a node at
depth d+1. This prevents any cycles, at the (minimal, in my opinion)
cost of omitting transpositions of different lengths.
I need the move for two reasons:
1) I
DAG's have a problem with graph history, especially with super ko
considerations. Do you need the parent play for more than ko
considerations?
-Original Message-
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of Peter Drake
Sent: Thursday, December 07, 2006 5:47 PM
To: Compu
(This is all within the context of Monte Carlo.)
Is anyone storing a search DAG (as opposed to a tree) and using the
firstChild/nextSibling representation? I'm having trouble seeing how
this would work, since when you traverse children (e.g., in UCT) you
have to know which move is associate
On 7, Dec 2006, at 2:09 PM, Peter Drake wrote:
Are you one of those who advocates ignoring the ko rule during MC
searches?
SlugGo is not monte carlo, but we launch parallel lookahead
sequences, so its not really different than your threads. We ignore
the ko info in the lookaheads and only
On Dec 7, 2006, at 11:08 AM, Don Dailey wrote:
On Thu, 2006-12-07 at 09:17 -0800, Peter Drake wrote:
I do have the undo ability, but I think it's done in (I think) a
very
efficient way. For example, when I want to undo a bunch of move at
once (e.g., after a MC run) I just reduce a stack pointer
If this randint routine is critical, you can save some calls to rand()
when you know that n is always below some value (see my previous post
about bitmap go).
For instance if n < 128 (probably true for 9x9 go), you could try:
while (true) {
r = rand();
if ((r & v) < n) return (r & v);
r >>=
What about having each MC thread queue up it's results and have another
thread read the queue and update the tree... This is assuming that a the
time to update the tree is long and the time to enqueue is very short.
Jeffrey Greenberg
http://www.inventivity.com
http://www.jeffrey-greenberg.com
On Thu, 2006-12-07 at 09:17 -0800, Peter Drake wrote:
> I do have the undo ability, but I think it's done in (I think) a
> very
> efficient way. For example, when I want to undo a bunch of move at
> once (e.g., after a MC run) I just reduce a stack pointer.
BINGO! I'm pretty sure that is yo
Precisely: I'm getting almost optimal use of my dual-core processor.
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 10:47 AM, Don Dailey wrote:
On Thu, 2006-12-07 at 10:24 -0800, Peter Drake wrote:
Got it -- now I'
On Thu, 2006-12-07 at 10:24 -0800, Peter Drake wrote:
> Got it -- now I'm getting just under 10,000 games per second! Whee!
Hold on, I thought the non-threaded version was doing 5,000? What
exactly did you change? Or are you just using 2 processors more
efficiently to get 10,000 games?
- Don
Let me propose the following rules for comment:
1) The vast majority of your time is spent making RANDOM moves
(beyond the leaves of your tree).
2) Almost none of your nodes have more than one child.
These, along with the KISS principle, seem to point to a lot of
optimizations in both time
Got it -- now I'm getting just under 10,000 games per second! Whee!
(FWIW, I actually don't have the UCT part in there yet -- these are
purely random games.)
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 10:07 A
I just made a wonderful discovery!
The D version is in fact only 7 percent slower than C.
Earlier I mentioned the ONLY difference was the random number generator
- well it turns out the random number generator was a big deal.
The Mersenne twister is apparently far faster than the D libra
There is a pattern that i don't remember the name for
this kind of tasks.
You should create a pool of n threads and assign work
to them from a main thread. You can use two queue per
thread.
On "in" queue you will insert a task, and on "out"
queue you will read the task's result.
Threads are bloc
Aha! Now I get it. You only have to look at the tree during the
opening part of the run. Once you've fallen off and are making purely
random moves, you can let someone else use the tree.
Thanks!
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~
> The problem is that a single MC run takes about 1/5 of a millisecond,
> so it's not worth the overhead of putting it off into another thread.
Creating a thread for each MC simulation is clearly very costy.
> I need some way to tell a thread to do many runs, then somehow
> incorporate the multipl
I test on IGS, and I also see a lot of cheating against the computer.
Many Faces does its own scoring and transmits dead stone status. This
prevents people from not indicating their dead stones. Many Faces keeps
track of people who escape without finishing a game and won't accept matches
from th
On Dec 7, 2006, at 9:42 AM, [EMAIL PROTECTED] wrote:
Hello,
Those of you with multithreaded UCT programs -- how do you do it?
Doesn't UCT pretty much require updating a common data structure
after each MC run?
in MoGo we simply protect the tree access using a mutex, so only
the MC
simulations
I'm afraid I don't follow you. I THINK I'm doing what you describe.
My Player object creates several threads, each of which plays a game.
After all of the games are completed, the main thread incorporates
them into the search tree. Here's the Java:
timer.schedule(interrupt, MSEC_PER_MOVE);
Hello,
> Those of you with multithreaded UCT programs -- how do you do it?
> Doesn't UCT pretty much require updating a common data structure
> after each MC run?
in MoGo we simply protect the tree access using a mutex, so only the MC
simulations are run in parallel. The tree update is done by onl
> Those of you with multithreaded UCT programs -- how
> do you do it?
> Doesn't UCT pretty much require updating a common
> data structure
> after each MC run?
you could hand a job (starting position) to each
thread and have the thread manager update a shared
memory segment that they all can r
Those of you with multithreaded UCT programs -- how do you do it?
Doesn't UCT pretty much require updating a common data structure
after each MC run?
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 7, 2006, at 9:17 AM, Peter Dr
In fact, I just wrapped this up into my Mersenne twister code - randInt
is now built in to the library and I eliminated the function call
overhead of calling rand() (or the mersenne equivalent.) Probably won't
make a noticeable difference, but since I'm porting it to D anyway, I
might as well fix
On Dec 7, 2006, at 9:05 AM, Don Dailey wrote:
Are you trying to keep a lot of information updated? Mine only tries
to play random games as fast as possible. It does not have the
ability
to undo moves - this is easily handled by copying state when you need
this feature.
I do have the und
On Thu, 2006-12-07 at 16:05 +0100, Łukasz Lew wrote:
> ii = pm::rand () % empty_v_cnt; // TODO improve speed "%"
Try this, I think it could be faster, not sure, but has the advantage
that it's slightly more correct.
// returns an integer between 0 and n-1 inclusive
//
unsigned lon
On Thu, 2006-12-07 at 08:15 -0800, Peter Drake wrote:
> On Dec 6, 2006, at 9:36 PM, Don Dailey wrote:
>
> > The equivalent C version (after I took out some optimizations) is
> > doing 13,745.70 games per second on an old pentium 4.
>
> I'd really love to know what I'm doing wrong. I was never abl
On Dec 6, 2006, at 9:36 PM, Don Dailey wrote:
The equivalent C version (after I took out some optimizations) is
doing 13,745.70 games per second on an old pentium 4.
I'd really love to know what I'm doing wrong. I was never able to get
more than about 6,000 games per second on a 2 GHz machin
On Thu, 2006-12-07 at 12:19 +0100, Łukasz Lew wrote:
> Big thanks from me for that. :)
>
> Have You tried to use C and D together?
I can now say I've tried, and it's completely trivial. I have a
routine that returns processor time in seconds for timing purposes and I
decided to see if I could
Yes, it's clear how you do it. I suspect this is better than what I
do. My list of intersections include ALL the intersections not just the
empty ones and use a fixed or static array. But this is all easy to
change.
I will give this a try at some point and let you know if it's faster.
- D
I really do randomize a whole vector of empty intersections before the playout.
When I get new empty intersection I just pick random place in vector,
move it to the end,
and use the place for new intersection.
Here is the code:
void add_rnd (v::t v) {
int ii;
empty_v_cnt++;
ii = pm::
On Thu, 2006-12-07 at 12:19 +0100, Łukasz Lew wrote:
> Big thanks from me for that. :)
>
> Have You tried to use C and D together?
That's a very good question. I probably still could use D for the GO
program simply by making the low level functions C code.The whole D
program right now is 7
Le mercredi 6 décembre 2006 23:01, Robert Jasiek a écrit :
> House, Jason J. wrote:
> > Can anyone honestly say that they're still working on the restrucring?
>
> When trying to read parts of it a few days ago, I have found it useful
> to restructure the related contents (topics: rules, ratings).
Hi
I did some clean up in http://senseis.xmp.net/?KGSBugs
most visible one is moving old KGS2/Cgoban2 bugs to
a separate page
btw, it would nice to have reading access to Bugs Tacking System
to add a link, and possibly add comment on senseis page.
Alain.
_
Big thanks from me for that. :)
Have You tried to use C and D together?
BTW
D is geting more popular recently.
http://www.tiobe.com/tpci.htm
Lukasz
On 12/7/06, Don Dailey <[EMAIL PROTECTED]> wrote:
Ok, here is my report on the D language for Go:
The gdc (gnu D compiler) compiler for D is a
John wrote:
> which confirm yours. we also found a general formula n^2 -
> floor((n^2+4n-16)/5)
The formula can also be written floor(4n(n-1)/5+4) for a slightly more
compact expression.
> here's a nice symmetric 19x19 position with 277 strings:
>
> X O . O . O X O . O . O X O . O . O X
> . X
50 matches
Mail list logo
