Re: [computer-go] Re: Dynamic Komi at 9x9 ?

[dhillismail]

Ingo,

I'm not a proper statistician, but I believe there's a crucial second step 
that's missing in your analysis of significance. Even if this were the only 
computer-go test that you personally had ever conducted, we would nevertheless 
need to take into account all of the other tests being conducted within the 
community. On any given day, some high number of similar tests are carried out 
by members of this list. They are testing different hypotheses to be sure, but 
that doesn't get us off the hook at all. 

What it boils down to is this: how frequently does *somebody* get a 95% 
confidence result about *something* that isn't going to hold up under further 
testing? This issue comes up all the time in epidemiology (e.g. cancer clusters 
near power lines), medical studies, bioinformatics, etc..

- Dave Hillis






-Original Message-
From: "Ingo Althöfer" <3-hirn-ver...@gmx.de>
To: computer-go@computer-go.org
Sent: Thu, Feb 18, 2010 7:28 am
Subject: [computer-go] Re: Dynamic Komi at 9x9 ?


Hello Don,
everal very good points by you!

 Does anyone have data based on several thousands games 
 that attempts to measure the effect of dynamic komi?
 I would like to see results that are statistically meaningful. 
I had eight handplayed (4 + 4) games on 19x19 with very 
igh handicap, where the version with dynamic komi (rule 42)
ained a 3-1 score and the version with static komi 
erformed 0-4 versus the same opponent. This is evidence 
n the 95% region that the version with dynamic komi is 
ot weaker than the static version.
> We need to see a few thousand games played
A few hundreds or even a few dozens may be sufficient when 
he outcome is very clear.
> against a fixed opponent WITH dynamic komi, and 
 then the same program without dyanmic komi playing 
 against the same opponent with the same number
 of games.   The number of games must be decided before 
 the test is run, or the error margin calculation is 
 meaningless.
I am willing to provide the statistical part, when programmers
un the experiments.

 As far as I can tell, nobody has yet to produce anything more 
 than anecdotal evidence that this works.
I have. See the 4 + 4 games mentioned above,
layed with my "rule 42".
> Having a person manually adjusting this after every game is 
 completely non-sceientific, unless they are doing it in a fixed 
 way with no decision making on their part 
Right.
> and they are playing thousands of games (or at least
 enough to get statistically significant results.)
Right, especially also the bracket part of your sentence.
> I'm not trying to rain on anyone's parade,  but I cannot 
 understand why no one has produced a statistically meaningful 
 result on this subject - 
I would have. Unfortunately I am not a programmer, and am also
ot fit in modifying a program code to include dynamic komi.
But, to repeat it, I am willing to do statistical home
ork.
> I am genuinely interested in this since I never was able to 
 make it work when I spent about one intense week on it.
 (I did not do this with handicap games, but with normal games.)
Your sentence in brackets is crucial. I only proposed to use
ynamic komi in games with high handicap. Especially I had in
ind the situation where the stronger side (giving high handicap)
s MC-based.
Perhaps, 9x9 instead of 19x19 makes it easier for some programmer
o start test series with dynamic komi.
Ingo.
-- 
icherer, schneller und einfacher. Die aktuellen Internet-Browser -
etzt kostenlos herunterladen! http://portal.gmx.net/de/go/atbrowser
__
omputer-go mailing list
omputer...@computer-go.org
ttp://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] scalability analysis with pachi

[dhillismail]

Yes. And while worrying about what happens after a win rate of 97% sounds like 
splitting hairs, I think we're talking about an awkward way of measuring 
something that's of practical interest.

Suppose Hideki's experiment were repeated, giving GNU GO a four stone handicap. 
If Zen plateau'd out at the same time-per-move, that would suggest a real limit 
in strength improvement against dissimilar opponents. If Zen plateau'd out at 
the same ELO point, that might suggest that a few percent of the games involved 
tactical situations that GNU GO could understand but Zen couldn't, even with 
much more time. The second possibility could be tested more efficiently by Zen 
taking the handicap.

- Dave Hillis




-Original Message-
From: Erik van der Werf 
To: computer-go 
Sent: Sun, Jan 17, 2010 8:06 am
Subject: Re: [computer-go] scalability analysis with pachi


Oh, ok. I was a bit surprised. Last time I checked my program scaled
uite nicely against GnuGo, at least for low numbers of simulations up
o about 97% winning rate. I suppose there could be some kind of
lateau when nearing 100% due to some missing knowledge/skills that
nly GnuGo has.
Erik

010/1/16  :
 Well, I thought "there seems to be a picture emerging" was sufficiently
 hedged that it would be construed as a conjecture, not a conclusion. :)
 I am thinking, in particular, of the scalability studies with Zen that
 Hideki reported to this list in Oct. 2009.
> BTW, recently I've measured the strength (win rate) vs time for a move
> curves with Zen vs GNU Go and Zen vs Zen (self-play) on 19 x 19 board.
> Without opening book, it saturates between +400 and +500 Elo against
> GNU but doesn't upto +800 Elo in self-play.  That's somewhat
> interesting (detail will be open soon at GPW-2009).
> Hideki
  There was a bit more information provided in a sequence of posts to this
 list during that month. I wonder if the paper is out now.
 - Dave Hillis

 -Original Message-
 From: Erik van der Werf 
 To: computer-go 
 Sent: Sat, Jan 16, 2010 12:55 pm
 Subject: Re: [computer-go] scalability analysis with pachi

 2010/1/15 
>
> Thank you for posting these interesting results There seems to be
> a picture emerging that MCTS engines scale very well in self play, and
> apparently against other MCTS engines, but not so well against the non-MCTS
> version of Gnugo.
> - Dave Hillis


 Do you have any data to back that conclusion?

 Erik

 ___
 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/

__
omputer-go mailing list
omputer...@computer-go.org
ttp://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] scalability analysis with pachi

[dhillismail]

Well, I thought "there seems to be a picture emerging" was sufficiently hedged 
that it would be construed as a conjecture, not a conclusion. :)

I am thinking, in particular, of the scalability studies with Zen that Hideki 
reported to this list in Oct. 2009.

> BTW, recently I've measured the strength (win rate) vs time for a move 
> curves with Zen vs GNU Go and Zen vs Zen (self-play) on 19 x 19 board.  
> Without opening book, it saturates between +400 and +500 Elo against 
> GNU but doesn't upto +800 Elo in self-play.  That's somewhat 
> interesting (detail will be open soon at GPW-2009).
> Hideki

 There was a bit more information provided in a sequence of posts to this list 
during that month. I wonder if the paper is out now.

- Dave Hillis


-Original Message-
From: Erik van der Werf 
To: computer-go 
Sent: Sat, Jan 16, 2010 12:55 pm
Subject: Re: [computer-go] scalability analysis with pachi


2010/1/15 

Thank you for posting these interesting results There seems to be a picture 
emerging that MCTS engines scale very well in self play, and apparently against 
other MCTS engines, but not so well against the non-MCTS version of Gnugo.

- Dave Hillis




Do you have any data to back that conclusion?

Erik



___
omputer-go mailing list
omputer...@computer-go.org
ttp://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] scalability analysis with pachi

[dhillismail]

Thank you for posting these interesting results There seems to be a picture emerging that MCTS engines scale very well in self play, and apparently against other MCTS engines, but not so well against the non-MCTS version of Gnugo.



- Dave Hillis




-Original Message-
From: Jean-loup Gailly 
To: computer-go 
Sent: Thu, Jan 14, 2010 6:53 pm
Subject: [computer-go] scalability analysis with pachi







I did some 19x19 scalability experiments with pachi, written by Petr Baudis.


This was run on one machine using 15 out of 16 2.2 GHz cores, against


Fuego using 100K playouts on 15 cores of another machine.  The results


are encouraging. Pachi's strength continues scaling linearly (in elo)


with each doubling of the number of playouts:














pachi2 is an instance of pachi running on kgs.  It temporarily got a


2d rating on 19x19 but many dans are now trying to lower this :-(


Note that Petr should be congratulated for this, I only did minor


changes myself.






Jean-loup








___
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: (no subject) wish hahn

[dhillismail]

Interesting is in the eye of the beholder, but I think a Hahn tournment would 
be interesting. 

Everyone with an MC bot could easily modify it to play by setting it 
(carefully) not to resign, and changing it to try to maximize average score 
rather than probability of win. That's really just a few lines of code. (It 
might not hurt to look at passing too.) Then we (I'll try to join) would face 
the choice of whether or not to retune the engine-rather a tiresome chore.

If everyone did that, I expect that we would see roughly the same 
stratification of the field that already exists. (But you never know). I 
picture the strong bots making safe moves and waiting for the weaker ones to 
make mistakes. 

What I hope would happen is that some of the people, experimenting with dynamic 
komi and the like, would combine it with some opponent modeling and be 
creative. When I take time out to concentrate on a related problem, I usually 
get new ideas that help me with the original problem.

A couple nagging worries: 
1) Taking the average score might be pretty noisy. Some luck in a tournament is 
good, too much is bad. Some preliminary simulations with a strongish 19x19 bot, 
might give some indication of whether a double round robin tournament would be 
adequate. 
2) Also some games would be incomplete due to inadvertent resignation, bot 
crashes, or loss on time. Nick would need to choose a policy for scoring in 
those cases . The tournament could easily be decided by how an incomplete game 
gets scored, and that would be a bit frustrating.

- Dave Hillis

-Original Message-
From: "Ingo Althöfer" <3-hirn-ver...@gmx.de>
To: computer-go@computer-go.org
Sent: Mon, Jan 4, 2010 1:51 pm
Subject: [computer-go] Re: (no subject) wish hahn


Hi all,
Alain Baeckeroot wrote:
 As a physicist i like to experiment first, and think later,
 to understand what happened, which obviously was not foreseen ;-)
This attitude I like very much, being an experimental mathematician.
> I believe it will reveal some hidden aspect of the stronger engines,
 and for sure it will be *fun* to see stronger bots destroy weaker ones,
 (MC-RAVE end-game of strong bots is boring on 19x19)
 ...

 No need to be perfect Hahn. Changing the aim to max_points seems
 to be just a change in metrics, it does not looks like very complicate

o with Hahn scoring looks similarily exotic like Pair-Bot-Go,
nd I understand the hesitation of all who live in performance-oriented
ategories. Perhaps it would help some people when such exotic tournaments
Hahn scoring, Pair-Go, ...) would be very clearly in a spirit where
inning and prizes does not count more than anything else. For this
relaxed spirit" it might help when the bots did not enter with their
raiditional (fame-burdened) names, but with related names like
en-Gaga, Mogo-Gaga, ManyFaces-Gaga or whatever.
or Gazenga, Gomogoga, gamanyfacesga ...)
I am already dreaming of a pair-bot-tournament with continental teams:
 ManyFaces & Fuego for North America
 Zen & Aya for Asia
 Mogo & Valkyria for Europe
- Dreamingo.
-- 
reisknaller: GMX DSL Flatrate für nur 16,99 Euro/mtl.!
ttp://portal.gmx.net/de/go/dsl02
__
omputer-go mailing list
omputer...@computer-go.org
ttp://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: Hahn system tournament and MC bots. and KGS tournament ?

[dhillismail]

I would enter a bot in a KGS Hahn tournament, of Nick's type (2) if it were 
held. (If KGS permits round-robin scheduling, I think that would be preferable, 
but not essential.) I think it would be a lot of fun. Which is not to suggest 
that the regular KGS tournaments need changing.

The early MCTS bots played to maximize territory but then we evaluated their 
performance in tournaments that only counted wins and losses. We found that 
changing the bots to maximize percentage (standing in for probability) of wins 
led to better performance in those tournaments. I think using MCTS playing to 
maximize territory works perfectly well, when that's how you intend to measure 
performance. Things like RAVE might even work better.

Here's a question. Suppose I want to measure the strength difference between 
two different playout policies for my engine.
1) I set up two versions to play Hahn games and evaluate the difference in 
terms of mean average territory per game.
2) I set them both up to maximize probability of win and evaluate the 
difference in terms of games won.
Which way will give me the answer I need with the fewest games? (Note that 
games for 2) will be shorter because of resignations.)

For weak bots, my experience testing 1) is not encouraging. Blowouts between 
weak bots are very common, making mean average territory quite a noisy metric. 
But for strong bots, 1) might be better than 2). I wouldn't be surprised. Using 
the median might be better than using the mean-I didn't think to try it at the 
time.

But for a KGS Hahn tournament, I would prefer using the mean average territory 
per game. I like the idea of encouraging the strongest bots to try to swindle 
away every last stone of their hapless prey. Although my bot would be on the 
receiving end of this...hmm.

- Dave Hillis


-Original Message-
From: Nick Wedd 
To: computer-go 
Sent: Tue, Nov 24, 2009 6:42 pm
Subject: Re: [computer-go] Re: Hahn system tournament and MC bots. and KGS 
tournament ?


In message <200911242252.09463.alain.baecker...@laposte.net>, Alain Baeckeroot 
 writes 
 
>In another thread Nick Wedd wrote: 
> 
>> The December KGS bot tournament will be 9x9. I guess that if a 
>> cluster-Zen competes in that (I am hoping it will), it will be 
>> unbeatable. 
>> 
>> The existing pattern of KGS bot tournaments (see 
>> http://www.weddslist.com/kgs/future.html) means that the January one 
>> will also be 9x9, then February and March will both be 19x19. 
>> ... 
> 
> 
>Is there a possibility for an Hahn tournament on KGS ? 
>maybe with simplified rules: one point on board is one point in tournament 
>( (c) R.Jasiek ) 
 
The tournaments I run on KGS use the server's tournament manager. This makes my 
job much easier. But it knows nothing about Hahn scoring. 
 
Two things I could do: 
1.) 
  Run a tournament manually, telling the operators who their opponents in each 
round will be, and adding up the score myself. I am not very keen on this, I 
see to much room for error. 
2.) 
  Use the tournament manager, and let it plan the pairings based on its own 
opinion of who is doing well in the tournament (this won't be too far from 
reality, Aya will beat WeakBot50K either way). But declare the result based on 
the total Hahn score of the players. 
 
I would prefer (2). I would be willing to hold a tournament like that. 
 
Nick 
-- Nick Wedd n...@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] Re: Hahn system tournament and MC bots

[dhillismail]

On Tue, Nov 24, 2009 at 16:11, Nick Wedd  wrote:
> Suppose my attempts to read the game tell me "If I seal off my territory at
> A, I will win by 5 points.  If instead I invade at B, then 70% of the time I
> will win by 25 points, 30% of the time I will lose by 5 points".
>
> If I am playing Go, I will prefer A.  If I am playing bang neki, I will
> prefer B.

I think opponent modeling should not be ignored or abstracted away. The bot can 
estimate the probabilities for A and B, assuming an equal strength opponent. 
But then there is an extra step. With confidence X, the opponent is so much 
weaker or stronger, in which case the probabilities would be different. If the 
opponent has been playing random-looking moves, the smart estimate of the 
probabilities will be different than if it has been playing strong moves and 
pulling ahead. 

It's interesting to consider the problem of writing an agent to make side bets. 
There could be a pool of spectator bot, each calculating an estimate of the 
final score, after every move, and placing wagers.

Suppose we were to hold a tournament to test out some of these theories. For 
CGOS, bots come and go at their minders' whim. I don't see a good way to hold a 
Hahn tournament like that. For KGS, perhaps it could be run as a round-robin 
tournament and then the scores calculated offline with a spreadsheet program. 
That's not ideal either.

- Dave Hillis



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

Re: [computer-go] Re: Hahn system tournament and MC bots

[dhillismail]

For my fast/dumb neural net engine, Antbot9x9, I coevolved the weights using a 
similar tournament system. Each individual played a number of games against all 
the others, round robin, and the score was the sum of points for all of its 
games.

Some observations/claims:
Non-transitive effects seem more visible. Consistently overplaying garners 
extra points from weak opponents but needlessly loses extra points against 
strong ones. It becomes more important to play your opponent as well as the 
board: if you think that you have him outmatched, take some risky gambles, 
overplay. Every game in the tournament matters, right till the end of that game.

I think it could be interesting to try some bot tournaments like this. It might 
be fun to watch. When the strongest bot was playing the weakest, even near the 
(painfully one-sided) end of the game there would be an element of suspense. 
The stronger bot would (or should) be trying to swindle a few last extra points 
it didn't deserve, and the fate of the tournament could hinge on it.

- Dave Hillis


-Original Message-
From: "Ingo Althöfer" <3-hirn-ver...@gmx.de>
To: computer-go@computer-go.org
Sent: Mon, Nov 23, 2009 4:10 am
Subject: [computer-go] Re: Hahn system tournament and MC bots


Alain Baeckeroot wrote:
 A Go tounrmaent with Hahn system has been retransmeted 
 see  ... http://www.suomigo.net/wiki/HahnSystem
Thanks for the interesting stuff and the links.
>From the link HahnSystem:
 Winning By 0.5-10   gets  60 points
 Winning by 10.5-20  gets  70 points
 Winning by 20.5-30  gets  80 points
 Winning by 30.5-40  gets  90 points
 Winning by >40.5gets 100 points

 Losing by  0.5-10   gets  40 points
 Losing by  10.5-20  gets  30 points
 Losing by  20.5-30  gets  20 points
 Losing by  30.5-40  gets  10 points
 Losing by  >40.5gets   0 point
I would have found a "completely continuous result system"
ore natural, for instance
iving +40.5 points for each win with 40.5 or more
iving -40.5 points for each loss with 40.5 or more
iving x points for each score in between +40.5 and -40.5
And I believe that MC-bots would gain about 2 rating levels
gainst human players, when compared with normal chinese scoring.
Just my 40.5 cent, Ingo.
-- 
reisknaller: GMX DSL Flatrate für nur 16,99 Euro/mtl.!
ttp://portal.gmx.net/de/go/dsl02
__
omputer-go mailing list
omputer...@computer-go.org
ttp://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] Elo move prediction

[dhillismail]

Just a wild guess here. One way to get catastrophically slow performance is to 
have superfluous nested loops. For instance, one could iterate over each board 
space, calling a routine to check for legality. If the legality routine also 
iterates over the whole board (perhaps by updating all liberty counts), then 
things will get pretty slow. This kind of bug can be elusive because it does 
give the correct results.
- Dave Hillis


On Thu, Nov 19, 2009 at 12:35:09AM -0800, Seth Pellegrino wrote:
> I'm working on an implementation of Rémi Coulom's Elo-based move
> prediction algorithm[1], and I seem to be running into efficiency
> issues. With my current implementation, I'm running at around 8 or 10
> playouts per second. I can't imagine that the playouts would be so
> accurate that I would be able to accurately evaluate my next move at
> that speed. It seems that simply visiting each vacant point on the
> board and checking whether that move would be a legal move for the
> current player (without even computing which gammas are present at a
> point) takes me down to about 60-75 playouts per second.

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

Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[dhillismail]

Hideki,

Thank you. Your results look quite compelling. Do you allow memory (the number 
of nodes in the tree) to grow along with thinking time or is there a fixed 
limit? 

IIRC Don et. al.'s excellent scaling studies included gnugo but its effect was 
probably small. Self play dominated. Perhaps, what David Doshay calls, the 
"evil twin effect" causes self play to give the appearance of scaling better.

- Dave Hillis





-Original Message-
From: Hideki Kato 
To: computer-go 
Sent: Sat, Oct 31, 2009 10:39 pm
Subject: Re: [computer-go] First ever win of a computer against a pro 9P as 
black (game of Go, 9x9).




hillism...@netscape.net: 
<8cc26e08cfc0f77-5fd0-a...@webmail-m052.sysops.aol.com>:
> -Original Message-
> From: Hideki Kato 
> To: computer-go 
> Sent: Wed, Oct 28, 2009 1:41 am
> Subject: Re: [computer-go] First ever win of a computer against a pro 9P as 
lack (game of 
Go, 9x9).
> ...
> BTW, recently I've measured the strength (win rate) vs time for a move 
> curves with Zen vs GNU Go and Zen vs Zen (self-play) on 19 x 19 board.  
> Without opening book, it saturates between +400 and +500 Elo against 
> GNU but doesn't upto +800 Elo in self-play.  That's somewhat 
> interesting (detail will be open soon at GPW-2009).

> Hideki

I'd say that is more than "somewhat" interesting. While we're waiting for the 
aper, 
can you give us a picture of how many games against Gnugo went into this 
nalysis? 
Do you see this in 9x9?
I've attatched two charts of current results for convinience.  
hart1 is against GNU Go and Chart2 is self-play.
The numbers for the 1st curve "HA8000 (AMD Opteron  2.3GHz) 16 thread" 
n Chart1 are:
ime(s) Win DrawAll Dup WR  std-dev Elo
.02325 27  2,933   0   11.54%  0.59%   -353.8
.1 509 23  728 0   71.50%  1.67%   +159.8
.2 946 47  1,147   0   84.52%  1.07%   +294.9
.5 1,803   60  2,000   0   91.65%  0.62%   +416.2
.0 1,849   33  2,000   0   93.28%  0.56%   +456.8
.0 4,455   121 4,812   0   93.84%  0.35%   +473.1
The numbers for Chart2 are:
ime(s) Win DrawAll Dup WR  std-dev Elo
.1 147 4   2,000   0   7.45%   0.59%   -437.7
.3 992 36  2,000   0   50.50%  1.12%   +3.5
.0 3,742   38  4,000   0   94.03%  0.37%   +478.8
.0 13,157  43  13,328  1   98.89%  0.09%   +779.3
Since above results are measured with no opening book, I'm now 
enchmarking opening book enabled but right now the samples are 
ot enough (642 games; see the 4th curve in Chart1, "HA8000 (AMD 
pteron  2.3GHz) 16 thread w/ Book").
 Not a curve but a point now :-)
For 9x9 it's not clear.  The curve starts saturating near +500 Elo 
ut still seems increasing.
Hideki
-
g...@nue.ci.i.u-tokyo.ac.jp (Kato)


___
omputer-go mailing list
omputer...@computer-go.org
ttp://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] First ever win of a computer against a pro 9P as black (game of Go, 9x9).

[dhillismail]

> -Original Message-
> From: Hideki Kato 
> To: computer-go 
> Sent: Wed, Oct 28, 2009 1:41 am
> Subject: Re: [computer-go] First ever win of a computer against a pro 9P as 
> black (game of Go, 9x9).
> ...
> BTW, recently I've measured the strength (win rate) vs time for a move 
> curves with Zen vs GNU Go and Zen vs Zen (self-play) on 19 x 19 board.  
> Without opening book, it saturates between +400 and +500 Elo against 
> GNU but doesn't upto +800 Elo in self-play.  That's somewhat 
> interesting (detail will be open soon at GPW-2009).

> Hideki

I'd say that is more than "somewhat" interesting. While we're waiting for the 
paper, 
can you give us a picture of how many games against Gnugo went into this 
analysis? 
Do you see this in 9x9?

- Dave Hillis




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

Re: [computer-go] Neural networks

[dhillismail]

[ Digression: Some ANN architectures are more biologically plausible than 
others. "Neuromorphic Engineering" is a good search term to see what's going on 
along those lines. (But for a beginner project, the standard multi-layer 
perceptron with backpropogation would still be the natural choice.) Neural nets 
have been called "the second best solution to every problem." That's both 
criticism and praise. When the objective is to quickly solve the engineering 
problem at hand and then move on with your life, it can be a handy skill to 
have. ]

 

For an interesting but realistic beginner project, I like this suggestion from 
Magnus.

 
> From: Magnus Persson magnus.pers...@phmp.se



> I guess neural networks is fine for learning pattern priorities for example.

> There are probably just simpler and faster 

> methods for doing that. 
 


> Anyway a good project would be learning 3x3 patterns for MC heavy playouts 
> with a large number of extra features 

> such as exact liberty counts, distance from edge and corner etc. I guess the 
> best use of a neural network would be

> to create a mapping from a huge feature space to a move ordering, where more 
> straightforward pattern matching 

> would fail because the number of patterns are too high. 



One could use the "simpler and faster methods" to compare against one's own 
results, before moving up to larger patterns, and patterns combined with 
features.



- Dave Hillis

 
Quoting Petr Baudis : 
 
> Hi! 
> 
> Is there some "high-level reason" hypothesised about why there are 
> no successful programs using neural networks in Go? 
> 
> I'd also like to ask if someone has a research tip for some 
> interesting Go sub-problem that could make for a nice beginner neural 
> networks project. 
> 
> Thanks, 
> 
> -- 
> Petr "Pasky" Baudis 
> A lot of people have my books on their bookshelves. 
> That's the problem, they need to read them. -- Don Knuth 
> ___ 
> computer-go mailing list 
> computer-go@computer-go.org 
> http://www.computer-go.org/mailman/listinfo/computer-go/ 
> 
 
 
--Magnus Persson 
Berlin, Germany 
___ 
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] Progressive widening vs unpruning

[dhillismail]

I made some more tables with 50K playouts, in case that is easier to look at.



50 K playouts?

LIGHT PLAYOUTs XX
rave
?? 1|?? 36?? 39?? 38?? 40?? 39?? 40?? 40?? 40?? 37 
?? 2|?? 38?? 40?? 42?? 42?? 42?? 42?? 42?? 40?? 40 
?? 3|?? 40?? 42?? 42?? 43?? 43?? 42?? 43?? 42?? 39 
?? 4|?? 39?? 42?? 44?? 43?? 44?? 44?? 43?? 42?? 41 
?? 5|?? 38?? 41?? 42?? 44?? 45?? 45?? 42?? 41?? 40 
?? 6|?? 40?? 41?? 42?? 43?? 45?? 43?? 44?? 42?? 39 
?? 7|?? 41?? 42?? 41?? 43?? 43?? 43?? 42?? 41?? 40 
?? 8|?? 39?? 41?? 41?? 43?? 42?? 40?? 41?? 40?? 41 
?? 9|?? 37?? 40?? 40?? 39?? 40?? 40?? 39?? 40?? 37 
NO CONTEXT xx
rave 
?? 1|?? 50?? 43?? 44?? 44?? 45?? 44?? 44?? 43?? 50 
?? 2|?? 43?? 49?? 48?? 48?? 48?? 48?? 48?? 49?? 43 
?? 3|?? 44?? 48?? 47?? 47?? 47?? 47?? 47?? 48?? 44 
?? 4|?? 44?? 48?? 47?? 47?? 47?? 47?? 47?? 48?? 44 
?? 5|?? 44?? 49?? 47?? 47?? 48?? 47?? 47?? 48?? 44 
?? 6|?? 44?? 48?? 47?? 47?? 47?? 47?? 47?? 48?? 44 
?? 7|?? 44?? 48?? 47?? 47?? 47?? 47?? 46?? 48?? 44 
?? 8|?? 43?? 49?? 48?? 48?? 48?? 48?? 48?? 49?? 43 
?? 9|?? 50?? 43?? 44?? 44?? 44?? 44?? 44?? 43?? 50? 


CONTEXT x
CRAVE
?? 1|?? 31?? 36?? 35?? 38?? 35?? 33?? 38?? 35?? 29 
?? 2|?? 36?? 38?? 40?? 40?? 39?? 41?? 40?? 38?? 34 
?? 3|?? 36?? 40?? 47?? 47?? 46?? 47?? 47?? 42?? 35 
?? 4|?? 34?? 40?? 46?? 47?? 46?? 47?? 47?? 40?? 37 
?? 5|?? 35?? 40?? 45?? 47?? 47?? 47?? 45?? 40?? 39 
?? 6|?? 35?? 42?? 46?? 46?? 47?? 47?? 47?? 39?? 38 
?? 7|?? 35?? 40?? 47?? 46?? 43?? 46?? 47?? 41?? 36 
?? 8|?? 36?? 37?? 40?? 42?? 41?? 41?? 41?? 39?? 34 
?? 9|?? 32?? 34?? 34?? 35?? 37?? 36?? 36?? 35?? 31 


- Dave Hillis




-Original Message-
From: dhillism...@netscape.net
To: computer-go@computer-go.org
Sent: Thu, Oct 1, 2009 4:50 pm
Subject: Re: [computer-go] Progressive widening vs unpruning




For 9x9 games, when I added progressive widening to AntiGo (before I added 
RAVE), it was low hanging fruit. I used my old program Antbot9x9 for the move 
ranking and got a very nice strength increase for very little effort. Then, 
with a bit of tweaking, I got more improvement. RAVE, on the other hand, gives 
me a small improvement, and it comes at the cost of having to fuss with it 
endlessly.

?

With no opening table and 5000 playouts per move, AntiGo wins against 
gnugo3.7.10 in the neighborhood of 60 and 70%, depending on what is enabled.

?

I optimized my playout policy before I added RAVE. They seem to interact poorly.

?

The following tables are from running UCT for black to move on an empty 9x9 
board and showing the RAVE scores at the root.

Here is the result when using light playouts.

RAVE

?? 1|?? 33?? 43?? 46?? 38?? 40?? 41?? 28?? 33?? 41 
?? 2|?? 37?? 44?? 37?? 35?? 43?? 42?? 37?? 42?? 40 
?? 3|?? 42?? 44?? 41?? 43?? 45?? 48?? 44?? 44?? 39 
?? 4|?? 35?? 45?? 46?? 45?? 43?? 42?? 48?? 45?? 35 
?? 5|?? 36?? 42?? 43?? 45?? 45?? 44?? 40?? 45?? 36 
?? 6|?? 40?? 42?? 40?? 43?? 45?? 43?? 45?? 43?? 37 
?? 7|?? 41?? 47?? 45?? 38?? 42?? 38?? 39?? 40?? 35 
?? 8|?? 32?? 45?? 44?? 45?? 46?? 47?? 45?? 40?? 38 
?? 9|?? 38?? 40?? 38?? 27?? 40?? 38?? 42?? 30?? 37??

It looks noisy, but perfectly reasonable. With more playouts, it looks nicer.

?

Here is the result when using my heavy playouts.

RAVE
?? 1|?? 53?? 44?? 45?? 44?? 45?? 47?? 46?? 43?? 54 
?? 2|?? 43?? 50?? 49?? 48?? 49?? 49?? 50?? 50?? 44 
?? 3|?? 46?? 49?? 49?? 50?? 49?? 49?? 48?? 49?? 46 
?? 4|?? 47?? 48?? 48?? 47?? 49?? 47?? 48?? 49?? 47 
?? 5|?? 45?? 49?? 47?? 49?? 49?? 50?? 47?? 49?? 47 
?? 6|?? 46?? 48?? 48?? 49?? 48?? 48?? 49?? 49?? 45 
?? 7|?? 47?? 50?? 49?? 50?? 49?? 48?? 49?? 50?? 45 
?? 8|?? 47?? 49?? 50?? 50?? 48?? 48?? 49?? 51?? 44 
?? 9|?? 54?? 45?? 47?? 45?? 46?? 46?? 46?? 46?? 54 

It looks like garbage! In fact, it's surprising that it could help at all. 
Progressive widening saves that day. While moves in the corner have higher RAVE 
scores, they have very low rank.

?

Here is the result when using my heavy playouts and CRAVE.


CRAVE
?? 1|?? 35?? 37?? 37?? 28?? 40?? 35?? 40?? 32?? 25 
?? 2|?? 38?? 35?? 44?? 39?? 38?? 49?? 39?? 42?? 34 
?? 3|?? 33?? 38?? 48?? 48?? 51?? 49?? 49?? 39?? 36 
?? 4|?? 41?? 41?? 48?? 50?? 50?? 47?? 49?? 41?? 37 
?? 5|?? 35?? 41?? 51?? 48?? 50?? 47?? 50?? 43?? 31 
?? 6|?? 39?? 40?? 51?? 50?? 50?? 47?? 51?? 46?? 41 
?? 7|?? 36?? 36?? 51?? 51?? 45?? 52?? 50?? 38?? 37 
?? 8|?? 37?? 40?? 45?? 41?? 47?? 37?? 43?? 39?? 32 
?? 9|?? 21?? 27?? 31?? 36?? 38?? 35?? 32?? 35?? 28 


Maybe CRAVE (and perhaps, progressive widening on 9x9) seems more useful to me 
because of compensation for problems other programs don't share.

?

- Dave Hillis





___
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/

Re: [computer-go] Progressive widening vs unpruning

[dhillismail]

For 9x9 games, when I added progressive widening to AntiGo (before I added 
RAVE), it was low hanging fruit. I used my old program Antbot9x9 for the move 
ranking and got a very nice strength increase for very little effort. Then, 
with a bit of tweaking, I got more improvement. RAVE, on the other hand, gives 
me a small improvement, and it comes at the cost of having to fuss with it 
endlessly.



With no opening table and 5000 playouts per move, AntiGo wins against 
gnugo3.7.10 in the neighborhood of 60 and 70%, depending on what is enabled.



I optimized my playout policy before I added RAVE. They seem to interact poorly.



The following tables are from running UCT for black to move on an empty 9x9 
board and showing the RAVE scores at the root.

Here is the result when using light playouts.

RAVE

?? 1|?? 33?? 43?? 46?? 38?? 40?? 41?? 28?? 33?? 41 
?? 2|?? 37?? 44?? 37?? 35?? 43?? 42?? 37?? 42?? 40 
?? 3|?? 42?? 44?? 41?? 43?? 45?? 48?? 44?? 44?? 39 
?? 4|?? 35?? 45?? 46?? 45?? 43?? 42?? 48?? 45?? 35 
?? 5|?? 36?? 42?? 43?? 45?? 45?? 44?? 40?? 45?? 36 
?? 6|?? 40?? 42?? 40?? 43?? 45?? 43?? 45?? 43?? 37 
?? 7|?? 41?? 47?? 45?? 38?? 42?? 38?? 39?? 40?? 35 
?? 8|?? 32?? 45?? 44?? 45?? 46?? 47?? 45?? 40?? 38 
?? 9|?? 38?? 40?? 38?? 27?? 40?? 38?? 42?? 30?? 37??

It looks noisy, but perfectly reasonable. With more playouts, it looks nicer.



Here is the result when using my heavy playouts.

RAVE
?? 1|?? 53?? 44?? 45?? 44?? 45?? 47?? 46?? 43?? 54 
?? 2|?? 43?? 50?? 49?? 48?? 49?? 49?? 50?? 50?? 44 
?? 3|?? 46?? 49?? 49?? 50?? 49?? 49?? 48?? 49?? 46 
?? 4|?? 47?? 48?? 48?? 47?? 49?? 47?? 48?? 49?? 47 
?? 5|?? 45?? 49?? 47?? 49?? 49?? 50?? 47?? 49?? 47 
?? 6|?? 46?? 48?? 48?? 49?? 48?? 48?? 49?? 49?? 45 
?? 7|?? 47?? 50?? 49?? 50?? 49?? 48?? 49?? 50?? 45 
?? 8|?? 47?? 49?? 50?? 50?? 48?? 48?? 49?? 51?? 44 
?? 9|?? 54?? 45?? 47?? 45?? 46?? 46?? 46?? 46?? 54 

It looks like garbage! In fact, it's surprising that it could help at all. 
Progressive widening saves that day. While moves in the corner have higher RAVE 
scores, they have very low rank.



Here is the result when using my heavy playouts and CRAVE.


CRAVE
?? 1|?? 35?? 37?? 37?? 28?? 40?? 35?? 40?? 32?? 25 
?? 2|?? 38?? 35?? 44?? 39?? 38?? 49?? 39?? 42?? 34 
?? 3|?? 33?? 38?? 48?? 48?? 51?? 49?? 49?? 39?? 36 
?? 4|?? 41?? 41?? 48?? 50?? 50?? 47?? 49?? 41?? 37 
?? 5|?? 35?? 41?? 51?? 48?? 50?? 47?? 50?? 43?? 31 
?? 6|?? 39?? 40?? 51?? 50?? 50?? 47?? 51?? 46?? 41 
?? 7|?? 36?? 36?? 51?? 51?? 45?? 52?? 50?? 38?? 37 
?? 8|?? 37?? 40?? 45?? 41?? 47?? 37?? 43?? 39?? 32 
?? 9|?? 21?? 27?? 31?? 36?? 38?? 35?? 32?? 35?? 28 


Maybe CRAVE (and perhaps, progressive widening on 9x9) seems more useful to me 
because of compensation for problems other programs don't share.



- Dave Hillis


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

Re: [computer-go] Progressive widening vs unpruning

[dhillismail]

I'm not sure whether they meant different things when they were first coined, 
but maybe that doesn't matter, and there are two different approaches that 
should be distinguished somehow.



When a node has been visited the required number of times:



1) Use patterns, heuristics, ownership maps from the earlier playouts through 
it, etc. to calculate a score for each move. Then rank them from prettier to 
uglier. At this node, only allow moves within the top N prettiest moves, where 
N grows slowly with the number of subsequent playouts through the node.



2) Calculate the score, as in 1). Initialize the win/loss record for each move 
*as if* many more "prior" playouts had already gone through this node. Prettier 
moves are initialized as if they had a higher proportion of prior?wins. 
Typically, it is the win/loss record for RAVE moves that gets this prior 
adjustment.



They can be combined too.



If the calculations involved?are expensive, then it is important to hold off 
until several playouts have gone through the node. Most nodes don't get visited 
more than once or twice.?If they use something like ownership maps, then, 
naturally, one has to wait until some data has been gathered.

- Dave Hillis


> -Original Message-
> From: computer-go-boun...@computer-go.org [mailto:computer-go-
> boun...@computer-go.org] On Behalf Of Petr Baudis
> Sent: Tuesday, September 29, 2009 7:07 AM
> To: computer-go@computer-go.org
> Subject: [computer-go] Progressive widening vs unpruning
> 
>   Hi!
> 
>   I'm a little unclear on this, so I'd like to make sure I'm not missing
> any important technique - is "progressive widening" and "progressive
> unpruning" synonymous?
> 
>   I have looked both into the pMCTS and the CrazyStone papers and it
> seems that "widening" differs from "unpruning" in that certain number of
> simulations is first made before limiting the number of searches. Which
> of the variants is commonly used? What "speed" of widening works for you
> best?
> 
>   Thanks,
> 
> --
>   Petr "Pasky" Baudis
> A lot of people have my books on their bookshelves.
> That's the problem, they need to read them. -- Don Knuth
> ___
> 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] Generalizing RAVE

[dhillismail]

They?are also known as ngrams. Their use in machine translation might provide 
some inspiration for computer go.



As with many of the ideas mentioned in this discussion, I've played with it 
enough to say it's not low hanging fruit but I?don't necessarily believe?it's a 
dead end. (I am fairly disenchanted with using patterns as context, though.)

-?Dave Hillis


-Original Message-
From: Peter Drake 
To: computer-go 
Sent: Fri, Sep 25, 2009 3:41 pm
Subject: Re: [computer-go] Generalizing RAVE





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] CUDA and GPU Performance

[dhillismail]

Interesting stuff. Thanks for reporting your results.



- Dave Hillis


-Original Message-
From: Christian Nentwich 
To: computer-go 
Sent: Wed, Sep 9, 2009 11:54 am
Subject: [computer-go] CUDA and GPU Performance



I did quite a bit of testing earlier this year on running playout algorithms on 
GPUs. Unfortunately, I am too busy to write up a tech report on it, but I 
finally brought myself to take the time to write this e-mail at least. See 
bottom for conclusions.?
?
For performance testing, I used my CPU board representation, and a CUDA port of 
the same (with adjustments), to test the following algorithm:?
?- Clear the board?
?- Fill the board according to a uniform random policy?
?- Avoid filling eyes, according to simple neighbour check?
?- Avoid simple ko?
?- Count the score and determine the winner?
?
In other words: no tree search is involved, and this is the lightest possible 
playout. The raw numbers are as follows:?
?- CPU Search: 47,000 playouts per CPU core per second, on an Intel 6600 Core-2 
Duo?
?- GPU Search: 170,000 playouts per second, on an NVidia Geforce 285 card?
?
The algorithm running on the GPU is a straight port, with several optimisations 
then made to severely restrict memory access. This means the algorithm is a 
"naive" sort of parallel algorithm, parallel on a per-board level like the CPU 
implementation, rather than per-intersection or some other sort of highly 
parallel algorithm.?
?
Memory access other than shared processor memory carries a severe penalty on 
the GPU. Instead, all threads running on the GPU at any one time have to make 
do with a fast shared memory of 16834 bytes. So:?
?- The board was compressed into a bit board, using 2*21 unsigned ints per 
thread?
?- The count of empty, white and black intersections and the ko position was 
also in shared memory per thread?
?- String/group/block type information was in global memory, as there was no 
way to store it in 16384 bytes?
?
Optimal speed was at 80 threads per block, with 256 blocks. The card had only 
9% processor occupancy, due to the shared memory being almost exhausted. 
However, branch divergence was at only 2%, which is not bad at all - suggesting 
that the form of parallelism may not be a block. This may be because the 
"usual" case of a point either being illegal to play, or a simple play without 
a need to merge or remove strings is by far the most common case.?
?
Conclusions:?
?
I see these results as broadly negative with the current generation of 
technology. Per-board parallelism on a GPU is not worth it compared to the CPU 
speed and the severe drawbacks of working on a GPU (testing is hard, unfamiliar 
environment for most programmers, lots of time to spend on optimisation, etc).?
?
The problems would be severely compounded by trying to integrate any tree 
search, or heavy playouts. Trees are almost impossible to construct on a GPU 
because pointers cannot be transferred from the host to the GPU. They could 
still be represented using arrays, but the random nature of tree access would 
cause huge penalties as it would prevent coalesced memory access.?
?
Highly parallel algorithms (e.g. one thread per intersection) can still be 
investigated, but my (unproven!) intuition is that it is not worth it, as most 
intersections will be idle on any given move, wasting processor occupancy time.?
?
My feeling is that GPUs may have some potential in this area, but possibly in a 
supplementary role such as running additional pattern matching in the 
background, or driving machine learning components.?
?
This e-mail is a bit hurried, so.. questions are welcome!!?
?
Christian?
?
___?
computer-go mailing list?
computer...@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] Mercy rule position

[dhillismail]

Well, it's a trade-off of course, but a?mercy rule threshold of 20?might 
be?pushing it a bit. For 9x9, I typically use 30. If you only invoke the rule 
for external nodes at least N plys away from any internal nodes, then the tree 
will catch some of these problems. 



Some playout policies tend to capture dead strings earlier than others.



- Dave Hillis








-Original Message-
From: Brian Sheppard 
To: computer-go@computer-go.org
Sent: Tue, Aug 18, 2009 4:24 pm
Subject: [computer-go] Mercy rule position



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

The "play and win" is a joke, of course. O has a big, dead,
one-eye group at bottom.

But Pebbles simulations was winning this position at over
84% for O, no matter how long it searched.

When I investigated, it turns out to be because of the "mercy
rule." I had set the threshold at 25% of the board, or 20
stones difference between the sides. Here is a position:

  1 2 3 4 5 6 7 8 9
A O - O O O - O - O 
B O O O O O O - O O 
C O O O - O - O O X 
D X X O O O X O X X 
E - X X O X O O X X 
F X - X X X X X X - 
G X X O O O O O X X 
H X O O O O O O O X 
J O O - X - O O O O 
O "wins" by mercy rule, 45 stones to 24

I can move the threshold, of course, and that "fixes" the
problem. But I am wondering if there is a more reliable approach.

What do you do in your program?

___
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] Dynamic komi at high handicaps

[dhillismail]

I think Terry's suggestion is the best way to test these ideas:



1) Take 2 severely mismatched engines (perhaps 2 versions of the same engine 
but with different numbers of playouts.)

2) Find the fair handicap by playing a sequence of games and adjusting the 
number of handicap stones whenever one side loses N out of M games.

3) Plot the handicap over time-it should converge, more or less.

4) Keeping one engine fixed, adjust the other engine, using dynamic Komi, or 
whatever you think is the best way, and see how much you can improve on the 
handicap.



- Dave Hillis

-Original Message-
From: terry mcintyre 
To: computer-go 
Sent: Wed, Aug 12, 2009 3:42 pm
Subject: Re: [computer-go] Dynamic komi at high handicaps




Ingo suggested something interesting - instead of changing the komi according 
to the move number, or some other fixed schedule, it varies according to the 
estimated winrate. 

It also, implicitly, depends on one's guess of the ability of the opponent. 

An interesting test would be to take an opponent known to be weaker, offer it a 
handicap, and tweak the dynamic komi per Ingo's suggestion. At what handicap 
does the ratio balance at 50:50? Can the number of handicap stones be increased 
with such an adaptive algorithm?

Even better, play against a stronger opponent; can one increase the win rate 
versus strong opponents?

The usual range of computer opponents is fairly narrow. None approach high-dan 
levels on2019x19 boards - yet.

 
Terry McIntyre 


“We hang the petty thieves and appoint the great ones to public office.” -- 
Aesop


From: Brian Sheppard 
To: computer-go@computer-go.org
Sent: Wednesday, August 12, 2009 12:33:13 PM
Subject: [computer-go] Dynamic komi at high handicaps

>The small samples is probably the least of the problems with this.  Do you
>actually believe that you can play games against it and not be subjective
in
>your observations or how you play against it?

These are computer-vs-computer games. Ingo is manually transferring moves
between two computer opponents.

The result does support Ingo's belief that dynamic Komi will help programs
play high handicap games. Due to small sample size it isn't very strong
evidence. But maybe it is enough to induce a programmer who actually plays
in such games to create a more exhaustive test.

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








___
omputer-go mailing list
omputer...@computer-go.org
ttp://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] RAVE problems

[dhillismail]

I'll add some detail. I have 10 features which give me 1024 possible context 
codes, not all of which are realizable. I keep a CAMAF table of approximate 
size 1024*(number of spaces)*colors (1024*81*2 for a 9x9 board). This table 
persists throughout the entire game, with suitable decays of the weights 
between turns. 

After each playout, I update the average score for each move made in the CAMAF 
table. For internal nodes, including the root, I only update the CRAVE values 
for moves that matched the context code of that space at that node. (Internal 
nodes don't need to store any more information than they would with RAVE-though 
storing the context codes can save time).

For an internal node, I have 4 pieces of information for every move considered:
1. win rate
2. Prior value (the humble equivalent of?the domain knowledge in Many Faces)
3. CRAVE
4. CAMAF
The relative usefulness of each piece of information will vary as more playouts 
go through?the node.

For an external node, I have 2 pieces of information for every move considered.
1. The normal move value I was using in my heavy playouts.
2. The CAMAF value
I can make the playouts adaptively learn sekis and other things that otherwise 
tend to get pushed over the horizon.

So, if I ever manage to get this all tuned up so that it actually makes my 
engine stronger instead of weaker, I hope to start playing my bot in 
tournaments again some day.

- Dave Hillis

-Original Message-
From: dhillism...@netscape.net
To: computer-go@computer-go.org
Sent: Fri, Aug 7, 2009 11:49 am
Subject: Re: [computer-go] RAVE problems



> -Original Message-
> From: terry mcintyre 
> To: computer-go 
> Sent: Fri, Aug 7, 2009 10:35 am
> Subject: Re: [computer-go] RAVE problems
> 


> Perhaps the "context" attached to RAVE needs to be more subtle than a static 
> 3x3 pattern - tactical and efficiency > considerations may apply - a move may 
> be good when it defends or kills a group, but bad if it has no effect upon 
> the > status - it may be wasted in such cases.

These are the context codes that I am currently testing. I'm using the terms 
context-AMAF (CAMAF) and context RAVE (CRAVE). 
10 bits:

case 0: printf("context %d: eye creating \n", k); break;
 0: printf("context %d: eye creating \n", k); break;
case 1: printf("context %d: pat \n", k); break;
 1: printf("context %d: pat \n", k); break;
case 2: printf("context %d: self_atari \n", k); break;
 2: printf("context %d: self_atari \n", k); break;
case 3: printf("context %d: capture \n", k); break;
 3: printf("context %d: capture \n", k); break;
case 4: printf("context %d: enemy-atari \n", k); break;
 4: printf("context %d: enemy-atari \n", k); break;
case 5: printf("context %d: ladder-like attack \n", k); break;
 5: printf("context %d: ladder-like attack \n", k); break;
case 6: printf("context %d: rescue \n", k); break;
 6: printf("context %d: rescue \n", k); break;
case 7: printf("context %d: liberties_for_move == 2 \n", k); break;
 7: printf("context %d: liberties_for_move == 2 \n", k); break;
case 8: printf("context %d: running \n", k); break;
 8: printf("context %d: running \n", k); break;
case 9: printf("context %d: squeeze \n", k); break;
 9: printf("context %d: squeeze \n", k); break;
default: printf("context %d: NO CONTEXT \n", k); break;

: printf("context %d: NO CONTEXT \n", k); break;

case 1, matching a pattern, is a binary flag indicating that the move makes any 
"good" 3x3 pattern.
case 4, ladder-like attack, means that it puts a foe group into atari, that 
group couldn't gain a liberty by capturing, and couldn't gain > 2 liberties by 
moving onto its single liberty.
case 8, running, means it gives a friendly group >= 3 liberties where it had 2 
liberties before.
case 9, squeeze, means it reduces a foe group to 2 liberties (but they might be 
eyes...).

If ladder testing is enabled, there is an 11th bit for that result.

I'm certain that this is not the ideal set of features. I'd be very interested 
in what the group thinks they should be.

- Dave Hillis









___
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] RAVE problems

[dhillismail]

> -Original Message-
> From: terry mcintyre 
> To: computer-go 
> Sent: Fri, Aug 7, 2009 10:35 am
> Subject: Re: [computer-go] RAVE problems
> 


> Perhaps the "context" attached to RAVE needs to be more subtle than a static 
> 3x3 pattern - tactical and efficiency > considerations may apply - a move may 
> be good when it defends or kills a group, but bad if it has no effect upon 
> the > status - it may be wasted in such cases.

These are the context codes that I am currently testing. I'm using the terms 
context-AMAF (CAMAF) and context RAVE (CRAVE). 
10 bits:

case 0: printf("context %d: eye creating \n", k); break;
 0: printf("context %d: eye creating \n", k); break;
case 1: printf("context %d: pat \n", k); break;
 1: printf("context %d: pat \n", k); break;
case 2: printf("context %d: self_atari \n", k); break;
 2: printf("context %d: self_atari \n", k); break;
case 3: printf("context %d: capture \n", k); break;
 3: printf("context %d: capture \n", k); break;
case 4: printf("context %d: enemy-atari \n", k); break;
 4: printf("context %d: enemy-atari \n", k); break;
case 5: printf("context %d: ladder-like attack \n", k); break;
 5: printf("context %d: ladder-like attack \n", k); break;
case 6: printf("context %d: rescue \n", k); break;
 6: printf("context %d: rescue \n", k); break;
case 7: printf("context %d: liberties_for_move == 2 \n", k); break;
 7: printf("context %d: liberties_for_move == 2 \n", k); break;
case 8: printf("context %d: running \n", k); break;
 8: printf("context %d: running \n", k); break;
case 9: printf("context %d: squeeze \n", k); break;
 9: printf("context %d: squeeze \n", k); break;
default: printf("context %d: NO CONTEXT \n", k); break;

: printf("context %d: NO CONTEXT \n", k); break;

case 1, matching a pattern, is a binary flag indicating that the move makes any 
"good" 3x3 pattern.
case 4, ladder-like attack, means that it puts a foe group into atari, that 
group couldn't gain a liberty by capturing, and couldn't gain > 2 liberties by 
moving onto its single liberty.
case 8, running, means it gives a friendly group >= 3 liberties where it had 2 
liberties before.
case 9, squeeze, means it reduces a foe group to 2 liberties (but they might be 
eyes...).

If ladder testing is enabled, there is an 11th bit for that result.

I'm certain that this is not the ideal set of features. I'd be very interested 
in what the group thinks they should be.

- Dave Hillis




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

Re: [computer-go] Slightly OT: Sound in CGoban

[dhillismail]

There are some relevant discussions in the computer go forum at 
http://www.godiscussions.com

-Original Message-
From: Alain Baeckeroot 
To: computer-go 
Sent: Thu, Jul 16, 2009 5:08 pm
Subject: Re: [computer-go] Slightly OT: Sound in CGoban



Le 16/07/2009 à 22:28, Peter Drake a écrit :
 I've recently been getting an odd distorted buzzing with every sound
 played by CGoban3, the KGS client. This doesn't happen with other
 applications, so I don't think it's a hardware or driver problem.

 Has anyone else encountered this?

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




you should mailto:ad...@gokgs.com to report this.
tw, if you can advocate fo a public bug tracker it would be a great
mprovement for the community :)
Alain.

__
omputer-go mailing list
omputer...@computer-go.org
ttp://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: Dynamic komi in commercial programs

[dhillismail]

There are 3 commonly cited problems and 4 commonly proposed remedies.
Problems:
1) Human games remain interesting, even after the winner is clear, because the 
players just naturally switch to playing for maximum territory. Wouldn't MCTS 
bots be more fun to play against if they did that too?
2) Sometimes a bot has a win by a small margin, but thinks it's a win by a big 
margin (because it is misreading a seki or whatever). Consequently, the bot 
neglects to defend the space that matters and loses after all.
3) For a big enough handicap, the bot plays random, ugly looking moves in the 
beginning. Can't that be improved?
Remedies:
a) Play for maximum territory sometimes.
b) Fake the Komi sometimes.
c) Unbalance the playout strength sometimes.
d) Worry about more important things.
The vagueness in the "sometimes" part doesn't help in deciding which remedy is 
best for which problem.

Looking at the handicap problem alone, how can I pick the best remedy and 
justify my decision? Maybe I could take my engine at a reasonable time setting 
and experiment with all the remedies to try to find the highest handicap I can 
give Wally and still win 50% of the games.

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

Re: [computer-go] Scoring - step function or sigmoid function?

[dhillismail]

Since this topic has resurfaced, I'll mention again the alternative strategy of 
using unbalanced playout rules to compensate for high handicaps. As Don pointed 
out, the existence of a high handicap *should* indicate that black is more 
likely to make mistakes. This is simple to model, assuming heavy playouts, by 
adding a bit more randomness to black moves (only outside the tree). 


?Personally, I'm inclined to believe that unbalancing the playouts should be 
superior to adjusting the Komi. When black's external playout moves are more 
random, white will be more likely to win unsettled areas, but settled areas 
will tend to stay settled. Inside the tree, we want white searching for 
complicated board positions and black searching for simpler ones. 


In my program, it was easy to find an appropriate adjustment for different 
handicaps through offline testing. From a purely subjective viewpoint, I found 
that the resulting opening moves looked much more reasonable. People who have 
tried dynamically adjusting the Komi, report similar, subjective, success. 
There might not be any practical difference. 
It's not obvious to me what a fair test would be.


I'm convinced that either method is worth doing in the opening for very high 
handicaps. Just looking at some examples is pretty persuasive. I'm more 
doubtful about trying them late in an even game when one side has pulled ahead.

- Dave Hillis


-Original Message-
From: Don Dailey 
To: computer-go 
Sent: Wed, Jul 8, 2009 8:49 am
Subject: Re: [computer-go] Scoring - step function or sigmoid function?






On Mon, Jun 8, 2009 at 7:35 AM, Stefan Kaitschick 
 wrote:





Thinking about why... In a given board position moves can be grouped
into sets: the set of correct moves, the set of 1pt mistakes, 2pt
mistakes, etc. Let's assume each side has roughly the same number of
moves each in each of these groupings.

If black is winning by 0.5pt with perfect play, then mistakes by each
side balance out and we get a winning percentage of just over 50%. If he
is winning by 1.5pt then he has breathing space and can make an extra
mistake. Or in other words, at a certain move he can play any of the
moves in the "correct moves" set, or any of the moves in the "1pt
mistakes" set, and still win. So he wins more of the playouts. Say 55%.
If he is winning by 2.5pts then he can make one 2pt mistakes or two 1pt
mistakes (more than the opponent) and still win, so he wins more
playouts, 60% perhaps. And so on.

My conclusion was that the winning percentage is more than just an
estimate of how likely the player is to win. It is in fact a crude
estimator of the final score.

Going back to your original comment, when choosing between move A that
leads to a 0.5pt win, and move B that leads to a 100pt win, you should
be seeing move B has a higher winning percentage.

Darren




Point well taken.Winning positions tend to cluster and critical swing moves are 
rare, statistically speaking.
If the position is more or less evenly balanced, the step function might 
allready be very close to optimal because of this.
But I would like to bring up a well known mc quirk: In handicap positions, or 
after one side scored a big success in an even game,
bots play badly with both sides, until the position becomes closer again. The 
problem here is that every move is a win (or every move is a loss).
On 9*9, its possible to beat a bot, giving it 2 stones, even when it's a close 
contest on even with komi. All it needs is a single bot missread at the moment 
the position becomes close(which it will, because the bot will be "lazy" until 
that point).


I would say it's foolish to purposely give the bot 2 stones in order to hope 
for a misread unless you are expert on that particular behaviour and can 
predict just where and why it will go wrong.? 

?


So it would be desirable for the bot to make keeping the score advantage large 
an auxiliary goal.
This has been tried ofcourse, but without much success sofar.
And it seems that the main reason is that tinkering with the scoring function 
to achive this, tends to worsen play in competitive situations.


This is easy to understand - it's because maximizing your winning chances is a 
better strategy than maximizing how many points you take.?? One is the actual 
goal of the game (to win) and the other is a different goal which is not as 
highly corelated as we like to think it is.?? 
?


I have an alternative suggestion: In handicap games, introduce a virtual komi, 
that gets reduced to 0 as the game progresses.
This would work for the bot on both sides: If the bot has b it will make less 
lazy plays, if it has w, it will be less maniacal.
For example, in a 4 stone 19*19 game, if the real starting advantage is about 
45 points, the bot could introduce an internal komi of about 30-35.
The bot should be optimistic with b and pessimistic with w, but not to the 
point that every move evaluates to the same value, and move selection becomes a 
toss-up. 

Re: [computer-go] 1x1 patterns?!

[dhillismail]

Sure, that would be a place to start. I also did some testing with just the 
number of pseudo-liberties at the position. That was pretty easy to code up. 
And I did have some limited success using 3x3 patterns-just not enough to 
justify the nuisance of carrying it along in my code.

There are quite a lot of choices involved. Testing them looks like the 
bottleneck to me.

- Dave Hillis

-Original Message-
From: Michael Williams 
To: computer-go 
Sent: Mon, Jun 22, 2009 4:28 pm
Subject: Re: [computer-go] 1x1 patterns?!


Why not start with the 5-vertex cross pattern? Going from 1x1 to 3x3 is a huge 
jump in complexity and debugability. With 5-vertex patterns, you can enumerate 
the patterns on paper (there are around 3^4 == 81 of them, ignoring symmetries) 
to sanity-check the details and see if the general idea works at all. There are 
too many to enumerate with 9-vertex 3x3 patterns (around 3^8 == 6561, ignoring 
symmetries).?
?
dhillism...@netscape.net wrote:?
> Yes. I think it's a good idea, but the devil is in the details. I've > become 
> pretty disenchanted with trying to use 3x3 or 5x5 patterns. > Currently, I 
> have about 300 1x1 patterns (I call them context codes) > that I'm playing 
> around with.?
> > You can also do the same for RAVE without needing any more memory. You > 
> > only adjust the RAVE values, at a node, after filtering out moves, in > the 
> > playouts, that don't match the context/pattern for that position at > that 
> > node.?
> > - Dave Hillis?
> > > -Original Message-?
> From: Michael Williams ?
> To: computer-go ?
> Sent: Mon, Jun 22, 2009 3:02 pm?
> Subject: Re: [computer-go] 1x1 patterns?!?
> > I had never considered using AMAF with larger pattern. That's an > 
> > interesting idea. Perhaps a 5-vertex cross-shaped pattern or a 3x3 > 
> > pattern. Has anyone tried this? > > Magnus Persson wrote: > > Probably 1x1 
> > patterns implies that different priorities are assigned > to > the absolute 
> > position of empty moves. AMAF can be seen this way. > AMAF > learns 
> > statistics of 1x1 patterns if the move is played in the > playout > but 
> > ignores all information surrounding the move at the time > it is > played. 
> > Another example would be to have lower priorities for > the moves > at the 
> > first and second line. > > > -Magnus > > > Quoting Peter Drake 
> > mailto:dr...@lclark.edu>>: > > >> I've seen reference in 
> > some papers to 1x1 patterns. What does that > even > >> mean? A point is 
> > either black, white, or vacant, and it's illegal to > >> play there unless 
> > it's vacant. > > > ___ > > 
> > computer-go mailing list > > computer...@computer-g
 o.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/ > > 
?
> Save energy, paper and money -- *get the Green Toolbar > 
> .*?
> > > ?
> > ___?
> computer-go mailing list?
> computer...@computer-go.org?
> http://www.computer-go.org/mailman/listinfo/computer-go/?
?
___?
computer-go mailing list?
computer...@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] 1x1 patterns?!

[dhillismail]

In my case, yes.

That is a correct interpretation for the context codes in my program, which are 
equivalent to some of the suggestions for the meaning of "1x1 pattern." (But I 
don't call them "1x1 patterns."?I also find that term confusing. I don't 
remember seeing it before.)

- Dave Hillis


-Original Message-
From: Peter Drake 
To: computer-go 
Sent: Mon, Jun 22, 2009 4:21 pm
Subject: Re: [computer-go] 1x1 patterns?!





On Jun 22, 2009, at 1:18 PM, dhillism...@netscape.net wrote:


Yes. I think it's a good idea, but the devil is in the details. I've become 
pretty disenchanted with trying to use 3x3 or 5x5 patterns. Currently, I have 
about 300 1x1 patterns (I call them context codes) that I'm playing around with.





So, at the risk of sounding pedantic, these patterns aren't REALLY 1x1 -- they 
take into account other information, such as the number of liberties a stone 
has. (Is this a correct interpretation?)











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] 1x1 patterns?!

[dhillismail]

Yes. I think it's a good idea, but the devil is in the details. I've become 
pretty disenchanted with trying to use 3x3 or 5x5 patterns. Currently, I have 
about 300 1x1 patterns (I call them context codes) that I'm playing around with.

You can also do the same for RAVE without needing any more memory. You only 
adjust the RAVE values, at a node, after filtering out moves, in the playouts, 
that don't match the context/pattern for that position at that node.

- Dave Hillis


-Original Message-
From: Michael Williams 
To: computer-go 
Sent: Mon, Jun 22, 2009 3:02 pm
Subject: Re: [computer-go] 1x1 patterns?!


I had never considered using AMAF with larger pattern. That's an interesting 
idea. Perhaps a 5-vertex cross-shaped pattern or a 3x3 pattern. Has anyone 
tried this??
?
Magnus Persson wrote:?
> Probably 1x1 patterns implies that different priorities are assigned to > the 
> absolute position of empty moves. AMAF can be seen this way. AMAF > learns 
> statistics of 1x1 patterns if the move is played in the playout > but ignores 
> all information surrounding the move at the time it is > played. Another 
> example would be to have lower priorities for the moves > at the first and 
> second line.?
> > -Magnus?
> > Quoting Peter Drake :?
> >> I've seen reference in some papers to 1x1 patterns. What does that even?
>> mean? A point is either black, white, or vacant, and it's illegal to?
>> play there unless it's vacant.?
> > ___?
> computer-go mailing list?
> computer...@computer-go.org?
> http://www.computer-go.org/mailman/listinfo/computer-go/?
> ?
___?
computer-go mailing list?
computer...@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] Tweak to MCTS selection criterion

[dhillismail]

Looking again, I was confusing a followup post with the original description of 
the pebbles rule. I have not tested this exact rule. Sorry for my confusion.

- Dave Hillis


-Original Message-
From: dhillism...@netscape.net
To: computer-go@computer-go.org
Sent: Sun, 7 Jun 2009 9:39 pm
Subject: Re: [computer-go] Tweak to MCTS selection criterion


The policy is only risk free on a per-move basis. For the game as a whole, 
using more time on one move means there will be less time available for later 
moves. Back when I tested this rule in my own program, I didn't see any 
significant difference in strength. YMMV.

- Dave Hillis

-Original Message-
From: Brian Sheppard 
To: computer-go@computer-go.org
Sent: Sun, 7 Jun 2009 6:05 pm
Subject: [computer-go] Tweak to MCTS selection criterion



> check if overtaking the leading move is mathematically impossible?

Yes. Pebbles does this.

Please note that the discussion has veered into time control policy,
which is not the subject of the original post.

The original post discusses move selection policy: when your program
stops, for whatever reason, which move should it select? Pebbles' policy
is to select the move that has the most wins, rather than the most trials.

Pebbles policy is a risk-free improvement over the standard policy
of selecting the move that has the most trials.

Brian

___
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] Tweak to MCTS selection criterion

[dhillismail]

The policy is only risk free on a per-move basis. For the game as a whole, 
using more time on one move means there will be less time available for later 
moves. Back when I tested this rule in my own program, I didn't see any 
significant difference in strength. YMMV.

- Dave Hillis

-Original Message-
From: Brian Sheppard 
To: computer-go@computer-go.org
Sent: Sun, 7 Jun 2009 6:05 pm
Subject: [computer-go] Tweak to MCTS selection criterion



> check if overtaking the leading move is mathematically impossible?

Yes. Pebbles does this.

Please note that the discussion has veered into time control policy,
which is not the subject of the original post.

The original post discusses move selection policy: when your program
stops, for whatever reason, which move should it select? Pebbles' policy
is to select the move that has the most wins, rather than the most trials.

Pebbles policy is a risk-free improvement over the standard policy
of selecting the move that has the most trials.

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] Tweak to MCTS selection criterion

[dhillismail]

> I had the early stop rule and didn't know if anyone else had thought of it.?? 
> But I never considered the pebbles rule, 
> which somewhat conflicts with the early stop rule.?? But as I layed out above 
> I think you could do both.

> This is probably one of those things that adds a little bit but is difficult 
> to measure.

> - Don

Hmm. Well, the way I remember it, I first heard the pebbles rule idea from you, 
Don. I checked my code to see if I could pinpoint a date, but no luck. This was 
a while ago. I could be wrong.

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

Re: [computer-go] Tweak to MCTS selection criterion

[dhillismail]

> -Original Message-
> From: Don Dailey 
> To: computer-go 
> Sent: Sat, 6 Jun 2009 5:59 pm
> Subject: Re: [computer-go] Tweak to MCTS selection criterion

> 2009/6/6 

> I think this is?one of those?design decisions that nobody takes on faith. We 
> all wind up testing it both ways and in > various combinations.
> 
> An additional advantage of using the number of visits is that branches at the 
> root become mathematically 
> eliminated and can be pruned away. It often also allows the search to be 
> stopped early. It can save a lot of time 
> for forced moves.


> Let me see if I understand what you are saying here.??? 

> If you have set a goal time for thinking of 10 seconds,? and let's say 6 
> seconds have progressed,?? then it might be 
> possible to stop the search early if you do the math and see that it's not 
> possible for any other move to have more 
> visits given an additional 4 seconds??? 

> So when there is a position that has only a single clearly best move, perhaps 
> a capture that cannot wait or a 
> necessary atari defense,? then you can probably save as much (or close to) as 
> half the thinking time on that move.?
>??? Is this correct?? 

Yes. (Although, in practice, it's lucky to shave a third off the time.) There 
is an additional, hard to qualify, benefit. Long before the winning move has it 
locked up, some moves may be mathematically eliminated, so any playouts through 
them would be totally wasted (assuming we can ignore RAVE).

> So if this understanding is correct, then it still makes sense to do the 
> "pebbles" test at this point and check to see 
> if another move has a higher score before stopping the search.??? If the move 
> really is forced and necessary,? then
?> the answer will be no and you can stop early.? If there is a move that 
currently appears better but with a "too small"
> sample,? then it seems foolish to stop early.??? If the move is a result of 
> just a few lucky playouts, then it will quickly
> be revealed and you can still stop early.

Sounds plausible... But I've tested this. You've tested this. Any benefit seems 
to be pretty hard to measure.

- Dave Hillis





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

Re: [computer-go] Tweak to MCTS selection criterion

[dhillismail]

I think this is?one of those?design decisions that nobody takes on faith. We 
all wind up testing it both ways and in various combinations.

An additional advantage of using the number of visits is that branches at the 
root become mathematically eliminated and can be pruned away. It often also 
allows the search to be stopped early. It can save a lot of time for forced 
moves.

- Dave Hillis


-Original Message-
From: Michael Williams 
To: computer-go 
Sent: Sat, 6 Jun 2009 5:07 pm
Subject: Re: [computer-go] Tweak to MCTS selection criterion


Another strategy to be considered is to not allow the thinking to cease until 
the maximum win rate and the maximum visit count agree on the same move. 
Obviously this requires some extra code to make sure you don't lose on time, 
etc.?
?
Brian Sheppard wrote:?
> When a UCT search is completed, the usual selection criterion is?
> "choose the move that has the most trials." This is more stable?
> than choosing the move that has the highest percentage of wins,?
> since it is possible to have an unreliably high percentage if the?
> number of trials is small.?
> > I have a small tweak to that criterion. Pebbles uses "choose the?
> move that has the most wins." This rule selects the same move as?
> the conventional criterion in almost every case. The reason why?
> Pebbles' rule is superior is revealed in the case where the moves?
> differ.?
> > When Pebbles chooses a different move than the conventional criterion,?
> it is because Pebbles move has more wins in fewer trials. When that?
> happens, Pebbles move would inevitably become the move with the most?
> trials if searching were to continue. So there is actually no downside.?
> Of course, the upside is minor, too.?
> > For validation, Pebbles has been using both strategies on CGOS games.?
> At present, the conventional selection strategy has won 341/498 = 68.47%.?
> Pebbles strategy has won 415/583 = 71.18%. This isn't statistically?
> conclusive or anything (0.7 standard deviations; we would need 4 to 8?
> times as many trials for strong statistical evidence). But Pebbles'?
> strategy should be better by a small amount, and it has been, so I?
> present it to you with confidence.?
> > Best,?
> Brian?
> > ___?
> computer-go mailing list?
> computer...@computer-go.org?
> http://www.computer-go.org/mailman/listinfo/computer-go/?
> ?
___?
computer-go mailing list?
computer...@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] Negative result on using MC as a predictor

[dhillismail]

I took a look at this once, testing?how well ownership maps predicted?the moves 
chosen in a large set of pro games. Ownership maps have some tricky artifacts, 
especially for forced moves. 

Consider a position, with white to move,?where black's previous move put a 
white group in atari, and white has one rescuing move. If you run a bunch of 
heavy playouts, the rescuing move will (almost) always be played and white will 
have a very strong ownership percentage for that space... seemingly indicating 
low urgency for white to move there. A map from light playouts might seem to 
show that the move would be hopeless. What happens for an internal node depends 
on the details of progressive widening, etc..

If you?generate an?ownership map using light playouts and compare it with one 
using heavy playouts, the heavy one will usually show spaces as being more 
strongly owned by one color or the other. The light maps will look fuzzier; the 
heavy maps will look crisper. Maps for internal nodes, using UCT, are crisper 
still. You need to pick your threshold with care.

- Dave Hillis

-Original Message-
From: Brian Sheppard 
To: computer-go@computer-go.org
Sent: Fri, 5 Jun 2009 9:39 am
Subject: [computer-go] Negative result on using MC as a predictor



In a paper published a while ago, Remi Coulom showed that 64 MC trials
(i.e., just random, no tree) was a useful predictor of move quality.

In particular, Remi counted how often each point ended up in possession
of the side to move. He then measured the probability of being the best
move as a function of the frequency of possession. Remi found that if
the possession frequency was around 1/3 then the move was most likely
to be best, with decreasing probabilities elsewhere.

I have been trying to extract more information from each trial, since
it seems to me that we are discarding useful information when we use
only the result of a trial. So I tried to implement Remi's idea in a UCT
program.

This is very different from Remi's situation, in which the MC trials are
done before the predictor is used in a tree search. Here, we will have
a tree search going on concurrently with collecting data about point
ownership.

My implementation used the first N trials of each UCT node to collect
point ownership information. After the first M trials, it would use that
information to bias the RAVE statistics. That is, in the selectBest
routine I had an expression like this:

   for all moves {
  // Get the observed RAVE values:
  nRAVE = RAVETrials[move];
  wRAVE = RAVEWins[move];

  // Dynamically adjust according to point ownership:
  if (trialCount < M) {
   ; // Do nothing.
  }
  else if (Ownership[move] < 0.125) {
   nRAVE += ownershipTrialsParams[0];
   wRAVE += ownershipWinsParams[0];
  }
  else if (Ownership[move] < 0.250) {
   nRAVE += ownershipTrialsParams[1];
   wRAVE += ownershipWinsParams[1];
  }
  else if (Ownership[move] < 0.375) {
   nRAVE += ownershipTrialsParams[2];
   wRAVE += ownershipWinsParams[2];
  }
  else if (Ownership[move] < 0.500) {
   nRAVE += ownershipTrialsParams[3];
   wRAVE += ownershipWinsParams[3];
  }
  else if (Ownership[move] < 0.625) {
   nRAVE += owner
shipTrialsParams[4];
   wRAVE += ownershipWinsParams[4];
  }
  else if (Ownership[move] < 0.750) {
   nRAVE += ownershipTrialsParams[5];
   wRAVE += ownershipWinsParams[5];
  }
  else if (Ownership[move] < 0.875) {
   nRAVE += ownershipTrialsParams[6];
   wRAVE += ownershipWinsParams[6];
  }
  else {
   nRAVE += ownershipTrialsParams[7];
   wRAVE += ownershipWinsParams[7];
  }

  // Now use nRAVE and wRAVE to order the moves for expansion
   }

The bottom line is that the result was negative. In the test period, Pebbles
won 69% (724 out of 1039) of CGOS games when not using this feature and
less than 59% when using this feature. I tried a few parameter settings.
Far from exhaustive, but mostly in line with Remi's paper.
The best parameter settings showed 59% (110 out of 184, which is 2.4
standard deviations lower). But maybe you can learn from my mistakes
and figure out how to make it work.

I have no idea why this implementation doesn't work. Maybe RAVE does a
good job already of determining where to play, so ownership information
is redundant. Maybe different parameter settings would work. Maybe just
overhead (but I doubt that; the overhead wouldn't account for such a
significant drop).

Anyway, if you try something like this, please let me know how it works out.
Or if you have other ideas about how to extract more information from
trials.

Best,
Brian

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

___

Re: [computer-go] Congratulations to Steenvreter!

[dhillismail]

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...@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] Published source for mercy rule?

[dhillismail]

Bruno Bouzy gives it credit for a 1% strength improvement in the tutorial:
"Old-fashioned Computer Go vs Monte-Carlo Go"
http://www.math-info.univ-paris5.fr/~bouzy/publications/CIG07-tutorial-1avril2007.pdf
(It's a pretty good read in general, btw.)

The Mercy rule interacts with ownership maps and RAVE in ways that are a bit of 
a nuisance.

- Dave Hillis


-Original Message-
From: Don Dailey 
To: computer-go 
Sent: Sun, 1 Mar 2009 1:51 pm
Subject: Re: [computer-go] Published source for mercy rule?



Has anyone done a good analysis on the value of the mercy rule?   It is
 major or minor speedup?   And how does it affect the quality of the
earch?   Is it more useful with bigger board sizes?  
It seems like I remember seeing that many believed it to be a very minor
mprovement if any,  but I'm curious if that is the current
nderstanding (as I have not experimented with it myself.)
- Don

On Sun, 2009-03-01 at 18:28 +0100, Łukasz Lew wrote:
 mercy rule in libego:
 
http://github.com/lukaszlew/libego/blob/77b4dd4e035e4b44c17204557c9930a52e10e0c0/ego/playout.h
 line 55.
 
 Regards,
 Łukasz Lew
 
 On Fri, Feb 27, 2009 at 01:00, Seth Pellegrino  wrote:
 > Hello list,
 >
 > I've managed to track the idea of a mercy rule in monte-carlo playouts back
 > to a mail sent to this list by David Hillis:
 >
 > http://computer-go.org/pipermail/computer-go/2006-December/007478.html
 >
 > I'm currently putting the finishing touches on
 a paper which includes this
 > idea, and I was wondering if anyone knew of any published sources where I
 > could cite the idea?
 >
 > Thanks,
 >
 > Seth Pellegrino
 >
 > ___
 > 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/
___
omputer-go mailing list
omputer...@computer-go.org
ttp://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] Published source for mercy rule?

[dhillismail]

I believe you've traced it back as far as it goes. I certainly haven't 
published it. Sometimes comp-go papers cite this list as a catchall source for 
the not-previously-published lore that's been posted here. I don't know of any 
better way to handle things like this.

- Dave Hillis

-Original Message-
From: Seth Pellegrino 
To: computer-go@computer-go.org
Sent: Thu, 26 Feb 2009 7:00 pm
Subject: [computer-go] Published source for mercy rule?


Hello list,?
?
I've managed to track the idea of a mercy rule in monte-carlo playouts back to 
a mail sent to this list by David Hillis:?
?
http://computer-go.org/pipermail/computer-go/2006-December/007478.html?
?
I'm currently putting the finishing touches on a paper which includes this 
idea, and I was wondering if anyone knew of any published sources where I could 
cite the idea??
?
Thanks,?
?
Seth Pellegrino?
?
___?
computer-go mailing list?
computer...@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] Presentation of my personnal project : evolution of an artificial go player through random mutation and natural selection

[dhillismail]

Ernest,

Fun stuff! I have a co-evolved neural net that used to play on KGS as 
“Antbot9x9”. I use the same net in the progressive widening part of my MCTS 
engine. I would guess that many people experiment along these lines but they 
rarely report results.

 

Here are some suggestions that might be relevant:

- If you test your approach on smaller board sizes you can get results 
orders of magnitude faster. 7x7 would be a good starting size. (If you use 5x5, 
make sure your super-ko handling is rock solid first.)

- Take the strongest net at every generation and benchmark it against 
one or more computer opponents to measure progress over time. Suitable computer 
opponents would be light playouts (random), heavy playouts (a bit tougher), 
Wally (there’s nothing quite like getting trounced by the infamous Wally to 
goad one into a new burst of creativity), and Gnugo.  When you have a net you 
like, it can play against other bots online at CGOS and get a ranking.

- Use a hierarchical architecture, or weight sharing or something to 
let your GA learn general principles that apply everywhere on the board. A 
self-atari move on one spot is going to be roughly as bad as on any other spot. 
You probably don’t want your GA to have to learn not to move into self-atari 
independently for every space on the board.

- Use the =E
2mercy rule” to end games early when one color has an overwhelming majority of 
the stones on the board.

- Feed the net some simple features. To play well, it will have to be 
able to tell if a move would be self-atari, a rescue from atari, a capturing 
move,… Unless you think it might not need these after all, do you really want 
to wait for the net to learn things that are trivial to pre-calculate? You are 
probably reluctant to feed it any features at all. As a motivating exercise, 
you could try having the GA evolve a net to calculate one of those features 
directly.

- GA application papers tend to convey the sense that the author threw 
a problem over a wall and the GA caught it and solved it for him. Really, 
there’s a lot of art to it and a lot of interactivity. Fortunately, that’s the 
fun part.
- Dave Hillis


-Original Message-
From: Ernest Galbrun 
To: computer-go 
Sent: Tue, 24 Feb 2009 7:28 am
Subject: Re: [computer-go] Presentation of my personnal project : evolution of 
an artificial go player through random mutation and natural selection






I read a paper a couple years ago about a genetic algorithm to evolve


a neural network for Go playing (SANE I think it was called?).  The
network would output a value from 0 to 1 for each board location, and
the location that had the highest output value was playe
d as the next
move.  I had an idea that the outputs could be sorted to get the X
"best" moves, and that that set of moves could be used to direct a
minimax or monte carlo search.  I haven't had the chance to prototype
this, but I think it would be an interesting and possibly effective
way to combine neural networks with the current Go algorithms.

Colin

 

This was a great achievement indeed, but although it might seem dumb, my 
approach here is to be as ignorant as I can (not very difficult given my 
knowledge in AI) of subtile and clever ways to make my players evolve. The SANE 
algorithm has proven to be very powerful, but it needs some assumptions to be 
true. As "probably true" this assumtpions are, I prefer to have none and look 
at a really random evolution pattern.




Ernest.




___
omputer-go mailing list
omputer...@computer-go.org
ttp://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] static evaluators for tree search

[dhillismail]

First, my code is in no shape for sharing.

Some time back, I experimented with training a neural net to predict ownership 
maps from 9x9 board positions. I wasn't looking for a static evaluator; I 
wanted something to speed up my MCTS bot. I used my own engine to generate 
ownership maps for training and testing sets from various board positions. I 
won't list all the things I tried. I will say that I am disenchanted with the 
idea of using a net to estimate ownership maps. 

Perhaps the biggest problem came from an unexpected quarter. MC playouts are 
very fast and neural nets are a bit slow. (I am talking about the forward pass, 
not the off-line training.) In the short time it took to feed a board position 
to my net and get the results, I could have run enough MC playouts to obtain a 
better estimate of the ownership map. :/

===
(Ha! While I was writing this, Darren beat me to it.)
===

If I were to pick this up again, this is the next thing I would try. Instead of 
using the net to estimate the ownership map, I would try to use it to predict 
the bias in the map generated by the MC playouts. MC playouts rather 
consistantly underestimate the safety of lightweight shapes, screw up ladders, 
etc.. 

To train it, I would take the ownership map from treeless MC playouts, and as 
my oracle, I would use my best-so-far MCTS to produce the desired map. The net 
would try to learn the difference between the two. Optimistically, I would 
incorporate the network into the best-so-far MCTS and bootstrap the system.

Of course, I've swept some stuff under the rug here, but maybe it will trigger 
an idea.

- Dave Hillis


-Original Message-
From: George Dahl 
To: computer-go 
Sent: Tue, 17 Feb 2009 12:27 pm
Subject: [computer-go] static evaluators for tree search



At the moment I (and another member of my group) are doing research on
applying machine learning to constructing a static evaluator for Go
positions (generally by predicting the final ownership of each point
on the board and then using this to estimate a probability of
winning).  We are looking for someone who might be willing to help us
build a decent tree search bot that can have its static evaluator
easily swapped out so we can create systems that actually play over
GTP.  As much as we try to find quantitative measures for how well our
static evaluators work, the only real test is to build them into a
bot.

Also, if anyone knows of an open source simple tree search bot
(perhaps alpha-beta or something almost chess like) for Go, we might
be able to modify it ourselves.

The expertise of my colleague and I is in machine learning, not in
tree search (although if worst comes to worst I will write my own
simple alpha-beta searcher).  We would be eager to work together with
someone on this list to try and create a competitive bot.  We might at
some point create a randomized evaluator that returns win or loss
nondeterministically for a position instead of a deterministic score,
so an ideal collaborator would also have some experience with
implementing monte carlo tree search (we could replace playouts with
our evaluator to some extent perhaps).  But more important is
traditional, chess-like searching algorithms.

If anyone is interested in working with us on this, please let me
know!  We have a prototype static evaluator complete that is producing
sane board ownership maps, but we will hopefully have many even better
ones soon.

- George
___
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] Black/White winning rates with random playout?

[dhillismail]

You can't just look at the mean. If you take a histogram and look at the 
distribution of scores, you'll see a Gaussian-like bump in the middle, but 
also huge tails where only one color was left. You can calculate the histogram 
once and then use it to derive the win rate for different Komis. (That would 
save time.) But you can't use the mean for that purpose.

- Dave Hillis


-Original Message-
From: Nuno Milheiro 
To: computer-go 
Sent: Thu, 8 Jan 2009 2:14 pm
Subject: Re: [computer-go] Black/White winning rates with random playout?


Given random play, komi value does not change play, so we could see what is the 
mean score (no komi) instead of playing games at different komis. But in this 
case we should not see those 2 exceptions.
Or else I'm wrong somewhere on my assumption.


2009/1/8 Rémi Coulom 


Isaac Deutsch wrote:

I ran some tests with 500k games each and came to this result:

with komi 0.5, white has 47.5 winn. perc.
with komi 1.5, white has 50.7 winn. perc.
with komi 2.5, white has 50.9 winn. perc.
with komi 3.5, white has 54.0 winn. perc.
with komi 4.5, white has 53.8 winn. perc.  <-- ?
with komi 5.5, white has 57.3 winn. perc.
with komi 6.5, white has 57.1 winn. perc. <- ?
with komi 7.5, white has 60.3 winn. perc.
with komi 8.5, white has 60.3 winn. perc.
with komi 9.5, white has 63.1 winn. perc.
with komi 10.5, white has 63.1 winn. perc.
with komi 1
1.5, white has 65.9 winn. perc.

The percentage is mostly according to komi, with 2 exceptions.
 



If your playouts don't score seki, then komi = 2n + 1.5 and komi = 2n + 2.5 are 
equivalent. So you should get the same winn. perc. for 1.5 and 2.5. Ditto for 
3.5 and 4.5, etc.

That's because White Score + Black Score = 81, so Black Score - WhiteScore = 81 
- 2 * WhiteScore is always odd.

Rémi 





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







-- 
Nuno Milheiro

-BEGIN GEEK CODE BLOCK-
Version: 3.12
GCM d+>! s: a C ULAS$
P+ L+++$ E+++ W+ N o? K-> w--$ O? M-
V-- PS+++ PE- Y+ PGP++ t 5? X+ !R
tv- b++>+++ DI++ D+ G+ e>+++ h
r+++ y>*
--END GEEK CODE BLOCK--



___
omputer-go mailing list
omputer...@computer-go.org
ttp://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] Black/White winning rates with random playout?

[dhillismail]

Sounds about right. Looking at my notes, I have 57% wins for white using 
similar playout?rules.

- Dave Hillis

-Original Message-
From: Don Dailey 
To: computer-go 
Sent: Thu, 8 Jan 2009 1:38 pm
Subject: Re: [computer-go] Black/White winning rates with random playout?



On Thu, 2009-01-08 at 19:27 +0100, i...@gmx.ch wrote:
> Hi,
> 
> What's an usual winning rate for black/white from an empty 9x9 board, black 
playing first, 7.5 komi? I play 50k games when starting my program, and I 
usually get around 60% winning rate for white. This seems rather high to me, 
and 
I suspect a bug somewhere. Do you have any data I could compare with? I use 
random playouts, only moves that fill eyes are pruned.
> 
> Cheers, ibd

I don't know the answer, but it's not too surprising - with random play
the komi should be something like 2 or 3,  so white with 7.5 komi has a
pretty good advantage. This advantage disappears (or almost
disappears) if the games are well played, but in your case they are
not. 

- 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] 3-4-5 rule

[dhillismail]

> -Original Message-
> From: Heikki Levanto 
> To: dailey@gmail.com; computer-go 
> Sent: Tue, 30 Dec 2008 5:22 pm
> Subject: Re: [computer-go] 3-4-5 rule
> 


> On Tue, Dec 30, 2008 at 02:01:29PM -0500, Don Dailey wrote:
> > It looks like 3 is no good: 
> > 
> > Rank Name   Elo+- games score oppo. draws 
> >1 base  2000  296  199 3   67%  18880% 
> >2 d3p   1888  199  296 3   33%  20000% 
> > 
> > I think I have proven decisively that 3 doesn't work,  it lost 2 out of
> > the 3 games I played :-)

> So sorry, but as far as I can see, three games don't prove very much. Could
> you please run at least 10 games more, before jumping into conclusions.

>   -H

Yes, 10 more trials would conclusively prove that 2.5 is the correct value. 
(Our sense of humor is what makes engineers the life of every party.)



Actually, the best?answer might turn out to be something like?2.5 or 3.5. 
I have a similar rule in my program, but I search for neighbors in a 
square region because I am interested in Knight's moves and Monkey Jumps.

?
- Dave Hillis




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

Re: [computer-go] Monte-Carlo Tree Search reference bot

[dhillismail]

Finally got a window of time. It's called the "epsilon trick." Here is a cut 
and paste of Lukasz' explanation from the archives, including how to calculate 
N.
- Dave Hillis

--

-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Sun, 14 Jan 2007 4:50 AM
Subject: [computer-go] Fast UCT (epsilon trick)


Hi 
I've looked back into the article and I see that it is not trivial to 
understand how does the epsilon trick (ET) works. Therefore I will 
describe it here on the example of UCT. 

The bottleneck of UCT algorithm is choosing a move. Program has to 
iterate over all children 
evaluating their UCB value. We want to use of this loop rarely. 
One way to do it is to group playouts together. I.e. play 2 or more MC 
simulations per each tree traversal. But this is not good enough as it 
doesn't distribute 
the playouts over the tree and some parts will not get enough of them. 

The ET works as follows: 
With each node of the tree program keeps additional information: 
- child_to_visit 
- visits_to_go 

When we visit node, 
if node.visits_to_go > 0 then 
node->visits_to_go <- node.visits_to_go - 1 
node = child_to_visit 

So we have predetermined strategy to go to particular child visits_to_go times. 

But 
if node.visis_to_go = 0 then // we have to set the strategy first 
node->child_to_visit = UCT_find_child (node) 
node->visits_to_go = Epsilon * node->visited_count // round up 

As we can see, when 
Epsilon is small or when a particular node is 
visited not too many times, UCT-ET is identical to UCT. 

But when node was visited more times (near the root, far from leaves), 
then UCT-ET may save some time and go to precalculated child. 

That's it. 
I hope You like it :) 
Łukasz Lew 

PS. 

In Df-PN, good Epsilon was 1/4 I believe that here it will be much 
smaller. 1/64 maybe. 
Or even one may change the Epsilon equation to: 
node->visits_to_go = Epsilon * sqrt(node->visited_count) 

If someone will do some experiments, I'm eager to hear the results. 

PS2 

float InvSqrt (float x) { 
  float xhalf = 0.5f * x; 
  int i = *(int*)&x; 
  i = 0x5f3759df - (i>>1); 
  x = *(float*)&i; 
  x = x * (1.5f - xhalf * x * x); 
  return x; 
} 

;-) 

___
--


-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Wed, 3 Dec 2008 12:56 am
Subject: Re: [computer-go] Monte-Carlo Tree Search reference bot


Hmm.. it could be that N is picked randomly each time... now I can't seem to 
find the description and my memory is not serving me well here. Perhaps someone 
else remembers? I'll try to track it down.

- Dave Hillis


-Original Message-
From: Michael Williams <[EMAIL PROTECTED]>
To: computer-go 
Sent: Wed, 3 Dec 2008 12:14 am
Subject: Re: [computer-go] Monte-Carlo Tree Search reference b
ot


That's going to repeat the same exact path through the tree three times, isn't 
it? If so, it seems like it would be more efficient to do N playouts from the 
leaf after each traversal of the tree. 
 
[EMAIL PROTECTED] wrote: 
> There is another speedup trick that might interest you. IIRC Lukasz Lew > 
> came up with it, but I forget what he called it. After calculating the > 
> selected move for an internal node (going through UCT and RAVE and > whatnot) 
> store that move. Then, for the next N visits to that node > (where N is 5 or 
> 10 or so), just repeat that move without having to > calculate what the move 
> would be. 
> > - Dave Hillis 
> > -Original Message- 
> From: Mark Boon <[EMAIL PROTECTED]> 
> To: computer-go  
> Sent: Tue, 2 Dec 2008 11:17 pm 
> Subject: Re: [computer-go] Monte-Carlo Tree Search reference bot 
> > I have made some minor performance improvements and this is as far as I > 
> > intend to take this particular project. I might make some small changes > 
> > if necessary, but most likely I'll leave this largely unchanged from now. > 
> > > I had set myself as an arbitrary goal that it should do at least 20K > 
> > playouts. But with real liberties, AMAF and a RAVE formula I got stuck > in 
> > the 16K-17K range. According to my profiler that is mostly due to the > 
> > expensive formula used to compare nodes, where it says it spends 25% of > 
> > total time. The formula I'm using is: > > beta * (virtu
al-win-ratio + RAVE) + (1-beta) * (win-ratio + UCT) > > beta = 1 - 
log(parent-visits) / 20 > UCT = exploration-factor *sqrt( log(parent-visits) / 
(nr-visits+1) ) > RAVE = exploration-factor *sqrt( log(parent-visits) / > 
(nr-virtual-visits+1) ) > > There are probably quite a few possibilities still 
to tune this program > with regards to playing streng th and performance. But I 
felt it doesn't > help to obscure the implementation by too many details. > > 
The implementation of the search algorithm was entirely > game-independent, 
until I introduced AMAF. I didn't see how to fix that, > as there's no way 
g

Re: [computer-go] Monte-Carlo Tree Search reference bot

[dhillismail]

Hmm.. it could be that N is picked randomly each time... now I can't seem to 
find the description and my memory is not serving me well here. Perhaps someone 
else remembers? I'll try to track it down.

- Dave Hillis


-Original Message-
From: Michael Williams <[EMAIL PROTECTED]>
To: computer-go 
Sent: Wed, 3 Dec 2008 12:14 am
Subject: Re: [computer-go] Monte-Carlo Tree Search reference bot


That's going to repeat the same exact path through the tree three times, isn't 
it? If so, it seems like it would be more efficient to do N playouts from the 
leaf after each traversal of the tree.?
?
[EMAIL PROTECTED] wrote:?
> There is another speedup trick that might interest you. IIRC Lukasz Lew > 
> came up with it, but I forget what he called it. After calculating the > 
> selected move for an internal node (going through UCT and RAVE and > whatnot) 
> store that move. Then, for the next N visits to that node > (where N is 5 or 
> 10 or so), just repeat that move without having to > calculate what the move 
> would be.?
> > - Dave Hillis?
> > -Original Message-?
> From: Mark Boon <[EMAIL PROTECTED]>?
> To: computer-go ?
> Sent: Tue, 2 Dec 2008 11:17 pm?
> Subject: Re: [computer-go] Monte-Carlo Tree Search reference bot?
> > I have made some minor performance improvements and this is as far as I > 
> > intend to take this particular project. I might make some small changes > 
> > if necessary, but most likely I'll leave this largely unchanged from now. > 
> > > I had set myself as an arbitrary goal that it should do at least 20K > 
> > playouts. But with real liberties, AMAF and a RAVE formula I got stuck > in 
> > the 16K-17K range. According to my profiler that is mostly due to the > 
> > expensive formula used to compare nodes, where it says it spends 25% of > 
> > total time. The formula I'm using is: > > beta * (virtual-win-ratio + RAVE) 
> > + (1-beta) * (win-ratio + UCT) > > beta = 1 - log(parent-visits) / 20 > UCT 
> > = exploration-factor *sqrt( log(parent-visits) / (nr-visits+1) ) > RAVE = 
> > exploration-factor *sqrt( log(parent-visits) / > (nr-virtual-visits+1) ) > 
> > > There are probably quite a few possibilities still to tune this program > 
> > with regards to playing strength and performance. But I felt it doesn't > 
> > help to obscure 
 the implementation by too many details. > > The implementation of the search 
algorithm was entirely > game-independent, until I introduced AMAF. I didn't 
see how to fix that, > as there's no way getting around that it's based on the 
fact that a move > is represented by a single coordinate, which is mapped to an 
array to > store the statistical values. But strip the AMAF part, which is a 
block > of 30 odd lines of code, and I think it can be used for other games > 
basically as-is. I did this not because I ever see myself program > another 
game, but because in my experience in doing so I get a cleaner > separation 
between modules. > > At 2,000 playouts, it's still quite a bit weaker than the 
plain MC-AMAF > refbot. It wins only about 33%. But that's probably because the 
> 1,000-2,000 playouts range is the sweet-spot for that particular type of > 
playing engine. It doesn't scale from there, whereas the MCTS ref-bot > only 
just gets warmed up with 2,000 playouts. > > This leads 
 me to a question. I suppose it might be of some interest to > put th

is bot up on CGOS. But what parameters to use? The main one being > the number 
of playouts, naturally. > > Mark > 
___ > computer-go mailing list > 
computer-go@computer-go.org  > 
http://www.computer-go.org/mailman/listinfo/computer-go/ > > 
?
> Tis the season to save your money! Get the new AOL Holiday Toolbar > 
>  > for 
> money saving offers and gift ideas.?
> > > ?
> > ___?
> computer-go mailing list?
> [EMAIL PROTECTED]
> http://www.computer-go.org/mailman/listinfo/computer-go/?
?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] Monte-Carlo Tree Search reference bot

[dhillismail]

There is another speedup trick that might interest you. IIRC Lukasz Lew came up 
with it, but I forget what he called it. After calculating the selected move 
for an internal node (going through UCT and RAVE and whatnot) store that move. 
Then, for the next N visits to that node (where N is 5 or 10 or so), just 
repeat that move without having to calculate what the move would be.

- Dave Hillis

-Original Message-
From: Mark Boon <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 2 Dec 2008 11:17 pm
Subject: Re: [computer-go] Monte-Carlo Tree Search reference bot


I have made some minor performance improvements and this is as far as I intend 
to take this particular project. I might make some small changes if necessary, 
but most likely I'll leave this largely unchanged from now.?
?
I had set myself as an arbitrary goal that it should do at least 20K playouts. 
But with real liberties, AMAF and a RAVE formula I got stuck in the 16K-17K 
range. According to my profiler that is mostly due to the expensive formula 
used to compare nodes, where it says it spends 25% of total time. The formula 
I'm using is:?
?
? beta * (virtual-win-ratio + RAVE) + (1-beta) * (win-ratio + UCT)?
?
? beta = 1 - log(parent-visits) / 20?
? UCT = exploration-factor *sqrt( log(parent-visits) / (nr-visits+1) )?
? RAVE = exploration-factor *sqrt( log(parent-visits) / (nr-virtual-visits+1) )?
?
There are probably quite a few possibilities still to tune this program with 
regards to playing strength and performance. But I felt it doesn't help to 
obscure the implementation by too many details.?
?
The implementation of the search algorithm was entirely game-independent, until 
I introduced AMAF. I didn't see how to fix that, as there's no way getting 
around that it's based on the fact that a move is represented by a single 
coordinate, which is mapped to an array to store the statistical values. But 
strip the AMAF part, which is a block of 30 odd lines of code, and I think it 
can be used for other games basically as-is. I did this not because I ever see 
myself program another game, but because in my experience in doing so I get a 
cleaner separation between modules.?
?
At 2,000 playouts, it's still quite a bit weaker than the plain MC-AMAF refbot. 
It wins only about 33%. But that's probably because the 1,000-2,000 playouts 
range is the sweet-spot for that particular type of playing engine. It doesn't 
scale from there, whereas the MCTS ref-bot only just gets warmed up with 2,000 
playouts.?
?
This leads me to a question. I suppose it might be of some interest to put this 
bot up on CGOS. But what parameters to use? The main one being the number of 
playouts, naturally.?
?
Mark?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] RAVE formula of David Silver (reposted)

[dhillismail]

I would be very interested to see the RAVE code?from Valkyria. I'm sure others 
would be too.

- Dave Hillis


-Original Message-
From: Magnus Persson <[EMAIL PROTECTED]>
To: computer-go@computer-go.org
Sent: Fri, 28 Nov 2008 8:58 am
Subject: Re: [computer-go] RAVE formula of David Silver (reposted)


This document is confusing, but here is my interpretation of it. And it works 
well for Valkyria. I would really want to see a pseudocode version of it. I 
might post the code I use for Valkyria, but it is probably not the same thing 
so I would probably just increase the confusion if I did...?
?
Quoting Mark Boon <[EMAIL PROTECTED]>:?
?
>?
> What is also not clear to me from the article is how this UCT_RAVE?
> value is used after it's calculated. In plain UCT search you select the?
> node with the highest win/loss+UCT value. How does the virtual win/loss?
> ratio get used in combination with the UCT-RAVE value resulting from?
> formula (14)? Is this explained in the original by Gelly and Silver??
?
The virtual win-visits (which I think you meant and not 'win/loss') ratios 
*are* what is computed in Equation 12. Equation 13 is "standard UCT". You use 
equation 14 instead of equation 13 to select the move to search. For moves that 
are searched a lot Eq14 will finally approach Eq13, since Beta should go 
towards 0.?
?
I think the term RAVE is often used in a confusing manner. Sometimes it just 
means AMAF or as I prefer virtual win-visit ratios, and sometimes RAVE seems to 
be that the algorithm that mixes the AMAF values with normal UCT-values as 
described in the PDF.?
?
-Magnus?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] Skynet likes Go

[dhillismail]

It's not auspicious. Last season, some poor computer chess developer got 
assassinated, and this episode a computer go start-up got violently taken 
apart. And this was at the hands of the good guys!

-Dave Hillis


-Original Message-
From: Michael Williams <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 25 Nov 2008 6:08 pm
Subject: Re: [computer-go] Skynet likes Go


You should be watching the show!?
?
Last season had references to a chess computer which they thought might be a 
precursor to Skynet. Now there is a new candidate A.I. and it's designer plays 
Go instead of chess. So the good Terminator briefly studied the game. "Strange 
things happen at the 1-2 point.", she/it said.?
?
http://senseis.xmp.net/?StrangeThingsHappenAtTheOneTwoPoint?
?
?
terry mcintyre wrote:?
>> From: Michael Williams <[EMAIL PROTECTED]>?
> >> There was a Computer Go reference on last night's episode of "Terminator: 
> >> The >> Sarah Connor Chronicles".?
> > Well, you must give us more than that! Who said what??
> > > > ___?
> computer-go mailing list?
> [EMAIL PROTECTED]
> http://www.computer-go.org/mailman/listinfo/computer-go/?
> ?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] FW: computer-go] Monte carlo play?

[dhillismail]

Yes, the best combination for my program, Antigo, is to use (somewhat) more 
stochastic 

moves for the first 5-9 ply. 


I decided to look into this after noticing how surprisingly badly my heavy 
playouts 

did as part of AMAF without UCT/tree search. A more stochastic version of my 
heavy 

playouts was much stronger when using just AMAF, but weaker when I used UCT. 
Switching after the first 7 plys gave me the strongest policy for AMAF with no 
tree. 
It also turned out to be the strongest policy when using UCT, although the 
improvement was small.


- Dave Hillis


-Original Message-
From: Michael Williams <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 17 Nov 2008 12:01 am
Subject: Re: [computer-go] FW: computer-go] Monte carlo play?



It seems move selection in the playouts should be very random at first and more 
deterministic toward the end of the playout. Has anyone tried that??
?
Mark Boon wrote:?
> > On 17-nov-08, at 02:42, George Dahl wrote:?
> >> So you say that: "...I'm observing that most of the increase in level?
>> comes from the selection during exploration and only in small part?
>> from the selection during simulation.", could you elaborate at all??
>> This is very interesting. That almost suggests it might be fruitful?
>> to use the patterns in the tree, but keep lighter playouts.?
> > That's exactly what it's suggesting. But as I said, I need to do some > 
> > more testing to make a hard case for that.?
> > Mark?
> > ___?
> computer-go mailing list?
> [EMAIL PROTECTED]
> http://www.computer-go.org/mailman/listinfo/computer-go/?
> ?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] enhanced test

[dhillismail]

Go81 by Tapani Raiko used decaying move weight values as part of AMAF. He 
published his source code, and a paper in 2004. Both are?well worth reading.

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

Re: [computer-go] OT: Harder than go?

[dhillismail]

Core Wars , robot soccer (there is a simulation league), pictionary,...

- Dave Hillis


?
- Original Message - From: "Darren Cook" <[EMAIL PROTECTED]>?
To: ?
Sent: Monday, October 27, 2008 8:54 PM?
Subject: Re: [computer-go] OT: Harder than go??
?
>>> Where "harder" means the gap between top programs and top human players?
>>> is bigger, are there any games harder than go? Including games of?
>>> imperfect information, multi-player games, single-player puzzle games.?
>>?
>> Poetry contests??
>?
> I caught the smiley, but if you can define the rules (such that a?
> mechanical referee can decide the winner, as in all games from go to?
> poker to scrabble) then I guess the computer would be strong [1].?
>?
> Thanks for the Arimaa and Havannah suggestions; I'd not heard of?
> Havannah before. I see both have bets by humans that they'll not be?
> beaten any time soon.?
>?
> David, is MCTS likely to be useful for Arimaa??
>?
> Darren?
>?
> [1]: Though http://en.wikipedia.org/wiki/Scrabble#Computer_players is?
> ambiguous about if computer scrabble players are stronger than human?
> players or not.?
>?
> -- > Darren Cook, Software Researcher/Developer?
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic?
> open source dictionary/semantic network)?
> http://dcook.org/work/ (About me and my work)?
> http://dcook.org/blogs.html (My blogs and articles)?
> ___?
> computer-go mailing list?
> [EMAIL PROTECTED]
> http://www.computer-go.org/mailman/listinfo/computer-go/ ?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] light vs. heavy playouts in Many Faces

[dhillismail]

David,

A while back, Don did a 9x9 scalability study (before this one 
http://cgos.boardspace.net/study/index.html) comparing light versus heavy 
playouts. The light playouts didn't?scale badly, they didn't plateau early, 
they just?weren't as strong?as the heavy ones. There was nothing to suggest 
that (enough) light playouts, in a MCTS, couldn't produce a strong engine. This 
is consistent with what you report.

("Scalability" is another good keyword for those interesting in keywords to 
guide search in this list.)

It sounds like you are passing up low hanging fruit here. I predict that a 
version of Many Faces incorporating, for instance, the heavy playout policy 
described in the (first?) Mogo paper would be significantly stronger than the 
current one. If it wasn't, I would be quite surprised and curious to learn why 
not. 

Naturally, I'm handicapped by not knowing the details of the current Many Faces 
playout policy. I bet I'm right, though.

- Dave Hillis
"Often in error, never in doubt."

-Original Message-
From: David Fotland <[EMAIL PROTECTED]>
To: 'computer-go' 
Sent: Tue, 14 Oct 2008 11:17 pm
Subject: RE: [computer-go] Go/Games with modified scores



I use Many Faces' knowledge in the search, but not the playouts.  I made
them as light and fast as I could.
I don't have a way any more to just do playouts without the uct search.  In
your position after a few thousand playouts, it gets over 95% win for white
and 5% win for black (depending on who I make move first).

If I limit the uct search to 1 ply, it thinks white wins 49.5% and black 49%
(of the best move for each, always D9)

I guess this confirms your assertion (and Don's as well) that light playouts
without UCT search can't play well.  With UCT search, it seems that light
playouts are quite effective.

David

> -Original Message-
> From: [EMAIL PROTECTED] [mailto:computer-go-
> [EMAIL PROTECTED] On Behalf Of Darren Cook
> Sent: Tuesday, October 14, 2008 7:42 PM
> To: computer-go
> Subject: Re: [computer-go] Go/Games with modified scores
> 
> > Many Faces uses quite light playouts, and is 1 kyu 19x19 on KGS when
> run on
> > 32 cores.  So I think you can make a fairly strong program using
> light
> > playouts.  My playouts are certainly far lighter than Crazystone or
> Mogo.
> 
> Hi David,
> "quite light" is a bit vague, and I got the impression you were using
> the classical many faces knowledge, at least the tactical search
> information, in your playouts?
> 
> What do your program's playouts think when presented with the board
> position in the article? This is a terminal position, both players have
> passed, a comfortable white win, yet pure random playouts think black
> will win more often.
> 
> Darren
> 
> >>
> http://dcook.org/compgo/article_the_problem_with_random_playouts.html
> 
> 
> --
> Darren Cook, Software Researcher/Developer
> http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic
> open source dictionary/semantic network)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/blogs.html (My blogs and articles)
> ___
> computer-go mailing list
> [EMAIL PROTECTED]
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 MC reference bot and specification

[dhillismail]

 11.  When selecting moves to play in the actual game (not playouts)
superko is checked and forbidden.


positional superko (as opposed to situational superko).

- Dave Hillis


-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Sat, 11 Oct 2008 9:11 am
Subject: [computer-go] simple MC reference bot and specification



On Sat, 2008-10-11 at 13:33 +0100, Claus Reinke wrote:
> I have a rough idea of what that might be. And I suspect that keeping
> this
> "de facto standard" implicit has been hiding some actual differences
> in what
> different people think that standard is. Some of my questions arise
> from trying
> to pin down where and why different authors have different ideas of
> what "the"
> standard is. If there has been some explicit standardisation since
> those papers
> were published, I'd be interested in a pointer to that standard and
> its rationale.

I'm going to publish a real simple java reference program and some docs
to go with it and a program to "test" it for black box conformance.
(Actually, it will test 2 or more and compare them.)   I would like to
get someone who writes better than I do to write up the standard in less
casual language but it goes something like this:

  1. A complete game playing program so it can also be tested in real
games.

  2. Play uniformly random moves except to 1 pt eyes and avoiding simple
ko.  When a move is otherwise not possible,  pass.

  3.  Playout ends after 2 consecutive pass moves (1 for each side.)

  4.  1 pt eye is an empty point surrounded by friendly stones for the
side to move.  Additionally, we have 2 cases.  If the stone is NOT on
any edge (where the corner is an edge) there must be no more than one
diagonal enemy stone.If the point in question is on the edge, there
must be NO diagonal enemy stones.  

  5.  In the playouts, statistics are taken on moves played during the
playouts.   If the move is played FIRST (during the playout) by the side
to move it is one data point and the win loss record is maintained.  

  6.  The move with the highest statistical win rate is the one selected
for move in the actual game.

  7.  In the case of moves with even scores a random selection is made. 

  8.  Pass move are never selected as the final move to play unless no
other non-eye filling move is possible.  

  9.  Random number generator is unspecified - your program 
should
simply pass the black box test and as a further optional test your
program should score close to 50% against other "properly implemented"
programs. 

 10.  Suicide not allowed in the playouts or in games it plays.  
 
 11.  When selecting moves to play in the actual game (not playouts)
superko is checked and forbidden.

 12.  If a move has NO STATS taken (which is highly unlikely unless you
do very few playouts) it is ignored for move selection.  

Did I miss anything?  I would like to get feedback and agreement on
this.   
 
Please note - a few GTP commands will be added in order to instrument
any conforming programs.   Haven't figured those out yet,  but it will
be designed so that it can report number of nodes, number of playouts,
average score of playouts, etc.   So the tester may set up some position
and a ko,  and ask for statistics based on the number of specified
playouts.

- 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] pseudo eye variations for playouts

[dhillismail]

There is a de facto standard light playout policy (algorithm). If you want to 
adhere to this standard, then by definition, there are correct and incorrect 
ways to do so. If you just want to design a better playout policy, naturally 
anything is fair game. But how are you going to measure whether it's really 
better?

My advice is to keep to this standard for a little while longer, write the rest 
of your engine, run it on CGOS where you can compare it directly with programs 
like myCtestxxx (maintained for that purpose by generous individuals) and 
verify that the other parts work. Then start improving the playout policy.

Just my suggestion.
- Dave Hillis


-Original Message-
From: Claus Reinke <[EMAIL PROTECTED]>
To: computer-go@computer-go.org
Sent: Fri, 10 Oct 2008 4:54 pm
Subject: [computer-go] pseudo eye variations for playouts



Thanks everyone for the answers regarding playout terminations. I still
have my suspicions regarding how artificial game length bounds affect
the position evaluation (I'd expect the values to fluctuate with length,
so arbitrary bounds would result in arbitrary differences).

For the moment, however, I'd like to focus on the variations wrt
pseudo-eyes (positions not to be filled during playouts). All of these
are known to be wrong in some cases, the main argument in favour of
pseudo-eyes being efficiency.

Since ruling out fill-ins introduces not only biases, but actual blind spots
into the playouts, something even heavy playouts otherwise try to avoid
(they prioritize "good" moves instead of eliminating "bad" moves) it is
important that the definition of pseudo-eyes errs on the safe side ("safe"
here meaning random play - any move is possible): they may permit
erroneous fill-ins, but must not rule out necessary fill-ins (only definitely
bad fill-ins may be ruled out).

Within that constraint, the goal is to rule out as many bad fill-ins as
possible without ruling out any good fill-ins. And all three variations
listed earlier (Gobble, Olga, Oleg)

http://computer-go.org/pipermail/computer-go/2008-October/016549.html

have their issues with that. For instance, consider the following position:

(
;
FF[1]
GM[1]
SZ[19]
AP[Jago:Version 5.0]
AB[ji][kj][jk][ij][jl][hj][jh][lj][jg][kf][ke][le][me][ne][of][og][oh][oi][ni][mj][nf][kg][nj][jm][jn][jo][jp][ip][hp][gp][fp][fo][fn][fm][fl][fk][fj][gj][gi][gh][hg][ig][ok][gf][pl][fe]
AW[ki][kh][li][lg][mh][lf][mf][ng][nh][kk][lk][kl][mi][mk][nk][ik][hk][gk][gl][gm][gn][il][im][in][io][go][hm][ho][jd][kd][ld][md][nd][od][pe][pf][ph][pg][pi][pj][ei][ej][ek][el][em][en][eo][ep][eq][fq][gq][hq][iq][jq][kq][ko][kp][kn][km][oj][ii][fi][fh][fg][gg][hf][if][jf][je][ih][oe]
C[black to move.

Gobble: 'a' is not an eye => fill it and die

Olga: 'a' is an eye, but would cease to be if 'b' was white

Oleg: 'a' is not an eye, but would be if 'b' was black]
L[jj][hh][nk][oj]
GN[playout-eyes]

)

If I set this up correctly, the black center group is "unconditionally" alive,
even if it was white's turn, while playouts with Gobble-style pseudo-eyes
will rate it as unconditionally dead (and hence the white strings 'c' and 'd'
as unconditionally alive, independent of conditions on the outside). Playouts
with Olga-style pseudo-eyes would fare better, but would be fooled into
considering fill-in at 'a' after white 'b'. Playouts with Oleg-style pseudo-eyes
have a chance of finding the black group alive, in case of black 'b' first.

Did I set this up right? And why does no-one else seem worried about it?-)

Claus

PS In case the sgf-labelling isn't standard, 'a' is K10/center, 'b' is H12.




___
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] programming languages

[dhillismail]

Computers + random = can of worms.

What if I get a fast benchmark by implementing the fastest, most awful, random 
number generator imaginable? What if every one of my "random" playouts looks 
the disturbingly similar?

As to the relevance, the time-eaters in my heavy playouts are different from 
the time-eaters in my light playouts.

- Dave Hillis


-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 9 Oct 2008 2:44 pm
Subject: Re: [computer-go] programming languages



On Thu, 2008-10-09 at 14:17 -0400, [EMAIL PROTECTED] wrote:
> >>> The http://shootout.alioth.debian.org/ site, ... 
> >>> 
> >>> If we, as a community, could come up with a sufficiently detailed 
> >>> description of light playouts algorithm (see the current "Light 
> >>> simulation : Characteristic values" thread), there is no reason
> that 
> >>> this algorithm couldn't join them. 
> 
> 
> Many potential ways to speed up light playouts involve taking some
> liberties regarding the uniform distribution of moves. Specifying and
> verifying the rules here, looks messy to me. 
> 
> Also, light playouts are more of an intermediate step than an end goal
> for engines. Is making them faster all that relevent anymore?


I think you're missing the point.   This would be nothing more than just
a benchmark.   You would be free to implemented it any way you like as
long as it conforms to the general guidelines, so all programs should be
equivalent.   However one program might use a totally different board
representation than another.   

Specifying the rules is probably not too hard but verifying them would
be trickier.   The simplest way to verify is:

  1.  benchmarks that provide strong empirical evidence.
  2.  Source code is available for all to inspect.

I agree that this is far from the best way to implement a program but it
would really be useful as a benchmark for board games.  I would trust
the results of this shootout way beyond the computer language shootout.
This is because it's an actual program that should also be able to play
a real game.

John Tromp did something along the same lines with connect-4.  He had a
java and C implementation that were equivalent in output.  I actually
didn't trust his benchmark because he wrote C code generic and simple,
not like a high performance guru would write C code.I can't really
be too critical unless I actually were to try to improve on the C
version.  

To me the advantage of C is that you can write code that you wouldn't
write in Java.   There is very littl
e advantage of C over Java
otherwise.   If you start with the best Java program you can and then
port it to C as faithfully as possible, you get a different result than
if you take the best possible C program you can write and try to port it
to Java.   For each language, you would probably write fast code
differently.  

I think the right way to do John's benchmark is to get each language
zealot in competition with each other.   Let the C programmer prove he
can do it much faster.  And the Java programmer can respond if he wants
to.


- Don




> 
> - Dave Hillis
> 
> 
> 
> __
> McCain or Obama? Stay updated on coverage of the Presidential race
> while you browse - Download Now! 
> ___
> 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] programming languages

[dhillismail]

>>> The http://shootout.alioth.debian.org/ site, ...?
>>>?
>>> If we, as a community, could come up with a sufficiently detailed?
>>> description of light playouts algorithm (see the current "Light?
>>> simulation : Characteristic values" thread), there is no reason that?
>>> this algorithm couldn't join them.?


Many potential ways to speed up light playouts involve taking some liberties 
regarding the uniform distribution of moves. Specifying and verifying the rules 
here, looks messy to me. 

Also, light playouts are more of an intermediate step than an end goal for 
engines. Is making them faster all that relevent anymore?

- Dave Hillis


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

Re: [computer-go] More Characteristic values (AMAF Characteristics from empty board)

[dhillismail]

I checked my notes. For Light playouts
---
average game length 111 (including final 2 passes)
not counting passes 107
---
When these numbers match, it's a pretty strong sign that the implementation is 
correct (particularly the eye rule).

- Dave Hillis

-Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Wed, 8 Oct 2008 9:09 am
Subject: Re: [computer-go] More Characteristic values (AMAF Characteristics 
from empty board)


Looking superficially... 
 
The game length appears in the right ballpark. I seem to remember 110-112 
moves, depending on how passed are counted. 
 
20k playouts/core/sec seems reasonable for lightly optimized. 
 
The center bias also looks correct. 
 
The win rates don't look right to me. 7.5 Komi gives white a significant edge 
in random playouts that results in a 40-60 split (don't take those numbers as 
exact) 
 
Sent from my iPhone 
 
On Oct 8, 2008, at 8:35 AM, Denis fidaali <[EMAIL PROTECTED]> wrote: 
 
> 
> hi, 
> Thanks Dave Hillis for this quick response. (And by the way, thanks > to Remy 
> Coulomb for a previous response he made a while ago. I just > though that 
> post containing only thanks would be noise to most > people there ...) 
> 
> To Don and Christoph : I reallize that i was probably not as clear > as i 
> though i was. 
> I have built up a light simulator. There are no tree involved. It is > only 
> choosing a move with20equiprobabilty from the set of empty > points on the 
> board. 
> If the move is not valid, it just choose another one. If it's a > "pseudo 
> eye" then it again chooses another point. Whenever no point > can be validly 
> chosen, it just pass. Whenever two consecutives pass > occurs, the simulation 
> end. 
> 
> Now, i wanted to make sure that my implementation had any chances to > be 
> correct. So i though I'd post the characteristic statistical > values that i 
> get out of it. Indeed i though it could benefits > others later on, in 
> particular if someone could corroborate them :) 
> 
> 
> So here is another set of Values. It is the all-move-as-first score > from an 
> empty board for black stones (black plays first in my > simulations). It 
> gives the probability of black wining the game > (while playing randomly), if 
> he has played an intersection before > white during the simulation. 
> ,0566 means 0.566 chances out of 1 that a game where black has > played there 
> is a win for black. 
> 
> Could anyone once again confirm that those results sounds correct ? 
> 
> 
> mean score =2.1726424464558005 
> 79655.5328628921 Playout/sec 
> Time=12.563621936 
> Number of playout=1000762.0 
> Mean moves per sim 111.0673969035 
> 
> Amaf Result : (from empty board, black plays first) 
> ||,490||,507||,506||,511||,514||,511||,506||,507||,490 
> ||,507||,524||,533||,539||,541||,539||,533||,524||,507 
> ||,506||,534||,544||,550||,553||,551||,544||,533||,505 
> ||,
511||,539||,550||,558||,561||,558||,551||,539||,511 
> ||,513||,541||,553||,562||,566||,560||,552||,541||,513 
> ||,511||,539||,550||,558||,560||,558||,550||,539||,511 
> ||,507||,532||,544||,551||,552||,550||,544||,532||,506 
> ||,507||,523||,534||,538||,541||,538||,532||,523||,507 
> ||,491||,507||,505||,512||,513||,511||,506||,507||,492 
> 
> 
> PS : how can i do so that my response to this mailing-list will be > 
> correctly indented ? (for example i would have liked to set this one > as a 
> response to my previous post). 
> _ 
> Email envoyé avec Windows Live Hotmail. Dites adieux aux spam et vir> us, 
> passez à Hotmail ! C'est gratuit ! 
> http://www.windowslive.fr/hotmail/default.asp___ 
> computer-go mailing list 
> [EMAIL PROTECTED]
> http://www.computer-go.org/mailman/listinfo/computer-go/ 
 
___ 
computer-go mailing list 
[EMAIL PROTECTED]
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] Light simulation : Characteristic values

[dhillismail]

Going from memory, that all looks right. (We've been calling it a "pseudo 
eye".) 

There's no need to do this, but for what it's worth, if you make a histogram of 
the scores,
 - you should only get odd scores
- there should be big spikes at the tails (+/- 81)
- there should be a Gaussian-looking bump in the middle with a center offset a 
bit from the mean score.

- Dave Hillis







-Original Message-
From: Denis fidaali <[EMAIL PROTECTED]>
To: computer-go@computer-go.org
Sent: Tue, 7 Oct 2008 11:33 am
Subject: [computer-go] Light simulation : Characteristic values




Hi, i have been searching a bit through the archive, and was not able to get a 
omplete list of the characteristics value for the light simulations.
 By light simulation i mean : Playing randomly the valid moves (No suicide 
llowed), but not in the "true" eyes. I have a rule for defining a true eye : 
ll vertical and horizontal point around are the player's color. And depending 
n the position :
- no edge around : NOT ( two diagonal or more are the opponent's color).
- one or two edge around : NOT ( one diagonal or more is the opponent's color)
The engine is written in java, and run on a quad core Q9300 @ 2.50 Ghz.
he code has been lightly optimized, and use pseudo-liberties to detect 
aptures.
Here is what i get :
--
mean score =2.086382709065067(black win on average by 2.08 points)
8454.10819786233 Playout/sec   (Trying to take advantage of20the 4 cores)
ime=12.752397841(in seconds)
umber of playout=1000478.0
ean moves per sim 111.05742754963127 (Number of move per simulation, 
onsidering pass as a move)
ean moves(no pass) per sim 107.37764148736903 (Number of move per simulation, 
ot counting passes).
Note : as there are no seki possible in the simulation, the mean score for the 
ight simulations maybe bugged for seki, and still get the correct value.

nstallez gratuitement les 20 émôticones Windows Live Messenger les plus fous ! 
liquez ici !
ttp://www.emoticones-messenger.fr/___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://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] Re: [EMAIL PROTECTED] (wasCongratulations to David Fotland!)

[dhillismail]

It depends on your definition of real-time. A play-by-email target, such as the 
Dragon Go Server is pretty flexible about scheduling moves. The project could 
do what many people do and play several games in parallel. Each participating 
computer would get a slice of multiple games to process in a batch, instead of 
a slice of one game to process in a hurry. It would have a long but potentially 
very fat pipe. The programing required might be pretty reasonable.

- Dave Hillis


-Original Message-
From: David Doshay <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 2 Oct 2008 3:43 pm
Subject: Re: [computer-go] Congratulations to David Fotland!


Yes, various kinds of off-line (not in-game) processing could be done.?
But nothing in a real-time game.?
?
Cheers,?
David?
?
?
On 2, Oct 2008, at 10:48 AM, terry mcintyre wrote:?
?
> An @home network might be better for things such as creating opening > books, 
> testing algorithms, etc.?
?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] Using playouts for more than position evaluation?

[dhillismail]

I agree with much of what you say (to the degree that anyone needs to "agree" 
with questions).

The discussions on this list dealing with "ownership maps", RAVE and AMAF have 
to do with using additional information from the playouts.

Playouts can't be "unbiased." Picking a move with uniform probability is a bias 
too, and not a good one.

Computer go papers here: http://www.citeulike.org/group/5884/library

- Dave Hillis

-Original Message-
From: Claus Reinke <[EMAIL PROTECTED]>
To: computer-go@computer-go.org
Sent: Sun, 28 Sep 2008 10:05 am
Subject: [computer-go] Using playouts for more than position evaluation?



>From browsing Monte-Carlo Go papers (*), I get the impression that random
playouts are used mainly to approximate an evaluation function, determining
some value for board positions arising in more traditional tree search.

Is that correct? It seems somewhat wasteful to calculate all those possible
board positions and only take a single value before throwing them away.
Have there been any attempts to extract other information from the playouts?

For instance, if an intersection belongs to the same colour in all playouts,
chances are that it is fairly secure (that doesn't mean one shouldn't play
there, sacrifices there may have an impact on other intersections).

Or, if an intersection is black in all playouts won by black, and white in
all playouts won by white, chances are that it is fairly important to play
there (since playouts are random, there is no guarantee, but emphasizing
such intersections, and their ordering, in the top-level tree search seems
profitable).

Secondly, I have been surprised to see Go knowledge being applied to the
random playouts - doesn't that run the danger of blinding the evaluation
function to border cases? It would seem much safer to me to keep the
random playouts unbiased, but to extract information from them to guide
the top-level tree search. Even the playout termination criterion (not filling
eyes) has to be defined fairly carefully (and there have been variations),
to avoid blinding playouts against sacrifices.

Since most Go knowledge isn't absolute, but comes with caveats, it would
seem that any attempt to encode Go knowledge in the playouts is risky
(mind you, I'm a weak player, so I might be wrong;-). For instance, a
bamboo joint connects two strings, unless (insert various exceptions here),
so if you encode a bamboo joint as a firm connection, your playouts include
a systematic error. Shouldn't the same hold for nearly all Go "rules"?

Thirdly, I have been trying to understand why random playouts work
so 
well for evaluating a game in which there is sometimes a very narrow
path to victory. Naively, it would seem that if there was a position from
which exactly one sequence of moves led to a win, but starting on that
sequence would force the opponent to stay on it, then random playouts
would evaluate that position as lost, even if the forced sequence would
make it a win.

Is it the full search at the top of the tree that avoids this danger (every
starting move gets explored, and for the correct starting move, random
plays are even worse for the opponent than being forced, so the forcing
sequence will emerge, if slowly and not certainly)? If yes, that would
explain the "horizon effect", where Monte-Carlo programs with slightly
deeper non-random search fare better at judging positions and squash
their opponents even without other improvements.

It might also explain why bots like Leela sometimes seem overconfident
of their positions, abandoning local fights before they are entirely stable.
Such overplay has traditionally been useful in playing against other bots,
even though it can be punished severly against strong human players. If
the opponent bot can't see the winning sequence, it may not continue
the local fight, and if it does continue the local fight with anything but 
the
optimal move, Leela tends to come back with strong answers, as if it
could suddenly see the danger. Either way tends to justify Leela's playing
elsewhere, if only against a bot opponent.

Of course, the third and second issue above are somewhat related:
if incorporating Go knowledge in the playouts is the only way to
avoid missing narrow paths to certain evaluations, one might have
to risk adding such knowledge, even if it boomerangs in other situations
(are ladders one such case, or are they better left to random evaluation?).

Ok, way too many questions already;-) I hope someone has some
answers, even if partial or consisting of references to more papers.

Claus

(*) btw, Comp
uter Go related papers seem to be widely distributed -
is there a central bibliography that keeps track of papers and urls?




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

Re: [computer-go] MoGo v.s. Kim rematch

[dhillismail]

There is a discussion at godiscussions
http://www.godiscussions.com/forum/showthread.php?t=7154
?The sgf's for the two games played are on page 2

Dave Hillis

-Original Message-
From: mingwu <[EMAIL PROTECTED]>
To: [EMAIL PROTECTED]; computer-go 
Sent: Sun, 21 Sep 2008 9:22 pm
Subject: Re: [computer-go] MoGo v.s. Kim rematch



Anyone knows the result, or better the game sgf?



On Sat, Sep 6, 2008 at 6:57 AM, Don Dailey <[EMAIL PROTECTED]> wrote:

Great news! ? Look forward to seeing it happen. ?I hope Mogo has some
great hardware.

- Don






On Fri, 2008-09-05 at 15:54 -0700, David Doshay wrote:
> MoGo and Myungwan Kim will hold an exhibition rematch at the Cotsen
> Open on Saturday September 20. The exhibition will start at about 5pm
> Pacific Daylight time.
>
> As probably known by all on this list, MoGo won the last game, held at
> the US Go Congress in Portland Oregon, when it was given a 9 stone
> handicap and played with a one hour time limit.
>
> At this time the expected handicap will be 7, and it is not clear if
> there will be one game or two. It is not known at this time how many
> cores MoGo will be running on. Mr Kim has asked for MoGo to be given
> 90 minutes because he saw how much the increase in time from 15
> minutes to one hour increased its playing strength. Mr. Kim has also
> asked that there be only one or at most 2 blitz games at the start.
>
> The MoGo team also wants to have some 9x9 games, but Mr Kim does not
> feel familiar enough with 9x9 to play those games, but he is searching
> for an alternate strong player. MoGo has some new features for 9x9,
> and the team is anxious to see the newest code in action.
>
>
>
> Cheers,
> David
>
>
>
> ___
> 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] semeai

[dhillismail]

Raises hand. Chinese rules version for 9x9 and 13x13 would be quite helpful if 
that's what you are offering. Different komi would be fine.

- Dave Hillis


-Original Message-
From: Darren Cook <[EMAIL PROTECTED]>
To: computer-go 
Sent: Sat, 6 Sep 2008 10:33 pm
Subject: Re: [computer-go] semeai



>> Has anyone tried implementing the ideas in Richard Hunter's "Counting
>> Liberties"

No, but I did make a test suite that included many of the interesting
positions (it also included many others of my own creation, both for
semeai and tactical search). (And, though almost all the positions were
modified enough from those in the book to probably not be covered by
copyright, I did get Richard's permission to include them in the test
suite.)

All positions were modified to fit on a 9x9 board, and IIRC all were set
up so that the correct move(s) won the game, while all incorrect moves
lost the game. (However that'd be in Japanese rules; they'll need
modifying or a different komi for the same to be true in Chinese rules.)

If there is any interest I'll dust them off and release the test suite
properly.

(And would there be interest in the same kind of test suite for 13x13
and 19x19 boards?)

Robert Jasiek wrote:
> - He overlooks some details like exceptional cases and liberty counts
> for approach defects. (And he does not mention the trivial cases at all.)
> - It may be suitable to include all L&D types in the classification.
> - For non-trivial types, algorithms need to be developed in addition.
> - Semeais with kos are more complicated than semeais without kos by a
> factor roughly between 100 and 1000. Firstly the number of cases
> explodes (already when there is only one basic ko). Secondly [endgame
> value] evaluation becomes much more difficult. Thirdly and obviously
> there are also peculiar ko shapes.

Hi Robert, do you have anything published? Or (even better from my point
of view) do you have some example positions that demonstrate the
exceptional cases, with the correct answer shown?

Darren


___
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] Playout acceleration

[dhillismail]

Yes, I tried heavy playouts for N plys, then switching to light.?It didn't 
really speed things up all that much but it weakened my bot quite a bit, on a 
per playout basis, resulting in a clear net loss.
?
I tried ladder reading for the first N plys, then no ladder reading. The 
results were muddled.

Currently, I use slightly more stochastic playout rules for the first 7 plys of 
the playouts, than for the remainder. It gives me a small, but statistically 
significant, strength increase against Gnugo.

- Dave Hillis


-Original Message-
From: Michael Williams <[EMAIL PROTECTED]>
To: computer-go 
Sent: Fri, 5 Sep 2008 1:43 pm
Subject: [computer-go] Playout acceleration


Has anyone tried heavy, slow playouts near the tree and light, fast playouts 
near the end of the game? I'm calling this "playout acceleration" because it 
starts slow and speeds up. You could have many different playout weights/speeds 
in a single playout. It seems like a reasonable idea to me since the moves near 
the tree should be the most important. Thoughts??
?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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: What's happening at the European Go Congress?

[dhillismail]

> -Original Message-
> From: Don Dailey <[EMAIL PROTECTED]>
> To: computer-go 
> Sent: Mon, 11 Aug 2008 11:09 pm
> Subject: Re: [computer-go] Re: What's happening at the European Go Congress?



> On Tue, 2008-08-12 at 11:50 +0900, Darren Cook wrote:
> > > Also, if you are down 8 or 9 stones, maximizing your winning chances is
> > > still the right strategy, right?   
> > 
> > With MCTS algorithms the error margin is high at the start of the game,
> > and low in the endgame. In a handicap game against a stronger opponent
> > the assumption is that the weaker player will make more mistakes (i.e.
> > has a higher error margin overall). But MCTS programs don't see it that
> > way - their opponent model is the same strength as they are. So they
> > choose a move that gives them 95% (+/- 20%) win (against themselves)
> > instead of the better move that they only gives them a 90% (+/- 20%) win
> > (against themselves). (I.e. I'm saying their error margin in the opening
> > is much greater than the difference in their estimate of move values.)

> There could be something to that.  

> Do you believe that they will play the 90% move if they are told they
> are not really down 9 stones? 


> I did a bunch of experiments and ALWAYS got a reduced wins when I faked
> the komi.   But there are a million ways to do this and I may not have
> stumbled on the right way.






If my engine plays in a high handicap game (and it has to be a pretty high 
handicap), 
for the first moves, it can't see a difference for any moves and plays 
randomly. 
I can fix this by making the playout asymetrical. I make the playout moves for 
black 
lighter (higher probability of being random). With this adjustment, it makes 
reasonable 
looking moves. I haven't tested this extensively because I don't have any need 
for an 
engine that plays better in high handicap games.
















- Dave Hillis













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

Re: [computer-go] CGOS server boardsize

[dhillismail]

Something that has worked well in other games would be to change the third CGOS 
every month. Each month, the parameters would be announced and the CGOS started 
empty except for the anchor(s). At the end of the month, the bot at the 
top?would be?the winner. That would allow us to experiment with novel settings 
like 11x11 boards or 20 seconds per game that might be interesting for a short 
while but maybe not for long. It can be a way of keeping things fresh and 
leveling the playing field a little.

- Dave Hillis


-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Fri, 1 Aug 2008 12:54 pm
Subject: [computer-go] CGOS server boardsize



There has been some discussion about which additional board sizes to use
for the server once it is running.   

Of course running all 3 board sizes is a possibility now that we will
have server space,  but my fear all along has been that they will kill
each other.  There is something to be said about numbers and you want as
many programs as possible playing on the server you want to test on. 

Instead of asking for a lot of opinions however, I think it makes sense
to put all 3 servers up and see what happens for a while.   In other
words you will vote with your participation.   I think we will see that
programs will gravitate more towards one server than another and I don't
know which one that will be.   If they all get reasonable usage I will
leave them all up,  but if one tends to get very little usage, I will
bring it down later.   I'll let them all stay up for a reasonable length
of time.

So there will be 9x9, 13x13 and 19x19, at least for the first month or
so, depending on usage.

For time controls,  I have changed my previous position, I think I
prefer somewhat faster time controls.   There are disadvantages but
almost many advantages.  The foremost advantages is that I believe it
encourages participation,  more programs are likely to test on the
server if they do not have to wait unduly long for solid results.
Another advantage is that the games are more fun to watch.  

Right now, the time control for 9x9 assuming the average number of moves
is roughly equivalent to the number of points on the board is about 3.7
seconds per move or 5 minutes.  Using this same exact reasoning if we
try to match the same rate of play per move we have this table:

  9x9  - 300 seconds or 5 minutes
 13x13 - 625 seconds or 10 minutes, 18 seconds. 
 19x19 - 1336 seconds or 22 minutes, 16 seconds per move.

There is no particular reason that the time control has to be in
multiples of 5 minutes except that we humans seems to be offended if
things are rounded nicely for us.

So we could accept those values as is, or we could ro
und it to what to
our sensibilities seems somehow more "normal" and use 5 minutes 10
minutes and 20 minutes for 9x9, 13x13 and 19x19 respectively.

If we want to speed things up a bit, we might consider going from 3.7
seconds per move to 2.5 seconds per move.   This gives the following
approximate table:

  9x9   -  202.5 seconds  or 3 minutes, 22 seconds
 13x13  -  422.5 seconds  or 7 minutes 2 seconds 
 19x19  -  902.5 seconds  or 15 minutes 2 seconds

These could be rounded to 3 minutes, 7 minutes and 15 minutes or kept as
is.  

There is some argument for making the bigger boards play faster based on
the notion that you SHOULD play faster since the game will have a lot
more moves in it.   

In this case, the time control could be set the same for all board
sizes, perhaps 15 minutes per game or even 10 minutes per game.  There
is some appeal to having this kind of consistency, but of course the
quality of the games on the big boards would suffer accordingly.  Of
course we don't care about absolute quality since we are testing
programs against each other and we accept that they play much better at
longer time controls.

But we could set the average time per move faster if we were not
comfortable with just making them all the same.   We could do something
like 5, 10, 15 or something like that.

In addition to the time control, there is currently a 0.75 second gift
which is configurable.  The gift makes it possible for some programs
with high latency connection issues to finish ridiculously long games
without defaulting on time despite the fact that they are playing
instantly.   So fast time controls shouldn't be dominated by network
speed considerations.  

My current default choice is:

   9x9 - 5 minutes.  (to keep it the same as it is.)
 13x13 - 10 minutes.
 19x19 - 15 or 20 minutes.

Feedback?

- Don







- 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] What Do You Need Most? 9x9 KGS rating

[dhillismail]

That was a great page while it lasted! Sure it could have been tweaked some 
more;?probably the ultra-blitz games shouldn't?be counted. The fundamental 
problem with deriving a bot's rating from 9x9 KGS games is that the people 
involved tend not to play seriously. But it was still fun.

- Dave Hillis


-Original Message-
From: Christian Nilsson <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 31 Jul 2008 2:46 pm
Subject: Re: [computer-go] What Do You Need Most?



On Thu, Jul 31, 2008 at 2:05 PM, Jason House
<[EMAIL PROTECTED]> wrote:
> On Jul 30, 2008, at 6:55 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
>
>> I think someone already has a website somewhere where they try to rank
>> bots based on KGS games.
>
> I'm pretty sure the site stopped doing rankings when KGS moved to gokgs.com


I'm afraid I am responsible for that awful page. :)

The move to gokgs.com also brought some changes to the structure of the game
archives ( I basically downloaded the game history of each Bot each
hour or so and
grabbed the data from it ) . I never liked the ugly hack I made into
that page and
the changes made to KGS definitely put a stop to my motivation...

Collecting the data from KGS archives isn't all that hard, although
I'd expect direct
access to the database would be easier. Getting that kind of access is
probably not
going to happen...

/Christian


>
>
>> If you can figure out how to make it
>> schedule games fairly and consistently then go for it.
>
> I doubt you'd get the CGOS style for either of these out of the box.
>
> Scheduling for automatch is likely a first-come, first-serve basis, probably
> with some kind of anti-repeat feature. Having engines reconnect at the start
> of a round could help fairness issues. Randomized connection times could be
> helpful too.
>
> KGS would limit games to within 9 stones and would automatically give
> handicap, but I consider that a good thing.
>
> Obviously, the more wms helps (or lets us provide code, the better things
> will be. I doubt we'd get anywhere without Nick Wedd backing the idea, and
> he probably wouldn't if you don't. A KGS alternative may never be as good as
> a custom computer go server, but if it's close, it has other side
> benefits... Game caches, wider human audiences, potential integration with
> human play, etc
>
>
>
>
>
>
>> I want to be
>> able to put my bot on line,  leave it alone for a day or more,  and know
>> it will play only other computers under a consistent rule set and get a
>> ranking.  Also I w
ant to know that you can't just disconnect and to
>> abort lost games.  I don't want the same player playing it 20 games in a
>> row and so on.   If you can get all that to happen without WMS support,
>> then I'm definitely interested.
>>
>>
>> - Don
>>
>>
>>
>> On Wed, 2008-07-30 at 18:20 -0400, Jason House wrote:
>>>
>>> Where there's a will, there's a way. It may not be hard to use auto
>>> match with the self-proclamed bot ranks as a first step approximation.
>>> All that's needed for that is to allow bots to be paired against each
>>> other. Ratings could be computed offline and used by a kgsGtp wrapper
>>> to update the self-proclaimed ratings between games.
>>>
>>> Everything else could be incremental tweaks as issues are identified.
>>>
>>> Sent from my iPhone
>>>
>>> On Jul 30, 2008, at 5:07 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
>>>
 I like KGS and the maturity of it compared to CGOS.   However, it's a
 different problem.   KGS doesn't schedule games for you.

 I also tried to persuade WMS to rate 9x9 bot games, but he was
 unwilling
 to add more indexes and overhead to the database.   And even if he
 agreed, sometimes I want to play other bots, although I like the
 idea of
 being able to play humans when I want that.   Still,  it's a
 scheduling
 issue that KGS just doesn't support.

 If WMS had made a computer go server that looks like KGS but does the
 scheduling and rating for bots only (or given a choice with humans
 too)
 and such, I would have never written CGOS.   If he does it later, I
 would probably prefer it to CGOS and would use it instead.

 - Don





 On Wed, 2008-07-30 at 15:35 -0400, Jason House wrote:
>
> Maybe we should approach wms about using KGS. Rank and pairings could
> be computed separately. Once upon a time, there was a page that
> computed 9x9 bot ratings
>
> Sent from my iPhone
>
> On Jul 30, 2008, at 3:16 PM, Don Dailey <[EMAIL PROTECTED]> w
rote:
>
>> There seems to be something special about 9x9 go for computers,
>> it's
>> very popular, perhaps because it's so much more approachable.
>>
>> However I personally think it's time to start looking at bigger
>> board
>> sizes seriously.If it were up to me, we would move to 11x11 on
>> CGOS
>> but I fear that would be especially unpopular because it's not one
>> of
>> t

Re: [computer-go] Incremental move weights

[dhillismail]

The people with stronger programs and more full-board experience will be better 
positioned to comment on this. I'll say that the two styles both need a lot of 
tweaking, making it hard to establish a fair test between them.

It's good to be able to match a 3x3 pattern very quickly. Since there aren't so 
many of them, it makes sense to build a lookup table.

- Dave Hillis


-Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 21 Jul 2008 10:27 pm
Subject: Re: [computer-go] Incremental move weights



On Jul 21, 2008, at 10:03 PM, [EMAIL PROTECTED] wrote:







I've tried both MoGo and CrazyStone style playouts. I find MoGo style playouts 
easier to work with. YMMV.





Besides ease of implementation, what other trades did you notice between the 
two methods? I'd expect Crazy Stone's method to be slower. Is it stronger?









My MoGo style heavy playouts are about 4 times slower than my light playouts.





That's not too bad, considering...

Were there any tricks to minimize the slowdown?











-Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 21 Jul 2008 8:45 pm
Subject: Re: [computer-go] Incremental move weights



On Jul 21, 2008, at 7:54 PM, [EMAIL PROTECTED] wrote:







I  use proximity in the heavy playouts themselves.





What kind of proximity heuristic do you use? Remí'
s paper implies a different weight for many many points on the board. I think 
MoGo uses an alternate approach of examining the local neighborhood and then 
considering a tenuki.




How much of a slow down did you observe when you went to heavy playouts?






I think most (all?) people do this. I have a precalculated table with the 3x3 
and 5x5 neighbors for every position on the board. 

- Dave Hillis


- Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 21 Jul 2008 7:32 pm
Subject: [computer-go] Incremental move weights


I'm starting heavy plyouts, with variable move selection weights. The proximity 
heuristic seems like a performance killer since most weights would require an 
update with each move. 
 
How do others handle this? Is proximity reserved for the search tree? 
 
How do others store data for rapid lookup? 
 
Sent from my iPhone 
___ 
computer-go mailing list 
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/ 


The Famous, the Infamous, the Lame - in your browser. Get the TMZ Toolbar Now! 




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

= 


___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/


The Famous, the Infamous, the Lame - in
 your browser. Get the TMZ Toolbar Now! 




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

= 


___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://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] Incremental move weights

[dhillismail]

I've tried both MoGo and CrazyStone style playouts. I find MoGo style playouts 
easier to work with. YMMV.

My MoGo style heavy playouts are about 4 times slower than my light playouts.

- Dave Hillis


-Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 21 Jul 2008 8:45 pm
Subject: Re: [computer-go] Incremental move weights



On Jul 21, 2008, at 7:54 PM, [EMAIL PROTECTED] wrote:







I  use proximity in the heavy playouts themselves.





What kind of proximity heuristic do you use? Remí's paper implies a different 
weight for many many points on the board. I think MoGo uses an alternate 
approach of examining the local neighborhood and then considering a tenuki.




How much of a slow down did you observe when you went to heavy playouts?






I think most (all?) people do this. I have a precalculated table with the 3x3 
and 5x5 neighbors for every position on the board. 

- Dave Hillis


-Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 21 Jul 2008 7:32 pm
Subject: [computer-go] Incremental move weights


I'm starting heavy plyouts, with variable move selection weights. The proximity 
heuristic seems like a performance killer since most weights would require an 
update with each move. 
 
How do others handle this? Is proximity reserved for the search tree? 
 
How do others store data for rapid lookup?C2
 
Sent from my iPhone 
___ 
computer-go mailing list 
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/ 


The Famous, the Infamous, the Lame - in your browser. Get the TMZ Toolbar Now! 




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

= 


___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://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] Incremental move weights

[dhillismail]

I? use proximity in the heavy playouts themselves. I think most (all?)?people 
do this.?I have a precalculated table with the 3x3 and 5x5 neighbors for every 
position on the board.?

- Dave Hillis


-Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 21 Jul 2008 7:32 pm
Subject: [computer-go] Incremental move weights


I'm starting heavy plyouts, with variable move selection weights. The proximity 
heuristic seems like a performance killer since most weights would require an 
update with each move.?
?
How do others handle this? Is proximity reserved for the search tree??
?
How do others store data for rapid lookup??
?
Sent from my iPhone?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] UCB/UCT and moving targets

[dhillismail]

> -Original Message-
> From: Jason House <[EMAIL PROTECTED]>
> On Jun 26, 2008, at 3:23 PM, [EMAIL PROTECTED] wrote:






Cool! Now for the cases where I'd want a Kalman filter, I'd need it to predict 
the future state of a non-stationary, multimodal distribution. A typical 
pattern is for a node to start out with optimistic scores but to experience a 
strong pessimistic trend later as UCT starts to focus more on effective enemy 
counter moves. Or the reverse, or sometimes a see-saw.





> The drift term is intended to take care of that kind of behavior.?


My limited experience is with objects moving in space, so please bear with me. 
The win rate is a 1 dimensional value analogous to a car moving on a road. If 
it has a constant velocity, we can model that with a Kalman filter having a 
drift rate. But if we assume a constant drift rate, we'll wind up with win 
rates greater than 1 or less than zero, right? When a car is at point A, for a 
while, then moves?to a final destination?point B, it has to (at least) 
accelerate for a while, then decelerate. In UCT, a new node will start with an 
initial win rate reflecting the fact that UCT is exploring moves fairly 
randomly, then settle eventually at a "final"?win rate where UCT would put it 
if it ran for a very long while.



Closer to the root, we are?seeing a superposition of many such distributions. 
My gut feeling is that the UCT tree is already doing a better job of what I'm 
asking the Kalman filter to do. But it's a nagging question for me.





> There's no way for a single floating point value to capture deeper structure.


Well, yes and no. There is more available than a single floating point number. 
You can, in fact, look at Monte Carlo go as a source separation problem. The 
sources are the values of the moves at the root, and the signals, the playouts, 
are mixtures of those sources. AMAF is a model that assumes very simple mixing 
of the sources in the playouts. But, maybe, this is a discussion for another 
day.

- Dave Hillis





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

Re: [computer-go] UCB/UCT and moving targets

[dhillismail]

Cool! Now for the cases where I'd want a Kalman filter, I'd need it to predict 
the future state of a non-stationary, multimodal distribution. A typical 
pattern is for a node to start out with optimistic scores but to experience a 
strong pessimistic trend later as UCT starts to focus more on effective enemy 
counter moves. Or the reverse, or sometimes a see-saw. Closer to the root, we 
are?seeing a superposition of many such distributions. My gut feeling is that 
the UCT tree is already doing a better job of what I'm asking the Kalman filter 
to do. But it's a nagging question for me.

Something, that actually has helped me, is to look at the difference of short 
term and long term averages as a diagnostic. For instance, when my program 
plays, I sometimes see the long term average at the root with a high score 
(probability of win), but the short term trend at the end showing a low score. 
When this happens, my program is in big trouble. One common cause is that the 
enemy has a winning sequence, but it involves making a self-atari move, or a 
monkey jump along the edge, or some other move that my progressive widening 
algorithm considers pathological and unworthy of early exploration.

-Dave Hillis

-Original Message-
From: Jason House <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 26 Jun 2008 2:00 pm
Subject: Re: [computer-go] UCB/UCT and moving targets



I probably exceeded my math quota already, but I should add that

? UCB = w + k*sqrt(P)




If k=a*sqrt(log(...)), this becomes:

? UCB = w + a*sqrt(log(...)*P)




Those looking for a drop into code, the above equation is what you'd want.




Note that if P = 0.25/n (from the no drift case), this should look nearly 
identical to typical UCT code...

? UCB = w + (a/2)*sqrt(log(...)/n)


On Jun 26, 2008, at 1:40 PM, "Jason House" <[EMAIL PROTECTED]> wrote:






On Thu, Jun 26, 2008 at 11:20 AM, <[EMAIL PROTECTED]> wrote:


You can use a windowed average where the window is a fixed fraction (say the 
last third) of the total times the move was made. I have often used an IIR 
filter and have never yet been able to prove that it actually helped. If I 
could write a decent Kalman filter, I would give that a try.

- Dave Hillis




Ooh, interesting idea!? I couldn't keep myself from working it out for the 
simplest of case of considering a single move in isolation with well-behaved 
noise.? At the end I show that this approach boils down to simple averaging of 
all samples when the drift is assumed to be zero.? I also give equations for 
updates that could be dropped into existing code.

Assuming a model of:
?? sample(n+1) = win_rate(n) + sample_noise
?? win_rate(n+1) = win_rate(n) + drift

sample = result of one monte carlo sim, 0 or 1
For simplicity, assume sample_noise and drift are stationary random processes
Most literature on UCT I see assumes variance(sample_noise) = 0.25

For the equations below, I'm going to use the following short hand:
? n = sample number
? s = sample(n+1)
? q = variance(sample_noise)?? (q for quantization)
? w = (estimated) win rate
? d = variance(drift)
? Other variables internal to the Kalman Filter:
? ?? P = estimation variance 
 K = gain
? 
That yields the following updates following each sample
? P = P + d
? K = P / (P + q)
? w = w + (s-w)*K
? P = (1-K)*P

If we assume d=0, and assume P has the form q/n before the sample, this becomes:
? w = w + (s-w)/n = (nw+s)/(n+1) = average of all samples
? P = q/(n+1)


= 


___
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] UCB/UCT and moving targets

[dhillismail]

You can use a windowed average where the window is a fixed fraction (say the 
last third) of the total times the move was made. I have often used an IIR 
filter and have never yet been able to prove that it actually helped. If I 
could write a decent Kalman filter, I would give that a try.

- Dave Hillis


-Original Message-
From: Peter Drake <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 26 Jun 2008 11:06 am
Subject: Re: [computer-go] UCB/UCT and moving targets


On Jun 26, 2008, at 1:35 AM, Magnus Persson wrote:?
?
> Quoting Peter Drake <[EMAIL PROTECTED]>:?
>?
>> UCB (and hence UCT) would treat the following sequences of wins >> (1) and?
>> losses (0) the same:?
>>?
>> 01010101010101010101010101010101?
>> ?
>> ?
>?
> I have two comments. Isn't the problem here that UCT will not > search the 
> second sequence at all because it is so bad initially??
?
Well, UCT never really discards a branch, just samples it less and less often. 
It would eventually go back to sequence 2 and discover that it had become good.?
?
> So will there ever be a situation like this? UCT will more likely > continue 
> to sample the first and third sequenc settling for the > first if their are 
> no change again. And when it finally discovers > that sequene 2 is good it 
> will quickly choose it.?
>?
> The second thing is that in practice you will rarely get any clear > patterns 
> like this so how would you be able to detect any recency??
?
I'm thinking of a situation where move A looks good when we're assuming a 
random response from the opponent, but once the child node starts using UCB, it 
is discovered that the opponent has a very good response, so now runs through A 
start losing. Later, runs through A start winning again because we discover a 
good counterresponse...?
?
> One simple trick is to always replay a move in the tree if it won > the last 
> time the position was visited, and only use UCT for > positions where the 
> last played moved lost. Should'nt this work > like a dream if sequence 2 
> truly goes to 100% winrate directly > after the wirst win is scored??
?
Probably, but we rarely get such pure victory branches. I have a number of 
schemes in mind, though.?
?
Has anyone tried this empirically??
?
Peter Drake?
http://www.lclark.edu/~drake/?
?
?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] 10k UCT bots

[dhillismail]

> -Original Message-
> From: Jacques Basaldúa <[EMAIL PROTECTED]>
> To: computer-go@computer-go.org
> Sent: Wed, 14 May 2008 6:38 am
> Subject: Re: [computer-go] 10k UCT bots


> Don Dailey wrote: 
 
> > [EMAIL PROTECTED] wrote: 
 
> >> For those currently coding this up, I think the most important thing 
>>>  about this playout algorithm is that it is 
>> >  *temporary*. You will  almost certainly be replacing it with something 
>>different and better 
>> > just a little bit down the road.  So you probably don't want to worry 
>> > about hair-splitting tweaks except as an academic exercise. 

> Yes, I agree. Also my hair brained scheme of pre-generated tables of
> > list traversal orderings was just an academic   exercise as you say.  

> But the problem is that when you do heavy playouts you have the same 
> problem except that the probabilities of the legal moves are no longer equal. 

The problem doesn't go away but the trade-offs change considerably. This is an 
interesting and relevant discussion, but if I were trying to code up light MC 
playouts for the first time, right now, I would be feeling that this 
dead-simple algorithm was actually very difficult and confusing. 

For someone in that position (and only them), my advice is
1. Implement light playouts first. It's simple; you will find many bugs that 
way; it's standardized enough that other people will understand what you're 
talking about; it's a fast way to get a basic bot; it will be a very handy 
thing to have as a baseline when you test other things.
2. Get it working the standard way before improving it. It's your baseline that 
you'll be testing improvements against.
3. Make it fast but don't spend excessive effort optimizing. "Better is the 
enemy of good enough." 

- Dave Hillis

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

Re: [computer-go] 10k UCT bots

[dhillismail]

For those currently coding this up, I think the most important thing about this 
playout algorithm is that it is *temporary*. You will almost certainly 
be?replacing it with something different and better just a little bit down the 
road.

Creating an MC-UCT bot has a well worn path and its kind of an ontology 
recapitulates phylogeny deal. First you implement light playouts (the random 
non-eyefilling moves people are describing), then you implement UCT, then you 
throw away the light playouts and replace them?with heavy playouts, then you 
start extreme modifications to UCT...

So you probably don't want to worry about hair-splitting tweaks except as an 
academic exercise.

- Dave Hillis


-Original Message-
From: Christoph Birk <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 13 May 2008 3:40 pm
Subject: Re: [computer-go] 10k UCT bots


On Tue, 13 May 2008, Mark Boon wrote:?
>>> If this asymmetry really bothers you, you could very easily fix this by?
>>> wrapping the search around. There's no asymmetry in a circle.?
>> >> That doesn't fix anything.?
>?
> Why not? The whole argument is about a bias against points towards the end. > 
> In a circular list there is no 'end'.?
?
No, it was a bias towards moves "behind" illegal moves.?
Those moves are twice as likely to be played than other moves. Consider a list 
with 5 moves:?
?
[Move1] [Move2] [Move3] [Move4] [Move5]?
?
You create a random number between 1 and 5. If Move2 is illegeal?
for example, then you will play?
?Move1 if random#=1?
?Move3 if random#=2 or 3,?
?Move4 =4?
?Move5 =5?
?
Move3 is twice as likely to be played. Even if you make a circular?
list.?
?
Christoph?
?
___?
computer-go mailing list?
[EMAIL PROTECTED]
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] Some beginner's questions concerning go bots

[dhillismail]

Hello,

> 3) What sort of algorithm is used to match patterns once you have mined them 
> from some data source? 

There are relatively few possible 3x3 patterns, so it is easy to make a look up 
table with an entry for every possible pattern. 

For larger patterns, it's more complicated. Mined patterns typically don't 
include don't cares. In that case, a?hash table works well. For patterns with 
don't cares, people have done this a lot of different ways. I don't think there 
is a consensus on the best way.

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

[computer-go] CGOS comment field. wasTest position set for MC programs

[dhillismail]

> -Original Message-
> From: Magnus Persson [EMAIL PROTECTED]

.> ..?
> A side note. Is it only me who are a little annoyed when strong programs play 
> with names that are impossible(for examlple 
> test-81725) to understand? Do not forget to add an entry on sensei at 
> http://senseis.xmp.net/?ComputerGoServer > 
> whenever you play with a new program on CGOS, it is much more fun to know who 
> is behind the programs and a short
> description of makes the program tick.?

I have a CGOS feature request. Something complementary to the CGOS information 
on Senseis. I would like the client to have an optional field to designate a 
"comments" text file. The file would contain a sentence or two describing the 
particular version of the engine running: the kind of information that we try 
to cram into the name, but less cryptic. The engine's Crosstable page?on the 
CGOS web site?might be a good place to display the comment.

I think the threshold for editing a comment file on one's own computer is lower 
then for editing a wiki page.

- Dave Hillis



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

Re: [computer-go] Test position set for MC programs

[dhillismail]

AntIgo
light playouts
1K    14 / 50
10K  25 / 50
100K 29 / 50
heavy playouts
1K    25 / 50
10K  32 / 50
100K 35 / 50

The numbers are noisey, because I'm too lazy to average multiple trials. In 
some cases, my engine picks the correct move (and I score it as correct), but 
it also thinks that black is so far behind that it should politely resign :-\

- Dave Hillis

-Original Message-
From: Gunnar Farnebäck <[EMAIL PROTECTED]>
To: computer-go 
Sent: Wed, 23 Apr 2008 3:33 pm
Subject: Re: [computer-go] Test position set for MC programs


Yamato wrote: 
> Thanks Gian-Carlo, Gunnar. 
> 
> Current list of results. 
> 
> GNU Go 3.7.12 level 0 : 24/50 
> GNU Go 3.7.12 level 10 : 34/50 
> GNU Go 3.7.12 level 15 : 37/50 
> GNU Go 3.7.12 mc, 1k : 30/50 
> GNU Go 3.7.12 mc, 10k : 31/50 
> GNU Go 3.7.12 mc, 100k : 38/50 
> GNU Go 3.7.12 mc, light, 1k : 33/50 
> GNU Go 3.7.12 mc, light, 10k : 30/50 
> GNU Go 3.7.12 mc, light, 100k : 25/50 
> GNU Go 3.7.12 mc, mogo, 1k : 34/50 
> GNU Go 3.7.12 mc, mogo, 10k : 33/50 
> GNU Go 3.7.12 mc, mogo, 100k : 35/50 
> Leela 0.3.14, 1k : 19/50 
> Leela 0.3.14, 10k : 28/50 
> Leela 0.3.14, 100k : 36/50 
> Zen 1.5, 1k : 19/50 
> Zen 1.5, 10k : 22/50 
> Zen 1.5, 100k : 24/50 
> 
> Leela seems to have good scalability. 36/50 passes is fine. 
> The results of GNU Go are a bit irregular because of its hybrid 
> strategy. If GNU Go could run on the MC only mode, it might be more 
> interesting, I guess. 
 
Ok, I patched out the contributions from normal move generation in the 
final move selection (but there's still some influence on UCT tree 
move ordering), giving this list: 
 
  Only MC 
GNU Go 3.7.12 level 0 : 24/50 - 
GNU Go 3.7.12 level 10 : 34/50 - 
GNU Go 3.7.12 level 15 : 37/50 - 
GNU Go 3.7.12 mc, 1k : 30/50 14/50 
GNU Go 3.7.12 mc, 10k : 31/50 29/50 
GNU Go 3.7.12 mc, 100k : 38/50 35/50 
GNU Go 3.7.12 mc, light, 1k : 33/50 7/50 
GNU Go 3.7.12 mc, light, 10k : 30/50 14/50 
GNU Go 3.7.12 mc, light, 100k : 25/50 22/50 
GNU Go 3.7.12 mc, mogo, 1k : 34/50 14/50 
GNU Go 3.7.12 mc, mogo, 10k : 33/50 21/50 
GNU Go 3.7.12 mc, mogo, 100k : 35/50 34/50 
 
/Gunnar 
___ 
computer-go mailing list 
[EMAIL PROTECTED]
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] scalability with the quality of play-outs.

[dhillismail]

Don,
 You may, very well, turn out to be right in the end, but I think you are 
getting ahead of the data here. And it isn't at all clear to me to how 
meaningfully we can compare strength of playouts with strength of alpha-beta 
evaluators.

 This continues to be a very interesting study and I thank you and the 
people contributing computer time to it.

- Dave Hillis


-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 21 Apr 2008 11:46 am
Subject: [computer-go] scalability with the quality of play-outs.



It looks like we have a clear trend now.   Light play-outs do not scale
as well as heavy play-outs.   

This is the same behavior we get with computer chess.   For the last few
decades it has been understood that a chess program with a better
evaluation function  improves MORE with increasing depth than one with a
lesser evaluation function so it appears that Go is not unique in this
regard or in it's general ability to scale with CPU power.

Here are the latest results:

  http://cgos.boardspace.net/study/13/index.html


- 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] Automated genetic parameters tuning

[dhillismail]

It's almost always better to just write your own. Or you might want to consider 
using a particle swarm optimizer instead.
http://www particleswarm.info/Standard_PSO_2006.c?has source code I found 
useful.
http://www.particleswarm.info/Programs.html?has lots of other implementations 
to choose from.

Either way, coding it up is easy; deciding on a practical fitness function is 
hard.

- Dave Hillis

-Original Message-
From: Petr Baudis <[EMAIL PROTECTED]>
To: computer-go@computer-go.org
Sent: Fri, 7 Mar 2008 6:41 pm
Subject: [computer-go] Automated genetic parameters tuning



  Hi,

  does anyone know of any pre-made open framework using genetic
algorithms that one could use to tune various parameters of a bot? I
have about 6 independent parameters for my bot so far that I would like
to find best values for (from domain-specific knowledge hint rates to p
parameter of the UCB1 formula), and I would hate to do redundant work
implementing such a framework on my own.

  Thank you,

-- 
Petr "Pasky" Baudis
Whatever you can do, or dream you can, begin it.
Boldness has genius, power, and magic in it.-- J. W. von Goethe
___
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: [EMAIL PROTECTED]: Re: [computer-go] Should 9x9 komi be 8.0 ?

[dhillismail]

An alternative (also maddening to tune) is to make the playout strength 
asymmetrical. For a high handicap game, making the playout rules for black 
stones lighter (more random) can make the bot play serious moves where 
otherwise it would see every move as having the same outcome. The implicit 
assumption, that the color that's ahead is blunder prone, is justified: those 
handicap stones are there for a reason.

My subjective impression is that it's hard to make things better, very easy to 
make things worse, and it's probably best only to do this when one color has a 
much stronger position.

Discussion of asymmetric playouts, and the general "balance of stupidity," 
principle crops up here, from time to time.

- Dave Hillis

-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 28 Feb 2008 1:01 pm
Subject: Re: [EMAIL PROTECTED]: Re: [computer-go] Should 9x9 komi be 8.0 ?]




Hideki Kato wrote:
> Don Dailey: <[EMAIL PROTECTED]>:
>   
>> [EMAIL PROTECTED] wrote:
>> 
 I experimented with something similar a while ago, using the
 publicly available mogo and manipulating komi between moves.

 If its win probability fell below a certain threshold (and the move
 number wasn't too high), I told it to play on the assumption that it
 would receive a few points more komi (and similarly when the win
 probability became high).
 
 
>>> That's certainly a nice solution !
>>>
>>> It's probably easy to implement, and relatively easy to tune.
>>>
>>> Now, the question is: did it seem stronger to our eyes because it played
>>> more human-like ?
>>>   
>>>   
>> I experimented with this idea extensively a while back and never found
>> an implementation that improved it's playing ability.In fact every
>> version played weaker.I tried versions that dynamically adjusted
>> komi during the course of a game when things looked close to hopeless
>> (or certain) and I came to the eventual conclusion that whenever you
>> didn't use the correct komi,  you were in fact decreasing it winning
>> chances. If you tell it that is not winning when it really IS
>> winning by 1/2 point,  then there will be games where it plays stupid
>> desperate moves when it doesn't have to. 
>>
>> If it is almost losing and you tell it (by adjusting komi) that it has a
>> good chance,  it will tend to lose with a higher score,  but you have
>> essentially treated it as a spoiled child,  lowering your expectations
>> for it and it is happy to play with the new goal of losing.  
>>
>> This whole concept is based on what appears to be a flawed idea,  
>> deceive the program into believing something that isn't true in the
>> hopes that it will somehow make it play better.   
>> 
>
> I don't agree. If the estimated score by playouts had no error, you 
> were correct.
>   

It's not about the error - it's about the side-effects of trying to
second guess the cure.My grandmother used to think castor oil was
the solution to every illness.   

It's naive to think some simplistic deception imposed upon the program
is going to correct the error when you don't even know if the program is
erring in the first place. How can you say,  "the program thinks it
is losing, but it MUST be in error and I'm going to change the komi so
that it will 'play better'?"You must have some basis for knowing the
program is in error before you can lower it's goal.  

You have basically 2 cases when losing.   One case is that the program
really is busted and is in a dead lost position.The other case is
that the program THINKS it's lost but really is winning (or at least has
excellent chances.) In the first case,  we are simply playing for a
miracle,  hoping that if we lower our expectations the opponent will
falter. This is at best a speculative and extremely minor
enhancement if we can even make it work and I argue that it also imposes
risks of it's own.Unless the score is actually zero in every line, 
the program is going to play for any outside chance of a win,  no matter
how small.   Telling it that a big loss is good enough will cause it to
play safer, not more aggressively like you think.  (Yes, you can
hand pick specific positions where you can "trick" it into doing the
right thing, but that is "cooking the books", it's not a real solution.) 
 
The other case is that the program really isn't losing even though it
thinks it is dead busted.How does the program know this is really
the case?If it knew that, your program would be better.So you
don't even know why it thinks it's busted.Even so,  I argue that
telling it to accept less than what is required to win is risky and will
lose more games than it will win  (which isn't very many since it almost
certainly losing anyway.)

So the bottom line is that you are trying to make it play better in
positions where it is probably dead lost.   That is a noble cause worth
a tiny gain in

Re: [computer-go] Re: computer-go Digest, Vol 43, Issue 8

[dhillismail]

>? -Original Message-
>? From: Don Dailey <[EMAIL PROTECTED]>
>? To: computer-go 
>? Sent: Mon, 18 Feb 2008 1:45 pm
>? Subject: Re: [computer-go] Re: computer-go Digest, Vol 43, Issue 8


> ...I have seen widely held beliefs be proven wrong before
>  (the earth is flat is one example.)  













You are older than I thought. :-) On a more serious note, what is the status of 
the scalability study?
- Dave Hillis
   




More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] gpugo

[dhillismail]

Hi Florian,

?

 That sounds like an interesting project. I've looked at this a little. If 
it were me, I would start by implementing the simplest possible MC playouts in 
gpgpu,?as efficiently as possible, before looking at adding things like 
patterns.?

 I also heartily encourage you to learn about genetic algorithms. (But?not 
really because of?RAVE.)

- Dave Hillis

-Original Message-
From: Florian Erhardt <[EMAIL PROTECTED]>
To: computer-go 
Sent: Mon, 11 Feb 2008 4:06 pm
Subject: [computer-go] gpugo



Hello !?
?
My name is Florian Erhardt, I am a bachelor student of computer sciences and am 
in the process of optimizing libEGO for gpgpu. For now I implemented the SFMT 
(even I can do copy and paste) on the gpu and am now atomizing the MC to be 
done by the gpu. If everything works as I planned it, I'll have a releasable 
program in a few months (I still have to learn lots about parallelizing, gpu 
programming and programming in general [maybe leaning about genetic algorithms 
can't hurt either - The RAVE algorithm is more like a genetic algorithm - Right 
?] - and I have to go to university :-) ).?
?
For now I'm using a MC-engine with UCT, trying out how much patterns and other 
things might make the results better.?
Now as I understand it, using patterns, groupstatus, ... during the MC-playout 
makes the results from the playout more meaningful (stronger - 30k instead of 
random), so if I would make the playout with a small engine (the easiest way to 
use the power of the gpu) the result should be more meaningful too. Has anyone 
done any test like that (like use gnugo level 0 instead of an MC-playout) ? 
Does anyone have a minimalistic non-MC go engine I could look at ? One more 
thing - has anyone tried using quasi-MC for go ??
?
Well - that's all folks.?
?
mfg?
?
Florian Erhardt?
___?
computer-go mailing list?
[EMAIL PROTECTED]
http://www.computer-go.org/mailman/listinfo/computer-go/?



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions

[dhillismail]

That's very interesting. RAVE, as described in the Mogo paper, incorporated 
some priors and gave a progressive widening effect. Have you looked at 
progressive widening with and without RAVE? Could you provide some details 
about how you made it work?

-Dave Hillis

-Original Message-
From: Hideki Kato <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 5 Feb 2008 9:39 pm
Subject: Re: [computer-go] More UCT / Monte-Carlo questions



My program ggmc has been improved about 300 ELO by RAVE.
-Hideki
Gunnar Farnebäck: <[EMAIL PROTECTED]>:
David Fotland wrote:
 > Can you elaborate on what is in a node, and what you mean by expand?   I
 > assume you have simple node, where each node represents a position and
 > the single move to get there.  Then when you find a node with no
 > children and expand it, you allocate up to 81 new nodes, but you only
 > make one random playout.  If uct picks a different leaf next time, you
 > end up with most of the leaf nodes never visited.  In this case you run
 > out of memory quickly.  If there are a few hundred K playouts to pick a
 > move, and 90% of the leaves have no visits, then you need over a million
 > nodes of memory.
 >
 >
 >
 > How do other programs handle this?  I see that aya has an array of all
 > children in each node.  This still means allocating memory for all
 > children when a new node is allocated.

MonteGNU has a linked list of visited children and a bitboard marking
moves which have not yet been visited. A new node is created without
children and the bitboard marks all possible moves.

 > It think many programs run several simulations through a node before
 > allocating the children.  I can see how this saves memory, but then how
 > do you save the RAVE information from the early simulations?

I have never managed to implement RAVE successfully. It made my
program significantly slower but no stronger even at a fixed number of
simulations.

/Gunnar
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
-
[EMAIL PROTECTED] (Kato)
__
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] More UCT / Monte-Carlo questions

[dhillismail]

Lots of good information here. In particular, I notice that my program has the 
explore needless captures in progressive widening weakness described below. My 
thanks to Magnus (and Remi, of course) for pointing it out. I'll fix that and 
then, I guess, I'll have to revisit the issue of reading ladders in playouts.

I think I get a worthwhile improvement from using UCB-Tuned over ordinary UCT. 

I haven't had any luck with RAVE, so far. I can break even, but I can't get a 
net?advantage from it.

- Dave Hillis

-Original Message-
From: Magnus Persson <[EMAIL PROTECTED]>
To: computer-go@computer-go.org
Sent: Tue, 5 Feb 2008 12:47 pm
Subject: Re: [computer-go] More UCT / Monte-Carlo questions


I cannot comment on why Orego does things in a certain way, but you adress 
things I guess make everybody doing UCT/MC scratch their heads.?
?
Quoting Mark Boon <[EMAIL PROTECTED]>:?
?
>?
> - It computes the UCT value in a completely different way. A comment?
> in the code refers to a paper called "Modification of UCT with?
> Patterns in Monte-Carlo Go". I haven't studied this yet, but whatever?
> it does it apparently doesn't do wonders over the standard C * sqrt (?
> (2*ln(N)) / (10*n) ) that I use.?
?
Although MoGo may benefit from a modified UCT it does not mean that light 
playouts do. With light playouts one has to search wide to overcome strong bias 
in every position. With heavy playouts my theory right now is that one can go 
much more seletive. And it also depends on other tricks one is using. I am 
experimenting with Valkyria 3 right know where C is optimal as 0.001 right know 
(but it is biased to search wide initially by "assumed priors"-trick). In 
Valkyria 2 this constant is 0.8 and earlier when the playouts were lighter I 
think it was 1.8.?
?
My guess is that what you are doing things right, and should be careful adding 
stuff without testing. But later on you might benefit from trying alternatives 
to UCT.?
?
> - It only initialises the list of untried moves in the tree after a?
> node had a minimum run-count of 81 (on 9x9). For the life of me I?
> couldn't figure out what the effect of this was or what it actually?
> does. I was wondering if this has an effect of what is counted as a?
> 'run' but I'm not sure.?
?
In Valkyria nodes are visited 7 times before expanding. Less and more than that 
makes the program weaker. I would like it to be more because it would save 
memory.?
?
> Then I found a paragraph (4.2) in Remi Coulomn's paper about ELO?
> raings in patterns. It briefly describes it as "As soon as a number of?
> simulations is equal to the number of points on the board, this node?
> is promoted to internal node, and pruning is applied." I can't help?
> feeling that the implementation in Orego is doing this. But I can't?
> figure out where it does any pruning or applying patterns of any kind.?
> Is there supposedly a general benefit to this even without pruning or?
> patterns? As stated before, at least it doesn't seem to provide any?
> benefit over my more primitive implementation. Maybe Peter Drake or?
> someone else familiar with Orego knows more about this??
?
I believe CrazyStone calculate "owner-at-end"statistics for each point on the 
board before applaying patterns and determine the move order for progressive 
widening. For the patterns it needs 64 runs to give priority to points on the 
board that is unstable (and with a bias towards defending own territory).?
?
> Anyway, reading the same paragraph mentioned above again I was struck?
> by another detail I thought surprising: after doing the required?
> number of runs, the candidates are pruned to a certain number 'n'?
> based on patterns. Does that mean from then on the win-ratio is?
> ignored? What if the by far most successful move so far does not match?
> any pattern? Am I misunderstanding something here? The paragraph is?
> very brief and does not elaborate much detail.?
?
There are two possible ways of implementing the tree. One is with lightweight 
nodes containg info only about the move and a pointer to all children. The 
other one is with supernodes that contains the information for all moves in a 
given position. In the former case the information for first runs through the 
node is lost (actually the children are random playout moves) in the latter 
case all information is recorded and one should not prune winning nodes. What I 
mean here is that there are two possible interpretations of what terminal node 
might mean, and if Orego does one thing and you something else you are bound to 
be confused.?
?
In valkyria 3 I do move ordering as soon as a supernode is created. But as I 
wrote above move ordering might become even better if it is delayed about 
50-100 runs if useful statistics can be collected from the playouts other than 
the winrate itself.?
?
> On to my next step I introduced some very basic tactics to save stones?
> with one liberty, capture the opponent's stones with one liberty and?
> capturing the opp

Re: [computer-go] not "Go knowledge and UCT"

[dhillismail]

That's an interesting story. I just wish I hadn't precipitated it by sharing my 
blinding flash of the obvious with the whole list. You are correct, of course. 
I got so focused on something that I didn't see the forest for the trees. 

- Dave Hillis

-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 31 Jan 2008 3:20 pm
Subject: Re: [computer-go] not "Go knowledge and UCT"




This is the famous horizon effect chess programs are suckers for.
One interesting example of it happened to my program in a human
tournament years ago.

It played the classic Bxa7 getting it's bishop trapped by b6.  
Computers used to be real suckers for this because it wins a pawn,  but
eventually the bishop, which has no where to go, will get captured.  It
has to see deeply enough to realize this.

It gets particular ugly when it only takes a couple of moves to capture
the bishop,  but the computer pushes the inevitable over it's "horizon"
with spite checks, and useless attacking moves,  which to the program
appears to "save" the bishop.   

In this case, it "sacked" a pawn to get a vicious attack in order to
delay the "loss" of the bishop.

As it turned out after later analysis,  the pawn capture was actually
the winning move after all, but the program did it for the entirely
wrong reasons.   The attack would not have worked if the bishop had not
moved, the pawn sacrifice was brilliant and there was not way to refute
the attack. Nevertheless, the program was simply fighting for it's
life - the whole vicious assault was not for the sake of the attack
itself but a desperate measure to delay the capture of the bishop.  

People watching the game believed the computer had played absolutely
brilliantly and didn't realize the whole thing was just self-deception
by the computer.

It's funny that a similar thing had happened to Bobby Fischer against
Spassky in 1972.Fischer took the pawn on h2 and everyone gasped.  
This move was talked about for a long time.It started out as being
called a stupid blunder,  a beginners error and so on.   But the move
actually had some good points.This move was Fischers way of pressing
for win in a basically drawn endgame and even though Fischer lost that
game, it was due to a blunder later in the game.The move itself
probably wasn't a blunder although it wasn't a winning move either.   
It probably was the best try for a win.

- Don




[EMAIL PROTECTED] wrote:
>
> A few trick moves in a row can cause problems. But the cases where I
> am most likely to be watching my bot's play through my fingers are
> when there is an obvious (to a 20 Kyu like me) situation but it's some
> plys in the future. (Or it can be pushed into the future!)
>
> A case of seki is easy for my tree search with UCT to handle. For
> external playouts, it's likely to be played wrong. So what does my bot
> do? Each color learns not to play into the seki at shallow, internal,
> nodes. They play somewhere else on the board, often totally pointless
> moves. But when, inevitably, play hits external nodes, one side or the
> other plays into the seki. I can tweak the policy for self-atari
> moves, but that just moves the problem elsewhere-it misplays more
> nakade situations.
>
> The real issue is that UCT (or any tree-search with MC) tends to push
> confusing board situations into the future where they will be dealt
> with using playout logic. It's not hard to hit local board situations
> where tree search would lead to a win for white, but playout logic
> would give black an edge. Black responds (sorry for anthropomorphism)
> by making distracting moves elsewhere on the board, deferring the
> situation to later plys. It's a bit like a ko fight with a huge supply
> of kos.
>
> - Dave Hillis
>
> -Original Message-
> From: Don Dailey <[EMAIL PROTECTED]>
> To: computer-go 
> Cc: Joe Cepiel <[EMAIL PROTECTED]>; Chris Hayashida
> <[EMAIL PROTECTED]>
> Sent: Thu, 31 Jan 2008 1:25 pm
> Subject: Re: [computer-go] Go knowledge and UCT
>
>
>
> terry mcintyre wrote:
> >
> > I may have misunderstood, so please clarify a point.
> >
> > Let's say the game hinges on solving a life-and-death problem - if you find 
> the right move, you win the game; if not, you lose. Many such problems - as 
> found in real games - are extremely order-dependent; there is exactly one 
right 
> way to begin the sequence; all other attempts fail. It is not unusual for a 
> sequence to be ten, twenty or thirty moves long, and to lead to an absolutely 
> provable result no matter how the opponent may twist and turn.
> >
> > Does "when the depth is great enough they are still considered" mean that 
> > an 

> unlikely move would not be considered for move A at the top of the tree, but 
> would be considered for move E or F, perhaps? Or have I misunderstood?
> >   
> The top of the tree is moves near the root since the tree is normally
> displayed upside down in computer science.So moves closer to t

Re: [computer-go] not "Go knowledge and UCT"

[dhillismail]

Right you are. Silly me.


-Original Message-
From: Álvaro Begué <[EMAIL PROTECTED]>
To: computer-go 
Sent: Thu, 31 Jan 2008 3:06 pm
Subject: Re: [computer-go] not "Go knowledge and UCT"





On Jan 31, 2008 2:59 PM, <[EMAIL PROTECTED]> wrote:

I'm going to call this the "procrastination effect." MY claim is that, when 
MC-UCT encounters a critical life and death board situation that its playout 
policy consistently gets wrong, the search will naturally tend to skew the tree 
so that relevant moves continue to be made during the playouts.


This has traditionally been called the "horizon effect".







___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] not "Go knowledge and UCT"

[dhillismail]

I'm going to call this the "procrastination effect." MY claim is that, when 
MC-UCT encounters a critical life and death board situation that its playout 
policy consistently gets wrong, the search will naturally tend to skew the tree 
so that relevant moves continue to be made during the playouts.

- Dave Hillis


-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Thu, 31 Jan 2008 2:18 pm
Subject: Re: [computer-go] not "Go knowledge and UCT"



A few trick moves in a row can cause problems. But the cases where I am most 
likely to be watching my bot's play through my fingers are when there is an 
obvious (to a 20 Kyu like me) situation but it's some plys in the future. (Or 
it can be pushed into the future!) 

A case of seki is easy for my tree search with UCT to handle. For external 
playouts, it's likely to be played wrong. So what does my bot do? Each color 
learns not to play into the seki at shallow, internal, nodes. They play 
somewhere else on the board, often totally pointless moves. But when, 
inevitably,?play hits external nodes, one side or the other plays into the 
seki. I can tweak the policy for self-atari moves, but that just moves the 
problem elsewhere-it misplays more nakade situations. 

The real issue is that UCT (or any tree-search with MC)?tends to push confusing 
board situations into the future where they will be dealt with using playout 
logic. It's not hard to hit local board situations where tree search would lead 
to a win for white, but playout logic would give black an edge. Black responds 
(sorry for anthropomorphism) by making distracting moves elsewhere on the 
board, deferring the situation to later plys. It's a bit like a ko fight with a 
huge supply of kos.

- Dave Hillis

-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Cc: Joe Cepiel <[EMAIL PROTECTED]>; Chris Hayashida <[EMAIL PROTECTED]>
Sent: Thu, 31 Jan 2008 1:25 pm
Subject: Re: [computer-go] Go knowledge and UCT





terry mcintyre wrote:
>
> I may have misunderstood, so please clarify a point.
>
> Let's say the game hinges on solving a life-and-death problem - if you find 
the right move, you win the game; if not, you lose. Many such problems - as 
found in real games - are extremely order-dependent; there is exactly one right 
way to begin the sequence; all other attempts fail. It is not unusual for a 
sequence to be ten, twenty or thirty moves long, and to lead to an absolutely 
provable result no matter how the opponent may twist and turn.
>
> Does "when the depth is great enough they are still considered" mean that an 
unlikely move would not be considered for move A at the top of the tree, but 
would be considered for move E or F, perhaps? Or have I misunderstood?
>   
The top of the tree is moves near the root since the tree is normally
displayed upside down in computer science.So moves closer to the top
of the tree are more likely to be considered.   The vast majority of
time is spent near the leaf nodes, and so it makes sense to prune more
aggressively near leaf nodes.Eventually, leaf nodes become nodes
closer to the root as the tree expands beyond them.

So if the first move of the sequence is hard to find but the rest are
reasonably normal moves,  the situation is not so bad.An example of
this might be a critical move to a 1 point eye where the program uses
progressive pruning and doesn't even consider the move for a while.   
In such a case the problem might still be solved in a reasonable amount
of time once some "more likley" moves are first exhausted.  

If the problem is such that many "unusual" moves must be discovered, 
moves that are normally bad patterns for instance,  then a UCT program
would truly have a difficult time with this position.   In theory it HAS
to eventually recover but of course we can find positions where this is
arbitrarily difficult for UCT. But you must understand that as you
get more difficult,  it takes more human expertise also.   So it's not
fair to fixate on just what the computers limitations are. I believe
humans are very very far away from perfect play themselves and "god"
could construct problems that would also give us fits. 

When go computers get into the several Dan strength level,   you will
start to see that they can do some things far better than humans but
will still have some obvious weaknesses that seem silly to us.   But
the only thing that matters is whether they can win. That's the
"bottom line" as the old timers like to say.

> Here are pointers to pictures of some real-life problems on the 19x19 board; 
these happened in actual play at the recent Oza 2008 West tournament.
>
> Black to play and capture 5 stones: 
> http://picasaweb.google.com/terry.mcintyre/OzaWest2008/photo#5158560976542534642
>
> What is the status of the white stones in the corner? 
> http://picasaweb.google.com/terry.mcintyre/OzaWest2008/photo#5158566963726945906
>
> White to play

Re: [computer-go] not "Go knowledge and UCT"

[dhillismail]

A few trick moves in a row can cause problems. But the cases where I am most 
likely to be watching my bot's play through my fingers are when there is an 
obvious (to a 20 Kyu like me) situation but it's some plys in the future. (Or 
it can be pushed into the future!) 

A case of seki is easy for my tree search with UCT to handle. For external 
playouts, it's likely to be played wrong. So what does my bot do? Each color 
learns not to play into the seki at shallow, internal, nodes. They play 
somewhere else on the board, often totally pointless moves. But when, 
inevitably,?play hits external nodes, one side or the other plays into the 
seki. I can tweak the policy for self-atari moves, but that just moves the 
problem elsewhere-it misplays more nakade situations. 

The real issue is that UCT (or any tree-search with MC)?tends to push confusing 
board situations into the future where they will be dealt with using playout 
logic. It's not hard to hit local board situations where tree search would lead 
to a win for white, but playout logic would give black an edge. Black responds 
(sorry for anthropomorphism) by making distracting moves elsewhere on the 
board, deferring the situation to later plys. It's a bit like a ko fight with a 
huge supply of kos.

- Dave Hillis

-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Cc: Joe Cepiel <[EMAIL PROTECTED]>; Chris Hayashida <[EMAIL PROTECTED]>
Sent: Thu, 31 Jan 2008 1:25 pm
Subject: Re: [computer-go] Go knowledge and UCT





terry mcintyre wrote:
>
> I may have misunderstood, so please clarify a point.
>
> Let's say the game hinges on solving a life-and-death problem - if you find 
the right move, you win the game; if not, you lose. Many such problems - as 
found in real games - are extremely order-dependent; there is exactly one right 
way to begin the sequence; all other attempts fail. It is not unusual for a 
sequence to be ten, twenty or thirty moves long, and to lead to an absolutely 
provable result no matter how the opponent may twist and turn.
>
> Does "when the depth is great enough they are still considered" mean that an 
unlikely move would not be considered for move A at the top of the tree, but 
would be considered for move E or F, perhaps? Or have I misunderstood?
>   
The top of the tree is moves near the root since the tree is normally
displayed upside down in computer science.So moves closer to the top
of the tree are more likely to be considered.   The vast majority of
time is spent near the leaf nodes, and so it makes sense to prune more
aggressively near leaf nodes.Eventually, leaf nodes become nodes
closer to the root as the tree expands beyond them.

So if the first move of the sequence is hard to find but the rest are
reasonably normal moves,  the situation is not so bad.An example of
this might be a critical move to a 1 point eye where the program uses
progressive pruning and doesn't even consider the move for a while.   
In such a case the problem might still be solved in a reasonable amount
of time once some "more likley" moves are first exhausted.  

If the problem is such that many "unusual" moves must be discovered, 
moves that are normally bad patterns for instance,  then a UCT program
would truly have a difficult time with this position.   In theory it HAS
to eventually recover but of course we can find positions where this is
arbitrarily difficult for UCT. But you must understand that as you
get more difficult,  it takes more human expertise also.   So it's not
fair to fixate on just what the computers limitations are. I believe
humans are very very far away from perfect play themselves and "god"
could construct problems that would also give us fits. 

When go computers get into the several Dan strength level,   you will
start to see that they can do some things far better than humans but
will still have some obvious weaknesses that seem silly to us.   But
the only thing that matters is whether they can win. That's the
"bottom line" as the old timers like to say.

> Here are pointers to pictures of some real-life problems on the 19x19 board; 
these happened in actual play at the recent Oza 2008 West tournament.
>
> Black to play and capture 5 stones: 
> http://picasaweb.google.com/terry.mcintyre/OzaWest2008/photo#5158560976542534642
>
> What is the status of the white stones in the corner? 
> http://picasaweb.google.com/terry.mcintyre/OzaWest2008/photo#5158566963726945906
>
> White to play; can the black group at the bottom middle be killed? 
http://picasaweb.google.com/terry.mcintyre/OzaWest2008/photo#5158572701803253954
>
> What is the status of the black group at the top? 
> http://picasaweb.google.com/terry.mcintyre/OzaWest2008/photo#5158572860717043922
>
> Black to play: who wins the capturing race between the large black dragon and 
the white group in the bottom right / center ? 
> http://picasaweb.google.com/terry.mcintyre/OzaWest2008/photo#5158579148549165890

Re: [computer-go] 19x19 Study - prior in bayeselo, and KGS study

[dhillismail]

> From: Don Dailey <[EMAIL PROTECTED]>
> ...
> > Rémi Coulom wrote:
> > ...
> > Instead of playing UCT bot vs UCT bot, I am thinking about running a
> > scaling experiment against humans on KGS. I'll probably start with 2k,
> > 8k, 16k, and 32k playouts.

> That would be a great experiment.   There is only 1 issue here and
> that's time control.   I would suggest the test is more meaningful if
> you use the same time-control for all play-out levels, even if Crazy
> Stone plays really fast.    This is because the ELO curve for humans is
> also based on thinking time.  

> If you set the time control at just the rate the program needs to use
> all it's time,    you might very well find the program plays better at
> fast time controls, it would be meaningless even as a rough measurement
> of ELO strength.


In addition to having all versions of the program use the same time control, I 
think it would be best if they all made their moves at the same rate. When 
humans play against a bot playing at a fast tempo, they tend to speed up 
themselves regardless of the time limits. The human's pondering is also a 
factor.

I've noticed this in games on KGS; a lot of people lose games with generous 
time limits because they, rashly, try to keep up with my dumb but very fast bot 
and make blunders.

- Dave Hillis




More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Some thoughts about Monte Carlo

[dhillismail]

If you like heavy playouts, you will love progressive widening. It all comes 
down to move prioritization and it's OK if it takes a little time to calculate. 
If I had a good traditional program (and I wish I did) I would focus my efforts 
to combine it with UCT-MC?here.

I found it helpful to read these 2 papers (about CrazyStone and Mango) 
side-by-side.
http://remi.coulom.free.fr/Amsterdam2007/MMGoPatterns.pdf?section 4.2 especially
and 
http://www.cs.unimaas.nl/g.chaslot/papers/pMCTS.pdf
Mogo does it too, though from a different angle.
http://www.machinelearning.org/proceedings/icml2007/papers/387.pdf

About the mercy rule: When it is invoked, it doesn't only shorten the playout, 
but it also obviates the need to score the board. That might help explain your 
timing measurements. It has one significant drawback in that it will mess up 
any statistics re. percentage of time black owns a position on the board. I 
think it is safe to set a relatively aggressive threshold in the beginning game 
(the actual game), but best to tighten it up later, when mistakes are more 
likely to favor one side over the other.

- Dave Hillis

-Original Message-
From: Mark Boon <[EMAIL PROTECTED]>
To: computer-go 
Sent: Fri, 18 Jan 2008 8:03 am
Subject: [computer-go] Some thoughts about Monte Carlo


I'm fairly new on the subject of Monte Carlo and am in the process of catching 
up on reading, so I hope you guys have some patience with me while I get into 
this and ask a lot of questions. I got side-tracked away from computer-Go 
programming for quite a while for various reasons but have been at it again 
full-time recently.?
?
Let me start by saying I haven't followed the whole Monte-Carlo / UCT story all 
that well. Although it was clear it did well on 9x9 I wasn't all that convinced 
it would scale up to 19x19. That it did well on 9x9 didn't surprise me much as 
I've always felt 9x9 is susceptible to see strong play using some extreme 
brute-force method using today's computing power.?
?
Combining Monte-Carlo methods with what's generally called "heavy playouts" 
changes things a lot however and this is where it piqued my interest. I often 
see reference to Monte-Carlo programs as opposed to "traditional" Go programs. 
But what I'm seeing with the heavy playouts is "deja-vu all over again". It 
seems to me the evolution of the heavy playouts is following a similar course 
of that of the first rule-based Go programs in the early 1980's. To use another 
famous quote "history doesn't repeat itself but it rhymes."?
?
So I wouldn't be surprised at all if at some point you'll see a marriage of the 
best ideas of traditional Go programs and Monte-Carlo / UCT. In fact, this is 
most likely already happening as these Monte-Carlo programs use algorithms / 
ideas from the traditional programs for tactics, pattern-matching and possibly 
others.. And I go out on a limb to predict that at some point "heavy playouts" 
will use information like territory, eye-space and group-strength to guide 
their playouts just like the "traditional" programs do. And that using fixed 
3x3 patterns will be a passing fad.?
?
Anyway, as it is I have made a few initial forrays into Monte-Carlo algorithms. 
I hereby thank Peter Drake on his work on Orego, which is a fine package to 
learn about Monte-Carlo. I used it to make my own implementation. Not that 
there was much wrong with Orego but the best way to understand and internalize 
a concept is to actually implement it. Moreover I felt I needed a framework 
that is a bit more generalized than Orego. Lastly I was convinced of course 
that I'd be able to make it faster. That last part didn't turn out to be true 
though. On my iMac, which is a 2Ghz Core Duo, I get a little under 30K playouts 
on 9x9. A little over 50K when using both cores. Orego is in the same 
ball-park. At least making a more generalized implementation didn't hurt 
performance so I'm OK with this first attempt. I think there's still room for 
optimizations, if I thought it was important at this stage.?
?
This comes to my first point. Optimizing early in a project is like listening 
to the devil. It eats up a lot of time, the visible progress is gratifying but 
in the grand scheme of things it's not all that important to do early. I 
implemented it using pseudo-liberties because... uh, well, because that's what 
everyone seemed to be doing to get high numbers of playouts per second. But I 
already start to doubt using pseudo-liberties are all that useful. Is anybody 
still using pure-random playouts for anything? As soon as you start to do 
anything more, pseudo-liberties are pretty useless. Yes, using real liberties 
slows things down a lot. But the speed of the random playout becoms less and 
less important with heavy playouts.?
?
Next I was thinking about another subject that got some attention on this list, 
the mercy rule. It seems to save about 10% in the number of moves per game (on 
19x19) and result in about 20% gain in 

Re: [computer-go] Suicide question

[dhillismail]

-Original Message-
From: Don Dailey [EMAIL PROTECTED]
...
> 
> For instance since is "legal" to resign,? we could randomly include this
> possibility in the play-outs, but it would not increase the resolving
> power of the play-outs. 
>

Hmm... It would speed things up, though. And if you made the probability of 
resigning a function of the difference in stone count, you would have a 
stochastic mercy rule. In case this turns out to help, I name it "Don's escape 
rule."

- Dave Hillis







More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] On average how many board updates/sec can top Go programs do these days?

[dhillismail]

Another possible reason could be for SIMD (vector) parallel processing. Years 
ago, I was a real-time image processing guy. Some time back, I did a 
back-of-the-envelope design for doing?light playouts on multiple go boards at 
once, on a dedicated parallel processing card. It meant?tiling all these boards 
into a large?image and using standard image processing-type operations. 
Avoiding single-stone suicide looked easy. Avoiding multi-stone suicide looked 
like a can of worms. 

If some one wanted to use, for instance, a graphics card to do fine grained 
parallel processing, permitting multi-stone suicides might be a tempting option.

- Dave Hillis

-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 15 Jan 2008 1:43 pm
Subject: Re: [computer-go] On average how many board updates/sec can top Go 
programs do these days?



I think the only reasonable argument for suicide in the play-outs is
speed.  It's possible to improve the speed of play-outs significantly if
you avoid the suicide test.

But I'm convinced that it comes at a price.   Suicide is the best move
very rarely,  and in rule-sets that do not allow it,  it's NEVER the
best move and it makes no sense to include them in the play-outs.  

- Don


Christoph Birk wrote:
>
> On Jan 15, 2008, at 10:00 AM, [EMAIL PROTECTED] wrote:
>
>> Um, by easier I mean faster. Also, I think single point suicide is
>> more likely to lead to infinite loops, depending on your eye-filling
>> rule.
>> - Dave Hillis
>
> I don't understand why anyone would allow suicide in playouts. No
> commonly
> used (in particular CGOS) ruleset allows it.
>
> 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/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] On average how many board updates/sec can top Go programs do these days?

[dhillismail]

Um, by easier I mean faster. Also, I think single point suicide is more likely 
to lead to infinite loops, depending on your eye-filling rule.
- Dave Hillis


-Original Message-
From: [EMAIL PROTECTED]
To: computer-go@computer-go.org
Sent: Tue, 15 Jan 2008 12:16 pm
Subject: Re: [computer-go] On average how many board updates/sec can top Go 
programs do these days?


Single stone suicide is much easier to test for. :)

- Dave Hillis


-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 15 Jan 2008 12:11 pm
Subject: Re: [computer-go] On average how many board updates/sec can top Go 
programs do these days?



Surely he meant the opposite.
- Don

Rémi Coulom wrote:
 Gian-Carlo Pascutto wrote:
> Multi-stone suicide is allowed, single stone not.

 Strange. The reverse would make more sense to me.

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

__
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/


More new features than ever. Check out the new AIM(R) Mail!




___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] On average how many board updates/sec can top Go programs do these days?

[dhillismail]

Single stone suicide is much easier to test for. :)

- Dave Hillis


-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 15 Jan 2008 12:11 pm
Subject: Re: [computer-go] On average how many board updates/sec can top Go 
programs do these days?



Surely he meant the opposite.
- Don

Rémi Coulom wrote:
 Gian-Carlo Pascutto wrote:
> Multi-stone suicide is allowed, single stone not.

 Strange. The reverse would make more sense to me.

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

__
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Sylvain Gelly thesis in english

[dhillismail]

Thanks Alain. I see I had given up on the paper too soon.
- Dave Hillis

-Original Message-
From: Alain Baeckeroot <[EMAIL PROTECTED]>
To: computer-go 
Sent: Sun, 13 Jan 2008 11:51 am
Subject: Re: [computer-go] Sylvain Gelly thesis in english



Le dimanche 13 janvier 2008, terry mcintyre a écrit :
 From: Rémi Coulom <[EMAIL PROTECTED]>
 
 
 >Sylvain Gelly wrote:
 
 >> Yes I did! :).It is not on my website, but will (soon?).
 >> However, you should not be so eager to read it :)
 
 >> Cheers,
 >> Sylvain
 
 >Google finds it:
 >http://tao.lri.fr/Papers/thesesTAO/SylvainGellyThesis.pdf
 
 Thanks, Rémi!
 
 Now eagerly awaiting the English translation!
It is in english since page 24. 
ages 1-23 are french summary :-)
Alain
___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How to get more participation in 19x19 CGOS?

[dhillismail]

That sounds like it would be weaker than Wally. You could just use Wally, 
though, with today's hardware,?I doubt many would find it a challenging 
opponent.

- Dave Hillis


-Original Message-
From: Don Dailey <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 8 Jan 2008 5:26 pm
Subject: Re: [computer-go] How to get more participation in 19x19 CGOS?





David Fotland wrote:
> It was Doug Larson's idea.  Something like:
> Pull a single stone out of Atari once
> Play in a liberty of the group with fewest liberties that has 5 or fewer
> liberties
> Play random
>   
Yes,  and we called the player Lardo after Doug Larson -   (LA)rson
(Do)ug. 

I can't find any trace of the binary or the source code on my computers!  

What I had in mind is taking the same general rules but instead of
playing random use the ELO rated 3x3 patterns - and perhaps doing any
really obvious fix-ups that don't involve  serious coding efforts.

- Don




>> I also am thinking about building a really fast and weak playing bot.
>> Something that is similar to the rule based program someone suggested
>> to
>> you, but with a few simple 3x3 patterns to supplement it.Do you
>> remember what we called that program? It played by simple rules
>> such
>> as attacking the group with the least liberties, etc.We names it
>> somewhat after the person who suggested the idea.
>>
>>
>> - Don
>>
>>
>>
>>
>>
>> David Fotland wrote:
>> 
>>> I think there are two reasons there are not more programs on 19x19
>>>   
>> CGOS:
>> 
>>> 1) The anchor, Gnugo, is quite strong, Many Faces 12 is stronger, and
>>> CrazyStone is much stronger.  Since the programs playing are so
>>>   
>> strong, it
>> 
>>> is demoralizing for a new program to lose so often.  Without weaker
>>> competition, it is hard to get accurate ratings for new, weaker
>>>   
>> programs.
>> 
>>> 2) The rounds take almost an hour, so it takes much too long to get
>>>   
>> enough
>> 
>>> games to see how your program is doing.  In my local testing, I use
>>>   
>> 10 or 15
>> 
>>> minutes per side.  I like to see 50 to 100 test games get any
>>>   
>> confidence
>> 
>>> that a new version is stronger.  I prefer to get a test run complete
>>>   
>> in
>> 
>>> under a day.
>>>
>>> I propose the following changes:
>>>
>>> I'll put up 3 weaker versions of Many Faces 12, so there is
>>>   
>> competition at
>> 
>>> lower ratings.  These versions are quite fast, using only a few
>>>   
>> seconds for
>> 
>>> a full game.  This will provide some stable opponents for the weaker
>>> programs.
>>>
>>> I think the time limits for CGOS19x19 should be reduced to 10 or 15
>>>   
>> minutes
>> 
>>> per side.  This is enough to test programs, and it's still a
>>>   
>> reasonable time
>> 
>>> limit for games against people.  Since programs that search scale
>>>   
>> with
>> 
>>> additional time, the relative ratings of these programs should be
>>>   
>> similar at
>> 
>>> 10 minutes per game and 30 minutes per game.
>>>
>>> -David
>>>
>>>
>>> ___
>>> 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/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] How to get more participation in 19x19 CGOS?

[dhillismail]

Down the road, when I'm ready for it, I'd like for there still to be a 19x19 
CGOS much like the one now. But, in the mean time, the current 19x19 CGOS is of 
no use at all in helping me get there. Ten minutes per side or faster would be 
ideal. Don's plan for 2 speeds on the same server sounds good, assuming bots 
don't have to wait too much.

 Currently, I see no good options for testing my 19x19 bot. Wally is much too 
weak, Gnugo is much too strong, and self-play is too hard to interpret. That's 
a major reason I haven't tried it much.

- Dave Hillis

-Original Message-
From: John Fan <[EMAIL PROTECTED]>
To: computer-go 
Sent: Tue, 8 Jan 2008 4:38 pm
Subject: Re: [computer-go] How to get more participation in 19x19 CGOS?


I do not have a 19x19 bot right now. But I found that fast engines have to wait 
for slow engines is kind of boring. For example, if a majority of engines 
finish the game within 5 minutes and only one or two engines will finish the 
games in 30 minutes. Then all the fast engines have to wait the slow engines 
finish the game. Maybe we should consider scheduling games for the available 
engines at every 10 minutes while still leave the time limits for each game at 
30 minutes? 


On Jan 8, 2008 4:06 PM, David Fotland <[EMAIL PROTECTED]> wrote:

Then 15 minutes should be good.  We want the anchor to play at the same
strength as before.


David

> -Original Message-
> From: [EMAIL PROTECTED] [mailto:computer-go-


> [EMAIL PROTECTED] On Behalf Of Alain Baeckeroot 
> Sent: Tuesday, January 08, 2008 12:40 PM
> To: computer-go
> Subject: Re: [computer-go] How to get more participation in 19x19 CGOS?
>





> Le mardi 8 janvier 2008, Don Dailey a écrit: 
> ...
> > On 19x19 it might be 30 minutes per side like we have now,  with 5
> > minute games for the fast time control.    We would probably have to
> > work it out so that program like gnugo would be able to handle the 
> fast
> > time control at their standard settings.
> >
>
> At level 10, gnugo might need more than 10 min for some games (with
> lots
> of possible ataris or kos).
> At level 0 (with tons of really ugly moves, and "only" 2 stones weaker 
> on kgs)
>  5 min should be ok.
>
> I think adding handicap to 19x19 is really a needed feature.
> Alain
>
> ___
> 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/








___
omputer-go mailing list
[EMAIL PROTECTED]
ttp://www.computer-go.org/mailman/listinfo/computer-go/



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Odd results on 19x19

[dhillismail]

I've mentioned this before, but hopefully not recently enough to make this 
annoying. Computer go people and corewars people overlap somewhat. 
Intransitivity is extremely important for corewars, making?corewars a good 
domain to study it.

Here is an example of a nice graphical way to visualize intransitivities 
between corewars programs.
http://www.koth.org/lcgi-bin/hugetable.pl?hill94x?

In corewars, you might look at a table like this and say "Oh, I'm losing too 
many games against x-type strategy, I need to concentrate on that aspect of my 
bot." Or you might say, "I'm doing great against y-type strategy, and I'm 
betting there will be a lot of those in the upcoming tournament." It's more 
than predicting the outcome of a particular matchup, or a ranking in a static 
field.

We haven't seen strong statistical evidence for intransitivity in computer go, 
but I don't think anyone has looked very hard yet.

- Dave Hillis

-Original Message-
From: Vlad Dumitrescu <[EMAIL PROTECTED]>
To: computer-go 
Sent: Sun, 6 Jan 2008 5:12 pm
Subject: Re: [computer-go] Odd results on 19x19



On Jan 6, 2008 11:00 PM, Don Dailey <[EMAIL PROTECTED]> wrote:
> The idea of a non one dimension rating model is interesting.  If you
> decide to pursue this I can give you the CGOS data in a compact format,
> 1 line per result.

Hi all,

I'm not sure I get the whole picture regarding multi-dimensional
ratings. How can you compare two players with a 2-dimensional rating?
You can't, so how would one use this rating? In my book, a rating's
goal is to make things comparable...

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



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Please have your bot resign, for your own good

[dhillismail]

After 2000 playouts, AntIgo checks the estimated score. If it's way ahead, it 
stops thinking and just plays the best move it has so far. This way it plays 
very quickly when the game is won and the opponent does not resign. (I don't 
apply this rule in the beginning to avoid confusion in handicap games.)
?
AntIgo gambles that thinking a long time on early moves can?buy it a won 
position. Sometimes the gamble pays off, sometimes not. Another benefit is that 
games against random/near-random bots are mercifully swift.

- Dave Hillis



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] Please have your bot resign, for your own good

[dhillismail]

Maybe some day computer go will reach the same level of "maturity" as computer 
chess and we will need safeguards against all sorts of churlishness. But so 
far, CGOS is very civilized.

I favor encouraging people to make their bots resign, but not penalizing those 
who don't. The MC programs are dominant enough already. 

It was utterly trivial to make my MC program resign from a lost position: maybe 
3 lines of code. On the other hand, I have a neural net bot which has no 
concept of gobal score and just looks for good moves. There's no way I'm going 
to bother modifying it to know when to resign. I'd have to graft a whole new 
engine on top of it. It would be like adding an air conditioner to a bicycle.

The neural net isn't as strong as a good MC program but it's stronger than a 
lot of bad ones. And, with the right time limits, it would probably beat all of 
them. :)

The TT rules make it easy for different algorithms to compete. I'd much rather 
see different time rules (like Fischer) than backing away from TT scoring.

- Dave Hillis






More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] A small optimization for scoring random playouts

[dhillismail]

Depending on your rule set, you might not want to use stones captured. 

I use more-or-less Tromp-Taylor rules; same as CGOS.
- Some form of mercy rule: if whiteStonesOnBoard == 0, I know who won. Early in 
the game, blowouts are *very* comon.
- I maintain an array of empty spaces. At scoring time, Every empty space 
should be a single point eye. I just check the eyes/empty spaces?to find a 
neighbor and I know who owns it.
- white terr = whiteStonesOnBoard?+ whiteEyes
It's fast.

If you are using a different rule set for playouts, my suggestions are 
worthless-ignore them. Is anyone using a different scoring system for playouts?

-Dave Hillis

-Original Message-
From: Imran Hendley <[EMAIL PROTECTED]>
To: computer-go 
Sent: Wed, 19 Dec 2007 5:18 pm
Subject: [computer-go] A small optimization for scoring random playouts


I'm not sure if everyone does this already, but I realized that at the end of a 
random playout there are no territories bigger than one intersection, so you 
don't really need to call your area score method in most cases. 

Let D = blackStonesOnBoard - whiteStonesOnBoard + whiteStonesCaptured - 
blackStonesCaptured - komi. If abs(D) > K for some small threshold K (I use 
size/2 = 4 for a 9x9 board, but you can use size if you want to be super safe) 
then D>0 means black wins, white wins otherwise. The only problem is when D is 
close to 0, since the real area score also counts each eye as one point and 
this is not reflected in D. So depending on how many eyes each side has, the 
result might go one way or another. We can either keep track of the number of 
eyes and update D accordingly, or we can just call the area score method for 
these borderline cases. If we do the latter we are still saving a lot of time 
in most cases if we choose K small enough. 

This gave me a nice speedup of 10% or so if I remember correctly.



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



More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MC-UCT and tactical information

[dhillismail]

> -Original Message-
> From: Jason House <[EMAIL PROTECTED]>
> To: computer-go 
> Sent: Fri, 14 Dec 2007 2:23 pm
> Subject: Re: [computer-go] MC-UCT and tactical information






So, what tactical information should be calculated, how should it be used, and 
yes how should it be stored? 



> Looking only at moves, I see the following basic needs:
> 1. Forced move pairs (peeps, miai)
> 2. Equivalent move classes (semeai)
> 3. Move sequences (joseki, fuseki, tactical L&D, endgame) 

> I've wondered previously about only storing #1 for use in sims, and using #3 
> to replenish the supply > of forced exchanges as long sequences get played 
> out.

> There's also higher level strategic stuff such as ensuring groups survive.? 
> Things that encode actions > instead of literal moves.? If actions include 
> establishing a connection, forming an eye, or getting two > eyes, they may be 
> able to be treated in a similar fashion to normal moves. 

OK. Let's consider using move sequences from life and death tests and applying 
them to the external nodes.
A synopsis of the heavy playout rules from the first Mogo paper, from memory:
1. If the previous move put a friendly string in atari and there are any moves 
that would get it out of atari, pick one at random.
2. If there are any acceptable moves within a 3x3 neighborhood of the previous 
move that match a nice pattern, pick one at random.
3. If there are any moves that would capture an enemy string, pick one at 
random.
4. Make a random move.

These rules handle a lot of forced move pairs, like peeps, but they are myopic.

Maybe we should use the life and death tests at the root node to form a list of 
"moves that must be answered" together with some appropriate?answers. Then we 
could add a new playout rule #0.

0. If the previous move was a "move that must be answered," pick an answering 
move at random. (Probably, by definition, an answering move would have to be 
available.)

- Dave Hillis







_




More new features than ever.  Check out the new AIM(R) Mail ! - 
http://webmail.aim.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/