Re: [Computer-go] Congratulations to Zen!

[Jason House]

I'm not sure what options are available for tournament setup, but assuming
we can enter skill levels manually...

I think it would be hard to pick perfect ratings, but I bet it wouldn't be
too difficult to generate a guess at ELO/kyu levels based on past
performance. Inputting something like ELO/2 (or similar fractional ELO)
might be a good way to start out without giving too much handicap. Future
tournaments could then be based on how well that works out.
On May 9, 2016 1:18 PM, "Gian-Carlo Pascutto"  wrote:

On 09-05-16 16:04, "Ingo Althöfer" wrote:
> Another point for discussion:
> Although there were only six participants they split in
> at least 4 classes, seperated by large gaps in strength:
> Zen >> abakus, HiraBot >> LeelaBot >> Imrsel, matilda
> Perhaps it makes really sense to think about a tournament
> with handicaps.

The first obvious question is then: how will you determine the handicaps?

As to the "large gaps in strength": the actual rating of Zen is 1 stone
above abakus, which is 1 stone above HiraBot. That seems to conflict
with your classification. I am not sure it's possible to draw these
conclusions by observing <= 3 games from every matchup.

--
GCP
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Congratulations to Zen!

[Jason House]

On May 9, 2016 10:38 AM, "Urban Hafner"  wrote:
>
>Also, you give me too much credit. I’m not the primary author of HouseBot,
that is Jason House. I was merely a co-author/contributor.
>
> Urban

I didn't even notice that in the report! I'm not too worried about credit
for my weak bot :)
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Congratulations to AlphaGo (Statistical significance of results)

[Jason House]

Statistical significance requires a null hypothesis... I think it's
probably easiest to ask the question of if I assume an ELO difference of x,
how likely it's a 4-1 result?
Turns out that 220 to 270 ELO has a 41% chance of that result.
>= 10% is -50 to 670 ELO
>= 1% is -250 to 1190 ELO
My numbers may be slightly off from eyeballing things in a simple excel
sheet. The idea and ranges should be clear though
On Mar 22, 2016 12:00 PM, "Lucas, Simon M"  wrote:

> Hi all,
>
> I was discussing the results with a colleague outside
> of the Game AI area the other day when he raised
> the question (which applies to nearly all sporting events,
> given the small sample size involved)
> of statistical significance - suggesting that on another week
> the result might have been 4-1 to Lee Sedol.
>
> I pointed out that in games of skill there's much more to judge than just
> the final
> outcome of each game, but wondered if anyone had any better (or worse :)
> arguments - or had even engaged in the same type of
> conversation.
>
> With AlphaGo winning 4 games to 1, from a simplistic
> stats point of view (with the prior assumption of a fair
> coin toss) you'd not be able to claim much statistical
> significance, yet most (me included) believe that
> AlphaGo is a genuinely better Go player than Lee Sedol.
>
> From a stats viewpoint you can use this approach:
> http://www.inference.phy.cam.ac.uk/itprnn/book.pdf
> (see section 3.2 on page 51)
>
> but given even priors it won't tell you much.
>
> Anyone know any good references for refuting this
> type of argument - the fact is of course that a game of Go
> is nothing like a coin toss.  Games of skill tend to base their
> outcomes on the result of many (in the case of Go many hundreds of)
> individual actions.
>
> Best wishes,
>
>   Simon
>
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] How to handle triple ko efficiently?

[Jason House]

There are longer cycles that can occur but I have never encountered any
that didn't naturally resolve themselves in the playout.

Zobrist having is cheap to compute (one xor if no stones were captured).
Comparing the resulting number against the others is also cheap. The hash
is also helpful for handling transpositions in the search tree.

https://en.m.wikipedia.org/wiki/Zobrist_hashing
On Aug 30, 2015 9:17 PM, "Minjae Kim"  wrote:

> Yes, but to 'remember' the prior board state, doesn't the program have to
> store the whole board position per every turn by whatever means including
> Zobrist hashing that you suggested?
>
> After that, the program has to search whether the current position matches
> any of the previous ones. You said 3 is enough for triple kos, but as far
> as I know aren't there some rare repeating positions with a cycle longer
> than 3?
>
> But anyway solving the problem this way seems too expensive to me.
> 2015. 8. 31. 오전 9:59에 "Jason House" 님이 작성:
>
>> Triple ko can be detected by remembering the prior three board states. A
>> zorbist hash value should be good enough to detect a repeat.
>> On Aug 30, 2015 8:46 PM, "Minjae Kim"  wrote:
>>
>>> I finally managed to build a program that can produce a sequence of
>>> random legal go moves. One problem I found recently is that it rarely never
>>> ends a game because of triple ko, especially on small boards.
>>>
>>> One possible solution would be saving every board position that has
>>> occurred and searching for a match before generating a move. But this
>>> doesn't sound like an efficient solution at all.
>>>
>>> How do you handle this problem?
>>>
>>> Also as a side question, white constantly seems to have a better winning
>>> rate in any board size larger than 9x9 with komi greater than 6 under area
>>> scoring in completely random games; is this natural?
>>>
>>> ___
>>> Computer-go mailing list
>>> Computer-go@computer-go.org
>>> http://computer-go.org/mailman/listinfo/computer-go
>>>
>>
>> ___
>> Computer-go mailing list
>> Computer-go@computer-go.org
>> http://computer-go.org/mailman/listinfo/computer-go
>>
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] How to handle triple ko efficiently?

[Jason House]

Triple ko can be detected by remembering the prior three board states. A
zorbist hash value should be good enough to detect a repeat.
On Aug 30, 2015 8:46 PM, "Minjae Kim"  wrote:

> I finally managed to build a program that can produce a sequence of random
> legal go moves. One problem I found recently is that it rarely never ends a
> game because of triple ko, especially on small boards.
>
> One possible solution would be saving every board position that has
> occurred and searching for a match before generating a move. But this
> doesn't sound like an efficient solution at all.
>
> How do you handle this problem?
>
> Also as a side question, white constantly seems to have a better winning
> rate in any board size larger than 9x9 with komi greater than 6 under area
> scoring in completely random games; is this natural?
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] michi-c a recoding in C of Petr Baudis's michi

[Jason House]

Michi's source is more than 540 lines. I've wondered about trying to split
the source into 3 pieces:
- UI/glue code not in the line count
- Board implementation
- Core playout/search code

I imagine that would allow easier customization of the board
implementation... Both in python or in ports to other languages.

I also think the core payout and search code would be a good candidate for
automated conversion to another language, but I may be underestimating the
difficulty of that!
On May 12, 2015 9:55 AM, "Denis Blumstein" 
wrote:

> Hello !
>
> End of March, Petr Baudis released his "Minimalist Pachi" called michi
> (thread Michi - "15x15 ~6k KGS in 540 lines of Python code"). I found the
> goals of his project (see the README at https://github.com/pasky/michi)
> very attractive.
>
> So, I decided to recode michi in C following Petr's suggestion
>  "One of the things I would hope to inspire is rewrite of the same
> algorithm in different, faster programming languages".
>
> I tried to keep C code very simple and translated michi python in a
> straightforward manner when this was possible (almost everywhere).
>
> The result is available at https://github.com/db3108/michi-c. (after some
> discussion by email with Petr, we decided that it would be better to make
> separate projects on GitHub)
>
> Obviously the code got fatter (1300 executable lines of C instead of 540
> of python). But it also got faster, almost a 10x acceleration, even if it
> is yet single threaded.
>
> Here is an extract of the results obtained against gnugo. More results can
> be found in the perfs.txt attached file.
>
> michi vs gnugo-3.7.10 level 10 (400 games 13x13)
> 
>  nsimulations/move  1400  4000 12000
> python   winrate (%)36.5
>  codetime per game (sec)   430.6
>C winrate (%)37.8  66.5   80.8
>  codetime per game (sec)44.2 123.4  340.7
>
> michi vs gnugo-3.8 level 10 (400 games 13x13)
> -
>  nsimulations/move  1400  4000 12000
> python   winrate (%)41.8
>  codetime per game (sec)   419.5
>C winrate (%)38.8  66.5
>  codetime per game (sec)44.9 124.6
>
> Uncertainty on winrates is between 2 and 2.4 %.
>
> There is still a lot of room for improvements. As the speed of the program
> is concerned, the 2 main ones are :
> - parallelization
> - fast board implementation with incremental update of blocks and
> liberties,
>
> I have plans to continue to work on it with the priority of implementing
> the fast board. Adapting existing and well tested code that I already have,
> this should not take too long, I hope.
>
> Meanwhile, if someone would like to try his hands on parallelization, his
> efforts would be much apreciated. Some kind of coordination should
> certainly be necessary, as I used for simplicity some constructs that could
> prevent easy parallelization. But I hope this could be manageable.
>
> For the above modifications we must relax the objective of brevity. So
> this will be the right time to include some functionalities that will
> increase the usability of the program (time management, variable parameters
> modifiable by gtp commands for CLOP tuning, variable boardsize,
> "intelligent" early passing, etc.)
>
> I believe that these new developments should not be detrimental to the
> clarity and the brevity of the original michi and I would like to let
> michi-c unchanged (except for bug corrections and/or modifications to make
> it clearer and shorter).
> Therefore, I have setup another project for the new developments at
> https://github.com/db3108/michi-c2
>
> Any thoughts ?
>
> PS. If someone can understand and help to correct the spurious message got
> from gogui-regress when running make test, I would be very grateful. ;-)
>
> Denis
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] evaluating number of wins versus looses

[Jason House]

The complex formula at the end is for a lower confidence bound of a
Bernoulli distribution with independent trials (AKA biased coin flip) and
no prior knowledge. At a leaf of your search tree, that is the most correct
distribution. Higher up in a search tree, I'm not so sure that's the
correct distribution. For a sufficiently high number of samples, most
averaging processes converge to a Normal distribution (due to central limit
theorem). For a Bernoulli distribution with a mean near 50% the required
number of samples is ridiculously low.

I believe a lower confidence bound is probably best for final move
selection, but UCT uses an upper confidence bound for tree exploration. I
recommend reading the paper, but it uses a gradually increasing confidence
interval which was shown to be an optimal solution for the muli-armed
bandit problem. I don't think that's the best model for computer go, but
the success of the method cannot be denied.

The strongest programs have good "prior knowledge" to initialize wins and
losses. My understanding is that they use average win rate directly
(incorrect solution #2) instead of any kind of confidence bound.

TL;DR: Use UCT until your program natures
On Mar 30, 2015 8:06 AM, "folkert"  wrote:

> Hi,
>
> When performing a montecarlo search, we end up with a number of wins
> and number of looses for a position on the board.
>
> What is now the proven methology for comparing these values?
>
> I tried the method described here:
> http://www.evanmiller.org/how-not-to-sort-by-average-rating.html
> ...which not only looks at how much more wins than looses there were
> for a position but also the total number for that position. So that a
> difference x with 10 playouts may be evaluated lower than a difference
> y with 11 playouts, even if x > y.
> This does not seem to give good results altough other factors may be in
> play here (my program is in it's infant stage).
>
>
> Folkert van Heusden
>
> --
> Finally want to win in the MegaMillions lottery? www.smartwinning.info
> --
> Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] What's a good playout speed?

[Jason House]

Housebot was probably on the low end with 10kpps on 9x9. Libego was
probably the highest with 100kpps. I attribute some of the difference to
compiler maturity (D vs. C++). I don't know how rust will perform.
On Jan 14, 2015 3:14 AM, "Urban Hafner"  wrote:

> Hey everyone,
>
> I'm currently in the early stages of writing my own Go engine and right
> now I'm trying to make my playouts reasonably fast. I've come a long way in
> the past few days. Probably not because the payouts are really fast right
> now, but because they were just so slow before. :) Right now I'm at
> ~2000pps on 9x9 and ~1000pps on 19x19. This is for playouts with simple ko
> and suicide checks and no concurrency. Now I wonder if this is fast enough
> to even start thinking about implementing a UCT/MCTS player and also if
> there's something I'm missing with the playouts, e.g. is the suicide check
> necessary?
>
> Thanks for your input!
>
> Urban
>
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [computer-go] Biasing nodes according to pattern gammas

[Jason House]

Since patterns are correlated with each other, the gamma sets are  
specific to the pattern set used. Since more patterns are used in the  
tree, itrequires a separate set of gammas than the in-tree search.


Sent from my iPhone

On Dec 16, 2009, at 2:50 PM, Jacques Basaldúa   
wrote:



> Petr Baudis wrote:
> > I wonder now, do you use separate set of gammas for simulations  
and node
> > biasing? Since I've found that the performance seems very bad if  
I don't
> > include some time-expensive features, since the gammas are then  
very
> > off; I will probably simply generate two gamma sets, but perhaps  
it's
> > enough to do some trick like merging features by computing  
weighted

> > (geometric?) averages?

> Rémi Coulom answered:
> I learn two sets of gammas separately for the two sets of features.

I don't get it. Why do you need two sets one for the tree and one
for the playouts? To learn gammas, I use a database of games.
The patterns compete, some of them win. This is computed using a
Bradley-Terry model. At that time moves are just moves, not tree moves
or simulation moves. When that offline learned model 'best' fits the
moves played (55000 games x 100 moves each in my case) I am done, I
have a set of gamma values.

I use these for playouts and biasing the tree. What else are you  
doing?

How do you compute a set for the playouts and a set for the tree?
Do you adjust gamma values one by one playing games?

Of course, I guess this is not very useful for 9x9 that's why I took
the (probably wrong) decision to work in 19x19 only.


Jacques.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Simple gogui problem

[Jason House]

On Dec 13, 2009, at 11:30 AM, Corey Harris  wrote:

Was looking for a basic UCT data structure. I guess a tree structure  
is created in memory. How is this managed, because memory can be  
exausted pretty fast.



It isn't as fast as you might think. You want to use zobrist hashing  
for looking up nodes. IIRC, Many Faces discards the search tree after  
each move and simply does not create more nodes when it runs out of  
memory.





>>• record results for all visited nodes 
___


Where do you record the results?


Logically, every node in the search tree has an estimated win rate.  
It's also possible to store the win rate of all follow-up moves for a  
given node. That's friendlier on the cache but uses more memory per  
node. I'm unsure what most bots do.


tracking of win rates can be done in a few different ways:
• Total simulations, Win percentage
• Total simulations, # of wins
• Total simulations, # of wins - # losses
• # of wins, # of losses

More important than how to store those values is how they're  
initialized based on domain knowledge.





I appologize for the simple questions, I'm new at this.

On Sun, Dec 13, 2009 at 9:48 AM, Jason House > wrote:

On Dec 13, 2009, at 9:38 AM, Corey Harris  wrote:

I know this is a simple issue but I'm not sure of the solution. I am  
currently in the very early stages of writing a go engine. I have  
the board state and simple opening library implemented (no play  
logic yet). I'm would like to output debugging/developnent output  
statements to the gogui shell window. If the engine sends printf 
("some output\n"); gogui  says "Sent a malformed response". If it  
fprintf(stderr, "some output\n"); nothing is displayed.


How can you print messages to the shell without disrupting the  
message protocol?


Writing to stderr works fine for me, but gogui does not show shell  
output immediately. It waits until some point in overall execution  
before showing anything in the shell output.





Also, is there a site that describes the workings of a UCT bot in  
detail similiar to some chess programming tutorial sites?


Not that I'm aware of, but senseis.xmp.net might be a good place to  
start. Basic UCT is simple:

• always start at tree root
• pick the child with the highest metric (upper confidence bound on  
win rate)

• repeat last step until you reach a leaf
• if simulations of the leaf > N, expand leaf and pick child with hi 
ghest metric

• play random game
• record results for all visited nodes__ 
_

computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Simple gogui problem

[Jason House]

On Dec 13, 2009, at 9:38 AM, Corey Harris  wrote:

I know this is a simple issue but I'm not sure of the solution. I am  
currently in the very early stages of writing a go engine. I have  
the board state and simple opening library implemented (no play  
logic yet). I'm would like to output debugging/developnent output  
statements to the gogui shell window. If the engine sends printf 
("some output\n"); gogui  says "Sent a malformed response". If it  
fprintf(stderr, "some output\n"); nothing is displayed.


How can you print messages to the shell without disrupting the  
message protocol?


Writing to stderr works fine for me, but gogui does not show shell  
output immediately. It waits until some point in overall execution  
before showing anything in the shell output.





Also, is there a site that describes the workings of a UCT bot in  
detail similiar to some chess programming tutorial sites?


Not that I'm aware of, but senseis.xmp.net might be a good place to  
start. Basic UCT is simple:

• always start at tree root
• pick the child with the highest metric (upper confidence bound on  
win rate)

• repeat last step until you reach a leaf
• if simulations of the leaf > N, expand leaf and pick child with  
highest metric

• play random game
• record results for all visited 
nodes___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Gongo: Go in Go

[Jason House]

Even a comparison against the java refbot's performance would be good.  
IIRC, my D port of the java refbot was within about 1%


Sent from my iPhone

On Dec 13, 2009, at 12:01 AM, Brian Slesinsky   
wrote:



I'd like to, but I can't find it. Where do I download it?

2009/12/12 Don Dailey :

That's awesome!

Do you have performance numbers on the same hardware for the C  
refbot?


- Don


On Sat, Dec 12, 2009 at 7:39 PM, Brian Slesinsky  


wrote:


Thought I'd announce that I've ported the Java refbot to the Go
language (with some modifications).

I'm getting about 10,000 random playouts/second on 9x9 using a  
single

thread on a 32-bit iMac, using the gc compiler, which doesn't do any
optimization. I suspect that a board structure that tracked
pseudo-liberties could do better.

I probably won't have a chance to work on this for a while, but I
think the next step might be some kind of tree search. I'd be
interested in a particularly simple, standard, and easy-to-port
implementation to use as reference.

Source code:
http://github.com/skybrian/Gongo

Previous discussion on the Go language list:

http://groups.google.com/group/golang-nuts/browse_thread/thread/99ab46f5b7219a5b/22e58d9223db10ef

- Brian
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MPI vs Thread-safe

[Jason House]

Sent from my iPhone

On Oct 30, 2009, at 9:53 AM, "Brian Sheppard"   
wrote:






confirming the paper's finding that the play improvement is
larger than multiplying number of sequential playouts appropriately.


Well, this is another reason why I doubt the results from the Mango  
paper.
Parallelization *cannot* provide super-linear speed-up. The  
existence of
super-linear speed-up proves that the underlying single-threaded  
program is

flawed.


I had the same issue with the paper. It told me that near the root,  
Mango settles on a subtree too quickly. Root parallelism was the only  
method that lead to a bushy root, and was therefore the only  
successful strategy.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: kgsGtp (was Re: [computer-go] Congratulations to AyaMC!)

[Jason House]

That already exists: kgs-game_over is sent after every game (if you  
support it). That it's up to your bot to decide if it should  
terminate, run a full garbage collection, pause pondering, etc... I  
think most people use a sentinel file.


Sent from my iPhone

On Oct 6, 2009, at 5:28 PM, Peter Drake  wrote:

Incidentally, if a new version of kgsGtp appears, the one feature I  
desperately want is a way to tell kgsGtp to disconnect after the  
current game. As it is, I have to either wait for the end of the  
game or kill my program in the middle of someone's game.


Peter Drake
http://www.lclark.edu/~drake/



On Oct 6, 2009, at 2:19 PM, Jason House wrote:

Yes, there is a way. Error responses start with "?" and success  
responses start with "=". The bigger issue is how to detect crashes  
in kgsGtp. Maybe it's as simple as having kgsGtp kill a bot with  
outstanding commands before joining a new game.


Sent from my iPhone

On Oct 6, 2009, at 3:22 PM, terry mcintyre  
 wrote:


Is there a way to implement "I don't understand that command"? a  
NAK, perhaps?


Terry McIntyre 

"And one sad servitude alike denotes
The slave that labours and the slave that votes" -- Peter Pindar


From: Nick Wedd 
To: computer-go 
Sent: Tue, October 6, 2009 9:13:17 AM
Subject: Re: [computer-go] Congratulations to AyaMC!

In message , Nick Wedd > writes
> Congratulations to AyaMC, winner of Sunday's KGS Computer Go  
tournament! My report is at

> http://www.weddslist.com/kgs/past/52/index.html
>
> Two people had bots crash after receiving the message
> "FINEST: Still an outstanding command".  I do not know what this  
means, and am reporting it to wms.


I have heard back from wms:

> The "still an outstanding command" message means that a
> command has been sent to the engine, but the engine hasn't yet
> answered it. That's probably a bug in the engine, because GTP
> requires all commands to be answered with an acknowledgement
> or an error.

So it seems that CzechBot (=MoGo) and Fuego need to implement  
something, I don't know what.  It's strange that this has never  
come up before.


Nick
-- Nick Weddn...@maproom.co.uk
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Congratulations to AyaMC!

[Jason House]

Yes, there is a way. Error responses start with "?" and success  
responses start with "=". The bigger issue is how to detect crashes in  
kgsGtp. Maybe it's as simple as having kgsGtp kill a bot with  
outstanding commands before joining a new game.


Sent from my iPhone

On Oct 6, 2009, at 3:22 PM, terry mcintyre   
wrote:


Is there a way to implement "I don't understand that command"? a  
NAK, perhaps?


Terry McIntyre 

"And one sad servitude alike denotes
The slave that labours and the slave that votes" -- Peter Pindar


From: Nick Wedd 
To: computer-go 
Sent: Tue, October 6, 2009 9:13:17 AM
Subject: Re: [computer-go] Congratulations to AyaMC!

In message , Nick Wedd > writes
> Congratulations to AyaMC, winner of Sunday's KGS Computer Go  
tournament! My report is at

> http://www.weddslist.com/kgs/past/52/index.html
>
> Two people had bots crash after receiving the message
> "FINEST: Still an outstanding command".  I do not know what this  
means, and am reporting it to wms.


I have heard back from wms:

> The "still an outstanding command" message means that a
> command has been sent to the engine, but the engine hasn't yet
> answered it. That's probably a bug in the engine, because GTP
> requires all commands to be answered with an acknowledgement
> or an error.

So it seems that CzechBot (=MoGo) and Fuego need to implement  
something, I don't know what.  It's strange that this has never come  
up before.


Nick
-- Nick Weddn...@maproom.co.uk
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [SPAM] Re: [computer-go] Progressive widening vs unpruning

[Jason House]

On Oct 2, 2009, at 2:24 PM, Olivier Teytaud   
wrote:




4) regularized success rate (nbWins +K ) /(nbSims + 2K)
(the original "progressive bias" is simpler than that)


I'm not sure what you mean here. Can you explain a bit more?
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cgosview?

[Jason House]

*sigh*

I made a wiki for CGOS as part of the sourceforge project. I should  
just take it down since it never became the official home page. I  
don't even think it has a link to it from the official home page! Even  
things like download links are duplicated...


Sent from my iPhone

On Sep 29, 2009, at 8:09 AM, Petr Baudis  wrote:


 Hi!

On Tue, Sep 29, 2009 at 01:45:40PM +0200, Lars Schäfers wrote:

I remeber a version where the call was just

./cgosview-linux-x86_32  cgos.boardspace.net  6819


 Ahh, thanks, that works. I think the website should be fixed  
then. :-)


   Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] AMAF collection experience

[Jason House]

On Sep 28, 2009, at 7:30 AM, Petr Baudis  wrote:


 Hi!

 Pachi has two RAVE/AMAF modes - in one, it counts as RAVE wins only
moves made by the player further down in the tree. In the other, it  
also

counts in the moves made in the playout phase.

 I think most people collect AMAF statistics only from the tree phase,
at least that's what I've been told.


I've never heard that. I've had success using Don Dailey's  
recommendations:

• Don't track the last 1/8 of the playout
• Only track which color played on a particular vertex first

This has worked up through at least 50k simulations per move on 9x9.  
Your mileage may vary, my bot is much weaker than yours.



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Generalizing RAVE

[Jason House]

I toyed with that a while back and the results were disappointing.  
Every move's best reply was to tenuki to at a big point. You may need  
to subtract out the normal rave values to find which replies become  
more important than normal, even if they aren't the biggest moves  
overall. Or maybe only look at local replies?


Sent from my iPhone

On Sep 25, 2009, at 3:41 PM, Peter Drake  wrote:


On Sep 24, 2009, at 8:45 PM, terry mcintyre wrote:

Indeed it is. How may a program reason about the order of moves? At  
higher levels of play, the order of moves is often crucial.



I plan to try the following:

Store win and run counts for each move in the context of the two  
previous moves. This would accumulate results for "forced" move  
sequences, such as edge-of-board hanes. In terms of the GRAVE model  
I discussed earlier, this says two boards are similar if they have  
the same last two moves (regardless of what happened elsewhere on  
the board).


Two moves, rather than one, are necessary to chain together  
sequences of moves. Otherwise, consider this:


.#O.
.#Od
.cab

If # moves at a, then b is the correct response, followed by c, then  
d. However, if # plays directly at c, O should not respond at d.


Obligatory acronym: SAVE (Sequence RAVE).

My guess is that this will not work as well as RAVE. It just might  
work to combine this information (which in a sense remembers local  
searches) with the RAVE information (which finds "globally" good  
moves). Combining pure AMAF might help, too, as it would solve the  
"missing sibling information" problem I mentioned earlier.


Peter Drake
http://www.lclark.edu/~drake/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Congratulations to MoGoTW!

[Jason House]

Is the Leela source really available? I don't see it. It also looks  
like Leela is a commercial program which makes source availability  
unlikely...


Sent from my iPhone

On Sep 21, 2009, at 1:49 PM, Nick Wedd  wrote:


Congratulations to MoGoTW, winner of yesterday's KGS bot tournament.

My report is at http://www.weddslist.com/kgs/past/51/index.html. It  
is longer than usual - perhaps because I found this event, with a  
very strong entry and a fast format, particularly interesting.


As usual, I am sure there are errors, and I look forward to  
receiving your corrections.


Nick
--
Nick Weddn...@maproom.co.uk
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Congratulations to MoGoTW!

[Jason House]

On Sep 21, 2009, at 3:21 PM, Peter Drake  wrote:



housebot tried to declare all of the white stones at the top dead,  
and Orego disagreed. A cleanup phase was entered, and I believe  
housebot crashed during the cleanup phase.


By the rules of the game end protocol, support for final_status_list  
dead is optional. kgsGtp incorrectly translates that to asserting all  
stones are alive, although I guess the net effect is the same.


HouseBot crashed when the game was resumed because of some kind of  
quirk in how time data is tracked. I still have to investigate that.  
My solution, to avoid having Nick force results throughout the  
tournament was to restart my bot after it crashed.


With luck, I won't crash in the next tournament :)




I don't know why that left the game alive with no clock ticking...



I'm surprised by this as well.





Peter Drake
http://www.lclark.edu/~drake/



On Sep 21, 2009, at 10:49 AM, Nick Wedd wrote:


Congratulations to MoGoTW, winner of yesterday's KGS bot tournament.

My report is at http://www.weddslist.com/kgs/past/51/index.html. It  
is longer than usual - perhaps because I found this event, with a  
very strong entry and a fast format, particularly interesting.


As usual, I am sure there are errors, and I look forward to  
receiving your corrections.


Nick
--
Nick Weddn...@maproom.co.uk
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Dead stones in human-bot games

[Jason House]

This comes up from time to time on this list. Rated games require the  
human to accept what the bot says (but can undo to continue play). In  
free games the bots must accept what the human says.


Sent from my iPhone

On Sep 17, 2009, at 5:27 PM, terry mcintyre   
wrote:



Is there no way for the bot to dispute the other player's decision?

I recall something of the sort in human-to-human play -- both have  
to agree before the scoring phase.


I do not know whether the KGS API works the same way.

Terry McIntyre 
"And one sad servitude alike denotes
The slave that labours and the slave that votes" -- Peter Pindar


From: Peter Drake 
To: Computer Go 
Sent: Thursday, September 17, 2009 1:52:07 PM
Subject: [computer-go] Dead stones in human-bot games

Orego has been doing well in 9x9 games on KGS, using the fast time  
controls of this weekend's upcoming tournament. I even improved the  
endgame behavior a bit: Orego will pass if (a) the opponent has  
passed first, and (b) after removing Orego's dead stones, but not  
the opponent's, Orego still wins. This means that Orego won't always  
play until there are no legal moves.


I looked at one of the lost games (attached), and found that (if I'm  
reading this correctly) the human won simply by marking all of  
Orego's (white) stones dead. Do bots automatically defer to humans  
when there are disputes? Isn't there supposed to be a cleanup phase?  
Would it be the same in a rated game?





Peter Drake
http://www.lclark.edu/~drake/




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] pure 3x3 pattern playouts weaker than light playouts?

[Jason House]

Same number of playouts? What are your pattern weights? Do they apply  
around the last move played or for all board areas?


Sent from my iPhone

On Sep 12, 2009, at 7:18 PM, Isaac Deutsch  wrote:


I now have playouts based on 3x3 pattern weights.

When I tested it on CGOS it seemed to be weaker than my old engine  
which used light playouts only. I used a comparable setup, and the  
elo difference is about 100 after more than 150 games.


I can also seem some weird RAVE value patterns (not 1-1 points are  
the worst, but the 2-1/2-2 points), but they are symmetrical so I  
doubt it's a bug.


Is this a known phenomenon and are 3x3 patterns only strong in  
combination with more knowledge, or should I start debugging? Or is  
it possibly an effect caused by the rating of the cgos bots not  
being the same as when I first tested?


regards,
ibd
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach

[Jason House]

Somewhat... One could generate a random number (r) and combine it with  
the move mask (m) as follows:

black moves = m & r
white moves = m & ~r

This has the drawback that the number of black and white moves may not  
be equal. It can be modified to give an equal number of moves such as  
requiring that each subset of n intersections generates the same  
number of black and white moves, or doing some kind of looping until  
the condition is met.


For looping, you could keep some subset of the generated moves in  
order to guarantee convergence. For example, if there are 14 more  
white moves than black moves, keep all generated moves except for 14  
white moves. Then you only have to pick 14 moves in the next loop  
iteration.


Sent from my iPhone

On Sep 10, 2009, at 8:43 AM, Petr Baudis  wrote:


On Thu, Sep 10, 2009 at 08:29:31AM -0400, Jason House wrote:

I've thought of something similar in the past, but with a twist:
pre-compute a subset of moves that could be safely played in
parallel. Even if you can only play 285 moves in parallel on an
empty 19x19, it could still be a huge speed boost.


Hmm, do you have some ideas how this pre-computation could be done in
less than O(N)?

I'm gonna think about this now during some travelling... ;-)

   Petr "Pasky" Baudis
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CUDA implementation of the per-intersection GPGPU approach

[Jason House]

I've thought of something similar in the past, but with a twist: pre- 
compute a subset of moves that could be safely played in parallel.  
Even if you can only play 285 moves in parallel on an empty 19x19, it  
could still be a huge speed boost.


Consider the following basic pattern for a 19x19 board. "?" means a  
move is allowed and "-" means a move is not allowed. Please view in a  
fixed width font.


?-?-?-?-?-?-?-?-?-?
???
-?-?-?-?-?-?-?-?-?-
???
?-?-?-?-?-?-?-?-?-?
???
-?-?-?-?-?-?-?-?-?-
???
?-?-?-?-?-?-?-?-?-?
???
-?-?-?-?-?-?-?-?-?-
???
?-?-?-?-?-?-?-?-?-?
???
-?-?-?-?-?-?-?-?-?-
???
?-?-?-?-?-?-?-?-?-?
???
-?-?-?-?-?-?-?-?-?-

Notice how each stone is guaranteed 1-2 pseudo liberties. This  
guarantees no captures will occur, regardless of how the colors of  
each move are set.


More efficient patterns may exist, but 75% is the best I came up with.  
It's possible to modify this for partially filled boards...


Sent from my iPhone

On Sep 10, 2009, at 7:54 AM, Magnus Persson   
wrote:


This is very interesting. Here is a crazy idea, maybe it the same as  
Marks but I want to take it to its extreme.


Since AMAF values are so helpful, perhaps one can let go of the idea  
of sequential play following the rules of go, and basically play  
moves in parallel on all empty intersection. Compute new state (do  
captures) and repeat a fixed number of times and evaluate.


Since I do not understand GPU programming at all I cannot judge  
whether this would make things easier to implement.


Also a lot of weird thing will happens when you do things in  
parallel. What happens when two adjacent blocks are captured at the  
same time. Are both removed? Are there tricks to remove the one that  
was most likely to captured to begin with.


-Magnus

Quoting Christian Nentwich :


Petr,

wow, I didn't expect to see so much experimentation being performed!
It's great that you have taken the time to implement this approach,
because this now shows people both alternatives for implementing a
playout algorithm on the GPU.

I strongly suspect the low performance in the per-intersection case  
is

down to two reasons - please let me know what you think:
- A big proportion of moves place one stone on an empty intersection.
In this case 80 of your 81 threads are asleep doing nothing. This  
means

GPU time is wasted.
- In quite a few other cases, we get to the old problem with Go: that
the intersections are not independent. Thus when you process captures
or merges, you possibly have to lock 80 of 81 threads.

You can't do much about the first. Did you find a solution for the
second? I was thinking for a while about whether it would be possible
to come up with a highly parallel algorithm for captures/merges that
requires no lock. That's quite hard so I concentrated on my own
experiment instead.

I agree with you that your approach could be very performant in  
pattern

matching scenarios. In fact, your work somewhat strengthens my
conclusion that doing just straight-forward playouts on the GPU is  
not

the way to go.

Christian


Petr Baudis wrote:

I have written a quick CUDA implementation of the per-intersection
GPGPU apprach; Christian's e-mail finally made me polish it up to
a somewhat presentable form.

In this implementation, each GPU thread maintains a single
intersection.

The implementation uses 9x9 board (10x11 internally); expanding to
19x19 would probably mean either moving some data to global memory
or splitting the playout of single board to multiple blocks or  
waiting

for GPUs with larger shared memory. ;-)

The speed is unfortunately very disappointing; on GTX260, I see
17,300 playouts per second, with 50 playouts running in parallel.
There are several "but"s:

- With some further obvious optimizations, I'm thinking it should be
  possible to get it to at least 22,000 playouts per second easily.

- Bit boards are an obvious thing to try, but I'm quite doubtful
  they will be an improvement

- The playouts are uniformly random now, but they have been
  implemented in a way to make heavier playouts easy; precise  
liberty

  count is maintained and it should be easy to add pattern matching;
  the move selection can deal with arbitrary probabilities for
  different intersections (I wonder, what are the standard
  high-performance numbers for heavier playouts with pattern  
matching?)


- Christian is playing 2650 games in parallel; I'm playing only 50
  games in parallel, in the meantime the CPU can pick next games to
  play from the tree

- My code already accounts for transferring board images from CPU to
  the GPU (different one for each playout) and getting scores back

- Christian's GPU seems quite better than mine

- Apparently I still suck at CUDA optimizations; this has been my
  first real small CUDA project, it would be awesome if someone more
  exper

Re: [computer-go] Dead stones in KGS tournaments

[Jason House]

If you're asking about stone cleanup in the KGS tournaments, then yes,  
there is a special phase. See Nick Wedd's site for full details.  
Here's the basics:

1. Play normally until two passes
2. Respond to final_status_list dead
[done if opponent supports final_status_list dead and there is  
agreement on dead stones]
3. Handle undo to resume game, or have an appropriate time buffer to  
handle game replay.
4. Capture all dead stones, play continues until both bots pass again  
(all stones marked alive. KGS will send kgs-genmove_cleanup instead of  
genmove if supported)


Support for #2 is optional, but is strongly encouraged.

Sent from my iPhone

On Sep 8, 2009, at 1:57 PM, Peter Drake  wrote:

I realize that most games in the KGS computer tournaments end in  
resignation, but just in case:


Is there a phase for removing dead stones (as in games with humans),  
or are dead stones supposed to be captured (as in MC playouts)?


Peter Drake
http://www.lclark.edu/~drake/



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] any mac programmers out there?

[Jason House]

On Sep 5, 2009, at 10:41 AM, terry mcintyre   
wrote:


Found an interesting article on Snow Leopard at Ars Technica ... 20- 
some pages.


http://arstechnica.com/apple/reviews/2009/08/mac-os-x-10-6.ars

Of interest to Computer Go programmers: the addition of blocks to C,  
which allow closures and other fun stuff, much like Lisp.



D and C# are other C-family languages with similar.


LLVM, which allows JIT compilation to multiple architectures,  
including GPUs; Grand Central Dispatch, which provides very light- 
weight concurrency; and CLANG, a new compiler which is said to be  
quite an improvement over GCC.


Łukasz reported a 15% performance drop for libego when moving from gcc  
to llvm.___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Is RAVE weighting biased?

[Jason House]

Your question is tough to answer without context; which RAVE  
implementation method are you looking at?


Sent from my iPhone

On Sep 2, 2009, at 8:53 AM, Łukasz Lew  wrote:


If the weight in RAVE formula is near 1 in one child of tree and near
0 in other then you basically compare RAVE value to regular average
value,
which might be comparing apples to oranges.

Have you ever tried to use the same weight for every move considered
(every child in the tree)?


Lukasz Lew
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Cycles / super ko in tree search

[Jason House]

I changed my search from one tree per search thread to a shared (lock- 
free) tree among all threads. Back with dedicated trees, I would set a  
visited flag as I walked the tree. With a shared tree are there any  
clever ways to detect cycles / super ko?


Here are the two ideas I'm thinking of:
1. An array of visited flags, and each thread uses a unique index into  
the array.
2. Track the last n search tree nodes visited and check against that  
list with every in-tree move.


Option #1 has a larger memory footprint and will not catch positional  
super ko.

Option #2 may be slow and is not guaranteed to solve all cycles.

A variation on #2 is to store a node's depth (at initial creation).  
Only when the depth does not increase, check the list for repeats.  
This loses positional super ko detection.


What do others do?

Sent from my iPhone
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] representing liberties

[Jason House]

On Aug 15, 2009, at 8:22 AM, Don Dailey  wrote:




2009/8/15 Jason House 
On Aug 14, 2009, at 11:02 PM, "David Fotland" games.com> wrote:



Moves often merge two groups.

I count liberties incrementally as I make moves, so no need to  
search to count.




How do you detect shared libreties to avoid double counting. Simple  
addition does not work for real liberties (and I think you've said  
previously that you track real liberties.


I don't know how David does it or if there are special tricks,  but  
you get real updates without that much extra work - you just have to  
look at a few points around the newly placed stone.





It's not that simple. Shared liberties can occur far away with longer  
changes. I've come up with a scheme that looks a few points around,  
but only works for chains up to about seven stones. Consider two  
parallel, linear chains of 5 stones each, separated by a space. A  
stone placed at one end to connect them is likely miss the more  
distant shared liberties.


X
+
X

It's also possible to construct more complicated cases (with non- 
linear chains) where there are no locally shared liberties, but some  
exist further away.___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] representing liberties

[Jason House]

On Aug 14, 2009, at 11:02 PM, "David Fotland" games.com> wrote:



Moves often merge two groups.

I count liberties incrementally as I make moves, so no need to  
search to count.




How do you detect shared libreties to avoid double counting. Simple  
addition does not work for real liberties (and I think you've said  
previously that you track real liberties.___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Monte-Carlo Simulation Balancing

[Jason House]

A web search turned up a 2 page and an 8 page version. I read the  
short one. I agree that it's promising work that requires some follow- 
up research.


Now that you've read it so many times, what excites you about it? Can  
you envision a way to scale it to larger patterns and boards on modern  
hardware?


Sent from my iPhone

On Aug 12, 2009, at 11:14 PM, Michael Williams > wrote:


After about the 5th reading, I'm concluding that this is an  
excellent paper.  Is anyone (besides the authors) doing research  
based on this?  There is a lot to do.



David Silver wrote:

Hi everyone,
Please find attached my ICML paper with Gerry Tesauro on  
automatically learning a simulation policy for Monte-Carlo Go. Our  
preliminary results show a 200+ Elo improvement over previous  
approaches, although our experiments were restricted to simple  
Monte-Carlo search with no tree on small boards.

Abstract
In this paper we introduce the first algorithms for efficiently  
learning a simulation policy for Monte-Carlo search. Our main idea  
is to optimise the balance of a simulation policy, so that an  
accurate spread of simulation outcomes is maintained, rather than  
optimising the direct strength of the simulation policy. We develop  
two algorithms for balancing a simulation policy by gradient  
descent. The first algorithm optimises the balance of complete  
simulations, using a policy gradient algorithm; whereas the second  
algorithm optimises the balance over every two steps of simulation.  
We compare our algorithms to reinforcement learning and supervised  
learning algorithms for maximising the strength of the simulation  
policy. We test each algorithm in the domain of 5x5 and 6x6  
Computer Go, using a softmax policy that is parameterised by  
weights for a hundred simple patterns. When used in a simple Monte- 
Carlo search, the policies learnt by simulation balancing achieved  
significantly better performance, with half the mean squared error  
of a uniform random policy, and equal overall performance to a  
sophisticated Go engine.

-Dave
--- 
-

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Congratulations to Aya!

[Jason House]

The place column has too many entries for 4th. There were no ties...

Sent from my iPhone

On Aug 10, 2009, at 11:21 AM, Nick Wedd  wrote:


Congratulations to Aya, winner of yesterday's KGS bot tournament.

My report is now at http://www.weddslist.com/kgs/past/50/index.html

As always, I will welcome comments and corrections.  But I am about  
to leave for a short holiday, so I won't respond to them for a few  
days.


Nick
--
Nick Weddn...@maproom.co.uk
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] August KGS bot tournament: small boards

[Jason House]

While I had planned on entering HouseBot into the tournmant, it appears
to be very unstable and very weak at the moment.  I'll compete next
month once I've ironed out the kinks.

On Tue, 2009-07-28 at 17:01 +0100, Nick Wedd wrote:
> The August 2009 KGS computer Go tournament will be on Sunday August 9th, 
> in the Asian evening, European morning and American night, starting at 
> 08:00 UTC/GMT (09:00 BST) and ending at 12:00 UTC/GMT (13:00 BST).
> 
> There will be only one division.  It will be a 12-round Swiss with 9x9 
> boards and nine and a half minutes each of main time.  It will use 
> Chinese rules with 7.5 points komi, and a very fast "Canadian Overtime", 
> of 25 moves in 20 seconds. There are details at
> http://www.gokgs.com/tournInfo.jsp?id=472.
> 
> Registration is now open.  To enter, please read and follow the 
> instructions at http://www.weddslist.com/kgs/how/index.html. The rules 
> are given at http://www.weddslist.com/kgs/rules.html.
> 
> Please send your registration email (with the words "KGS Tournament 
> Registration" in the title) to me at maproom at gmail dot com (converted 
> to a valid address in the obvious way).
> 
> Nick

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Double/Triple Ko situation

[Jason House]

On Aug 6, 2009, at 12:19 PM, Peter Drake  wrote:


I may fix this before this weekend's KGS tournament.

(Speaking of which, where are all the contestants?)


I procrastinate, but I'll compete. I may enter more than one bot, but  
that depends on how much prep time I have.



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Double/Triple Ko situation

[Jason House]

The largest nakade shape is the rabbity six. My wild guess would be to  
outlaw self-atari for groups of 7+ stones.


Sent from my iPhone

On Aug 5, 2009, at 11:10 PM, Peter Drake  wrote:


On Aug 5, 2009, at 6:15 PM, Brian Sheppard wrote:


Pebbles has the same ko rules as Orego, but it doesn't have the same
search behavior.

If Orego rejects self-atari moves of large strings, then the left
side should become a seki almost always. If you are seeing 60% wins
then something must be wrong there.


There's the rub. I should implement that.

What's your threshold for "large"? Do you absolutely reject such  
moves, or just penalize them?



Another possibility is Orego's handling of transpositions. There are
only 16 points that could possibly vary (again, assuming self-atari
processing) so the position is almost bounded.


Peter Drake
http://www.lclark.edu/~drake/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: bias in UCT and RAVE

[Jason House]

That's exactly the issue. You don't know if it's an underestimate or  
overestimate, but you can be sure that the RAVE and UCT values will  
not match... Even if you run millions of simulations (without  
expanding the tree), the values still will not match. I expect the  
RAVE bias is the expected magnitude of that difference.




Sent from my iPhone

On Jul 28, 2009, at 7:28 PM, Yung-Pin Chen  wrote:


Jason,

Thanks for your explanation.  If RAVE "combines results from many
variations," how can we justify it is an overestimate or underestimate
of the true value of a move?  Is it reasonable to assume that both
UCT and RAVE are equally-biased?

Yung-Pin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] libraries

[Jason House]

There are others too. Off the top of my head, libego (C++), orego  
(Java), and refbot variants. There has to be more, but I can't think  
of others any besides an old C++ branch of my project. I switched to D  
when I switched to Monte Carlo.


Sent from my iPhone

On Jul 26, 2009, at 9:27 PM, xiefan_hotmail   
wrote:



hi,

yes, the source code of many famous programs could be download from  
internet such as gnugo(from official website) , fuego(on sourceforge.org 
) . Both of them are written by C++. my program Yogo is an MC Go  
program based on java, and I also plan to share it on sourceforge in  
the near future.


Fan

On Mon, Jul 27, 2009 at 2:23 AM, Folkert van Heusden > wrote:

Hi,

Are there any libraries in c/c++/java for development of a go-brain?
I imagine that things like finding connected areas has been  
implemented

a million times?


Folkert van Heusden

--
MultiTail is a versatile tool for watching logfiles and output of
commands. Filtering, coloring, merging, diff-view, etc.
http://www.vanheusden.com/multitail/
--
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] bias in UCT and RAVE

[Jason House]

Oops... The disadvantages of touch screens...

RAVE can be computed faster, but it combines results from many  
variations, and that makes it less accurate.


Sent from my iPhone

On Jul 24, 2009, at 5:49 PM, Jason House   
wrote:



Think of RAVE as a fast way of approximating the UCT value.

Sent from my iPhone

On Jul 24, 2009, at 5:07 PM, Yung-Pin Chen  wrote:


Hi,

In Gelly and Silver's work on combining UCT and RAVE, there is a bias
term for both UCT and RAVE.  One assumption is that UCT is unbiased
and RAVE is biased.   Can anyone explain or define the bias term  
here?


Yung-Pin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] bias in UCT and RAVE

[Jason House]

Think of RAVE as a fast way of approximating the UCT value.

Sent from my iPhone

On Jul 24, 2009, at 5:07 PM, Yung-Pin Chen  wrote:


Hi,

In Gelly and Silver's work on combining UCT and RAVE, there is a bias
term for both UCT and RAVE.  One assumption is that UCT is unbiased
and RAVE is biased.   Can anyone explain or define the bias term here?

Yung-Pin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Computating ELO ratings, again.

[Jason House]

On Jul 24, 2009, at 12:04 PM, Isaac Deutsch  wrote:



To answer exactly, I need to know more about how you set up your  
patterns. If every point gets one, and exactly one 3x3 pattern,  
then fixing one 3x3 pattern is required. If some points have no 3x3  
pattern, then you're implicitly fixing an "other" pattern to a  
value of 1 and then no fixing of a 3x3 pattern is needed.


Just like 3x3 patterns, any orthogonal subset should have one value  
fixed...


Does that help?


When teaching a position, all legal positions get a pattern. This  
means positions that would be suicidal, ko, or aren't empty get no  
pattern. All legal positions get exactly one 3x3 pattern assigned.


What do you mean with orthogonal subset?

Please tell me if you need more information.


Here's a really simple example:

Consider the following 4 patterns:
A: 3rd or 4th line
B: Any other line
X: No adjacent stones in 3x3
Y: Some adjacent stones in 3x3

Now let's arbitrarily assign the following probabilities for some  
board position:

AX: 4%
AY: 3%
BX: 2%
BY: 1.5%

One solution for gammas would be:
A: 2
B: 1
X: 4
Y: 3

Another would be
A: 100
B: 50
X: 4
Y: 3

Another would be:
A: 2
B: 1
X: 100
B: 75

Because of how I defined the patterns, selection of A or B is  
completely independent of the selection of X or Y. I think of the  
feature set a={A,B} as orthogonal to b={X,Y}. Because of this  
property, set a can have its gammas multiplied by an arbitrary  
constant. Set b can also be multiplied by an arbitrary constant. If we  
fix one member of each set to 1 (let's say A and Y), a unique solution  
exists:

A: 1
B: 0.5
X: 1.3...
Y: 1

It sounds to me like your 3x3 patterns are an orthogonal set relative  
to everything else. Because of that, you must pin on 3x3 gamma. You  
may need to pin a few more... Note that any set of features where you  
don't pick one for every legal move doesn't require pinning because  
you implicitly have an "anything else" that is pinned to a value of 1.


I hope that helps!

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Computating ELO ratings, again.

[Jason House]

On Jul 24, 2009, at 11:23 AM, Isaac Deutsch  wrote:






An overall drift in the numbers might be nothing. Some pattern (sub) 
sets can be multiplied by a constant value without affecting  
overall prediction accuracy. Fixing one or more gamma values may  
fix your drift issue. I think Remí's paper forced the average gamm 
a to be 1 after each iteration.


If I fixed the average gamma, wouldn't that make the other features  
drift *upwards*? I know it isn't a problem in general, but if the  
number range is too big I might get precision issues.


Do you suggest I fix the value of a single 3x3 pattern? Would that  
stabilize the 3x3 pattern values or would it also affect the other  
values (extend, kill, etc.)?


To answer exactly, I need to know more about how you set up your  
patterns. If every point gets one, and exactly one 3x3 pattern, then  
fixing one 3x3 pattern is required. If some points have no 3x3  
pattern, then you're implicitly fixing an "other" pattern to a value  
of 1 and then no fixing of a 3x3 pattern is needed.


Just like 3x3 patterns, any orthogonal subset should have one value  
fixed...


Does that help? 
 ___

computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Computating ELO ratings, again.

[Jason House]

On Jul 24, 2009, at 10:41 AM, Isaac Deutsch  wrote:


Hi Jason,

OK I see that this alters the result.

The "full pattern set" is just all 3x3 patterns, so there isn't a  
lot of additional knowledge. Nevertheless, there is a downwards  
tendency for all patterns. You can find the exact patterns  
(triangle, connect and hane) and the average rating of all patterns  
here:


http://pastie.org/557743

Thanks,
Isaac



An overall drift in the numbers might be nothing. Some pattern (sub) 
sets can be multiplied by a constant value without affecting overall  
prediction accuracy. Fixing one or more gamma values may fix your  
drift issue. I think Remí's paper forced the average gamma to be 1  
after each iteration. ___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Computating ELO ratings, again.

[Jason House]

Adding a prior through a 3rd player should alter your results. There's  
minimal data on how A compares to B, so since the data for dummy says  
they're equal, you should expect results closer to one.


You could do priors that simply set the initial guesses. That won't  
alter the results. You also could increase the number of games between  
A and B. That'll push the results back to theoretical.


Are you sure the connect pattern is still valuable once the other  
patterns are taken into account? It may be that without other  
knowledge, it works well, but that a full pattern set can better  
differentiate when a connection is good or not?


Sent from my iPhone

On Jul 24, 2009, at 9:33 AM, Isaac Deutsch  wrote:


Hello,

I have a question regarding the paper by Rémi Coulom. There is a lin 
k to it here:


http://computer-go.org/pipermail/computer-go/2007-December/012557.html

My first question also relates to that mailing list post. Rémi says:
"My suggestion would be to test your code with very small amounts of  
artificial data. For instance, start by two players A and B, and,  
say A beats B twice and B beats A once. Gammas should converge to  
gamma_A = 2 * gamma_B."
I tried this test and it converges to the right solution when I have  
no prior. When I have a prior (which means 2 competitions where each  
feature wins and loses once versus a dummy feature), it does not  
converge to the right solution. Instead, gamma_A approx. = 1.66 *  
gamma_B. Is this normal? Also, are there other artificial tests I  
could try?



Secondly, I used the technique explained in the paper to calculate  
ELO data for various features, including 3x3 patterns. I get good  
convergence for all features except the 3x3 patterns. I have made a  
chart showing this:


http://files.getdropbox.com/u/1298345/elo.png

It is most notable for the "connection pattern" (an example 3x3  
pattern that connects 2 groups), but it also applies to the hane and  
empty triangle pattern. It seems like the gamma value isn't totally  
wrong, but it doesn't converge to a stable value but to zero  
instead. Any ideas how I can fix this, or where I should start  
debugging?
I used about 4000 pro games and every 4th move in these games for  
training data, so about 100k trained positions. I do merge  
symmetrical patterns.


Regards,
Isaac___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Dead stones at end of game

[Jason House]

IIRC, the user can do whatever they want in a free game. Only rated  
games require the bot to agree with the scoring


Sent from my iPhone

On Jul 16, 2009, at 6:18 PM, Peter Drake  wrote:

I was looking at this game that Orego played against a human on KGS  
recently:




I note that Orego's dead stones are marked as dead, but Zanarkand's  
are not. Does KgsGtp defer to the human when there are disputes  
about dead stones? Is that the most likely explanation?


(What if there is a dispute between programs?)

Orego loses even if all of the dead stones are removed, but I'm a  
bit dismayed that Orego passed. (Zanarkand passed first.) I believe  
Orego reasoned, "If I pass, the game ends, and if all stones on the  
board are alive, I win!" I'll have to look into this...


Peter Drake
http://www.lclark.edu/~drake/



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Random weighted patterns

[Jason House]

On this list I've heard of row sums. You scan by row subtracting  
weights and then scan by column adding weight... Each time looking for  
zero crossings.


Sent from my iPhone

On Jul 15, 2009, at 7:06 PM, Mark Boon  wrote:


When using patterns during the playout I had improvised some code to
select patterns randomly, but favour those with higher weights more or
less proportionally to the weight..

I was wondering though if there's an established algorithm for
something like this. To be a little more precise, if I have a set of
values and two of those are represented by A and B. If A is twice as
high as B it should have twice the chance to be selected. If there's a
third value C that is 1.5 times A then it should be 1.5 times as
likely to be selected as A and 3 times as likely as B. Etc.

There are many strategies I can think of that make a randomly weighted
selection from a set. But none of them are really straightforward. So
I'd be interested to hear how others handled something like this. And
if there's maybe a standard known algorithm, this kind of thing must
appear in a lot of fields.

Mark
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Basic question concerning the edges of the board

[Jason House]

Consider this layout for a 2x2 go board


?++?
?++?


If you copy that row by row, into a 1d array, you get
?++??++?

That can be reduced to
++?++


Sent from my iPhone

On Jul 13, 2009, at 1:27 PM, Carter Cheng   
wrote:




Thanks all for the replies. I am not sure I quite get the 20x21+2  
idea but I will take a look back in the archives. Does anyone  
remember roughly when it was posted to the list?


Thanks again,

Carter.

--- On Mon, 7/13/09, Peter Drake  wrote:


From: Peter Drake 
Subject: Re: [computer-go] Basic question concerning the edges of  
the board

To: "computer-go" 
Date: Monday, July 13, 2009, 9:08 AM
As in LibEGO, if you define the
off-board points to be both black AND white, finding
captures requires fewer branches.
Peter Drakehttp://www.lclark.edu/~drake/


On Jul 13, 2009, at 8:48 AM, David Fotland
wrote:
I use one dimensional arrays for speed (to
avoid a multiply by 21).

Old Many Faces code uses arrays of 363 (361 points, pass,
and null-point).
The smallest possible arrays were required to run under 500
KB total memory.
I avoided edge checks by having a set of small offset
arrays (with 2, 3, or
4 offsets), chosen by the board.

My MCTS code uses single dimension arrays with size
suggested by Mark Boon,
from Goliath, 20 * 21 + 2.  This is enough to have
points off the edge on
all sides and diagonals.

David

-Original Message-
From:
computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org]
On Behalf Of Carter Cheng
Sent: Monday, July 13,
2009 8:36 AM
To: computer-go@computer-go.org
Subject: [computer-go]
Basic question concerning the edges of the board


Hi,

I have again been
considering trying my hand at implementing a simple go
program. The question
I have pertains to checking for the edge of the
board
in capture situations and so on.
For a modern CPU (given what limited
information I have on
this) the extra branches might result in pipeline
stalls if I am
constantly checking if values are in range. Is it best to
extend the size of the
board to say 21x21 to somehow avoid these sorts of
checks? Or are the
relative cost of these branches negligible in the
scheme
of things?

Thanks in advance,

Carter.



___
computer-go mailing
list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


-Inline Attachment Follows-

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Big trees

[Jason House]

What do use for your counters? 32 bit numbers max out at 4 billion,  
and you're already beyond that.


Is it possible to generate an SGF file showing the dominant variations  
with the number of wins and losses? It'd be interesting to see what  
the bot considers to be the best sequences are...


Sent from my iPhone

On Jul 10, 2009, at 10:10 PM, Michael Williams > wrote:


Now that I have this system of generating really big game trees,  
what sort of interesting things could I do with it?  The exact  
number of nodes I can store is not exact because I'm doing various  
things to reduce each node's footprint when it goes to disk.  I'm  
currently building a tree that is bushy at the root (heavy  
exploration term) and normal UCT beneath that.  It is at 28 billion  
nodes now and projecting a capacity of 122 billion.  The current  
node rate is about 130k per second (on 1 Core2 core).  This is on a  
9x9 board.  I'm still using Libego for playouts.  And I'm deleting  
symmetrically-equivalent moves from the tree.  That is all that gets  
pruned.


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Complicated seki with Ko

[Jason House]

It might, but the iPhone mail viewer does not.

Sent from my iPhone

On Jun 30, 2009, at 2:00 PM, Álvaro Begué   
wrote:



Jason,

Gmail has an option "show in fixed width font" that is perfect for
these situations.

Álvaro.


On Tue, Jun 30, 2009 at 1:25 PM, Jason House> wrote:
Is it possible to explicitly use a monospace font? I can't read  
your board

positions.

I haven't heard of any handling of seki in playouts except for Remi's
CrazyStone. I don't think he's ever given specifics on how he did  
it. Maybe

he'll respond to your e-mail?

Sent from my iPhone

On Jun 26, 2009, at 1:37 PM, "Brian Sheppard"   
wrote:


Here is a position that exposed some bugs in Pebbles. Maybe it  
will help

you.

 1 2 3 4 5 6 7 8 9
A - O - O X - - X -
B - X O - O X - O O
C - O O - O - X O -
D X X X O O O O O O
E - O X X X O X O O
F - - O X O X X X X
G - - X X O O X X -
H - O X O - O O X X
J - O X O O - X - X
X to play.

X is already doomed in this position. The bottom O group is in a  
seki
with the X group at right. O cannot play J6 self-atari. X cannot  
fill
in J8 and then play J6, and after X J6, O captures and X cannot  
recapture.

So it will be dual life. Because the top of the board is O's, O have
more than half the board, even without komi.

The playouts have to handle certain issues well in order to find  
that.

The first point is to filter out plays that make self-atari on large
groups. This will cause the rest of the board to fill up until only
the seki remains.

The the playout will be in a position like the following:

 1 2 3 4 5 6 7 8 9
A - O - O O - O O -
B O - O - O O - O O
C - O O - O - O O -
D X X X O O O O O O
E - X X X X O X O O
F X X - X O X X X X
G X - X X O O X X -
H X X X O - O O X X
J X - X O O - X - X
X to play.

Pebbles does not detect superko in playouts, so this position will  
loop
forever with J6/J8/J7/pass. In Pebbles, infinite games were scored  
as

draws. I changed that to give the win to O on the basis of its
preponderance
of material. (No doubt that will bite me at some point.)

Even if we detect the superko repetition, it seems to me that we  
are only
getting the right answer by accident. For instance, if X plays J6  
then

after J8/J7 there is no move for X, so X has self-ataried himself.

Another possibility if to see that X's J6 is atari and also self- 
atari, so
X can look for the approach move. In this case X would play J8  
instead of

J6
which avoids the ko. Then the seki is obvious.

How do other programs handle this case?

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Complicated seki with Ko

[Jason House]

Is it possible to explicitly use a monospace font? I can't read your  
board positions.


I haven't heard of any handling of seki in playouts except for Remi's  
CrazyStone. I don't think he's ever given specifics on how he did it.  
Maybe he'll respond to your e-mail?


Sent from my iPhone

On Jun 26, 2009, at 1:37 PM, "Brian Sheppard"   
wrote:


Here is a position that exposed some bugs in Pebbles. Maybe it will  
help

you.

 1 2 3 4 5 6 7 8 9
A - O - O X - - X -
B - X O - O X - O O
C - O O - O - X O -
D X X X O O O O O O
E - O X X X O X O O
F - - O X O X X X X
G - - X X O O X X -
H - O X O - O O X X
J - O X O O - X - X
X to play.

X is already doomed in this position. The bottom O group is in a seki
with the X group at right. O cannot play J6 self-atari. X cannot fill
in J8 and then play J6, and after X J6, O captures and X cannot  
recapture.

So it will be dual life. Because the top of the board is O's, O have
more than half the board, even without komi.

The playouts have to handle certain issues well in order to find that.
The first point is to filter out plays that make self-atari on large
groups. This will cause the rest of the board to fill up until only
the seki remains.

The the playout will be in a position like the following:

 1 2 3 4 5 6 7 8 9
A - O - O O - O O -
B O - O - O O - O O
C - O O - O - O O -
D X X X O O O O O O
E - X X X X O X O O
F X X - X O X X X X
G X - X X O O X X -
H X X X O - O O X X
J X - X O O - X - X
X to play.

Pebbles does not detect superko in playouts, so this position will  
loop

forever with J6/J8/J7/pass. In Pebbles, infinite games were scored as
draws. I changed that to give the win to O on the basis of its  
preponderance

of material. (No doubt that will bite me at some point.)

Even if we detect the superko repetition, it seems to me that we are  
only

getting the right answer by accident. For instance, if X plays J6 then
after J8/J7 there is no move for X, so X has self-ataried himself.

Another possibility if to see that X's J6 is atari and also self- 
atari, so
X can look for the approach move. In this case X would play J8  
instead of J6

which avoids the ko. Then the seki is obvious.

How do other programs handle this case?

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: fuego strength

[Jason House]

Will the new server handle small description strings about the bots?  
It'd be great if we could provide/lookup basic data on bots. Example  
data would be a homepage or a 1-2 sentence summary. For example "John  
Smith's experimental Fuego 0.4 with heavy playout for reading semeai"


Sent from my iPhone

On Jun 24, 2009, at 1:12 PM, Don Dailey  wrote:




On Wed, Jun 24, 2009 at 12:52 PM, Michael Williams > wrote:
A while back, I wrote a general purpose monitor tool that checks a  
specified URL for a specified RegEx and takes a specified action  
based on the result.  The action can be play a sound or send an  
email or flash the tray icon.  Something like that might work (it  
would be much easier if the CGOS page gave a simple list of all  
connected clients).


When I get the new CGOS pages up,  I will provide a list of clients  
and their status.  A bot can be connected but busy playing a game,   
waiting for a game,  or in limbo - where it has not agreed to play  
the next game yet.   It can also be non-responsive.


I noticed that there are still cases where there server THINKS a bot  
is connected but it isn't - so I need to solve that problem before  
bringing the server up - although it's currently functional.I am  
hoping that tomorrow we can bring it up although most of the web  
stuff won't be working yet.


I've considered the idea of having a network of anchors - bots that  
are extremely active and who's ratings would be based solely on  
their performance rating (not incremental rating) against each  
other.   Performance ratings are more accurate and stable if the  
entity is fixed.   This would serve as a stable backbone for the  
rating system and incremental ratings would be more trustworthy as a  
result.


- Don
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Re: fuego strength

[Jason House]

That raises an interesting point. I've also put bots up in a setup and  
forget scenario, but inevitably the bit is off of CGOS within a few  
days and I had no idea when it went down.


What's the right way to solve this issue so such altruistic bots can  
be more easilly maintained? This may also help the anchor absence  
issue too.


Sent from my iPhone

On Jun 24, 2009, at 12:14 PM, "David Fotland" games.com> wrote:



I can have a reduced version of Many Faces up all the time on an old
computer, but I don't monitor it, so someone would have to email and  
remind
me when it goes down (usually because of a Microsoft automatic  
reboot :( )


David


-Original Message-
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of Magnus Persson
Sent: Wednesday, June 24, 2009 5:55 AM
To: computer-go; Don Dailey
Subject: Re: [computer-go] Re: fuego strength

On 9x9 I have been worrying of the lack of strong anchors but not
enough to complain about. What I think is more important is that
stronger programs are actually active on CGOS for longer periods of
time. I tried to contribute more by having versions of Valkyria  
online

with a fixed number of playouts. The nice part of that is that I can
then run other tests on the same machine that all uses fixed number  
of

playouts and still get proper results. If I run a full strength
version of Valkyria on CGOS I cannot have anything else running.

So, I think if more people with strong programs had reduced versions
running, we could have many middle strength programs it would also
become more meaningful to play with full strength programs.

I am looking forward to the new server because I think everyone
would/should be eager to login to it.

Magnus

Quoting Don Dailey :


2009/6/24 Christian Nentwich 


Don,

you might have your work cut out if you try to control inflation

directly,
that can turn into a black art very quickly. Multiple anchors  
would be
preferable. An offline, X * 1000 game playoff between gnugo and  
another

candidate anchor would be enough to fix their rating difference. If

their
bilateral winnings drift away during continuous play, the anchor  
rating

could be tweaked.



It's all a black art anyway.  The anchor itself absorbs (or gives  
away)
rating points into the pool.  There is not much difference if I  
just use

it
to monitor the inflation/deflation and control it directly -  
except that

I
have the ability to control the magnitude of this adjustment.
And the
advantage is that the anchor player becomes a monitor of the  
inflation

level.

Don't worry, I don't plan to change it from what I'm doing.The

anchor
can still monitor inflation if I track what adjustment I would  
normally

make

to it if it were not an anchor.   For instance if the opponent

adjustments

tended to be more negative than positive it would indicate that the

entire
pool was overrated.   A way to help compensate is to adjust the  
initial

rating of new players.  However, the first game against a brand new

player

is not rated for the established player and the K constant is so low

(for

the new players opponents) that it hardly matters. Each player

starts
with a high K and it gradually drops to 3.   But this K is  
modified from

0%

to 100% depending on the opponents K - so the first game against a

player

a
new player is effectively not rated for his opponent.But I  
think the
initial value does have an impact on deflation/inflation of the  
entire

pool.







I'm not sure if the worries voiced on this list about anchors are  
not

somewhat overdone.



I'm pretty sure it's overdone, but I reserve judgment.  I know the
phenomenon of self-play intransitivity exists,  but it's minor.
This

is
something that can easily be tested privately with a 100,000 games  
or so

to
get the amount nailed down - at least for specific trio's of  
players.

I

think I may try gnugo vs fuego at 2 different levels.

I think that MCTS are all similar and that this is the bigger issue.

And

as you say,  gnugo introduces bias too, it's unavoidable.



Other bots, with improvements, may do just as well against an old

version

of Fuego as the full Fuego does, we don't know. Maybe they would do

better
than new versions of Fuego. All this reliance on gnugo introduces  
bias,

too,
and after all the anchor player is not a single control variable  
that

determines the destiny of the server. Players will still play many

different

opponents. If Fuego keeps beating the anchor player but losing to

everybody

else, it still won't get a higher rank.

For me, gnugo as an anchor is fine, as I am still experimenting  
around

a

low ELO level. For authors of strong programs: I am quite surprised

that

you
are not insisting on a much more highly rated anchor. I remember  
when

KGS
was anchored in the kyu ranks, many years ago. I found myself 7  
dan one

day,
until somebody intervened and reanchored the server

Re: [computer-go] Time controls for KGS tournament

[Jason House]

For testing purposes, the kgsGtp setting would be

rules.time=18:00+25/0:20

Sent from my iPhone

On Jun 18, 2009, at 11:01 AM, Peter Drake  wrote:


The Canadian overtime is new to me.

1) Can a program that simply never runs out of basic time safely  
ignore this?


2) Is there something special that has to go in the config file? I  
currently have this line:


rules.time=18:00

Thanks,

Peter Drake
http://www.lclark.edu/~drake/



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Time controls for KGS tournament

[Jason House]

Overtime only applies after you run out of time, so you should be able  
to safely ignore it. I think kgsGtp ignores the time setting in  
tournament mode


Sent from my iPhone

On Jun 18, 2009, at 11:01 AM, Peter Drake  wrote:


The Canadian overtime is new to me.

1) Can a program that simply never runs out of basic time safely  
ignore this?


2) Is there something special that has to go in the config file? I  
currently have this line:


rules.time=18:00

Thanks,

Peter Drake
http://www.lclark.edu/~drake/



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] cgos clients

[Jason House]

There's another place to find binaries:
http://sourceforge.net/project/showfiles.php?group_id=209690&package_id=252733

There's a lot of duplicated pages lying around.  The sf.net site has a
wiki with old content.  I have no clue what the standard way cgos users
are supposed to find information/binaries.  In recent times, I've simply
compiled it from source rather than worry about it :(

Maybe the new cgos is a good excuse to clean things up.  I'm the admin
of the sf.net stuff, but Don calls the shots!


On Wed, 2009-06-17 at 01:29 +0200, Łukasz Lew wrote:
> Hi,
> 
> I have a couple of question about cgos client programs.
> 
> Why there are two links to clients 32bit linux?
> 
> The first one is on page
> http://cgos.boardspace.net/9x9/
> http://cgos.boardspace.net/public/cgos3-x86_32.zip
> and is broken, but the page refers to it as version 1.1 compared to
> the one on the main page
> http://cgos.boardspace.net/
> http://cgos.boardspace.net/software/cgosGtp-linux-x86_32.tar.gz
> which works but the version is 0.98.
> 
> Can I add some more engines to config file without restarting cgos client?
> 
> What is the -p PLAYER_FIRST option ?
> 
> cgosGtp 0.98 alpha - engine client for CGOS Linux-x86_64 by Don Dailey
> Usage: /home/lew/cgos/cgosGtp-linux-x86_64/main.tcl  -c CONFIG_FILE
> -k KILL_FILE  -p PLAYER_FIRST -s
> 
> What is the priority in config file?
> 
> Thanks
> Lukasz
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] New CGOS - need your thoughts.

[Jason House]

Given all the negative reaction to nested time control, I have to say  
I like it. The pool won't be diluted as long as there's an obvious  
main venue.


Sent from my iPhone

On Jun 15, 2009, at 7:20 PM, Don Dailey  wrote:


I've been working on the new server and I'm almost at the point where
I can think about time controls - and since this is primarily for
developers, I would like to get your thoughts.

First, a brief explanation of how the time control works.   When the
client starts up it will inform the server of which venues it is
willing to play in.   It must choose an available boardsize and then
any of N different time controls.  Initially, N will probably be
2 or 3.   For each board size,  a time control is called a "venue."

Let's assume there are 3 venues for boardsize 9x9.  The time control
for each venue will be significantly different from the others.
One will be very fast, one will be very slow and there will be one in
between.

Each time control will be in sync with the others and the process will
be recursive.  So the basic scheduling algorithm is to NOT start a new
round for a given venue until any players who have registered to play
in this venue and are currently playing in FASTER venues are available
for scheduling.

In addition to this, new rounds are not scheduled for any particular
venue as long as the next slower venue is stalled waiting for these  
faster

venues to complete.

I hope this idea allows more choice and keeps players busy a greater
percentage of the time by allowing them to fill dead space with fast
games.

Each bot can choose which venues to play in.  If you only want to play
fast games, then you can.

Now the questions I pose to you are these:

How many venues for each boardsize?   (two, three, more?)

What time controls should they be?

It's almost certainly the case that certain combinations of time
control venues will work together better than others.  There will
always be the issue of waiting for games to complete and in fact this
may make the problem a bit worse for those programs that only want to
play in the longest venue.  I suggest that each venue is spaced at
least a factor of 2 apart in time.  For instance 1 minute, 2 minutes,
4 minutes, etc.

My own suggestion for 9x9 is to have 3 venues of 1 minute, 5 minutes
and 15 minutes per game per player.

It's also not too late to change our minds and not have venues if we
think the disadvantages outweigh the advantages.

- Don




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Python CGOS Client

[Jason House]

As long as Don doesn't object, I'll give you SVN access to the CGOS  
project on sourceforge.net. It makes sense to keep everything  
together. Are you up for merging your project into the existing one?


Sent from my iPhone

On Jun 10, 2009, at 2:23 PM, Christian Nentwich > wrote:



All,

I have released an alternative client for CGOS, written in Python. I  
had some features in there that are useful to me, and I thought  
maybe others could benefit from it.


Some key interesting features:
 - GTP extensions that tell your engine who the opponent is, and  
what the result was (useful if you persist your own SGF)

 - Local SGF persistence
 - Local "mirroring" to a GTP observer engine of all moves. This  
lets you watch games locally using GoGUI. Nice for the server, and  
nice graphics :-)

 - Usual failover using the CGOS servers move replay
 - Separate logging. The console output has only high-level stuff  
(like what colour your engine is playing, and against who)


Head on over here: http://cgos-python.sourceforge.net/

I would be interested in hearing feedback, and ideas for further  
features. I'm thinking of adding mail notification for very long  
sessions. I run this on Windows 7 (64 bit) and XP (32 bit). If you  
run into issues on Linux (shouldn't.. but...), let me know.  
Contributors also welcome, of course.


Christian
p.s. Don: if you are reading this - this client obeys the TCL  
client's convention of not hammering the server on reconnects (uses  
30 seconds + random number), and the rest of the protocol.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] bots and handicaps (Re: New CGOS)

[Jason House]

At 1 or 2 stones difference, the handicap system works well.At  
greater handicaps it's skewed.   The "coincidence" that I'm talking  
about is that it works to a reasonable degree at larger handicaps.


The handicap system is based on the idea that no matter what your  
level of play,  you can give 7 stones to a player 7 stones  
weaker.Everyone knows this is not true.   It is very accurate at  
low handicaps, and progressively less accurate at high handicaps (as  
well as high levels) so for instance a professional player with a  
relatively low professional ranking does not need as many stones as  
indicated by his opponents ranking to beat another professional WHO  
IS SEVERAL RANKS HIGHER.



Is handicap accurate at all with professional ranks? I've heard before  
that they are 1/4 stone apart.


I am 3k on KGS and I'd say that I win nearly every game that I give  
handicap and lose over half the games that I receive handicap. That  
would seem to imply that more handicap should be given near my rank.

















Is this not correct? When I say it's imperfect, that is what I  
am talking about.


There is nothing wrong with defining 1 stone handicap as a "rank"  
and I don't view that definition as imperfect and that is a  
reasonable basis for defining the ranking system in GO.   What's  
imperfect is the assumption that 9 stones makes it a perfectly even  
match if you are 9 ranks apart no matter where along the scale you  
are.


If you wanted to know what handicap is needed to win a match at  
various handicaps from beginner to world chamption,  you would need  
a 2 dimentonal table lookup because it's not as simple as just  
taking the difference in their rankings.With the table lookup  
and a huge amout of data to back it up,  you would have a predictor  
as good as ELO.


Does that clarify what I meant when I said the handicap system is  
imperfect?As we discussed many times on this forum and in  
private email,  a one stone handicap has a different meaning at  
different levels - it's just an awkward system to deal with  
mathmatically on a go server for computers where wild mismatches  
will be common.




the fact that chess doesn't have a fine-grained way to
handicap a game, in fact, the fact that most games don't,
doesn't mean that it's hard to deal with.

There are simple ways to deal with it.  One could simply increase or  
decrease your rank as soon as you start winning or losing  you games  
at your current handicap level.We don't need ELO for that and  
it's simple to do.


What I see on most servers and in this modern day and age is a move  
away from the centuries old system, not an embrace of it as being  
superior.Of course I understand there is a sentimental  
attachment to it.It was like this in chess many years ago when  
the old fashion descriptive chess notation was replace in the USA  
with algebraic notation in order to stay with the modern world and  
to many people it was just not chess anymore.




my guess is that any go playing program that doesn't
depend upon an opening book for a lot of its strength
is going to adapt just fine.  experiments between players
of different CGOS-measured strengths could find this out for
sure -- time for another set of experiments?  i'll donate some
cpu time.

It took a lot of work and energy to do these studies - I'll have to  
think about this one.


Of course they would adapt if that was the system.   Even if this  
idea was not good for current MCTS programs they would adjust is  
that was what was required to do well in competition.





if it helps to encourage the authors, just keep in mind
that winning with handicap is extremely convincing
evidence to "regular go players" that one player is much
stronger than another.  plus, it takes exponentially fewer
games to determine that difference.

with a logarithmic (in range of handicap, say, +/-6 stones)
number of games you could get a very accurate view of
the strength difference between two players.  say, take
best of 2 out of 3 at each test level and do binary search.

some go clubs just keep track of the relative difference
in stone strength between pairs of players, requiring, say, a
3-win streak by one player to adjust the handicap by a
single stone.

alternatively, you can (somewhat cheesily) map ELO
to handicap and vice-versa for a limited range of ELO
and handicap.

Like I say, a table will do it, and I believe some kind of formula  
could be fitted to the data.


- Don




s.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-

Re: [computer-go] Problem with cgos client

[Jason House]

I am pretty sure the client source has no reference to /tmp. It's  
either your use of the client or a nuance of tcl that I don't know.  
Don can answer better. The client is also open source if you want to  
debug it.


Sent from my iPhone

On Jun 6, 2009, at 9:15 PM, Łukasz Lew  wrote:


Hi,

Is cgos client creating any files in /tmp ?
lsof command suggests it is true,

It is a problem in my case as I have a very small qouta on this  
directory.

Is there a way around it?

Lukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] New CGOS

[Jason House]

On Jun 5, 2009, at 5:59 PM, Christoph Birk  wrote:


On Fri, 5 Jun 2009, Don Dailey wrote:

Handicap games opens a can of worms.   The last time we discussed it,
it was difficult to get any kind of reasonable agreement on how to  
do it.


Handicap games are for humans ... they get frustrated losing
over and over. Computers have no problems with that.


There are humans watching and reviewing the games. Handicap can give  
an unpredictable outcome, meaning both developers can look for small  
things to improve that could have changed the game outcome. Also, at  
least some bots on CGOS are intended for more than just games against  
computers. Having test data from handicap games could help refining  
how the bot handles such situations.



I agree with Don, adding a handicap server is an unnecessary  
complication.


It is a complication. I would be shocked if the first release of the  
new CGOS supported it.


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] New CGOS

[Jason House]

On Jun 5, 2009, at 2:49 PM, Don Dailey  wrote:




On Fri, Jun 5, 2009 at 12:36 PM, Michael Williams > wrote:
There will be multiple time controls, but they will be in sync, so  
that your
program can always play in a shorter time control game without  
missing a
game at the longer time control.The idea is to keep your bot  
busy while
waiting for future rounds.You play in the longest time control,  
but when
you are finished you can play fast games while waiting.   I will  
have 2 or 3
levels of this,  I haven't decided yet. If I have 3 levels, the  
slowest
time control will probably need to be a little slower than CGOS uses  
now.


That sounds fine for those bots that have implemented time controls.
Simple-minded bots that just play a given number of simulations, or  
do other
things in (more or less) constant time will loose the too fast games  
straight

out.

That's fine as long as the ratings are kept separate for each time  
control.


The more I think about it, the more I think it's important that I  
keep ratings separate for each time control.


- Don



Any chance of handicap games when there is a large rating imbalance?___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] UCT tree pruning

[Jason House]

On Jun 2, 2009, at 6:56 PM, Michael Williams > wrote:


Two things:  Firstly, I'm storing (only in RAM) the precalculated  
Winrate and InvSqrtVisits and keeping them updated.

So my UCT formula went from

   Wins / Visits + sqrt(lnParentVisits / Visits)

to

   WinRate + sqrtLnParentVisits * InvSqrtVisits;



Which equations do you use for the incremental updates? Or do you just  
recompute the values?




This has a memory cost, but I don't care so much about RAM since I  
can send the nodes to disk.


And the second thing is to store in the parent node a reference to  
what is likely the UCT-best child node.  If the parent has been  
visited 100*boardspaces times, I will go directly to the likely-best  
child with probability 2047/2048.  Anytime a proper UCT loop occurs,  
the likely-best reference is updated (about 90% of the time there is  
no change, so I think it's safe).



What is a proper UCT loop?




Jason House wrote:

That sounds like a good optimization. What did you do?
Sent from my iPhone
On Jun 2, 2009, at 3:16 PM, Michael Williams > wrote:
Update:  After concentrating on tightening the UCT loop, I've  
optimized myself back into needing the SDD  :/


But now I should be able to get to 20B nodes in just one day.

(still only doing 7x7 Go)


Michael Williams wrote:
Yes, when memory is full, I save and free all leaf nodes (which  
is the vast majority).  Nodes are loaded as needed.

Don Dailey wrote:



On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams  <mailto:michaelwilliam...@gmail.com>> wrote:


  I've optimized my disk access to the point where I'm mostly CPU
  limited now, even when using a standard hard disk instead of  
an SSD.
   I can now create trees of up to about 30 billion nodes, which  
would
  take about a week.  The simulation rate is continuously going  
down

  because so much time is spent in UCT loops in the huge tree.


That's impressive.   Are you doing things which move parts of  
the tree onto the disk and back when needed? I'm curious  
about the details!


- Don






  Don Dailey wrote:



  On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch   <mailto:i...@gmx.ch> <mailto:i...@gmx.ch  
<mailto:i...@gmx.ch>>> wrote:



  > Well, I'll take that over crashing with an out-of- 
memory

  error. :)

 Still, pruning seems better to me and has the same  
effect. ;p



  But is it better?   I think it's not so obvious without  
thorough

  testing.

  Pruning throw away information that is lost forever and  
may need
  to be recalculated.   Requiring more simulations does not  
throw
  out results, but results in some inefficiencies.   So it's  
not
  clear to me which is better - it may even be that it  
depends on

  how much you push it.   I am just guessing but I would guess
  that pruning is better in the short term, worse in the  
longer

  term.   Imagine a search at a corespondence level, where the
  computer thinks for 24 hours.   Which method is best  
there?  Could you use hard disk or SSD?   Using some  
kind of caching
  system,  where you relegate the oldest unvisited nodes to  
the
  hard dirve.   It may be that nodes you might normally  
prune are

  unlikely to get used again but if they do you still have the
  data.This is no good unless you can guarantee that the  
disk
  is used very infrequently - but with SSD it may be more  
practical.



  - Don




 --
 Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL  
6.000

  Flatrate und
 Telefonanschluss nur 17,95 Euro/mtl.!*
  http://portal.gmx.net/de/go/dsl02
 ___
 computer-go mailing list
 computer-go@computer-go.org
  <mailto:computer-go@computer-go.org>
  <mailto:computer-go@computer-go.org
  <mailto:computer-go@computer-go.org>>

 http://www.computer-go.org/mailman/listinfo/computer-go/



   
--- 
--- 
--



  ___
  computer-go mailing list
  computer-go@computer-go.org <mailto:computer-go@computer-go.org 
>

  http://www.computer-go.org/mailman/listinfo/computer-go/


  ___
  computer-go mailing list
  computer-go@computer-go.org <mailto:computer-go@computer-go.org>
  http://www.computer-go.org/mailman/listinfo/computer-go/



--- 
--- 
--


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.compute

Re: [computer-go] UCT tree pruning

[Jason House]

That sounds like a good optimization. What did you do?

Sent from my iPhone

On Jun 2, 2009, at 3:16 PM, Michael Williams > wrote:


Update:  After concentrating on tightening the UCT loop, I've  
optimized myself back into needing the SDD  :/


But now I should be able to get to 20B nodes in just one day.

(still only doing 7x7 Go)


Michael Williams wrote:
Yes, when memory is full, I save and free all leaf nodes (which is  
the vast majority).  Nodes are loaded as needed.

Don Dailey wrote:



On Mon, Jun 1, 2009 at 4:57 PM, Michael Williams  > wrote:


   I've optimized my disk access to the point where I'm mostly CPU
   limited now, even when using a standard hard disk instead of an  
SSD.
I can now create trees of up to about 30 billion nodes, which  
would
   take about a week.  The simulation rate is continuously going  
down

   because so much time is spent in UCT loops in the huge tree.


That's impressive.   Are you doing things which move parts of the  
tree onto the disk and back when needed? I'm curious about the  
details!


- Don






   Don Dailey wrote:



   On Mon, Jun 1, 2009 at 11:22 AM, Isaac Deutsch >> wrote:



   > Well, I'll take that over crashing with an out-of- 
memory

   error. :)

  Still, pruning seems better to me and has the same  
effect. ;p



   But is it better?   I think it's not so obvious without  
thorough

   testing.

   Pruning throw away information that is lost forever and may  
need
   to be recalculated.   Requiring more simulations does not  
throw
   out results, but results in some inefficiencies.   So it's  
not
   clear to me which is better - it may even be that it  
depends on

   how much you push it.   I am just guessing but I would guess
   that pruning is better in the short term, worse in the longer
   term.   Imagine a search at a corespondence level, where the
   computer thinks for 24 hours.   Which method is best  
there?  Could you use hard disk or SSD?   Using some kind  
of caching

   system,  where you relegate the oldest unvisited nodes to the
   hard dirve.   It may be that nodes you might normally prune  
are

   unlikely to get used again but if they do you still have the
   data.This is no good unless you can guarantee that the  
disk
   is used very infrequently - but with SSD it may be more  
practical.



   - Don




  --
  Nur bis 31.05.: GMX FreeDSL Komplettanschluss mit DSL  
6.000

   Flatrate und
  Telefonanschluss nur 17,95 Euro/mtl.!*
   http://portal.gmx.net/de/go/dsl02
  ___
  computer-go mailing list
  computer-go@computer-go.org
   
   >

  http://www.computer-go.org/mailman/listinfo/computer-go/




--- 
--- 
--



   ___
   computer-go mailing list
   computer-go@computer-go.org 

   http://www.computer-go.org/mailman/listinfo/computer-go/


   ___
   computer-go mailing list
   computer-go@computer-go.org 
   http://www.computer-go.org/mailman/listinfo/computer-go/



--- 
--- 
--


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Future KGS bot tournaments

[Jason House]

On Jun 2, 2009, at 6:07 AM, Nick Wedd  wrote:


Erik van der Werf  writes


I like events with many (fast) rounds such as the one yesterday.


So do I - they are certainly more interesting for me.  I had been
tending to avoid them, in the belief that most programmers,  
particularly
of UCT-based programs, preferred slow games.  But in view of what  
you, a
successful UCT programmer, say, I shall hold more fast events in  
future.


I know that SlugGo and Go++ prefer slow time limits - if they start to
show interest in these events, I will hold slow tournaments again.  I
may hold another week-long tournament if there is interest - five
rounds, twelve hours each sudden death.

dhillism...@netscape.net writes

One factor is that there seems to be a narrow range between too few
entrants and too many. For any given contest, the potential pool
includes an elite few who have a chance at first place and maybe a
couple who have a new or newly improved bot. There is a larger group,
back in the pack, whose last breakthrough was a while ago. For many  
of

us in that last group, it would be easy enough to enter, but hard to
know if that would help or hinder.


In my view, more is always better, for many reasons.  We get to see  
more
bots perform, we see how bots perform against unfamiliar strategies,  
we

don't get repeat games between the same opponents, if there's an odd
number of players the byes are not too significant.  I can't think of
any convincing reason for preferring small numbers.

I assure you, if antbot wants to play in these events, it will be very
welcome.

Steve Uurtamo and Jason House agree.

Jason House  writes

In the past, I've entered bots and indicated that I would not be
offended if my bot was removed. Don has made use of such offers from
Aloril in the past. Maybe you could make a similar offer?


You have made this offer in the past.  I never took it up, because I  
had

the same offer from Aloril.  Such offers are useful, as they let me
ensure that numbers are even, and avoid byes.  Given the choice, I
preferred to remove his artificially stupid IdiotBot and retain your
HouseBot.  Now that Aloril is less active in computer Go, I will be
grateful to have one of your bots enter on the same basis.


I don't mind entering hb04 along with one of the my modern  
implementations because it uses almost no load (it's a pattern player).


In the same category of pattern players, Remi's pattern player may  
make a good low end bot. It'd probably beat hb04.


Maybe Don Dailey's anchor bot from CGOS would be good too? It has  
tunable strength.


PS: sorry about getting your name wrong :(



David Fotland  writes
I prefer full size boards, since that's a more difficult problem,  
and games
at 19x19 give me more to work with.  Short time limits are fine.   
Perhaps
19x19 with 15 or 20 minutes each?  After all, that's a good time  
limit for

games against people.


Sounds good to me.  The next event will probably be 19x19, 18 minutes
each.

Christian Nentwich  writes
I am hoping that I can join this at some point, at the lower end of  
the

field to start with :)

Is it possible to set a bar at these tournaments? In human McMahon
tournaments, that very successfully allows a top tier of competition
while guaranteeing at least some fun for everybody else.


A bar makes sense in a McMahon tournament, where the number of players
exceeds 2^(number of rounds).  But these events aren't McMahon, they  
are

Swiss.  Also they never have that many players; and now that we have
decided on faster and more rounds, they aren't going to.

The tournament formats supported by KGS are:
 Single elimination
 Double elimination
I don't like elimination tournaments.  Someone who has set up his  
bot to

play wants to see it play, not to see it eliminated.
 Swiss
as used for all these events
 McMahon
McMahon involves the server using the entrants' ratings.  But many  
bots

don't have ratings.  KGS admins are reluctant to allow bots to play as
rated bots.
 Round Robin
I haven't been using Round Robin because it means the length of the
event depends on the number of players.  I am not willing to make an
open-ended commitment of my time.

So these events will continue to be Swiss, unless someone makes a  
strong

case for a change.

After the first few rounds, the Swiss system achieves the same  
effect as

McMahon: the strong players are paired against each other, as are the
weaker players.  (In fact, when there are fewer players than rounds,  
all
the players end up playing all possible opponents anyway.  This  
happens

with both Swiss and McMahon).



To summarise - time limits will generally be faster than formerly.   
Lots

of entrants, lots of weak entrants, are strongly encouraged.  There is
nothing wrong with entering a bot that loses all its games.  I was  
very

pleased to see Rango pla

Re: [computer-go] Congratulations to Steenvreter!

[Jason House]

In the past, I've entered bots and indicated that I would not be  
offended if my bot was removed. Don has made use of such offers from  
Aloril in the past. Maybe you could make a similar offer?


Sent from my iPhone

On Jun 1, 2009, at 6:33 PM, dhillism...@netscape.net wrote:

One factor is that there seems to be a narrow range between too few  
entrants and too many. For any given contest, the potential pool  
includes an elite few who have a chance at first place and maybe a  
couple who have a new or newly improved bot. There is a larger  
group, back in the pack, whose last breakthrough was a while ago.  
For many of us in that last group, it would be easy enough to enter,  
but hard to know if that would help or hinder.


- Dave Hillis


-Original Message-
From: David Doshay 
To: computer-go 
Sent: Mon, 1 Jun 2009 5:32 pm
Subject: Re: [computer-go] Congratulations to Steenvreter!

SlugGo has not been participating because we had made no progress.
I hope to have something by the end of summer.

Cheers,
David


On 1, Jun 2009, at 1:39 PM, Nick Wedd wrote:

> would like to know what I might do to attract more entrants.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Wanna slim down for summer? Go to America Takes it Off to learn how.
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Congratulations to Steenvreter!

[Jason House]

On Jun 1, 2009, at 6:10 PM, Erik van der Werf  
 wrote:




I will also welcome opinions and preferences about the format of  
such events
in future.  Attendances got low towards the end of last year, so I  
gave them
up for a few months.  The last two, in April and May, have each had  
six
players, which I consider just about enough to make them worth  
running.  But
I would prefer more, and would like to know what I might do to  
attract more

entrants.


I like events with many (fast) rounds such as the one yesterday.


Me too. It's much more fun to watch. I'd also hope for more warning  
time so I can ensure my bot is ready.

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Time weighting in opening

[Jason House]

On May 24, 2009, at 8:47 AM, Don Dailey  wrote:


2009/5/24 Christian Nentwich 
Jason,

I used this time management code on CGOS and for off-line test  
tournaments so far. I cannot claim that I have made additional  
efforts to model/address network lag in it, so I don't yet know what  
else I need to do with KGS, etc. Perhaps a percentage applied to the  
result computed by the curve, for safety, or perhaps subtract two  
seconds from the time estimate sent by the server?


The extra time in CGOS is designed so that you don't have to add  
your own compensation for network lag,   and so that you don't lose  
a game purely on communication time with the server.


The amount of time currently configured is 3/4 second.  You only get  
the amount of this credit that you use.So if you have a fast  
network and you take 1/4 second to move from the servers point of  
view,  you only get 1/4 second of that time,  not the full 3/4.


Think of this like a Bronstein clock,  which does exactly the same  
thing.


It's not designed to be "fair" because if you have a fast network  
you will still have an advantage over an opponent with a slow  
network.   It is designed to prevent programs with a slow network  
from losing on time even though they are playing instantly.


I think the best way to deal with it using your algorithm is to  
either ignore it and just use your algorithm as is,  or if you are  
confident that you have a fast network add an additional 3/4 second  
to each move (or some fraction of that if you want to be safer.)
Add the time after you do your normal calculation.


- Don


Believe it or not, I had to do special coding to handle CGOS. my bot  
tried to adapt to network lag. Because the average lag for CGOS is  
negative, subtracting future network lag before allocating time is  
incorrect. The time allocation math would plan to have no time left at  
the end of the game, but since the final few moves are supposed to be  
less than the gift, the planned allocation would hit zero before the  
end of the game. ___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Time weighting in opening

[Jason House]

I also use a time management system based on assumed moves left.  
Before applying my logic to compute time to play based on the reported  
time left, I subtract out network lag


Net lag buffer = (moves left) * (mean net lag) + (confidence level) *  
sqrt [(net lag variance) * (moves left)]


I use a confidence level of 4 (standard deviations), but a confidence  
of zero probably works fine too.


The square root term is relatively small relative to the linear term  
except when the moves remaining is pretty small. For the most part,  
it's only important with byo yomi and canadian overtime.


Sent from my iPhone

On May 24, 2009, at 6:03 AM, Christian Nentwich > wrote:



Jason,

I used this time management code on CGOS and for off-line test  
tournaments so far. I cannot claim that I have made additional  
efforts to model/address network lag in it, so I don't yet know what  
else I need to do with KGS, etc. Perhaps a percentage applied to the  
result computed by the curve, for safety, or perhaps subtract two  
seconds from the time estimate sent by the server?


You're right about the initial move estimates, it's just another  
thing I overlooked. The initial move estimate is (9 x 9 x 1.6) / 2.  
However, later in the game the initial move estimate (when the  
original falls below a threshold) is set to all playable empty  
points, not half. This is because you cannot let your opponent force  
you to run out of time by passing when playing with Tromp Taylor  
rules. It's not a problem usually, because by the time you get to  
the threshold, you are playing filling moves.


I am actually not convinced that I have the right approach to  
estimating the right number of moves left, but the time curve itself  
works well. Refining the move estimation is a nicer problem to have.  
Because the curve equates the time under it to the total time  
available, it can play optimally at least in the sense that it will  
neither use too much, *nor* too little time as far as the whole game  
is concerned. Where it spends the time is up to the curve control  
parameters.


Christian


On 23/05/2009 22:57, Jason House wrote:


How have you tested your time management code? CGOS is very bad for  
testing time management because it gives a gift of time on every  
move (to compensate for assumed network lag)


I think you might be missing a factor of two in your computations.  
Only half the moves in a game count against your time.


Sent from my iPhone

On May 23, 2009, at 4:26 PM, Christian Nentwich > wrote:




This time management business is quite interesting. I looked into  
this in some detail a while ago and came up with something I think  
is reasonable for 9x9. I'd love to hear what you all think about it.


My algorithm relies on two key parameters: the time left (which is  
either reported by a server periodically, or maintained by the  
engine), and an estimate of how many moves are left. The estimate  
of moves left is set to 1.6 * board area (i.e. 9 x 9 x 1.6)  
initially based on the average length of playouts in experiments.  
Towards the end of the game, especially with Tromp Taylor rules,  
the algorithm instead counts the number of empty intersections  
left, plus a haircut for captures. This is usually quite accurate.


So, given the time left, T, and the number of estimated moves  
left, M, the task is to find out how much time to spend on the  
current move. We know we want to spend (a lot) more on early  
moves, and less later.


Now assume you have moves numbered along the x axis, from 1 to M,  
and the y axis shows how much time to spend on a move. I used a  
downward sloping curve with the following form: 1 / x ^ (1 / n)  
where 'n' controls the steepness of the curve. We know the total  
area under the curve *must* be equal to T, so that you provably  
never run out of time given your estimated number of moves.


Integrating over dx and some algebra gives (remember n is a  
steepness constant, M is the number of moves left, T is time left):


time(current move) = T * (n - 1) / (n * (M ^ (n-1 / n) - 1)

Add a haircut of 5-10%, just in case of network funnies. Works  
very nicely for me, at least as far as time management is  
concerned, my code is not strong yet but it never loses on  
time :-) Plus, it gets to spend super-linear time in the  
beginning. If you plot the initial curve equation, you can see how  
it works.


Christian



On 23/05/2009 18:38, Don Dailey wrote:




On Sat, May 23, 2009 at 12:34 PM, Brian Sheppard > wrote:

>My general impression (also based on experiences from chess):
>Distributing time rather balanced over the moves is a stable
>strategy.

I have found in Chess that you also want to spend more time up  
front.  Part, but not all of the reason for this  is that you  
don't know how long a game will last and you do not want to be on  
the losing end of a short game where you have a lot of time  
l

Re: [computer-go] Time weighting in opening

[Jason House]

How have you tested your time management code? CGOS is very bad for  
testing time management because it gives a gift of time on every move  
(to compensate for assumed network lag)


I think you might be missing a factor of two in your computations.  
Only half the moves in a game count against your time.


Sent from my iPhone

On May 23, 2009, at 4:26 PM, Christian Nentwich > wrote:




This time management business is quite interesting. I looked into  
this in some detail a while ago and came up with something I think  
is reasonable for 9x9. I'd love to hear what you all think about it.


My algorithm relies on two key parameters: the time left (which is  
either reported by a server periodically, or maintained by the  
engine), and an estimate of how many moves are left. The estimate of  
moves left is set to 1.6 * board area (i.e. 9 x 9 x 1.6) initially  
based on the average length of playouts in experiments. Towards the  
end of the game, especially with Tromp Taylor rules, the algorithm  
instead counts the number of empty intersections left, plus a  
haircut for captures. This is usually quite accurate.


So, given the time left, T, and the number of estimated moves left,  
M, the task is to find out how much time to spend on the current  
move. We know we want to spend (a lot) more on early moves, and less  
later.


Now assume you have moves numbered along the x axis, from 1 to M,  
and the y axis shows how much time to spend on a move. I used a  
downward sloping curve with the following form: 1 / x ^ (1 / n)  
where 'n' controls the steepness of the curve. We know the total  
area under the curve *must* be equal to T, so that you provably  
never run out of time given your estimated number of moves.


Integrating over dx and some algebra gives (remember n is a  
steepness constant, M is the number of moves left, T is time left):


time(current move) = T * (n - 1) / (n * (M ^ (n-1 / n) - 1)

Add a haircut of 5-10%, just in case of network funnies. Works very  
nicely for me, at least as far as time management is concerned, my  
code is not strong yet but it never loses on time :-) Plus, it gets  
to spend super-linear time in the beginning. If you plot the initial  
curve equation, you can see how it works.


Christian



On 23/05/2009 18:38, Don Dailey wrote:




On Sat, May 23, 2009 at 12:34 PM, Brian Sheppard  
 wrote:

>My general impression (also based on experiences from chess):
>Distributing time rather balanced over the moves is a stable
>strategy.

I have found in Chess that you also want to spend more time up  
front.  Part, but not all of the reason for this  is that you don't  
know how long a game will last and you do not want to be on the  
losing end of a short game where you have a lot of time left. 
This by itself makes early moves more important.   Also, early  
decisions shape the game more than later decisions.


In 9x9 GO I have found that it's VERY beneficial to spend more time  
on early moves.This seem to be more true than in chess.   I  
think it is because the early game is much harder to play than the  
ending and you don't want to have a lot of time built up playing  
easy moves.


Like everything else, the trick is to find the right balance.  
With 19x19, time allocation is probably  more difficult.


With sudden death time controls,  a reasonable algorithm is to set  
some percentage of the remaining time on the clock as your goal  
time.  For chess I have used numbers like 1/30th of the remaining  
time.In my opinion the number should be a low estimate on how  
many moves you expect to have to make.   Although games can be  
really short or really long, in general you expect that most games  
will take at least about 30 moves and not exceed 60 or 70 moves.


This does not allocate time evenly, which is good.  Each move will  
be played slightly faster than the previous.   But it will NEVER  
run out of time either, at least mathematically since there is  
always some time left over.This fraction can be tuned of course  
to your comfort level.   I remember one older program used 1/60 but  
a couple of years later the author reported to me that it was way  
too high.  This was a program that dominated computer chess for a  
few years.


You can get a feel for this by just doing the math to see how much  
time you would have for an unusually short game or an unusually  
long game.   If your program supports multiple board sizes you pick  
a divisor that is some function of the board size, such as 1 /  
(N*N)  (which is probably far too conservative.)   So perhaps 1 /  
((N*N) * 0.6) where you tune the 0.6 constant.


So I'm saying that this is good in Chess and I believe based on  
Brian's comments and my own experience that it is ESPECIALLY good  
in GO.


- Don





Reasoning on the basis of experience in chess is OK, but you must
account for the differences between the domains.

Chess is more or less uniformly difficult across the whole game.

Re: [computer-go] 7x7 komi

[Jason House]

There is more than one optimal line of play. A few lines are only  
optimal with certain rulesets


Sent from my iPhone

On May 21, 2009, at 5:54 PM, terry mcintyre   
wrote:


Has anyone analyzed the lines of play by today's top programs at  
7x7? Does it come down to a single line of perfect play, or are  
there interesting variations?


All of this is, of course, contingent on the ruleset.

Terry McIntyre 

Any system of entrusting the government to judge and correct its own  
abuses is the same as appointing the accused criminal as his own  
judge and jury: don't expect many convictions.


-- Allen Thornton, Laws of the Jungle


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] 7x7 komi

[Jason House]

On May 21, 2009, at 5:28 PM, Don Dailey  wrote:




On Thu, May 21, 2009 at 5:09 PM, Michael Alford   
wrote:

Don Dailey wrote:
I believe with CGOS rules,  it is believed to be 9.0

I don't know if there is a proof of that, but I don't think there is  
any dispute.


- Don


On Thu, May 21, 2009 at 4:29 PM, Michael Williams  > wrote:


   What was the consensus on 7x7 komi?  It was discussed back during
   Don's scalability study, but I couldn't find the number itself.   
Was

   it 9.0?
   ___
   computer-go mailing list
   computer-go@computer-go.org 

   http://www.computer-go.org/mailman/listinfo/computer-go/



--- 
-



___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


delurk/

9 may be too small, the smaller the board, the more komi w needs,  
however, when i teach beginners, the more interesting variation is  
for w to try and live in two places :)


I feel very confident that 9 is not too small.   With  9.5 komi  
white wins every game.


We did experiments with go programs on 7x7 and with 9.5 komi white  
won almost every game.   When the komi was reduced to 8.5, black won  
nearly every game.


If you think 9 is too low,  you can probably repeat this  
experiement.   Try beating one of the strong MCTS programs on 7x7 as  
black with 9.5 komi.   I'll bet you cannot do it.


7x7 isn't solved by computer, but the best ones play it extrememly  
well.   Does anyone have any information on how well they play it?
My guess is that with 9.5 komi,  a strong computer playing white  
won't lose much to anyone (as it's starting from a dead won position.)



There's also an SGF file with analysis of variations and results done  
by some amateur dans. It also concluded the correct Komi is 9___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] CGOS: How to access old sgf games?

[Jason House]

There's no great way to do this. I guess one could sequentially  
download files and examine them for the player to play.


I've always wanted to be able to click on a crosstable entry and get a  
more detailed summary of performance along with links to the last  
10(?)  games between the pair. I've been too lazy to add the  
functionality myself.


Sent from my iPhone

On May 5, 2009, at 8:42 AM, Łukasz Lew  wrote:


But not as old as January archive, but for example from yesterday.
Can I get games of a cgos login?

Lukasz
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Fuego technical report

[Jason House]

Overall, it's a good read.

Nitpicks:
 • The scalability graphs need to be clearer. Maybe add a caption or  
change the single-threaded label? I looked at the graphs first and  
took a bit to figure out why "single-threaded" outperformed all else.
 • The RAVE section wasn't all too clear. I think it tried to  
explain too much or tried too hard to avoid math.
 • The scalability graphs aren't very informative once the win rate  
gets too high. It'd be better if the reference had something like four  
seconds per move instead of one
 • The placement of graphs at the end felt awkward, but it may be  
the best place for them since I believe the paper's goal is ease of  
reading. Maybe make the references to the graphs less explicit in the  
text?



Sent from my iPhone

On May 4, 2009, at 1:54 PM, Martin Mueller   
wrote:


Our technical report describing the Fuego framework is now available  
on

http://www.cs.ualberta.ca/research/techreports/2009/TR09-08.php

I will probably make at least one more revision, so all feedback and  
suggestions are welcome.


Thank you

   Martin
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Simple MC implementations

[Jason House]

Here are the candidates that I'm aware of:

* Don's reference bots
* Libego (C++) http://github.com/lukaszlew/libego/tree/master
* Plug and Go (Java) https://plug-and-go.dev.java.net/

Since I use libego, I'd hope you'd pick that as your starting point :)
It aims to be a high performance library for use by others.  It's pretty
easy to read.

On Sun, 2009-05-03 at 23:09 +0200, Heikki Levanto wrote:
> Hi,
> 
> I have some ideas I would like to play with, but too little time to write a
> whole program from scratch. So I am looking for a decently written MC program
> for a starting point. (Later I may want to look at some tree search too, so
> it it has UCT or similar, it would be a bonus). I am fluent in C and C++,
> can manage Java, and a number of other languages. I work on a Linux system.
> 
> I know there are a number of "reference implementations" around, but are
> they all listed on a single page, so I could quickly take a look at a
> handful, before deciding where to go? Simple googling didn't get me to sucha
> list...
> 
> At this point I don't care for performance, multi-threading, or even time
> controls. All I want is a simple implementation of MC that is easy to read
> and to tweak, so I can see if my idea works at all.
> 
>   - Heikki
> 

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Digital Mars

[Jason House]

Of course, I now realize what I missed after sending it. Playout vs.  
Playout move... At a little over 100 moves per playout, our numbers  
agree


Sent from my iPhone

On Apr 24, 2009, at 12:54 PM, Jason House  
 wrote:



My math seems to be way different
1e9 / 45000= 22,222 cycles per playout

On Apr 24, 2009, at 12:22 PM, Michael Williams > wrote:


According to my math, that comes out to around 205 cycles per  
playout move.  Pretty damn good, I'd say.



Łukasz Lew wrote:
On Fri, Apr 24, 2009 at 01:52, Łukasz Lew  
 wrote:

I get
g++-4.1  35 kpps/GHz
g++-4.2  45 kpps/GHz
g++-4.3  40 kpps/GHz
I'm happy it's quite consistent on core2

I'm curious about 4.4 as well.

g++-4.4 45 kpps/GHz
package gcc-snapshot on ubuntu
$ /usr/lib/gcc-snapshot/bin/g++ --version
g++ (Ubuntu 20081024-0ubuntu1) 4.4.0 20081024 (experimental) [trunk
revision 141342]
so quite old.
Lukasz

Lukasz

PS

On Fri, Apr 24, 2009 at 01:29, Adrian Grajdeanu  
 wrote:

I have two benchmarks:

On an: Intel(R) Core(TM)2 CPU T7200  @ 2.00GHz stepping 06
g++ --version
g++ (GCC) 4.1.2 20070925 (Red Hat 4.1.2-33)
I had to modify SConstruct to refer to the default g++, not g++. 
4.2 and

had to remove -march=native

= Benchmarking, please wait ...

= 20 playouts in 2.72759 seconds
73.3249 kpps
36.5657 kpps/GHz (clock independent)
105316/94359 (black wins / white wins)

= 20 playouts in 2.73858 seconds
73.0304 kpps
36.4108 kpps/GHz (clock independent)
104924/94746 (black wins / white wins)

= 20 playouts in 2.72858 seconds
73.2981 kpps
36.5291 kpps/GHz (clock independent)
105097/94582 (black wins / white wins)

= 20 playouts in 2.76258 seconds
72.3961 kpps
36.1141 kpps/GHz (clock independent)
105139/94547 (black wins / white wins)

= 20 playouts in 2.74358 seconds
72.8974 kpps
36.3124 kpps/GHz (clock independent)
104896/94794 (black wins / white wins)

= Try 'help'



on an: Intel(R) Core(TM)2 Quad CPUQ9650  @ 3.00GHz stepping 0a
g++ --version
g++ (GCC) 4.3.0 20080428 (Red Hat 4.3.0-8)
(with -march=native flag)
= Benchmarking, please wait ...

= 20 playouts in 1.65575 seconds
120.791 kpps
40.2566 kpps/GHz (clock independent)
105316/94359 (black wins / white wins)

= 20 playouts in 1.65275 seconds
121.011 kpps
40.3069 kpps/GHz (clock independent)
104924/94746 (black wins / white wins)

= 20 playouts in 1.65375 seconds
120.937 kpps
40.2789 kpps/GHz (clock independent)
105097/94582 (black wins / white wins)

= 20 playouts in 1.65475 seconds
120.864 kpps
40.2917 kpps/GHz (clock independent)
105139/94547 (black wins / white wins)

= 20 playouts in 1.65175 seconds
121.084 kpps
40.3084 kpps/GHz (clock independent)
104896/94794 (black wins / white wins)

= Try 'help'


I'd be curious g++ 4.4 what gives?

Cheers,
Adrian

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Digital Mars

[Jason House]

My math seems to be way different
1e9 / 45000= 22,222 cycles per playout

On Apr 24, 2009, at 12:22 PM, Michael Williams > wrote:


According to my math, that comes out to around 205 cycles per  
playout move.  Pretty damn good, I'd say.



Łukasz Lew wrote:
On Fri, Apr 24, 2009 at 01:52, Łukasz Lew  w 
rote:

I get
g++-4.1  35 kpps/GHz
g++-4.2  45 kpps/GHz
g++-4.3  40 kpps/GHz
I'm happy it's quite consistent on core2

I'm curious about 4.4 as well.

g++-4.4 45 kpps/GHz
package gcc-snapshot on ubuntu
$ /usr/lib/gcc-snapshot/bin/g++ --version
g++ (Ubuntu 20081024-0ubuntu1) 4.4.0 20081024 (experimental) [trunk
revision 141342]
so quite old.
Lukasz

Lukasz

PS

On Fri, Apr 24, 2009 at 01:29, Adrian Grajdeanu   
wrote:

I have two benchmarks:

On an: Intel(R) Core(TM)2 CPU T7200  @ 2.00GHz stepping 06
g++ --version
g++ (GCC) 4.1.2 20070925 (Red Hat 4.1.2-33)
I had to modify SConstruct to refer to the default g++, not g++. 
4.2 and

had to remove -march=native

= Benchmarking, please wait ...

= 20 playouts in 2.72759 seconds
73.3249 kpps
36.5657 kpps/GHz (clock independent)
105316/94359 (black wins / white wins)

= 20 playouts in 2.73858 seconds
73.0304 kpps
36.4108 kpps/GHz (clock independent)
104924/94746 (black wins / white wins)

= 20 playouts in 2.72858 seconds
73.2981 kpps
36.5291 kpps/GHz (clock independent)
105097/94582 (black wins / white wins)

= 20 playouts in 2.76258 seconds
72.3961 kpps
36.1141 kpps/GHz (clock independent)
105139/94547 (black wins / white wins)

= 20 playouts in 2.74358 seconds
72.8974 kpps
36.3124 kpps/GHz (clock independent)
104896/94794 (black wins / white wins)

= Try 'help'



on an: Intel(R) Core(TM)2 Quad CPUQ9650  @ 3.00GHz stepping 0a
g++ --version
g++ (GCC) 4.3.0 20080428 (Red Hat 4.3.0-8)
(with -march=native flag)
= Benchmarking, please wait ...

= 20 playouts in 1.65575 seconds
120.791 kpps
40.2566 kpps/GHz (clock independent)
105316/94359 (black wins / white wins)

= 20 playouts in 1.65275 seconds
121.011 kpps
40.3069 kpps/GHz (clock independent)
104924/94746 (black wins / white wins)

= 20 playouts in 1.65375 seconds
120.937 kpps
40.2789 kpps/GHz (clock independent)
105097/94582 (black wins / white wins)

= 20 playouts in 1.65475 seconds
120.864 kpps
40.2917 kpps/GHz (clock independent)
105139/94547 (black wins / white wins)

= 20 playouts in 1.65175 seconds
121.084 kpps
40.3084 kpps/GHz (clock independent)
104896/94794 (black wins / white wins)

= Try 'help'


I'd be curious g++ 4.4 what gives?

Cheers,
Adrian

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Roadmap 2020 - using analysis mode to improve programs

[Jason House]

I've only looked at the first game, but it does seem very interesting to
analyze.  The white group around H2 is near death as well and I think
Leela's evaluation considered that group to be threatened.  Once that is
solidly alive, it does switch to the semeai on the right. I probably
would not have tenuki'd on move 206, but it appears safe when I read out
how to respond after move 211.  Moves 218 and 220 are reasonable
tesuji's when played in a semeai (even if wrong for that semeai).  I
think you're right that there's probably plenty of analysis to do on how
leela went wrong in the game.  It may even be that weaker bots read out
how to kill the S6 stones on the right and instead of focusing on a
liberties race with a one eyed group.  

On Wed, 2009-04-22 at 18:27 -0700, terry mcintyre wrote:
> I haven't got a ladder example at the moment, but here's an instance
> where Leela does not realize it is in terrible trouble.
> 
> 
> I ( with my 8 kyu AGA rating) know with certainty by move 223 (T5)
> that Black has captured a large white group. A stronger player could
> read this out sooner than I. This fight is too big to lose for either
> side; nothing else on the board matters. ( anyone? how early is this
> outcome pre-ordained? )
> 
> 
> Based on the results of its analysis mode, Leela does not recognize
> the outcome of this semeai until the large white group in the bottom
> right is down to two liberties.
>  
> The problem is even more stark in example2 -- similar board, black has
> foolishly played one of his own liberties for illustrative purposes.
> It is black's play, black has three liberties, white has three. Black
> must take away a liberty from white to win the capturing race, or make
> two eyes at T8. Black has only four playable moves; any other choice
> fails.
> 
> 
> Leela proposes - even after several minutes of analysis and a million
> nodes - that Black should tennuki at H14. That would snatch defeat
> from the jaws of certain victory; White would dive into T8 and win the
> race.
> 
> 
> I started this thread with the contention that analysis mode can help
> developers find problems, I hope this example explains why. My theory
> is that if a program could reliably recognize the outcome of such
> capturing races five or ten moves sooner, it could crush the likes of
> me. :D
>  
> Terry McIntyre 
> 
> "Government is an association of men who do violence to the rest of
> us."
> - Leo Tolstoy
> 
> 
> 
> 
> __
> From: Michael Williams 
> To: computer-go 
> Sent: Tuesday, April 21, 2009 1:57:54 PM
> Subject: Re: [computer-go] Reply to Lukasz and Don + Roadmap 2020
> 
> Mention the program so that the author can either refute your claim or
> fix the bug.
> 
> 
> terry mcintyre wrote:
> > Is it reasonable to expect pro players to use 6-dan programs as a
> tool for analysis? The pro players are markedly better - at a rough
> guess, a pro player could give a 6 dan amateur human or program a 3
> stone handicap.
> > 
> > On the other end of the scale, beginning players and mid kyu players
> could indeed make good use of an analysis mode by a program which is
> better than themselves.
> > 
> > Lastly, an analysis mode would be helpful to developers, methinks.
> After winning a game, I like to back up a few moves and find out when
> the program realized that it was behind. This often happens several
> moves after the fatal blow has already been struck. I know the feeling
> too well, when stronger players deftly skewer my group and I only
> discover the problem five moves later. What do they know that I don't?
> What do they know that the program doesn't?
> > 
> > We have a saying, you learn the most from reviewing games which you
> have lost. An analysis mode can help developers to discover when their
> pride and joy first begins to miss the target.
> >  Lately, I have been playing quite a bit with a commercially
> available program. An almost-ladder which has an extra liberty will
> apparently be evaluated the same as a true ladder, and the program can
> be tricked into trying to capture my ladder-like position. This sort
> of predictable flaw might provide a clue to improve the next version.
> > 
> > Terry McIntyre 
> > 
> > "Government is an association of men who do violence to the rest of
> us."
> > - Leo Tolstoy
> > 
> > 
> > 
> >
> 
> > 
> > ___
> > computer-go mailing list
> > computer-go@computer-go.org
> > http://www.computer-go.org/mailman/listinfo/computer-go/
> 
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
> 
> 
> 
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

___

Re: [computer-go] Digital Mars

[Jason House]

There's a big difference between kpps and kpps/GHz! For your system,  
you need to divide by two (and on my core2, divide by 1.66).


For raw kpps, I think I had 70 on my core2 and 100 on the AMD64.

Do you consistently get garbage such as -154.124 for your kpps/GHz?

Sent from my iPhone

On Apr 22, 2009, at 7:25 PM, elife  wrote:

On my "Intel(R) Core(TM)2 Duo CPU T7200  @ 2.00GHz", using linux  
and

the exact compiler libego was tuned for, I get 70 kpps/GHz.

= 20 playouts in 2.85618 seconds
70.0236 kpps
-154.124 kpps/GHz (clock independent)
104896/94794 (black wins / white wins)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Digital Mars

[Jason House]

That seems like a good speed.  

On my "Intel(R) Core(TM)2 Duo CPU T5450  @ 1.66GHz", using linux and
the exact compiler libego was tuned for, I get 42 kpps/GHz.

On my "AMD Athlon(tm) 64 X2 Dual Core Processor 5000+", using the same
compiler, I only get 37 kpps/GHz.



On Wed, 2009-04-22 at 18:09 -0400, Michael Williams wrote:
> After I used a better MinGW build, with a newer gcc (the one Ben suggested), 
> I get must better results with no compiler warnings:
> 
> 40.0609 kpps/GHz
> 
> Lukasz, the march options of native, i686 and core2 all worked and came out 
> to similar results with i686 being slightly faster for me.
> 
> 
> Łukasz Lew wrote:
> > 2009/4/22 Michael Williams :
> >> This worked for me:
> >> C:\Libego\lukaszlew-libego-476a46885f80e1f4d83494bb632398b3974e901b>g++ -o
> >> engine.exe ego/ego.cpp example/main.cpp -O3 -Iego -fomit-frame-pointer
> >> -ffast-math -frename-registers
> >>
> >> (I removed the -march switch)
> >>
> >> 22.5101 kpps/GHz
> > 
> > No too much :)
> > Can you try -march=i686 and -march=core2 (if you have core2) ?
> > 
> >>
> >> And I was able to create a DLL like this:
> >>
> >> C:\Libego\lukaszlew-libego-476a46885f80e1f4d83494bb632398b3974e901b>g++
> >> -shared -o libego.dll ego/eg
> >> o.cpp exported.cpp -O3 -Iego -fomit-frame-pointer -ffast-math
> >> -frename-registers
> >>
> >> 46274.8727441 pps
> >>
> >> SUCCESS!  Thanks for everyone's help.
> >>
> >>
> >> Here are the contents of exported.cpp:
> > 
> > This is almost the same as Benchmark::do_playout in benchmark.cpp
> > 
> >>
> >> #include "ego/ego.h"
> >>
> >> __declspec(dllexport) void DoPlayouts(int playout_cnt, int * blackWins, int
> >> * whiteWins)
> >> {
> >>  SimplePolicy policy;
> >>  Board board [1];
> >>  Board mc_board [1];
> >>  Playout playout(&policy, mc_board);
> >>
> >>  for (int i = 0; i != playout_cnt; i++) {
> >>mc_board->load(board);
> >>playout_status_t status = playout.run ();
> >>if (status != too_long)
> >>{
> >>  int score = mc_board -> score ();
> >>  if (score > 0)
> >>  {
> >>(*blackWins)++;
> >>  }
> >>  else
> >>  {
> >>(*whiteWins)++;
> >>  }
> >>}
> >>  }
> >> }
> >>
> >>
> >> Łukasz Lew wrote:
> >>> Please download newest version, I made some ifdefWIN 32 ... to aid
> >>> mingw porting.
> >>> http://github.com/lukaszlew/libego/zipball/master
> >>>
> >>> Under linux I can cross compile to windows binary with a following command
> >>> $ i586-mingw32msvc-g++ -o engine.exe ego/ego.cpp example/main.cpp -O3
> >>> -march=native -Iego -fomit-frame-pointer -ffast-math
> >>> -frename-registers
> >>>
> >>> It might just work :)
> >>>
> >>> FYI
> >>> $ i586-mingw32msvc-g++ --version
> >>> i586-mingw32msvc-g++ (GCC) 4.2.1-sjlj (mingw32-2)
> >>>
> >>> And the performance I get is around 32 kpps/GHz
> >>>
> >>> Lukasz
> >>>
> >>> 2009/4/22 Michael Williams :
>  Ok, I have Mingw installed now.  That sounds like the way to go.  But I
>  still don't know how to compile it  :/
> 
>  According to the SConstruct file, I should be doing something like this
>  to
>  build, but it complains:
> 
>  C:\Libego> g++ /Fobuild\ego\dbg\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3
>  -Wall
>  -Wextra -Wswitch-enum -fno-inline /nologo /Iego
> 
>  g++: /Fobuild\ego\dbg\ego.obj: No such file or directory
>  g++: /c: No such file or directory
>  g++: /nologo: No such file or directory
>  g++: /Iego: No such file or directory
>  In file included from ego\ego.h:27,
> from ego\ego.cpp:47:
>  ego\gtp.h:73: warning: `class Gtp' has virtual functions but non-virtual
>  destructor
>  In file included from ego\ego.cpp:54:
>  ego\player.cpp: In constructor `Player::Player()':
>  ego\player.cpp:27: warning: converting of negative value `-0x1'
>  to
>  `uint'
>  In file included from ego\ego.cpp:55:
>  ego\color.cpp: In constructor `Color::Color()':
>  ego\color.cpp:27: warning: converting of negative value `-0x1' to
>  `uint'
> 
> 
>  I also tried the build command for the optimized version:
> 
> 
>  C:\Libego> g++ /Fobuild\ego\opt\ego.obj /c ego\ego.cpp -DDEBUG -ggdb3
>  -Wall
>  -Wextra -Wswitch-enum -O3 -march=native -fomit-frame-pointer -ffast-math
>  -frename-registers /nologo /Iego
> 
>  g++: /Fobuild\ego\opt\ego.obj: No such file or directory
>  g++: /c: No such file or directory
>  g++: /nologo: No such file or directory
>  g++: /Iego: No such file or directory
>  ego\ego.cpp:1: error: bad value (native) for -march= switch
>  ego\ego.cpp:1: error: bad value (native) for -mtune= switch
> 
> 
>  Sorry for my ignorance.
> 
> 
> 
>  Łukasz Lew wrote:
> > 2009/4/21 Łukasz Lew :
> >> mingw rules!
> >> I compiled libego with it and got a decent 32kpps / GHz ( native g++
> >> was 44kpps / GHz)
> > I used wine to run r

Re: [computer-go] Rating Drift

[Jason House]

On Apr 21, 2009, at 11:57 AM, sheppar...@aol.com wrote:


>Not using a new login after significant changes leads to some issue
>with both rating schrmes. It helps you and everyone else.

Pebbles learns from every game it plays. So I can't agree; drift is
inherent.


Interesting. Is this an opening book or something else such as  
successful patterns? Do you take the opponent's rank into account when  
learning?




>Do you mind sharing what pebbles does? UCT+RAVE? Any other  
enhancements?


It is UCT+RAVE, but I am not sure that what I have implemented is
the same as what others have. For example, I have never been
clear on how RAVE differs from AMAF. I have done a lot of reading,
but there are a lot of overlapping ideas and variations and  
alternatives.

Not to mention tweaks and tunings.


AMAF and RAVE are the same thing. The MoGo team pioneered use of AMAF  
but called it RAVE because of their paper's target audience.




Aside from the learning mentioned above, the engine uses only
methods that have been published in this mailing list or in Mogo  
papers.

And then only a small subset of those, and I am not sure that I have
always carried out the intent of the inventors.


I'm sure we all feel that way :)







Brian

The Average US Credit Score is 692. See Yours in Just 2 Easy Steps!
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Digital Mars

[Jason House]

I always recommend cygwin. I'm a linux guy and can't live without all  
my little tools and simple package installation. You should be able to  
get the exact gcc libego was optimized for that way.


I use the digital mars d compiler and it's blazingly fast. All my d  
files can compile and link faster than gcc compiles one of libego's c+ 
+ files. I'm not knocking libego, just giving a relevent reference  
point. I'm using libego under the hood for playouts.


Sent from my iPhone

On Apr 20, 2009, at 9:18 PM, Michael Williams > wrote:


I got Libego compiled to a Windows DLL using Visual Studio and was  
able to call it, but I was only getting around 5k pps on my Core2.   
So I wanted to try another compiler.  Has anyone used the Digital  
Mars C++ compiler?  Or is there another compiler I should try?

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Rating Drift

[Jason House]

On Apr 20, 2009, at 6:11 PM, sheppar...@aol.com wrote:

>At the moment, Pebbles is creating a huge drift. Brian - CGOS  
requires us to use
>new names on the server each time we change our bots. It computes  
the strength
>using all games (heavilly biased with the results of the first 100  
games)


This is basically my first working version. Its rating dropped from  
1500 to 800
while I worked out time control, position repetition, crash bugs and  
so on.

Pebbles is basically just getting those points back.

The solution to drift is to keep Fatman-1 running.

I recall reading about an Elo system that had better adaptation to  
players whose

rating changes. It was called Glicko-2. Here is a link: 
http://en.wikipedia.org/wiki/Glicko_rating_system



It's well known that the simple CGOS rating system could be improved.  
CGOS continually increases its confidence level in a rank as the  
number of games increase, regardless of upsets. That means the more  
games you played with a buggy bot, the longer you will take to get a  
proper rank. It also creates a larger drift tendency.


Also, while CGOS does only incremebtal adjustments based on recent  
games, bayes ELO will look at all games to compute a rank.


Not using a new login after significant changes leads to some issue  
with both rating schrmes. It helps you and everyone else. I'll be  
quiet about this now.




>Pebbles is probably closer to 2000 ELO than 1000 ELO based on the  
games against my bots.


Closer, yes, but I don't think it could be that high, as Pebbles has  
a significant minus

in recent games against bots rated over 1800.

Its Bayes Elo is 1519, which also does not suggest that it is headed  
for 2000.


Also, it searches only 20K light (mostly) playouts per turn. (Old  
computer.)



Do you mind sharing what pebbles does? UCT+RAVE? Any other enhancements?

>I did spot a bug in hb797-50k in its first resignation to Pebbles.  
My count was hb797-50k +1.5


Happy to help. :-)


Brian

The Average US Credit Score is 692. See Yours in Just 2 Easy Steps!
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Could be that nobody is playing?

[Jason House]

hb-797-RAVE-50k
1827 -181 +142

hb797-50k
1477 -88 +84

Identical hardware. AMD64x2 with one search thread and no pondering.

The error bars don't overlap, but they come close. I'm rarely patient  
enough to wait for 500 games to get +/-50 ELO.



Sent from my iPhone

On Apr 20, 2009, at 4:43 PM, Don Dailey  wrote:


Jason,

This means nothing - can you give us more details?   What did the  
error bars look like?   Which hardware were each run on?  etc.


- Don


2009/4/20 Jason House 
Earlier today, I looked up my identical 50k RAVE bots and found  
ratings of 1827 (old) and 1468 (new).


Sent from my iPhone

On Apr 20, 2009, at 4:08 PM, Don Dailey  wrote:


That should be interesting.

So we have

  1. ego-v0.115-100k

  2. libEGO-v0.115-100k

Is that correct?   We can watch it's bayelo rating as well as it's  
incremental rating.


- Don





On Mon, Apr 20, 2009 at 3:13 PM, Łukasz Lew  
 wrote:

Rated: 1713 as of 2007-12-29 09:28:46
http://cgos.boardspace.net/9x9/cross/libEGO-v0.115-100k.html

I am running exactly the same binary file to check it recent rating.
ego-v0.115-100k

Lukasz

On Mon, Apr 20, 2009 at 20:16, Christoph Birk  wrote:
> On Mon, 20 Apr 2009, ?ukasz Lew wrote:
>>
>> Is there a rating drift? I remember that pure UCT no RAVE with  
100k

>> playouts got over 1700 elo.
>
> That seems a little high. My 50k-pure-UCT searcher is around
> 1580 for a long time.
>
> Christoph
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Could be that nobody is playing?

[Jason House]

Earlier today, I looked up my identical 50k RAVE bots and found  
ratings of 1827 (old) and 1468 (new).


Sent from my iPhone

On Apr 20, 2009, at 4:08 PM, Don Dailey  wrote:


That should be interesting.

So we have

  1. ego-v0.115-100k

  2. libEGO-v0.115-100k

Is that correct?   We can watch it's bayelo rating as well as it's  
incremental rating.


- Don





On Mon, Apr 20, 2009 at 3:13 PM, Łukasz Lew  w 
rote:

Rated: 1713 as of 2007-12-29 09:28:46
http://cgos.boardspace.net/9x9/cross/libEGO-v0.115-100k.html

I am running exactly the same binary file to check it recent rating.
ego-v0.115-100k

Lukasz

On Mon, Apr 20, 2009 at 20:16, Christoph Birk  wrote:
> On Mon, 20 Apr 2009, ?ukasz Lew wrote:
>>
>> Is there a rating drift? I remember that pure UCT no RAVE with 100k
>> playouts got over 1700 elo.
>
> That seems a little high. My 50k-pure-UCT searcher is around
> 1580 for a long time.
>
> Christoph
>
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Could be that nobody is playing?

[Jason House]

At the moment, Pebbles is creating a huge drift. Brian - CGOS requires  
us to use new names on the server each time we change our bots. It  
computes the strength using all games (heavilly biased with the  
results of the first 100 games)


Pebbles is probably closer to 2000 ELO than 1000 ELO based on the  
games against my bots. I did spot a bug in hb797-50k in its first  
resignation to Pebbles. My count was hb797-50k +1.5


Sent from my iPhone

On Apr 20, 2009, at 4:47 AM, Łukasz Lew  wrote:


Is there a rating drift? I remember that pure UCT no RAVE with 100k
playouts got over 1700 elo.
I will try to run it today again.

Lukasz

2009/4/20 Jason House :

I've started two bots: hb797-10k and hb797-50k
They are pure UCT+RAVE with light playouts, one search thread, and no
pondering.
The number at the end represents the playouts per move.

I forget the approximate ratings for each version. I'll guess 1200-1300 
 for

10k and 1500-1600 for 50k.
I messed up the first round and both bots lost on time due to no  
internet

connection.
Sent from my iPhone
On Apr 17, 2009, at 4:49 PM, Jason House  


wrote:

I can run my bot (1600-1700 ELO), but I may a few days depending on  
free

time over the weekend.

Sent from my iPhone
On Apr 17, 2009, at 4:23 PM, "Brian Sheppard"   
wrote:


There are actually very few programs playing on CGOS (9x9). My  
engine is

rated around 1000, which means that it plays 75% of its games against
AverageLib (rating 670), and occasional games against Aya (rating  
2300). All
games have the predictable result, so I haven't been learning much  
lately.


I saw on Sensei's Library page http://senseis.xmp.net/?CGOSBasicUCTBots 
 that
there are a range of basic UCT implementations that would be  
excellent
opponents (rating 1171 through 1603), but I haven't seen these  
players in

weeks. Is it possible to get them back up?

If so, I would deeply appreciate it.

Thanks,
Brian


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Could be that nobody is playing?

[Jason House]

I've started two bots: hb797-10k and hb797-50k

They are pure UCT+RAVE with light playouts, one search thread, and no  
pondering.


The number at the end represents the playouts per move.


I forget the approximate ratings for each version. I'll guess  
1200-1300 for 10k and 1500-1600 for 50k.


I messed up the first round and both bots lost on time due to no  
internet connection.


Sent from my iPhone

On Apr 17, 2009, at 4:49 PM, Jason House   
wrote:


I can run my bot (1600-1700 ELO), but I may a few days depending on  
free time over the weekend.


Sent from my iPhone

On Apr 17, 2009, at 4:23 PM, "Brian Sheppard"   
wrote:


There are actually very few programs playing on CGOS (9x9). My  
engine is rated around 1000, which means that it plays 75% of its  
games against AverageLib (rating 670), and occasional games against  
Aya (rating 2300). All games have the predictable result, so I  
haven't been learning much lately.


I saw on Sensei's Library page http://senseis.xmp.net/?CGOSBasicUCTBots 
 that there are a range of basic UCT implementations that would be  
excellent opponents (rating 1171 through 1603), but I haven't seen  
these players in weeks. Is it possible to get them back up?


If so, I would deeply appreciate it.

Thanks,
Brian

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] engine/cgosGtp.kit miscommunication

[Jason House]

From memory, when something goes wrong (engine crash?), the client  
incorrectly sends the previous move. This then causes the server to  
boot the bot due to an illegal move. Everything then shuts down,  
leaving a confused programmer :)


Sent from my iPhone

On Apr 18, 2009, at 3:51 PM, "Brian Sheppard"   
wrote:


I have observed a few times that cgosGtp.kit sends a command to my  
engine, but my engine does not receive it. I am wondering if anyone  
else has seen such behavior, and can tell me how it happens.


Some possibly relevant background info:

   - I am shamelessly stealing the GTP code (and pondering code)  
from Fuego

   - Um, thanks Martin!
   - Running on Vista
   - I invoke as follows: tclkitsh cgosGtp.kit -c cgos-config.txt -k  
Quit.txt   1>log.txt

   - the file log.txt ends with some command, like 'genmove w'
   - my engine's log of commands received ends with the previous  
command, like 'time_left w 70 0'
   - The behavior is intermittent. Out of almost 400 games, I have  
seen it 3 times.


The result of this state is that my engine is pondering, and  
cgosGTP.kit is waiting for the engine to respond.


This will continue until CGOS times out the game.

Now, losing the game on time doesn't bother me. It bothers me that  
the hang-up between my engine and cgosGtp.kit will persist, so my  
engine *never* plays another game until I restart. This wastes a  
whole night.




Any ideas?

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Could be that nobody is playing?

[Jason House]

I can run my bot (1600-1700 ELO), but I may a few days depending on  
free time over the weekend.


Sent from my iPhone

On Apr 17, 2009, at 4:23 PM, "Brian Sheppard"   
wrote:


There are actually very few programs playing on CGOS (9x9). My  
engine is rated around 1000, which means that it plays 75% of its  
games against AverageLib (rating 670), and occasional games against  
Aya (rating 2300). All games have the predictable result, so I  
haven't been learning much lately.


I saw on Sensei's Library page http://senseis.xmp.net/?CGOSBasicUCTBots 
 that there are a range of basic UCT implementations that would be  
excellent opponents (rating 1171 through 1603), but I haven't seen  
these players in weeks. Is it possible to get them back up?


If so, I would deeply appreciate it.

Thanks,
Brian

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Tree Contention

[Jason House]

On Apr 15, 2009, at 6:50 PM, Michael Williams > wrote:



You can change the value all you want.  You just can't change the key.


Right... That's the design in the google talk. Remi said he "can reuse  
cache entries" and so avoids resizing / copying (greatly simplifying  
the algorithm). I find that 32 bit zobrist hashing takes a few minutes  
before reusing a single hash value. That's too infrequent to use in  
place of real cleanup. Smaller hashes (such as 16 bit) would have too  
much ovelap to be useful... So rejecting that possibility leaves me  
clueless about what reusing a hash entry could mean besides replacing  
a complete slot in the table.









Jason House wrote:
On Apr 14, 2009, at 7:57 PM, Rémi Coulom fr> wrote:

Jason House wrote:
Out of curiosity, how do you intelligently delete old nodes?  
Reference counting won't always work due to cycles, and a nieve  
scan of the tree could block all threads.


I store a date of birth in every node. At the beginning of a new  
search, I increment time, and refresh the date of birth of all the  
descendants of the new root. When allocating a new node, I can  
reuse old hash entries.
Reuse hash entries? I assume you don't mean reuse entries because a  
later hash value matches (should be quite rare, even with 32 bit  
hash codes). The lockless hash you gave links to does not handle  
ever changing a hash value once it's set.
If you CAS the tombstone value before the key, I guess it'd be  
reasonably safe, but not guaranteed. Did you add any new states to  
guarantee safety?
Or am I thinking about this the wrong way?   
___

computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Tree Contention

[Jason House]

On Apr 14, 2009, at 7:57 PM, Rémi Coulom   
wrote:



Jason House wrote:
Out of curiosity, how do you intelligently delete old nodes?  
Reference counting won't always work due to cycles, and a nieve  
scan of the tree could block all threads.


I store a date of birth in every node. At the beginning of a new  
search, I increment time, and refresh the date of birth of all the  
descendants of the new root. When allocating a new node, I can reuse  
old hash entries.


Reuse hash entries? I assume you don't mean reuse entries because a  
later hash value matches (should be quite rare, even with 32 bit hash  
codes). The lockless hash you gave links to does not handle ever  
changing a hash value once it's set.


If you CAS the tombstone value before the key, I guess it'd be  
reasonably safe, but not guaranteed. Did you add any new states to  
guarantee safety?


Or am I thinking about this the wrong way? 
  ___

computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Tree Contention

[Jason House]

On Apr 14, 2009, at 6:46 PM, Rémi Coulom   
wrote:



Jason House wrote:


In my implementation, I found that node allocation is the most  
difficult part. For a tree, I suppose it may be done easily by pre- 
allocating a node pool for each thread, and managing memory  
allocation locally.



I was happy to hear recently that the D standard library will move  
to one heap per thread. That should eliminate that issue for me. I  
assume you mean the node allocation issue was because of locking on  
a global heap?


Yes.

Also, don't you have to be careful that two threads don't create the  
same node at the same time ? Maybe if this happens, it will just  
waste a node and a playout, so it does not matter much.


That's a good point. I assume that if an insert with CAS fails, one  
can read the value back out and discard the duplicate search node.


Out of curiosity, how do you intelligently delete old nodes? Reference  
counting won't always work due to cycles, and a nieve scan of the tree  
could block all threads. ___

computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Tree Contention

[Jason House]

On Apr 14, 2009, at 5:42 AM, Rémi Coulom   
wrote:



Jason House wrote:
I use atomic increments and atomic reads. It's really simple x86  
assembly. To do that, I used to have a counter for wins and a total  
simulations counter, but switched to wins and losses counter. Doing  
that allows independent increments to those counters.
In my implementation, I found that node allocation is the most  
difficult part. For a tree, I suppose it may be done easily by pre- 
allocating a node pool for each thread, and managing memory  
allocation locally.



I was happy to hear recently that the D standard library will move to  
one heap per thread. That should eliminate that issue for me. I assume  
you mean the node allocation issue was because of locking on a global  
heap?



A hash table could use a similar scheme. I believe this is what  
Cliff Click Jr. calls "striping". But according to his talk, it is  
less efficient than the test-and-set approach.


I'm not sure what striping is either. The talk left me with the  
impression it was an implementation detail of Java's concurrent hash  
map.



Also, you've commented previously about not resizing your table. If  
you're using Cliff's algorithm, how do you clear tombstones? I assume  
copying the table is nearly as much work as dynamic resizing. I  
imagine in-place deletions could be done with the appropriate  
barriers, but I'd have to research the race conditions and performance  
impact of that.___

computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] COGS bug in Ko detection?

[Jason House]

Please take the ensuing rules argument/discussion off-list. The last  
ko rules discussion resulted in way too many e-mails in everyone's  
inbox.


Sent from my iPhone

On Apr 14, 2009, at 2:06 PM, Robert Jasiek  wrote:


Richard Brown wrote:
And what is the _reason_ to leave out the information of whose turn  
it is?

Elegant, but not a _rationale_.


One can do two basic things with information: use it or ignore it.  
Unless we set other principles as a context, we cannot judge which  
of the two is better.


You advocate using information. At the same time, you ignore a lot  
of information. You ignore much more than you use. Why? And why then  
do you advocate on using a particular piece of information but not  
the other available information as well? Which additional  
information? The sequence of situations, which are the combination  
of a position and a player having the turn, since the first  
occurrence of a position / situation about to be recreated. We do  
not want to use that much information - rather we want to leave out  
quite some information. There is a rationale behind leaving out also  
the who-has-the-turn information (e.g., having the minimal rule that  
works like a superko rule) and there is a rationale behind not  
leaving out it (e.g., endless recycling of

alternating moves is expressed more easily as multiples of situational
cycles). But this does not answer yet why you consider it better to  
also

consider the turn.

It is a ko rule that depends on one type of information only: The  
colour

of each intersection.

And what is the _reason_ to leave out the very pertinent information
of whose turn it is?
No _rationale_ for that.


It is, e.g., to have the minimal rule that works like a superko  
rule. Or: To have that variant of a superko rule that by far most go  
players

that have heard about superko imagine as the superko rule.

And... Oh, never mind, of course you must be right.  You're the  
expert.


Being an expert does not replace the necessity of providing reasons.  
Not
being an expert is not a good excuse for not providing reasons,  
either.


Also you emphasize rationale, so we should exchange not just opinions
but reasons.

To offer an on-topic reason: positional superko requires less storage
and execution time than situational superko.

--
robert jasiek
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Tree Contention

[Jason House]

I use atomic increments and atomic reads. It's really simple x86  
assembly. To do that, I used to have a counter for wins and a total  
simulations counter, but switched to wins and losses counter. Doing  
that allows independent increments to those counters.


I have not done a lockless hashtable yet. I'm tempted to use double  
wide CAS and be done with it, but I don't know if that'll work on 64  
bit machines.


Sent from my iPhone

On Apr 13, 2009, at 5:03 PM, Michael Williams > wrote:


What tricks are people doing to minimize the performance degradation  
due to multiple threads contending for access to the tree (in  
MCTS)?  Do you only lock a portion of the tree?  How would that work?


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] COGS bug in Ko detection?

[Jason House]

That sounds like a classic _positional_ super ko violation. Any board  
repetition is a ko violation, regardless of the player to play.


Sent from my iPhone

On Apr 13, 2009, at 9:32 AM, "Brian Sheppard"   
wrote:


Black is flagged for an illegal Ko at the end of game 738921 on  
CGOS. Black played H1, which looks legal to me. Server bug?


Scanning through the log today, I found a similar situation in game  
738998.


The setup is that two stones in the corner are captured by playing 1  
stone. Recapture of the capturing stone is declared a Ko. There was  
no SuperKo repetition involved in either game.


Best,
Brian

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Dependency inversions in Monte-Carlo Go

[Jason House]

On Apr 8, 2009, at 3:15 AM, Łukasz Lew  wrote:

On Tue, Apr 7, 2009 at 23:52, Claus Reinke   
wrote:

Last time I looked more closely at what my MC bot (simple, no tree)
was doing, I noticed that it has a tendency to try the impossible  
moves

(suicides) first, discarding them as impossible for every genmove.

Looking at more statistics, and thinking about it, it finally  
dawned on
me that this is a consequence of the standard move evaluation  
approach

based on win rate:

- what one hopes for is the move with the best chance of winning
   (move enables win)
- what one might get is a move that can only be played when winning
   (win enables move)

For suicide moves, this is particularly obvious: they become possible
only in the small number of games in which the opponent group
surrounding the pseudo-eye has died (or is killed by playing in the
pseudo-eye after removing all other liberties). The larger the group,
the more likely that the game is going to be won if that group dies
(roughly), so the larger the opponent group, the more tempting its
pseudo-eyes seem for win-rate-based evaluation, however unlikely
it is that the group actually dies in non-random play (certainly not
by starting with the pseudo-eye).

Something similar might be happening at a less obvious scale,
such as playing a move into self-atari: there is one opponent
move that renders this useless, but it is only one move - any
game in which the stone is not captured might look rather
good in terms of winning.


Good insight, well known too.



Is there a known method of reducing the impact of these outliers
(other than building a real tree and seeing by trial-and-error
that many good-looking moves aren't really useful)?


Heavy playouts introduce lot's of knowledge to avoid moves that can be
easily and with high probability detected that are bad.

If you are asking about domain-independent techniques, then only MCTS
and AMAF/RAVE are well known.
Nothing else is in popular. But more and more people are thinking how
to make adaptive playouts.


Heavy playouts aren't the only way. Initialization heuristics and  
progressive widening also work.




It seems
that one cannot just devalue moves with low hit counts - after
all, if there is only one sequence of moves that will rescue the
game, one doesn't want to discount it just because it is rare.

One thing that might help are move-number statistics: those
moves that tend to be played late in the playouts in which
they occur might depend on other moves to be played first,
so perhaps one should have lower bounds on when each
move can be considered for actual play?


In light playout moves are played at random, so the moment of playing
a move doesn't carry too much information.

Lukasz



Claus




___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[OT] Re: [computer-go] Pseudo liberties: Detect 2 unique liberties?

[Jason House]

This reminds me of a related question I had a while back. In a single  
MCTS/UCT search node, how do people store the children? Does a node  
contain summaries of all their children, or just pointers to the  
children?


Pure pointers are simple but requires allocating many more objects,  
including greater hashtable usage. Local summaries should be more  
cache friendly, but may miss out on updates to children searched  
through other paths.


Sent from my iPhone

On Apr 7, 2009, at 12:33 PM, Łukasz Lew  wrote:


Thanks. What about linked lists?
They seem to be both compact and fast to merge and detect duplicates.
Why have you abandoned them?

Lukasz

On Tue, Apr 7, 2009 at 17:42, David Fotland games.com> wrote:
Yes, I walk both chains looking for duplicates.  This is quite fast  
if done

efficiently, since group merging is rare enough.  I found keeping the
liberty arrays to be slower since they are big, so there is more copy
overhead in the UCT tree, and they are not cache friendly.

David


-Original Message-
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of Lukasz Lew
Sent: Tuesday, April 07, 2009 2:32 AM
To: computer-go
Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique  
liberties?


On Tue, Apr 7, 2009 at 07:40, David Fotland games.com>

wrote:
In Many Faces' playouts I don't keep arrays of liberties.  I just  
keep

the

counts.  In the older program I keep linked lists of liberties.


How do you count the number of liberties when you merge two groups?
Do you walk over both chains searching for duplicates in their empty
neighbourhoods (duplicated liberties)?

Lukasz



David


-Original Message-
From: computer-go-boun...@computer-go.org [mailto:computer-go-
boun...@computer-go.org] On Behalf Of w...@swcp.com
Sent: Monday, April 06, 2009 10:36 AM
To: computer-go
Subject: Re: [computer-go] Pseudo liberties: Detect 2 unique  
liberties?


Isaac,

My numbers were extracted from the insert() function,
so my numbers don't say how long the average search.
would be. When you place a stone on the board, you
immediately add up to 4 adjacent liberties, one at a
time. Never-the-less, it does say something.

I have intended to measure the distributions of all
set operations in the board funcions, but I have not
finished them.

Space is also very significant when choosing a
representation. Another issue is whether the board
can undo or rewind to saved positions. The arrays
that store liberties take 19*19*256 shorts or
184832 bytes. (A chain can only have about 2/3 of
the locations on the board as liberties, if you
follow the usual rules.) This overwhelms all
other data in the board.

Michael Wing


I made some artificial tests where I do x inserts, 1 delete, 10

counts

and
1 merge. For x=4 inserts, linear arrays are about 4 times  
faster. For

x=8

inserts, linear arrays are about 3 times faster. From your data I

calculated
an average liberty count of 2.8 (which seems low to me). This  
means

that

for
the used board sizes, the constant time merge does not pay off  
vs.

the

constant time count.

So I can confirm that the linear arrays do seem to be faster,  
however

I
haven't tested how they compare to pseudo libs. For heavier  
playouts,

I

reckon that true liberties might be a bit faster and more useful.

Isaac

 Original-Nachricht 

Datum: Fri, 3 Apr 2009 10:22:37 MDT
Von: w...@swcp.com
An: "computer-go" 
Betreff: Re: [computer-go] Pseudo liberties: Detect 2 unique

liberties?



Isaac,

Most groups have only say 4 to 8 liberties. This is why simple

arrays

of

liberty locations work so well. The new Intel CPUs have

instructions

that can search strings 16 bytes at a time, so it could run even

faster.


Bit vectors also work, but if you want a true liberty count,  
then

you

have

to avoid counting (1 or 1) as 2, which is the pseudo liberty

problem,

and

which takes more code to write and more time to compute.

When I started, I wanted to find a better implementation than

gnugo,

and

I was unable to do so. Of course one can refine or simplify the

gnugo

code

in many different ways, but gnugo has all of the good ideas.

Michael Wing



PS: Here is the data for how many times the program tried to  
insert
a stone into a chain that has x liberties or x adjacencies. It  
was

taken
from a run that combined monte carlo simulations and ladder  
reading

exercises. Note that there are only 2% as many

liberties/adjacencies
of size 8 as there are of size 0. Chains with liberties/ 
adjacency

lists

of size 16 are so few as to be irrelevant.

   data here.



On Thu, Apr 2, 2009 at 5:14 AM,   wrote:

Isaac,

I implemented about 6 way to track liberties,
a couple years ago, and measured the running
performance, and by far the best is also the
simplest: keep an array of liberties for each
chain, and do a simple linear search.

This may seem slow, but it has a couple real
advantages. First, it works with the ca

Re: [computer-go] April KGS bot tournament: results

[Jason House]

I disagree with your comment about AyaMC's move 28 in round 4. The  
move looks to me like it primarilly aims to build a large framework  
along the bottom/center. All basic fights seem to favor white..


I'm only KGS 3k, so take my comments with a grain of salt...

Sent from my iPhone

On Apr 6, 2009, at 10:52 AM, Nick Wedd  wrote:


The results of yesterday's KGS bot tournament are now available at
http://www.weddslist.com/kgs/past/46/index.html

As usual, I expect there are mistakes, and I will welcome corrections.

Congratulations to the winner, CzechBot!

Nick
--
Nick Weddn...@maproom.co.uk
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Shortcuts in the tree

[Jason House]

I think you're looking for a post by Łukasz Lew about the epsilon  
trick...


Sent from my iPhone

On Mar 31, 2009, at 8:37 PM, Michael Williams > wrote:


It seems like there was a short discussion here recently about a  
strategy for reducing the amount of time spent updating the MCTS  
search tree, but now I can't find it.  I don't remember much else  
about it.  Does this ring any bells for anyone?

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/


___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Transpositions in Monte-carlo tree search

[Jason House]

Which Mogo paper(s)? Not all Mogo papers contain ideaa used by Mogo in  
public releases / competitions. Some things are just research. I  
remember hearing that the grandfather heuristic isn't good.


Sent from my iPhone

On Mar 30, 2009, at 5:36 PM, Matthew Woodcraft  
 wrote:



How are transpositions normally handled in monte-carlo tree search?

I have been assuming that the natural thing would be to have a single
shared node for each board position, so that simulations which reach  
the

same position will use the same set of statistics (but when backing up
the result, to only update the nodes for the simulation actually
played).

But I see in some of the Mogo papers that some of the contributions to
the heuristic value of a node depend on the position of the previous
move.

So do MCTS programs not recognise transpositions at all? Or are the
heuristics from the time when the node was first created allowed to
stand, no matter what the simulation route is next time?

-M-
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/