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

[Olivier Teytaud]

> Could you give us at least a general picture of improvements compared to
> what was last published as 
> www.lri.fr/~teytaud/eg.pdf? Is it "just"
> further tuning and small tweaks or are you trying out some exciting new
> things? ;-)
>

There is one important improvement, for which I must check with coauthors if
they agree for me to explain it. Below the other recent improvements in 9x9.

We have also recently encoded some (very simple) tricks against bad cases as
we had
against Fan Hui (i.e. cases in which the only good move is not simulated).
Roughly,
is the value of the node is very bad, then simulate randomly among the sons.
We can
show (mathematically) that with such tricks, we have the consistency (as
UCT),
plus some frugality (i.e. we do not simulate all the tree, even with
infinite computation time whereas UCT simulates all the tree AND simulates
all the tree infinitely often).
It gives very little improvement in self-play, but it understands better at
least the situation seen in the game with Fan Hui. What I like in this
improvement is that it's
the first time there is something which was mathematically developped for
mogo and
which leads to a positive result. Well, maybe this changes only 1% of games,
but maybe it makes mogo more robust for complicated ko fights which do not
occur in self-play.

Finally, there was a GP-based development of new patterns. However, this is
quite minor I guess - I like the fact that this GP-based module works in a
somehow stable manner, but maybe it would only be worth using it on an
implementation which is not
yet optimized.

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

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

[Petr Baudis]

On Tue, Oct 27, 2009 at 08:47:41AM +0100, Olivier Teytaud wrote:
> > Could you give us at least a general picture of improvements compared to
> > what was last published as 
> > www.lri.fr/~teytaud/eg.pdf? Is it 
> > "just"
> > further tuning and small tweaks or are you trying out some exciting new
> > things? ;-)
> >
> 
> There is one important improvement, for which I must check with coauthors if
> they agree for me to explain it. Below the other recent improvements in 9x9.
> 
> We have also recently encoded some (very simple) tricks against bad cases as
> we had
> against Fan Hui (i.e. cases in which the only good move is not simulated).
> Roughly,
> is the value of the node is very bad, then simulate randomly among the sons.
> We can
> show (mathematically) that with such tricks, we have the consistency (as
> UCT),
> plus some frugality (i.e. we do not simulate all the tree, even with
> infinite computation time whereas UCT simulates all the tree AND simulates
> all the tree infinitely often).
> It gives very little improvement in self-play, but it understands better at
> least the situation seen in the game with Fan Hui. What I like in this
> improvement is that it's
> the first time there is something which was mathematically developped for
> mogo and
> which leads to a positive result. Well, maybe this changes only 1% of games,
> but maybe it makes mogo more robust for complicated ko fights which do not
> occur in self-play.

Interesting! Conceptually, I don't like this that much since it just
work-arounds RAVE bias instead of solving it in more general way, but I
can see its technical value.

AIUI, once upon N simulations in a node you take let's say the node with
the lowest value, pick one son of it at random within the tree and start
a simulation?

> Finally, there was a GP-based development of new patterns. However, this is
> quite minor I guess - I like the fact that this GP-based module works in a
> somehow stable manner, but maybe it would only be worth using it on an
> implementation which is not
> yet optimized.

Wow - one of my planned little projects was genetic development of the
3x3 patterns... To evaluate patterns, do you use tournaments or some
smarter method? I feared one generation would take awfully long...

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

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

[Christian Nentwich]

I suspect I am in your camp, Mark, though obviously it would be nice if 
we had measurements on this instead of conjectures.


I will offer some anecdotal evidence concerning humans playing other 
humans, from club and tournament playing experience: you will find that 
shorter time limits amplify the winning probability of stronger players 
when humans play other humans. Beating somebody 2 stones stronger than 
you on Blitz is much harder than beating them on a longer time limit; 
you may find that you need 3 handicap stones. The bigger the strength 
difference, the worse it gets. Beating a professional player in Blitz Go 
is *ferociously* difficult, even with very high handicap.


Humans are extremely good at recognizing patterns, whole board 
awareness, and intuition about influence; reading more into the game is 
useless for a human without these skills. It has never really surprised 
me that stronger players are that much better at short time limits, 
given their larger experience and knowledge. At the extreme end, you 
have the beginner: even if it's a human with incredible reading ability, 
he/she will still lose with a three hour time limit, to somebody a few 
stones stronger, and on a 10 minute limit.


Well, some trials with different time limits against computers would be 
nice, I guess :)


Christian


On 26/10/2009 23:14, Mark Boon wrote:

2009/10/26 Don Dailey:
   

Yes, you understood me right.   I disagree with Olivier on this one.To
me it is self-evident that humans are more scalable than computers because
we have better heuristics.   When that is not true it is usually because the
task is trivial, not because it is hard.

 


Personally I rather think that what makes a human good at certain
tasks is not necessarily a conscious effort, and that doesn't have to
be a trivial task. So then actively thinking longer doesn't help as
much because you lack the control over the thought-process. I believe
very much that Go falls in that category, where Chess does not.

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

   


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

[computer-go] MC hard positions for MCTS

[Petri Pitkanen]

Hello,

Are there more peculiar situation that will cause problems for MCTS apart
from the three I know.
1. Nakade (this is partuially solved in most of the programs)
2. Semeais
3. Double Ko.

Last one was new to me. See
http://files.gokgs.com/games/2009/10/26/ManyFaces-Hyoga.sgf

In that game manyfaces wastes ko-threats in hopeless ko in lower left
corner. And wins game by human weakness of pushing with stones taht are
short of liberties.

Is there any nice way to solve this or shouldd all of these solved in
expanding the node using "classical" go-AI-engine.

Petri

-- 
Petri Pitkänen
e-mail: petri.t.pitka...@gmail.com
___
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 asblack (game of Go, 9x9).

[Stefan Kaitschick]

c) There was one non-blitz game (45 minutes per side). MoGo was unlucky 
  as it was black, but it nonetheless won the game. This game is enclosed. 
 All games can be found on KGS (account nutngo)

Congratulations.


b) MoGo already won a game as black, against Catalin Taranu, but I guess 
   the pro, at that time, had played an original opening somehow for fun 
   (I'm not sure of that, however).

c) My feeling is that blitz games are not favorable to computers... Statistics 
are in accordance with this I guess. Humans are stronger for short time
settings.

I just can't believe the general statement that computers scale better than 
humans on time.
Tripling the number of playouts surely won't do much for the program.
So if it's supposed to help, it means that the extra time will do practically 
nothing(or worse) for the human.
I'm willing to concede, that that might have exactly been the case.
The pro had allready won the shorter games and was probably inflicted by the 
same momentary imbalance as Catalin. That's actually very human. The bots have 
to earn their respect.
Also, in serious future showdowns, there will have to be regenerative pauses 
between the games.


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

Re: [computer-go] MC hard positions for MCTS

[Stefan Kaitschick]

I would add invasions.
This is especially obvious when the position cries for a san-san invasion.
Nakade may be a part of it.
But the biggest problem is that the path to life/ko is very narrow.
The defender has many useful moves and the invader has few.
So MCTS will falsely judge invadable areas to be safe.

Stefan


  - Original Message - 
  From: Petri Pitkanen 
  To: computer-go 
  Sent: Tuesday, October 27, 2009 11:05 AM
  Subject: [computer-go] MC hard positions for MCTS


  Hello,

  Are there more peculiar situation that will cause problems for MCTS apart 
from the three I know.
  1. Nakade (this is partuially solved in most of the programs)
  2. Semeais
  3. Double Ko.

  Last one was new to me. See 
http://files.gokgs.com/games/2009/10/26/ManyFaces-Hyoga.sgf

  In that game manyfaces wastes ko-threats in hopeless ko in lower left corner. 
And wins game by human weakness of pushing with stones taht are short of 
liberties.

  Is there any nice way to solve this or shouldd all of these solved in 
expanding the node using "classical" go-AI-engine.

  Petri

  -- 
  Petri Pitkänen
  e-mail: petri.t.pitka...@gmail.com



--


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

Re: [computer-go] MC hard positions for MCTS

[Petr Baudis]

  Hi!

On Tue, Oct 27, 2009 at 12:05:57PM +0200, Petri Pitkanen wrote:
> Are there more peculiar situation that will cause problems for MCTS apart
> from the three I know.
> 1. Nakade (this is partuially solved in most of the programs)
> 2. Semeais
> 3. Double Ko.

  Yes, these are all just particular instances of a general class; it
shows up in fights at many points. They all manifest as a problem where
the simulations introduce a massive bias in the particular situation,
misjudging life of certain group, usually where there is one right move
and many bad ones in the position (right one will be played only with
small probability).

  This causes what I call the "horizon effect" which prevents the
tree exploration to work properly - the moment the tree finds a sequence
that unbiases the simulations, it is horrified by the bad results [*] and
switches to a different branch, until it finds the same; thus, the bot
pushes the resolution (unbiasing) of the situation over the tree horizon
for as long as possible. This shows in actual games as the bot playing
random throwins and obviously pass moves before resigning.

  In case of nakade, the bias is introduced by anti-self-atari
heuristics in the playouts and is probably indeed largely solved by
smarter self-atari detection. In case of various kos, perhaps a
simulation bias for re-taking the ko could help, but this is probably
fairly simple. In case of semeai, the bias is obvious and the solution
is currently totally unobvious.

  There are two ways to deal with this - removing the bias from the
simulations by increasing the intelligence within cautiously, and
finding a way to deal with the bias in the tree. I'd say so far all
improvements of simulations since uniform playout could be described
as trying to solve this problem, and to a certain point it greatly
helps increase the convergence to good result, but I think we are behind
that point now and making the simulations smarter is now only pushing
away the inevitable.

  I don't know how much hidden ongoing research is being done about
dealing with the bias in the tree, the only result so far I'm aware of
is Remi Coulom's criticality heuristic, and it wasn't that effective;
I personally have some clear ideas I want to start experimenting with as
soon as possible - I think we need a top-down counterpart for the
bottom-up propagation function of RAVE. IMHO a substantial progress
in this direction is the next big thing to happen in computer go.


  [*] "Bad results" for the parent node owner - I have seen the bias
as being both unduly positive _and_ unduly negative, though the latter
seems fairly rare - I think I saw it only once in a rather complicated
large temporary seki fight and while the bot obviously won it, the
percentages were horrible, it was lucky they stayed above the resign
threshold until the situation finally got resolved.

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

Re: [computer-go] MC hard positions for MCTS

[Darren Cook]

> But the biggest problem is that the path to life/ko is very narrow.
> The defender has many useful moves and the invader has few.
> So MCTS will falsely judge invadable areas to be safe.

Interesting, I'd not thought about it in that respect: I know I can soon
find positions where the defender has only one way to defend but the
attacker has many choices.

But, has anyone gathered stats on positions, from real games, that
require precise play by the defender/attacker/both/neither? Is defending
really easier than attacking?

Darren


-- 
Darren Cook, Software Researcher/Developer
http://dcook.org/gobet/  (Shodan Go Bet - who will win?)
http://dcook.org/mlsn/ (Multilingual open source semantic network)
http://dcook.org/work/ (About me and my work)
http://dcook.org/blogs.html (My blogs and articles)
___
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).

[Darren Cook]

> I will offer some anecdotal evidence concerning humans playing other
> humans, from club and tournament playing experience: you will find that
> shorter time limits amplify the winning probability of stronger players...

Another anecdote. At a Fost Cup (Computer Go tournament) from 10-15
years ago, a pro player had made his own program. I think it was based
on patterns and though it wasn't one of the stronger programs, it played
very quickly. This was at Nihon Kiin, and another pro friend popped in
to visit; I forget his name, but he was one of the top 9p players. He
played the fast program, and they played a 19x19 game at the pace of at
least 60 moves/minute.

I forget if it was an even game or 9-stone handicap as it didn't matter
- the pro killed every group. But what impressed me was he made shapes
and strength that even dan players would've had to work hard to get. A
wall of stones along one side of the board naturally ended up being in
just the right place to work with joseki played earlier on the other
side of the board, stones played long before ended up on just the
critical points to kill, yet he took not even a breath to plan any of this.

So, I wonder if the blitz strength of very strong go players is
something special and peculiar to the game of go. Patterns and shape
knowledge is so important in go, that humans (*) gain relatively little
extra strength from extra thinking.

Darren

*: Meaning very strong players who've spent years studying and
appreciating good shape.

-- 
Darren Cook, Software Researcher/Developer
http://dcook.org/gobet/  (Shodan Go Bet - who will win?)
http://dcook.org/mlsn/ (Multilingual open source semantic network)
http://dcook.org/work/ (About me and my work)
http://dcook.org/blogs.html (My blogs and articles)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MC hard positions for MCTS

[Petri Pitkanen]

That is well known fact of go, that usually defence is easier. But evidence
is anecdotal.  Getting real evidence from real games cannot be automated as
all concept involved are rather vague and difficult to classify. Hence I am
willing to accept such information as passed on to me in books like "defence
and attack"

Petri

2009/10/27 Darren Cook 

> > But the biggest problem is that the path to life/ko is very narrow.
> > The defender has many useful moves and the invader has few.
> > So MCTS will falsely judge invadable areas to be safe.
>
> Interesting, I'd not thought about it in that respect: I know I can soon
> find positions where the defender has only one way to defend but the
> attacker has many choices.
>
> But, has anyone gathered stats on positions, from real games, that
> require precise play by the defender/attacker/both/neither? Is defending
> really easier than attacking?
>
> Darren
>
>
> --
> Darren Cook, Software Researcher/Developer
> http://dcook.org/gobet/  (Shodan Go Bet - who will win?)
> http://dcook.org/mlsn/ (Multilingual open source semantic network)
> http://dcook.org/work/ (About me and my work)
> http://dcook.org/blogs.html (My blogs and articles)
> ___
> computer-go mailing list
> computer-go@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>



-- 
Petri Pitkänen
e-mail: petri.t.pitka...@gmail.com
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

Re: [computer-go] MC hard positions for MCTS

[Stefan Kaitschick]

But, has anyone gathered stats on positions, from real games, that
require precise play by the defender/attacker/both/neither? Is defending
really easier than attacking?

Darren



Who is the defender?
One side is defending his territory, the other side is defending his group.
I think the general bias is towards overestimating the chance of killing.
Thats what makes MCTS programs such an aggressive lot :-)

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

Re: [computer-go] MC hard positions for MCTS

[Stefan Kaitschick]

 This causes what I call the "horizon effect" which prevents the
tree exploration to work properly - the moment the tree finds a sequence
that unbiases the simulations, it is horrified by the bad results [*] and
switches to a different branch, until it finds the same; thus, the bot
pushes the resolution (unbiasing) of the situation over the tree horizon
for as long as possible. This shows in actual games as the bot playing
random throwins and obviously pass moves before resigning.



 I don't know how much hidden ongoing research is being done about
dealing with the bias in the tree, the only result so far I'm aware of
is Remi Coulom's criticality heuristic, and it wasn't that effective;
I personally have some clear ideas I want to start experimenting with as
soon as possible - I think we need a top-down counterpart for the
bottom-up propagation function of RAVE. IMHO a substantial progress
in this direction is the next big thing to happen in computer go.




Petr "Pasky" Baudis


I like the criticality heuristic. It certainly points to an important 
problem.
One trick might be to identify "hot spots" with something akin to 
criticality and then penalize jumping between them. Because permutating 
moves between separate important areas is exactly what leads to the 
consequence evading horizon effect.


Stefan

___
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).

[Hideki Kato]

I strongly believe that such patterns must not be only spatial 
(static) but also temporal, ie, dynamic or sequence of pattens which 
allow the player quickly remember the results of local fights or 
L&D.

Hideki

Darren Cook: <4ae6d9b6.1070...@dcook.org>:
>> I will offer some anecdotal evidence concerning humans playing other
>> humans, from club and tournament playing experience: you will find that
>> shorter time limits amplify the winning probability of stronger players...
>
>Another anecdote. At a Fost Cup (Computer Go tournament) from 10-15
>years ago, a pro player had made his own program. I think it was based
>on patterns and though it wasn't one of the stronger programs, it played
>very quickly. This was at Nihon Kiin, and another pro friend popped in
>to visit; I forget his name, but he was one of the top 9p players. He
>played the fast program, and they played a 19x19 game at the pace of at
>least 60 moves/minute.
>
>I forget if it was an even game or 9-stone handicap as it didn't matter
>- the pro killed every group. But what impressed me was he made shapes
>and strength that even dan players would've had to work hard to get. A
>wall of stones along one side of the board naturally ended up being in
>just the right place to work with joseki played earlier on the other
>side of the board, stones played long before ended up on just the
>critical points to kill, yet he took not even a breath to plan any of this.
>
>So, I wonder if the blitz strength of very strong go players is
>something special and peculiar to the game of go. Patterns and shape
>knowledge is so important in go, that humans (*) gain relatively little
>extra strength from extra thinking.
>
>Darren
>
>*: Meaning very strong players who've spent years studying and
>appreciating good shape.
--
g...@nue.ci.i.u-tokyo.ac.jp (Kato)
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

[computer-go] Designing coefficient functions

[Petr Baudis]

  Hi!

  Does anyone have some tips about designing effeciently-computable
coefficient functions that would have similar properties to the "eg
paper"?

  I.e. something like:

  a + b + c = 1
  n(d) = 0  a ~ 0, b ~ 0, c ~ 1
  n(d) smallb >> a
  n(d) -> infty a ~ 1

  It sounds simple, but I'm a bit lost about embedding the c term to my
RAVE equation. :) (Currently I use the Silver beta formula, same as
in Fuego.)

  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/

RE: [computer-go] MC hard positions for MCTS

[David Fotland]

Don’t forget about ladders.  Many programs have special code to avoid
playing in losing ladders.

 

From: computer-go-boun...@computer-go.org
[mailto:computer-go-boun...@computer-go.org] On Behalf Of Petri Pitkanen
Sent: Tuesday, October 27, 2009 3:06 AM
To: computer-go
Subject: [computer-go] MC hard positions for MCTS

 

Hello,

Are there more peculiar situation that will cause problems for MCTS apart
from the three I know.
1. Nakade (this is partuially solved in most of the programs)
2. Semeais
3. Double Ko.

Last one was new to me. See
http://files.gokgs.com/games/2009/10/26/ManyFaces-Hyoga.sgf

In that game manyfaces wastes ko-threats in hopeless ko in lower left
corner. And wins game by human weakness of pushing with stones taht are
short of liberties.

Is there any nice way to solve this or shouldd all of these solved in
expanding the node using "classical" go-AI-engine.

Petri

-- 
Petri Pitkänen
e-mail: petri.t.pitka...@gmail.com

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

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

[Olivier Teytaud]

>
>
> AIUI, once upon N simulations in a node you take let's say the node with
> the lowest value, pick one son of it at random within the tree and start
> a simulation?
>

I'll try to write it clearly (for binary deterministic games, extensions can
be shown but they are too long and out of topic in this mailing list I guess
:-) ):

If (average value of father < threshold )
then
randomly pick up one son
   else
   pick up the son with maximum score
end

If the score is asymptotically equivalent to the success rate, and if the
threshold is >0 and < 1, then this ensures
consistency (convergence to optimal move). If the score is well done, then
this is consistent without visiting all the tree.

UCT (with non-zero constant) visits all the tree, and does so infinitely
often.
UCT (with zero constant) does not visit all the tree, but it is not
necessarily consistent.

Wow - one of my planned little projects was genetic development of the
> 3x3 patterns... To evaluate patterns, do you use tournaments or some
> smarter method? I feared one generation would take awfully long...
>

We use a stupid method, i.e. the success rate. The pattenrs are bigger than
3x3, with jokers in them. Bandits (Bernstein races, slightly modified) are
used
for distributing the computational effort among the tested patterns.

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

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

[Olivier Teytaud]

Dear all, some comments by my Taiwanese colleagues about the game played by
MoGo against the 9p pro:

1) mogoTW finally ran on the 16*8 system on Oct. 26, 2009.

2) Contributors for which I did not know their real name: "Hsien-Der Huang"
and "Cheng-Wei Chou"  (sorry for them!)

3) Some comments by the pro, translated by people from Taiwan:

===

He told the jounalists that he made a mistake on move 26, which is a move
that it is hard to find such kind an error (move 26) even for a professional
Go player. However, he was so surprised that MoGoTW found this mistake that
he made during the game. That means the level of MoGoTW in 9x9 game has made
an improvement than last time (08/2009).

In addition, he also told the journalists that MoGoTW made a good move at
Move 29. He thought that the main reason that MoGoTW won the game was Move
29 and MoGoTW didn't make any mistake after Move 29.
==
___
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).

[Mark Boon]

On Oct 27, 2009, at 3:39 AM, Hideki Kato wrote:


I strongly believe that such patterns must not be only spatial
(static) but also temporal, ie, dynamic or sequence of pattens which
allow the player quickly remember the results of local fights or
L&D.


I think that's exactly right. At least for humans. Maybe for computers  
there's another way.


After reading On Intelligence (anyone follow my advice and read it?) I  
got to thinking the human brain possibly does a lot of little playouts  
in parallel. Not random, whole-board playouts from beginning to end,  
but short, local playouts, following strong patterns at each choice.  
Each time the result is fed back into the first layer so that the  
result of this playout gets used to guide the next playout. And the  
variance of the outcome of each of these playouts gets fed into the  
next layer to recognise higher-level concepts. Maybe for a few levels  
until it reaches a conscious level.


The reason why thinking longer only helps marginally is that these  
small playouts follow a limited set of patterns. It takes time and  
practice to add these patterns, you can't easily consciously add a  
pattern in there during the game.


So 'thinking' is restricted to a higher level, trying to think steps  
ahead in the game. Obviously this helps a lot for strength too, and  
pros are very good at that too. But with each stone you read ahead it  
becomes harder for your brain to do the pattern-matching because it  
doesn't have the complete (visual) input. So humans tend to think  
ahead in rather fixed sequences along the lines of play in the  
patterns that are followed sub-consciously. So when Sakata claimed he  
can read ahead 30 moves in a blink, he doesn't do a search of lots of  
possibilities. Instead, his brain is able to do these little playouts  
a lot deeper than mere mortals can. Most likely the main candidates  
all come up in the first (split) second. The rest of the time he  
spends verifying their results.


This is all rather speculative of course. Christian Nentwich is right  
that it would be nice if we could measure this somehow. That's going  
to be difficult. But it shows a bit why I have the opinion that I have.


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

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

[Olivier Teytaud]

I forgot the most important thing around this win against a pro:
this press conference was for the starting of a project, and in this project
we have funding for ph.D. or postdocs.
If there are people interested in a ph.D. or a post-doc around Monte-Carlo
Tree Search, candidates are welcome (Monte-Carlo Tree Search, and not
necessarily / not only computer-go).

Best regards,
Olivier
___
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 asblack (game of Go, 9x9).

[Stefan Kaitschick]

29, turning into a won ko, really is a great way to play.
It would be interesting to know if MoGo perceived itself to be on the home 
stretch here.
So it would be great to have the bots win rate estimations as sgf comments.

Stefan
  - Original Message - 
  From: Olivier Teytaud 
  To: computer-go 
  Sent: Tuesday, October 27, 2009 5:38 PM
  Subject: [computer-go] First ever win of a computer against a pro 9P asblack 
(game of Go, 9x9).


  Dear all, some comments by my Taiwanese colleagues about the game played by 
MoGo against the 9p pro:

  1) mogoTW finally ran on the 16*8 system on Oct. 26, 2009.

  2) Contributors for which I did not know their real name: "Hsien-Der Huang" 
and "Cheng-Wei Chou"  (sorry for them!)


  3) Some comments by the pro, translated by people from Taiwan:

  ===


  He told the jounalists that he made a mistake on move 26, which is a move 
that it is hard to find such kind an error (move 26) even for a professional Go 
player. However, he was so surprised that MoGoTW found this mistake that he 
made during the game. That means the level of MoGoTW in 9x9 game has made an 
improvement than last time (08/2009).

  In addition, he also told the journalists that MoGoTW made a good move at 
Move 29. He thought that the main reason that MoGoTW won the game was Move 29 
and MoGoTW didn't make any mistake after Move 29.

  ==





--


  ___
  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] Re: First ever win of a computer against a pro 9P asblack (game of Go, 9x9).

[Ingo Althöfer]

Stefan Kaitschick wrote:
> 29, turning into a won ko, really is a great way to play.
> It would be interesting to know if MoGo perceived itself 
> to be on the home stretch here.
> So it would be great to have the bots win rate estimations 
> as sgf comments.

I do not have MoGo at hand. But I entered the crucial position
in two other bots.

MFoG 12.016
wants to play 29. f8 with 43 %  
(29.g7 from the game was not in the list of candidates)
However, after 29.g7 MFoG
gives only 53 % for Whites position (proposing 30. h7)

Leela 3.16
wants to play 29.g7 (so the MoGo move) with 58 %
After the response 30.f6 from the game, Leela
wants to play 31.h7 (so, MoGo move again) with 58 %
After the response 32.f7 from the game, Leela
wants to play 33.d8 (so, MoGo move again), with 65 %.


Observe that this does not mean that Leela is in general better
than MFoG. It is just one (probably) interesting position.

Ingo.

-- 
Neu: GMX DSL bis 50.000 kBit/s und 200,- Euro Startguthaben!
http://portal.gmx.net/de/go/dsl02
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/

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

[Petr Baudis]

On Tue, Oct 27, 2009 at 06:32:44PM +0200, Olivier Teytaud wrote:
> >
> >
> > AIUI, once upon N simulations in a node you take let's say the node with
> > the lowest value, pick one son of it at random within the tree and start
> > a simulation?
> >
> 
> I'll try to write it clearly (for binary deterministic games, extensions can
> be shown but they are too long and out of topic in this mailing list I guess
> :-) ):
> 
> If (average value of father < threshold )
> then
> randomly pick up one son
>else
>pick up the son with maximum score
> end
> 

Aha, thanks for clearing that up.

> If the score is asymptotically equivalent to the success rate, and if the
> threshold is >0 and < 1, then this ensures
> consistency (convergence to optimal move). If the score is well done, then
> this is consistent without visiting all the tree.

But is it shown that "the score is well done" for these properties to
hold in case of RAVE-guided exploration? Since it massively perpetuates
any kind of MC bias...

> > Wow - one of my planned little projects was genetic development of the
> > 3x3 patterns... To evaluate patterns, do you use tournaments or some
> > smarter method? I feared one generation would take awfully long...
> >
> 
> We use a stupid method, i.e. the success rate. The pattenrs are bigger than
> 3x3, with jokers in them. Bandits (Bernstein races, slightly modified) are
> used
> for distributing the computational effort among the tested patterns.

Thank you for pointing me to more study material. :-)

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

Re: [computer-go] MC hard positions for MCTS

[Petr Baudis]

On Tue, Oct 27, 2009 at 01:10:09PM +0100, Stefan Kaitschick wrote:
> 
> >But, has anyone gathered stats on positions, from real games, that
> >require precise play by the defender/attacker/both/neither? Is defending
> >really easier than attacking?
> >
> >Darren
> 
> 
> Who is the defender?
> One side is defending his territory, the other side is defending his group.
> I think the general bias is towards overestimating the chance of killing.
> Thats what makes MCTS programs such an aggressive lot :-)

I think they are agressive mainly since killing big group is much surer
way of victory than drawn-out close game, they want to maximize the
advantage the quickest way possible.

Also my collected anectodal evidence suggests MCTS might be actually
quite lousy at counting score in tight games (at least on 19x19, and
that fact makes a lot of sense to me) - I'm not completely sure of this
though, did anyone do some extensive testing of modern MCTS on hard
endgame problems?

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

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

[Hideki Kato]

Olivier Teytaud: :
>I forgot the most important thing around this win against a pro:
>this press conference was for the starting of a project, and in this project
>we have funding for ph.D. or postdocs.
>If there are people interested in a ph.D. or a post-doc around Monte-Carlo
>Tree Search, candidates are welcome (Monte-Carlo Tree Search, and not
>necessarily / not only computer-go).

Excuse me, but what press conference and where to ask?

You wrote in your first post of this thread,
>This was during a press conference at Taipei around a French-Taiwanese grant
>for joint research.
but I can find no links even with Google.

Hideki
--
g...@nue.ci.i.u-tokyo.ac.jp (Kato)
___
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).

[Hideki Kato]

Mark Boon: <4ec4bc46-e52f-4ac2-a7ff-edaf17de3...@gmail.com>:
>On Oct 27, 2009, at 3:39 AM, Hideki Kato wrote:
>
>> I strongly believe that such patterns must not be only spatial
>> (static) but also temporal, ie, dynamic or sequence of pattens which
>> allow the player quickly remember the results of local fights or
>> L&D.
>
>I think that's exactly right. At least for humans. Maybe for computers  
>there's another way.

That could be a challenging problem in this century...

>After reading On Intelligence (anyone follow my advice and read it?) 

I bought (:-) English version and read Japanese one immediate after 
their publish.  IMHO, Jeff's idea is still very interesting while 
the implementation by the staff in Numenta have been going to not 
right direction.  More generalized version of his idea could be that 
Cerebral cortex works to reduce temporal error similar to visual 
cortex but spatial error.

>I  
>got to thinking the human brain possibly does a lot of little playouts  
>in parallel. Not random, whole-board playouts from beginning to end,  
>but short, local playouts, following strong patterns at each choice.  
>Each time the result is fed back into the first layer so that the  
>result of this playout gets used to guide the next playout. And the  
>variance of the outcome of each of these playouts gets fed into the  
>next layer to recognise higher-level concepts. Maybe for a few levels  
>until it reaches a conscious level.

Those playouts are done in Cerebellum using some associative memory, I 
beleive.  Then the mechanism, how to communicate with Cerebral, is a 
mistery, assuming some kind of tree search is done in Cerebral.

>The reason why thinking longer only helps marginally is that these  
>small playouts follow a limited set of patterns. It takes time and  
>practice to add these patterns, you can't easily consciously add a  
>pattern in there during the game.

Agree.

>So 'thinking' is restricted to a higher level, trying to think steps  
>ahead in the game. Obviously this helps a lot for strength too, and  
>pros are very good at that too. But with each stone you read ahead it  
>becomes harder for your brain to do the pattern-matching because it  
>doesn't have the complete (visual) input. So humans tend to think  
>ahead in rather fixed sequences along the lines of play in the  
>patterns that are followed sub-consciously. So when Sakata claimed he  
>can read ahead 30 moves in a blink, he doesn't do a search of lots of  
>possibilities. Instead, his brain is able to do these little playouts  
>a lot deeper than mere mortals can. Most likely the main candidates  
>all come up in the first (split) second. The rest of the time he  
>spends verifying their results.

The games in last Meijin-sen in Japan, Iyama vs Cho, may support 
your thought.

>This is all rather speculative of course. Christian Nentwich is right  
>that it would be nice if we could measure this somehow. That's going  
>to be difficult. But it shows a bit why I have the opinion that I have.

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
--
g...@nue.ci.i.u-tokyo.ac.jp (Kato)
___
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).

[Mark Boon]

On Oct 27, 2009, at 7:41 PM, Hideki Kato wrote:


  IMHO, Jeff's idea is still very interesting while
the implementation by the staff in Numenta have been going to not
right direction.


That was also my opinion. What I thought was strange is that Numenta's  
implementation doesn't have feed-back connections, which is a corner- 
stone of the ideas in the book.



Those playouts are done in Cerebellum using some associative memory, I
beleive.  Then the mechanism, how to communicate with Cerebral, is a
mistery, assuming some kind of tree search is done in Cerebral.


It's not so sure to me there's a clear boundary between the activity  
of the two. It seems the tree search is done in the Cerebral cortex.  
But that may simply be because we're conscious of it. It's unclear  
what exactly happens during the unconscious processes. It mays also be  
a form of tree search that blends in with the conscious process.  
Knowledge about how the brain works is growing, but I believe it's  
mostly still a mystery. The way it's being observed currently is  
mostly like trying to figure out a computer-program by observing a  
piece of computer-memory on the screen. You see bits flashing on and  
off but you have to guess what instructed it to do so.




The games in last Meijin-sen in Japan, Iyama vs Cho, may support
your thought.


I'm rather out of touch with what happens in tournaments. I've never  
heard of Iyama and even Cho could be a different one than I know. What  
happened in that match that is relevant to this discussion?


Mark

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