[computer-go] Former Deep Blue Research working on Go
Joshua Shriver
http://www.spectrum.ieee.org/oct07/5552
Interesting part for me so far:
" At my lab at Microsoft Research Asia, in Beijing, I am organizing a
graduate student project to design the hardware and software elements
that will test the ideas outlined here. If they prove out, then the
way will be clear for a full-scale project to dethrone the best human
players."
Thoughts, comments?
Deep Go anyone?
-Josh
_______________________________________________
computer-go mailing list
compu...@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Benjamin Teuber
a) determine the life status of groups
b) build an evaluation function out of this
Benjamin
Joshua Shriver schrieb:
Joshua Shriver
I couldn't help to get the feeling the author was poking fun at
Kasparov at times.
Despite that, I am curious to see what kind of hardware he and his
students produce. Guess if there is going to be a Deep Go he'd be the
one to design it. Should make for some interesting progress in our
field.
-Josh
Jeff Nowakowski
> Found this link and thought you all might find it interesting.
>
> http://www.spectrum.ieee.org/oct07/5552
Umm, this article was linked to and discussed heavily here within the
past week:
http://computer-go.org/pipermail/computer-go/2007-October/thread.html#11302
-Jeff
Joshua Shriver
Eduardo Sabbatella
care about.
May sound unpolite. But Deep Blue reached a very
important step in IA. They will be known for ever.
But, from a research point of view, they didn't much
really. It was mainly a technological/technical
achivement.
Don't trow me veggies. :-)
Eduardo
--- Joshua Shriver <jshr...@gmail.com> escribió:
Los referentes más importantes en compra/ venta de autos se juntaron:
Demotores y Yahoo!
Ahora comprar o vender tu auto es más fácil. Vistá ar.autos.yahoo.com/
Tapani Raiko
> May sound unpolite. But Deep Blue reached a very
> important step in IA. They will be known for ever.
> But, from a research point of view, they didn't much
> really. It was mainly a technological/technical
> achivement.
>
supercomputer, and claim to have the strongest computer Go player ever. :-)
--
Tapani Raiko, <tapani...@tkk.fi>, +358 50 5225750
http://www.cis.hut.fi/praiko/
Don Dailey
Hash: SHA1
Eduardo Sabbatella wrote:
> Deep Blue guy, but without cash, I don't see much to
> care about.
>
> May sound unpolite. But Deep Blue reached a very
> important step in IA. They will be known for ever.
> But, from a research point of view, they didn't much
> really. It was mainly a technological/technical
> achivement.
You are not being polite to them. They worked very hard on that project
and got very little back from it. Even the good feeling of
accomplishment from beating Kasparov was watered down and they took
enormous criticism that they didn't deserve.
I don't think they would disagree with you - what they did was a
technological achievement and I can't speak for them but I don't think
they believed they were primarily researchers. But they did publish
papers and contribute ideas to the computer chess community.
I felt rather bad for them for the criticism they took about a lot of
things. Since they were "on top" they were targets. Kasparov was
not very kind to them either.
I have had my criticisms too. In retrospect, I would have avoided some
of my own comments had I known what they were going through.
In a lot of ways the core team was caught up in the middle of something
they didn't have a lot of control over. They were not calling the
shots but they were taking the hits.
- - Don
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHCj75DsOllbwnSikRAv9CAJ9GrjL/+DR3/LPEQZQmyEl3oSTwxwCgnw6u
FCX5SsRBWUCf3/AduHxjLy8=
=PzHQ
-----END PGP SIGNATURE-----
terry mcintyre
IIRC, a few Microsoft researchers did some interesting work with SVMs and the prediction of pro-level moves. I've always wondered whether that could be integrated with UCT to narrow the search tree.
They mean to govern well; but they mean to govern. They promise to be kind masters; but they mean to be masters. -- Daniel Webster
From: Tapani Raiko <Tapani...@tkk.fi>
To: computer-go <compu...@computer-go.org>
Sent: Monday, October 8, 2007 6:45:13 AM
Subject: Re: [computer-go] Former Deep Blue Research working on Go
> May sound unpolite. But Deep Blue reached a very
> important step in IA. They will be known for ever.
> But, from a research point of view, they didn't much
> really. It was mainly a technological/technical
> achivement.
>
supercomputer, and claim to have the strongest computer Go player ever. :-)
--
Tapani Raiko, <tapani...@tkk.fi>, +358 50 5225750
http://www.cis.hut.fi/praiko/
computer-go mailing list
compu...@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
Eric Boesch
> > May sound unpolite. But Deep Blue reached a very
> > important step in IA. They will be known for ever.
> > But, from a research point of view, they didn't much
> > really. It was mainly a technological/technical
> > achivement.
> >
> Maybe they will reimplement Mogo, try a null-move tweak, use a
> supercomputer, and claim to have the strongest computer Go player ever. :-)
Naive null move is unhelpful because throughout much of a go game,
almost every move is better than passing, but generalizations of null
move can help in local fights, where most of the board really doesn't
matter. Thomsen calls lambda search an extension of null move. I
implemented a local search that involved a "pass to fill outside
liberties" move that acted as a stand-in for all nonlocal moves. Maybe
Feng-hsiung has something similar in mind. For programs that read out
local goals in the first place, it's natural to implement some method
-- lambda proof-number search with inversions, as in Thomsen's MadLab,
is probably one of the better ones -- to insure you're not searching
the whole board just to solve, say, a lousy crane's nest
(http://senseis.xmp.net/?CranesNestTesuji). I think Mogo and
CrazyStone do not do this, instead using very good whole-board vision
to compensate for relatively weak local tactics.
Even MadLab can be slow to solve the kind of tactical problems you
would think it. MadLab's search is admissible (though a bit buggy in
case of ko), and it seems that admissible search is often very hard
even when making a guess that is probably right is easy. With many
harder problems (MadLab did solve some some tricky, let's say 3 dan
level, problems very quickly, when the key variation stayed reasonably
narrow all the way to the end) I concluded that MadLab was finding the
tesujis that you would normally call the "solution", but then getting
bogged down in the easier (to human eyes) life and death problem of
mopping up cut-off chains. There are endless practical examples of
easy to guess, hard to prove positions, with wide-branching (even
after narrowing the search region down to intersections that really
matter), deep, boring, straightforward grinds towards inevitable
victory, where a glance or 100 Monte Carlo simulations might reveal
the correct answer. For example, can a black stone in the center of an
empty 19x19 board live? Of course the answer is yes. Okay, now try to
prove it -- or don't, because it's my bet that even with computer
help, no one will succeed in doing so in the next five years. In
running battles with sketchy boundaries and nothing resembling an eye
yet, you can usually forget about trying to prove who will win. (If
the aforementioned stone in the center of the board had the 17x17
region above the first line all to itself, it might still be dead --
strong players say that if just the border of the 19x19 board is
filled with stones of one color, then with correct play by both sides,
the other player cannot live anywhere inside.) Even in the closed and
semi-closed go problems the Smart Tools team examined in their paper,
they said (I'm paraphrasing from memory, but I hope I get the gist
right) that often, proving the correct answer with their tsume-go
solver took far longer than just being 95% sure. Similar issues also
arise in chess, but are easier to handle within a classic alpha-beta
framework -- if proving checkmate is hard but recognizing the sure win
is easy, it's usually because one side forces a material advantage,
which even the crudest static evaluator can recognize. If you're
writing a generalize go playing program, there's plenty of opportunity
to admissibly optimize tactical searches, but don't expect tweaking
the admissible elements of your search to the limit to adequately
compensate for lack of guessing skill when proof is not practical,
even if the search is meant only for clearly tactical problems and
not for direct application to opening play, strategic decisions, or
loose positions.
Andrés Domínguez
> On 10/8/07, Tapani Raiko <Tapani...@tkk.fi> wrote:
> > > May sound unpolite. But Deep Blue reached a very
> > > important step in IA. They will be known for ever.
> > > But, from a research point of view, they didn't much
> > > really. It was mainly a technological/technical
> > > achivement.
> > >
> > Maybe they will reimplement Mogo, try a null-move tweak, use a
> > supercomputer, and claim to have the strongest computer Go player ever. :-)
>
> Naive null move is unhelpful because throughout much of a go game,
> almost every move is better than passing,
I think this is not the point of null move. Null move is "if pass is good enough
to an alpha cut, then will be a _better_ move". It is not important if
pass is the
worse move, is important that there is a better (>=) move than pass (not
zugzwang). Then you bet searching not so deep.
But null nove is not a trick in Go, because pass is always a legal move. There
isn't zugzwang in Go.
Andrés
Sorry my bad english
Don Dailey
Hash: SHA1
Pass is just as good as a null move - it's the same and it isn't an
issue that hurts null move pruning.
But null move pruning isn't just about the null move. It's about the
subsequent search reduction that goes with it, otherwise it's no saving.
In GO, threats tend to be very indirect and distant, at least from the
point of view of a naive search algorithm and this is a real killer to
the idea - my feeling is that null move in GO is not workable. Perhaps
if a really good static evaluation came along that was sensitive to the
urgency of a threat it would be workable - but I doubt it.
- - Don
> ------------------------------------------------------------------------
>
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDC/gDsOllbwnSikRAsPUAJ9jxoCXymM9WRS6nF4pyFLzP3GgzACfY3hU
P1hnjZKPPIuPZRBuSDIPWgg=
=UXeh
-----END PGP SIGNATURE-----
Don Dailey
Hash: SHA1
Andrés,
You are right about null move of course. The assumption that other
moves are >= to the value of a pass is much stronger in GO than in
Chess, yet ironically it's not as effective in Go.
- - Don
> ------------------------------------------------------------------------
>
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDDBtDsOllbwnSikRAki9AKDnb8vj/606wCP/AEIZaEbRSXhg+gCfVO+G
3rW+K09cKN25k4Ro4yJJbnc=
=awa+
-----END PGP SIGNATURE-----
Andrés Domínguez
>
> Andrés,
>
> You are right about null move of course. The assumption that other
> moves are >= to the value of a pass is much stronger in GO than in
> Chess, yet ironically it's not as effective in Go.
That was what i was trying to say. Pass is one of the worst moves
(except final) is good for null-move on Go. Of course you have
reduced depth, probably bad with alpha-beta with a bad evaluation
function, but looks interesting with UCT reducing the number of
simulations and increasing the % value. I don't use UCT, so I
haven't tried it.
Andrés
Rémi Coulom
>
> IIRC, a few Microsoft researchers did some interesting work with SVMs
> and the prediction of pro-level moves. I've always wondered whether
> that could be integrated with UCT to narrow the search tree.
This is what I do in Crazy Stone:
http://remi.coulom.free.fr/Amsterdam2007/
Mango does something similar, too.
Rémi
Rémi Coulom
UCT does no alpha-beta pruning, so null-move pruning cannot be used.
Rémi
Rémi Coulom
> Andrés Domínguez wrote:
>> 2007/10/10, Don Dailey <drda...@cox.net>:
>>
>>> Andrés,
>>>
>>> You are right about null move of course. The assumption that other
>>> moves are >= to the value of a pass is much stronger in GO than in
>>> Chess, yet ironically it's not as effective in Go.
>>>
>>
>> That was what i was trying to say. Pass is one of the worst moves
>> (except final) is good for null-move on Go. Of course you have
>> reduced depth, probably bad with alpha-beta with a bad evaluation
>> function, but looks interesting with UCT reducing the number of
>> simulations and increasing the % value. I don't use UCT, so I
>> haven't tried it.
>>
>> Andrés
>>
> Hi,
>
> UCT does no alpha-beta pruning, so null-move pruning cannot be used.
>
> Rémi
I did not read your reply carefuly before answering, sorry. I still
don't believe your approach could work. You would waste a lot of
simulations searching a bad move, and it would be extremely difficult to
determine how much the % value should be increased. In alpha-beta tree
search, you only need to determine that one move is better than another,
regardless of the difference in value. In UCT, it is very important to
also determine how much better one move is. I cannot see any reasonable
approach to determine how much the null move is worse than the others.
Depending on very subtle details of the position, it could be a lot or
very little.
Regarding the question of null move in Go, I remember that some
programmers who tried it in alpha-beta programs did not manage to make
it work (Peter MacKenzie comes to mind, maybe others). As Don wrote, the
main problem of null move is the depth reduction. It hides long-term
threats that the evaluation function might not be able to evaluate.
Erik van der Werf
> In GO, threats tend to be very indirect and distant, at least from the
> point of view of a naive search algorithm and this is a real killer to
> the idea - my feeling is that null move in GO is not workable.
I have the same feeling. Some years ago in Magog I did quite a lot of
experiments with tricks like (recursive) null move pruning. Although
it provided significant reductions in the search tree it consistently
made the program play weaker. The only trick that (almost) seemed to
work was Multi-Cut.
Erik
steve uurtamo
> main problem of null move is the depth reduction. It hides long-term
> threats that the evaluation function might not be able to evaluate.
even with a very good evaluation function, i would think that another problem
(this is likely just restating what you and others have already said) is that your opponent
can quite readily often crush you if you pass, even if he plays what would
otherwise be a fairly substandard move. the sheer advantage of having sente for
free can be huge. at the beginning of the game it's an entire handicap stone,
and near the endgame it can mean several new ko threats. in the middle game
it means winning any reasonable liberty race, turning many reasonable kills into
sekis, blocking any ladder, etc. so it wouldn't, generally, ever generate any cutoffs,
and yet you'd be checking it with every move for effectively no reason.
there is a related concept that go players actually do use, and it has to do
with reordering a set of moves that have been played to see if it changes the
position. tewari analysis -- this is probably more useful than null-move pruning,
as it should be able to make a relatively weak evaluation function act stronger.
s.
____________________________________________________________________________________
Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more.
http://mobile.yahoo.com/go?refer=1GNXIC
Magnus Persson
>
> Regarding the question of null move in Go, I remember that some
> programmers who tried it in alpha-beta programs did not manage to
> make it work (Peter MacKenzie comes to mind, maybe others). As Don
> wrote, the main problem of null move is the depth reduction. It hides
> long-term threats that the evaluation function might not be able to
> evaluate.
I used null-moves in my old program Viking which used alpha-beta with lazy
MC-Evaluation. It worked in the sense that it searched deeper, but I never
observed an increase in playing strength. This might of course mean that the
implementation was buggy or could be improved somehow.
--
Magnus Persson
Berlin, Germany
Ray Tayek
>Found this link and thought you all might find it interesting.
>
>http://www.spectrum.ieee.org/oct07/5552
thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244
---
vice-chair http://ocjug.org/
Chris Fant
"Monte Carlo techniques have recently had success in Go played on a
restricted 9-by-9 board. My hunch, however, is that they won't play a
significant role in creating a machine that can top the best human
players in the 19-by-19 game."
The author loses credibility with this statement.
Richard J. Lorentz
Don Dailey
Hash: SHA1
He is clearly posing for a picture, this is not a spontaneous
photograph. Notice the "Thinker" pose.
I'm not a good go player at all, but the board position seems a little
unnatural to me. But it could be my lack of experience.
Over the last few decades, there have been may movies and television
shows where a chess board appears in some scene with perhaps someone
player a game. These are almost always WRONG in some obvious way.
For instance someone plays a move and announces check. Then the
response is a checkmate! Possible, but highly improbably. Very
common is the king and queen on the wrong squares or a pawn on the 1st
rank or something else really silly. Although a king and queen could
move to these squares, it's extremely unlikely, especially near the
opening.
- - Don
> ------------------------------------------------------------------------
>
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDZWKDsOllbwnSikRAjGzAKDKUOHaEPnme19+d/UxJkSsNbJrzwCgiJeH
/CvKCzEEo8Ds5e8+ZFA1BbU=
=t0zW
-----END PGP SIGNATURE-----
Don Dailey
Hash: SHA1
Chris Fant wrote:
> I'm just now reading the article.
>
> "Monte Carlo techniques have recently had success in Go played on a
> restricted 9-by-9 board. My hunch, however, is that they won't play a
> significant role in creating a machine that can top the best human
> players in the 19-by-19 game."
>
> The author loses credibility with this statement.
Monte Carlo is the best thing going right now and the most probable
future direction, software or hardware - that's my hunch anyway!
- - Don
>
> On 10/10/07, Ray Tayek <rta...@ca.rr.com> wrote:
>> At 02:33 PM 10/7/2007, you wrote:
>>> Found this link and thought you all might find it interesting.
>>>
>>> http://www.spectrum.ieee.org/oct07/5552
>> thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244
>>
>>
>> ---
>> vice-chair http://ocjug.org/
>>
>>
>> _______________________________________________
>> computer-go mailing list
>> compu...@computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDZZMDsOllbwnSikRAj1JAJ94Msw1bcN0Iu4gpAR3XuQuCkpkKQCfeuwc
T7o/PxRxGxSanLOc7kug3Wg=
=6fTh
-----END PGP SIGNATURE-----
steve uurtamo
it certainly hasn't already played such a role, and there is
no evidence that it will or can.
s.
----- Original Message ----
From: Chris Fant <chri...@gmail.com>
To: computer-go <compu...@computer-go.org>
Sent: Wednesday, October 10, 2007 9:15:18 PM
Subject: Re: [computer-go] Former Deep Blue Research working on Go
I'm just now reading the article.
"Monte Carlo techniques have recently had success in Go played on a
restricted 9-by-9 board. My hunch, however, is that they won't play a
significant role in creating a machine that can top the best human
players in the 19-by-19 game."
The author loses credibility with this statement.
On 10/10/07, Ray Tayek <rta...@ca.rr.com> wrote:
> At 02:33 PM 10/7/2007, you wrote:
> >Found this link and thought you all might find it interesting.
> >
> >http://www.spectrum.ieee.org/oct07/5552
>
> thread on slashdot: http://slashdot.org/article.pl?sid=07/10/10/1758244
>
>
> ---
> vice-chair http://ocjug.org/
>
>
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
_______________________________________________
computer-go mailing list
compu...@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
____________________________________________________________________________________
Catch up on fall's hot new shows on Yahoo! TV. Watch previews, get listings, and more!
http://tv.yahoo.com/collections/3658
Chris Fant
"At the 19x19 level, Monte Carlo programs are now at the level of the
strongest traditional programs."
[https://webdisk.lclark.edu/drake/publications/GAMEON-07-drake.pdf]
And MC programs are more scalable that traditional programs. That
seems like some evidence that it can or will. Especially given that
the current techniques are still so young.
Don Dailey
Hash: SHA1
Let's cut to the chase and the real issue:
"Monte Carlo techniques have recently had success in Go played on a
restricted 9-by-9 board. My hunch, however, is that they won't play a
significant role in creating a machine that can top the best human
players in the 19-by-19 game."
This statement is more about the feasibility of Monte Carlo techniques
on the 19x19 board than it is about beating the top human player.
The author wants to design an alpha/beta brute force searcher on big
hardware because he thinks IT WILL play a significant role and Monte
Carlo WILL NOT.
Since we don't know if this will every happen in our life-times a more
interesting question in my opinion is this:
Will programs having a significant Monte Carlo component (perhaps UCT)
be able to dominate program NOT having a significant Monte Carlo
component in the near future?
That's really what we are talking about.
I can only guess, but right now I have a strong "hunch" that the basic
Mogo approach is the best way forward.
I know a way we can try to answer that question right away - I will post
about it in a minute.
- - Don
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDjA+DsOllbwnSikRAmNbAJ4yF2eeGHUJHGb+0ZuwerxVOP423wCg5FQ+
9WZ3ZLDZxW5NN/4ncCkjOCE=
=P1DI
-----END PGP SIGNATURE-----
Eric Boesch
> 2007/10/9, Eric Boesch <ericb...@gmail.com>:
> > almost every move is better than passing,
>
> I think this is not the point of null move. Null move is "if pass is good enough
> to an alpha cut, then will be a _better_ move". It is not important if
> pass is the
> worse move, is important that there is a better (>=) move than pass (not
> zugzwang). Then you bet searching not so deep.
Sorry, that was sloppy writing in several places. I was not trying to
argue why null-move pruning (NMP) would give the wrong answer, but
why, even if NMP performs as intended and horizon effects don't spoil
its evaluation, it might not prune many moves. The hope is to prune
variations that are bad and lopsided enough that starting at some
point, one side loses the equivalent of a whole move compared to, er,
more or less, correct play by both sides, right? The fraction of
variations that fit that description will increase with the depth of
the tree and the variability of move quality. The depth and
variability are both likely to be lower in global go search than in
global chess search. (As for local go search, as I already explained,
I think that even if NMP is effective when compared with bare-bones
alpha-beta, it is still less effective than other approaches like
lambda search.)
If all moves except pass for both players are better than nothing,
then if NMP works as intended, no moves will be pruned in the first
two plies of the search (it takes at least two moves by the same
player to fall a full move behind). If an average move is more than
two-thirds as valuable as the best move -- which is usually true in go
for, very roughly, the first 20 moves of a typical 19x19 game --
you'll have to go six levels deep before you see many NMP cutoffs
(even if white's sequence is below average and cumulatively a move
worse than best, it may not lose a full move to black's imperfect
responses, so only a minority of 6-ply sequences will be eligible, and
then you have to consider how many of those sequences would be cut off
by alpha-beta anyhow -- I would assume the sequences that NMP might
prune would be cut off by ordinary alpha-beta at a greater rate than
more balanced sequences would be). You won't see NMP cutoffs at the
bottom of the tree, either, because it's too late to prune then. If
NMP doesn't prune much near the root or the deepest nodes, and the
tree is not very deep because the branching factor and static
evaluation cost are high enough that there isn't time to search very
deeply, then NMP isn't doing much, period. I think that is at least
part of what has limited the benefits of null move pruning for
full-breadth global search in go. Selective global search allows
deeper searches, but a good selector should prune away most of the
sequences NMP might otherwise have caught.
None of this is an argument that NMP would be literally useless, just
that it's unlikely to lead to a dramatic strength improvement. Even in
chess, Chrilly Donninger said NMP was good for, what, 100 Elo points?
The only alpha-beta tweak that can add 400 Elo to a chess program on
its own is transposition tables, and everybody already has those. That
makes it difficult to understand why non-go-programmers are sometimes
so willing to believe that just souping up an alpha-beta search could
turn today's top go programs, which I would say are at about the go
equivalent of class B at 19x19, into the go equivalent of
grandmasters. A simple-but-fast full-breadth alpha-beta go solver
would have even further to go to reach grandmaster level, because it
would need to reach the level of being competitive with the top tier
of extant programs first (which no such program currently is). Either
way, in terms of performance measured in human terms, the jump from
the state of the art to world-champion-caliber play would be a far
bigger leap beyond the state of the art than Deep Thought and Deep
Blue ever made. (The "leap" to dan level, if gaining just two stones
can be called that, surely requires only throwing a little more
hardware at existing programs.)
Okay, enough of that. If people aren't persuaded by other programmers'
experience trying to map computer chess methods to computer go in a
straightforward way, then they're not likely to be convinced by my
hand-waving arguments either.
[Regarding programmers' experience: when a top chess programmer
(Chrilly) and a successful go programmer (Peter Woitke) collaborated
on a chess-style go program, the result fell -- at last report, anyhow
-- about 600 Elo points short of the top tier of programs at 9x9, and
presumably much farther short at real go. (The 600 figure is derived
from Chrilly's claims of a 60% success record against GnuGo, and
GnuGo's placement nearly 700 Elo points behind Mogo on CGOS -- 9x9 is
not GnuGo's long suit.) That should dispel any residual hopes that
applying state-of-the-art chess-search techniques to a go program
otherwise short on distinguishing ideas could yield a state-of-the-art
go program, let alone something stronger. (I assume Suzie does have
other distinguishing ideas, but surely it would only be weaker without
them.)]
Don Dailey
Hash: SHA1
Several points:
Null move is usually applied to a beta cutoff - but of course this is
mostly semantics. In the literature if you can "pass" (play the null
move) and still get a beta cutoff then you are in a fruitless line of
play because your opponent has the power to avoid this line of play.
Null move is pointless without a depth reduction, otherwise it just adds
1 extra node to this level in many cases.
When I played around with null move it only hurt the program some -
because it does reduced the tree significantly which partially
compensates for the reduced quality of the tree. That gives some hope
that it's not totally stupid but it would need some bolstering somehow.
Null move is nothing more than a test. If there is some other way to
estimate an upper or lower bound on the score, it could be used the same
way that null move is.
Alpha Beta pruning hasn't been explored to it's full potential in
computer GO. Translating a chess program to go by itself is not going
to work but in my experience there is some pretty strong evidence that
you can be a lot more sloppy about selectivity in Go. For instance
you can throw out a lot of moves without it killing the search
completely. In chess you have to be paranoid about which move you can
throw out.
The secret is that you don't throw out any move permanently, unless you
can prove admissibility. You taper the search. Perhaps with patterns
you can eliminate most of the moves NEAR the leaf nodes, but at some
point you have to reintroduce them. Null move is a recursive
mechanism to re-introduce moves but we probably need something else in
GO.
One thing is clear - if alpha beta is to be workable it has to be
extremely liberal about pruning moves.
- - Don
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDktPDsOllbwnSikRAoNpAJ4sup2J3uYc8hnQY1NGg8CgWbEcTwCgiyPx
MhxAlANrJdla0Sy6ahw50ws=
=kx0p
-----END PGP SIGNATURE-----
David Fotland
I would not agree with this statement. I think it is likely that the
current Monte Carlo programs can get good results agaisnt traditional
programs, but I don't think they are as strong against people. Certainly
they don't play in a human style. One of the resons they do well against
knowledge based programs is that they play strange moves (at 19x19). I
think people are more able to exploit the way the programs play.
I do agree that since monte carlo is scalable, these programs will improve
much faster than traditional programs.
David
> -----Original Message-----
> From: computer-...@computer-go.org
> [mailto:computer-...@computer-go.org] On Behalf Of Chris Fant
> Sent: Thursday, October 11, 2007 5:24 AM
> To: computer-go
> Subject: Re: [computer-go] Former Deep Blue Research working on Go
>
>
> In your own paper you say:
>
> "At the 19x19 level, Monte Carlo programs are now at the
> level of the strongest traditional programs."
> [https://webdisk.lclark.edu/drake/publications/GAMEON-07-drake.pdf]
>
>
Don Dailey
Hash: SHA1
I thought Monte Carlo plays and thinks MORE like human players. That
might make them easier to beat, I don't know. Playing "like" a human
doesn't imply they are harder to beat. I have heard people complain
that they couldn't beat the early chess programs BECAUSE they didn't
play normal moves.
You would know more than me because you are much stronger. But you
claim they are better against the more human knowledge based programs
for the reason I stated, that they play strange moves. But why should
that not help against humans who play more "human like?"
You are basically saying there is a great deal of in-transitivity
between humans, monte carlo players, and knowledge based players. I
don't believe there is that much. For instance when Mogo dominated at
9x9 it was found that it is also quite strong against humans (compared
to other kinds of programs.)
I know the argument that I will hear - 19x19 isn't 9x9. I believe in
Occams razor - whichever program proves to be stronger in head to head
is probably stronger against other opponents - at least that is the
simple conclusion and the burden of proof should go to the one claiming
otherwise. I don't have any problem with you being right - but you are
claiming something that is contrary to the simplest explanation.
- - Don
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDnNYDsOllbwnSikRAtYJAJ9AtB5QlGYZl7YIPI8nPTMW1AW0cACgg3Ly
ryaPGSKLsPRhyAu3KedBxEk=
=zXh0
-----END PGP SIGNATURE-----
David Fotland
about the strong moves. When Mogo plays an unconventional move, Many Faces
has less knowledge, and is more likely to do something really stupid.
People are more able to respond well to odd moves.
9x9 is a different case, since mogo plays nearly perfectly once the opening
is done, unless there is a rare tactic that falls outside the uct tree so
the monte carlo doesn't see it. In 19x19 middle games, mogo is still
relying on the monte carlo playouts rather than the uct tree, so it is more
sensitive to tactics. I've watched it play 19x19, and it plays greedy for
territory while leaving many weaknesses. A human will focus on the
weaknesses and find some deep tactics to exploit them. Many Faces won't do
this since it expects the opponent to play the "honest" move and not leave
this kind of weakness.
But the only way to settle this is to do some experiments. I could
certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and
we also have them play for ratings against people on kgs, it would settle
it.
Don Dailey
Hash: SHA1
Good common sense answer. I agree that this could be settled.
I'll go ahead and help Chris Fant set up a the server which he will
administer.
Meanwhile, can you experiment with the 9x9 server just to see if you can
get it working on CGOS? You can use any anonymous name.
- - Don
David Fotland wrote:
> It's because strong players play strong moves, and the program has knowledge
> about the strong moves. When Mogo plays an unconventional move, Many Faces
> has less knowledge, and is more likely to do something really stupid.
> People are more able to respond well to odd moves.
>
> 9x9 is a different case, since mogo plays nearly perfectly once the opening
> is done, unless there is a rare tactic that falls outside the uct tree so
> the monte carlo doesn't see it. In 19x19 middle games, mogo is still
> relying on the monte carlo playouts rather than the uct tree, so it is more
> sensitive to tactics. I've watched it play 19x19, and it plays greedy for
> territory while leaving many weaknesses. A human will focus on the
> weaknesses and find some deep tactics to exploit them. Many Faces won't do
> this since it expects the opponent to play the "honest" move and not leave
> this kind of weakness.
>
> But the only way to settle this is to do some experiments. I could
> certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and
> we also have them play for ratings against people on kgs, it would settle
> it.
>
> David
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDnfuDsOllbwnSikRAjIxAKDMtn/IC7ybKC40Gc73k93y5zkOxACg4qoT
JOZy56ZHYDPqyno9XMqLhuk=
=9Kou
David Fotland
The results have aged off the server, but I think it had a rating between
1750 and 1850. So I had working GTP code about 8 months ago. I'll give it
a try today on 9x9 to see if it still works.
> -----Original Message-----
> From: computer-...@computer-go.org
> [mailto:computer-...@computer-go.org] On Behalf Of Don Dailey
> Sent: Thursday, October 11, 2007 12:22 PM
> To: computer-go
> Subject: Re: [computer-go] Former Deep Blue Research working on Go
>
>
Eric Boesch
> But the only way to settle this is to do some experiments. I could
> certainly be wrong. If we have a mogo-many faces match on 19x19 cgos, and
> we also have them play for ratings against people on kgs, it would settle
> it.
Mogobot1 and mogobot2 are rated 2k and 3k, respectively, on KGS.
CrazyStone is rated 2k. All of these numbers are with moderate time
controls (not the 15 minute sudden death time controls that became a
subject of controversy).
There was also KCConGui, running KCC Igo, that played for a while on
KGS. I don't know whether it was an official bot, or whether its
departure had anything to do with its lopsided losing record against
CrazyStone. The KCConGui page notes that KCC Igo won the Gifu
Challenge four years in a row, most recently against sparse
competition, but the best claim to the computer go throne belongs to
Steenvreter, for edging out Mogo and CrazyStone in the stronger ICGA
tournament.
Chris Fant
there, Erik?
Ian Osgood
On Oct 11, 2007, at 1:49 PM, Eric Boesch wrote:
> On 10/11/07, David Fotland <fot...@smart-games.com> wrote:
>> But the only way to settle this is to do some experiments. I could
>> certainly be wrong. If we have a mogo-many faces match on 19x19
>> cgos, and
>> we also have them play for ratings against people on kgs, it would
>> settle
>> it.
>
> Mogobot1 and mogobot2 are rated 2k and 3k, respectively, on KGS.
> CrazyStone is rated 2k. All of these numbers are with moderate time
> controls (not the 15 minute sudden death time controls that became a
> subject of controversy).
>
> There was also KCConGui, running KCC Igo, that played for a while on
> KGS. I don't know whether it was an official bot, or whether its
> departure had anything to do with its lopsided losing record against
> CrazyStone. The KCConGui page notes that KCC Igo won the Gifu
> Challenge four years in a row, most recently against sparse
> competition, but the best claim to the computer go throne belongs to
> Steenvreter, for edging out Mogo and CrazyStone in the stronger ICGA
> tournament.
I thought Steenvreter only played 9x9 Go. The 19x19 ICGA tournament
winners were MoGo, CrazyStone, and GnuGo in that order.
Ian
Erik van der Werf
yet found enough time to work on 19x19. For now the throne rightfully
belongs to Mogo.
Erik
David Fotland
would be around 4k to 6k.
> -----Original Message-----
> From: computer-...@computer-go.org
> [mailto:computer-...@computer-go.org] On Behalf Of Eric Boesch
> Sent: Thursday, October 11, 2007 1:50 PM
> To: computer-go
> Subject: Re: [computer-go] Former Deep Blue Research working on Go
>
>
Eric Boesch
> I thought Steenvreter only played 9x9 Go. The 19x19 ICGA tournament
> winners were MoGo, CrazyStone, and GnuGo in that order.
How did I mess that up? Thanks for the correction.
terry mcintyre
It would be great to see Steenvreter on the 9x9 cgos server. BTW, can you translate "Steenvreter" for us English speakers? Thanks!
yet found enough time to work on 19x19. For now the throne rightfully
belongs to Mogo.
Erik
Chris Fant
Erik van der Werf
> It would be great to see Steenvreter on the 9x9 cgos server.
It is still on my to do list...
> BTW, can you translate "Steenvreter" for us English speakers? Thanks!
It is a combination of the Dutch words "Steen" and "vreter". (Dutch
has the nice property that we can glue words together to create new
ones.)
The translation of "steen" is "Stone".
"Vreter" is more difficult. "vreten" is a kind of rude form of eating,
like an animal. I don't really know an accurate translation, maybe
something like "devourer"?
On 10/12/07, Chris Fant <chri...@gmail.com> wrote:
> Someone already did: Stone eater.
Phonetically this may be the best option, but the meaning is bit
different. It would have been accurate for "Steeneter", but coming
from "Steenvreter" the implied lack of etiquette is lost in
translation.
Erik
Unknown
> Someone already did: Stone eater.
>
> On 10/11/07, terry mcintyre <terrym...@yahoo.com> wrote:
> >
> > Erik,
> >
> > It would be great to see Steenvreter on the 9x9 cgos server. BTW, can you
> > translate "Steenvreter" for us English speakers? Thanks!
"Eater" is a bit too weak, IMHO.
"Stone gobbler" or "stone muncher" seems more appropriate.
HTH,
AvK
steve uurtamo
> My hunch, however, is that they won't play a
> significant role in creating a machine that can top the best human
> players in the 19-by-19 game.
i agree with this statement.
> And MC programs are more scalable that traditional programs. That
> seems like some evidence that it can or will. Especially given that
> the current techniques are still so young.
i do not agree with this statement.
"top the best human players in a 19x19 game" is quite a bit different than
"at the level of the strongest traditional programs". "at the level of", or
"near the level of", or "slightly better than" just means (perhaps) that the
wheel has been re-invented. it could mean more than that, but there surely
doesn't seem to be much evidence for that at this point.
"scalable" doesn't mean linear, and it also doesn't give an asymptotic growth
function or a constant. if anyone anywhere could give a good estimate for how
many cpus it would take, with any particular algorithm, to beat a professional
player, and if the number were feasible, there's no reason not to start building
such a machine.
s.
____________________________________________________________________________________
Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out.
http://answers.yahoo.com/dir/?link=list&sid=396545433
Don Dailey
Hash: SHA1
Hi Steve,
I don't fully understand what you are saying here.
steve uurtamo wrote:
> I think that there's an apples/oranges thing going on here.
>
>> My hunch, however, is that they won't play a
>> significant role in creating a machine that can top the best human
>> players in the 19-by-19 game.
>
> i agree with this statement.
My hunch is that won't happen for a few decades. If I'm right, then
it's too far to predict which technique will do it. Probably something
new.
Again, it's more interesting to talk about which technique will become
the rage and produce the best programs in the short term.
I think that is UCT and it's happening now. UCT is the most promising
for 19x19 progress that we have now.
>> And MC programs are more scalable that traditional programs. That
>> seems like some evidence that it can or will. Especially given that
>> the current techniques are still so young.
>
> i do not agree with this statement.
I think this statement is more or less true. Didn't you see the
scalability data for 19x19? In fact didn't you help me produce it?
> "top the best human players in a 19x19 game" is quite a bit different than
> "at the level of the strongest traditional programs". "at the level of", or
> "near the level of", or "slightly better than" just means (perhaps) that the
> wheel has been re-invented. it could mean more than that, but there surely
> doesn't seem to be much evidence for that at this point.
This is a hard paragraph to understand. I wish you had included the
statement that you are referencing here and who said it.
In what sense could this be the wheel re-invented?
It appears to be the case that 19x19 UCT MC programs are "better than"
the traditional program now. At least from the email from Rémi.
I'm not sure what you imply by lack of evidence, but the evidence is
getting pretty strong in favor of UCT type programs being superior if
that's what you mean. It isn't even a question at smaller boards.
> "scalable" doesn't mean linear, and it also doesn't give an asymptotic growth
> function or a constant. if anyone anywhere could give a good estimate for how
> many cpus it would take, with any particular algorithm, to beat a professional
> player, and if the number were feasible, there's no reason not to start building
> such a machine.
There is almost a constant ELO improvement for each factor of speed
increase such as a doubling. This may not apply to every
implementation - it's possible to apply non scalable improvements that
may have to be removed later. I think Mogo did this earlier with a
scheme to reduce the work in earlier version of the 19x19 player. I
figured they would have to remove this eventually because it seemed
cheesy to me. And sure enough they did.
I'm sure some will believe this observed scalability is short lived but
I know of no reason to believe that other than superstition.
Even to this day, people keep thinking this about computer chess. My
friend and former partner Larry Kaufman recently told me that many were
surprised that the scalability of extra CPU power in chess has remained
nearly linear. For decades now it was predicted that this was "about to
end" based purely on irrational hunches but this hasn't happened yet.
Yes, it has gradually tapered, but it's been remarkably gradual and now
computers are playing well above the best humans and computers rarely
lose a game to the best humans. Even more remarkable is that there is
a fight among the best computers - they vary significantly in strength
and this is an indication that there is still a long way to go. There
is no indication whatsoever than computers are even close to topping out
in computer chess.
That's why I believe a super hardware gizmo could easily be built that
would be in the DAN range somewhere at 19x19, at least low Dan. I'm
not so bold as to predict that it will be at top human levels any time
soon though.
- - Don
> s.
>
>
>
>
>
> ____________________________________________________________________________________
> Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out.
> http://answers.yahoo.com/dir/?link=list&sid=396545433
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDtNEDsOllbwnSikRAmy0AKDc57sD8hl+t8pWXR4izlTB2AIXaACgofqs
P21m+sIN+Bx8gqWpbrx+bLI=
=u+Pm
-----END PGP SIGNATURE-----
steve uurtamo
> for 19x19 progress that we have now.
yes, it's new, and it's doing quite well. my hunch is simply that a few
thousand more ELO are not going to happen in hardware with this method.
> I think this statement is more or less true. Didn't you see the
> scalability data for 19x19? In fact didn't you help me produce it?
we tested some very low ELO ranges. speculating about how that
scales up to the "upper stratosphere" of ELO is pretty difficult for
me. it wasn't straight enough for me to believe that it doesn't go
"log" at some point nearby and start to cripple the doubling of cpu
advantage.
> This is a hard paragraph to understand. I wish you had included the
> statement that you are referencing here and who said it.
oh, this is just in response to the quote from the paper. my point
was simply that doing very well is easy for a new method, and doing
as well as the state-of-the art, or even doing slightly better, is interesting,
new, and exciting, but that we shouldn't extrapolate to imagine
that it will solve future problems.
> In what sense could this be the wheel re-invented?
in the sense that 19x19 is still brutally difficult, and that these
methods haven't improved the state of the art by more than a stone
or two, if that. so we should definitely not extrapolate, or expect
them to perform, any better than we already have evidence for.
> It appears to be the case that 19x19 UCT MC programs are "better than"
> the traditional program now. At least from the email from Rémi.
i'll let david fotland field this. a stone or two is a good thing, but i'm
not yet convinced that it scales, in a real-world way, to the additional
15 stones or so required to beat top humans.
> I'm not sure what you imply by lack of evidence, but the evidence is
> getting pretty strong in favor of UCT type programs being superior if
> that's what you mean. It isn't even a question at smaller boards.
i agree that on smaller boards UCT-type programs are superior.
without trying too hard to sound like an apologist/traditionalist, i will mention that
boardsize isn't merely a "scaling factor" in this problem. things change
in a fundamental way inbetween 9x9 and 19x19 that direct search can't
recognize. (this is essentially what monte carlo methods are doing, as
they are somewhat carefully sampling from the move distribution).
> I'm sure some will believe this observed scalability is short lived but
> I know of no reason to believe that other than superstition.
i hate to do this, but i'll give you an analogy that i think is relevant.
if you crawl at 1/2 mph across the desert for 7 years, encounter a
tiny hill, and manage to scale it, you may say to yourself that you've
made a massive accomplishment. and you have. but it doesn't
imply, entail, or otherwise suggest that all future obstacles will be
of similar size.
honestly, 9x9 doesn't even leave *room* for some of the important
problems that are critical on a 19x19 board. those problems don't exist on
a small board because it's a full-on tactical fight from the get-go. this
is a different kind of problem than being willing to trade 40% of the board
for a 51% likelihood of getting 41% of the board in exchange. 9x9 is
about getting a 100% likelihood of winning as soon as possible.
> There is no indication whatsoever than computers are even close to topping out
> in computer chess.
don't get me wrong -- computers are remarkably good at chess. much
better than people. all at once, the world's best player lost a few games
to a computer, and then the whole thing skyrocketed. it was pretty amazing
to watch.
right now we're talking about computers possibly playing go at the level of
someone who thinks about the game but who would be absolutely crushed in a
simultaneous demonstration by a professional. is that around 1500 in chess?
how little hardware could you get away with and still play at the 1500 level
in chess these days? could my phone do it? could my pc, as a screensaver?
> That's why I believe a super hardware gizmo could easily be built that
> would be in the DAN range somewhere at 19x19, at least low Dan. I'm
> not so bold as to predict that it will be at top human levels any time
> soon though.
i think that we're likely in agreement here. crazy hardware could get you into
the 1 dan range, but professional play is way, way out of bounds at this point.
to see why i think this, watch a 7d game on kgs and listen to the 1d kibitz.
note how ridiculously out-of-touch they are with the game that is going on
in front of them. pro play is yet another magnitude or two of "out of touch" from
amateur play.
Don Dailey
Hash: SHA1
Hi Steve,
So this doesn't get too lengthy I'll remove the stuff I'm not responding
to.
>> I think this statement is more or less true. Didn't you see the
>> scalability data for 19x19? In fact didn't you help me produce it?
>
> we tested some very low ELO ranges. speculating about how that
> scales up to the "upper stratosphere" of ELO is pretty difficult for
> me. it wasn't straight enough for me to believe that it doesn't go
> "log" at some point nearby and start to cripple the doubling of cpu
> advantage.
But why would it suddenly go "log" at some point nearby? This is the
same superstition people had in computer chess for decades! Everyone
had this gut feeling based on nothing whatsoever.
> in the sense that 19x19 is still brutally difficult, and that these
> methods haven't improved the state of the art by more than a stone
> or two, if that. so we should definitely not extrapolate, or expect
> them to perform, any better than we already have evidence for.
What do you consider evidence? If every doubling so far has yielded
the same approximate improvement then I would say the evidence is pretty
good that the next one will. I guess you believe there is no evidence
the next one will?
> i agree that on smaller boards UCT-type programs are superior.
> without trying too hard to sound like an apologist/traditionalist, i will mention that
> boardsize isn't merely a "scaling factor" in this problem. things change
> in a fundamental way inbetween 9x9 and 19x19 that direct search can't
> recognize. (this is essentially what monte carlo methods are doing, as
> they are somewhat carefully sampling from the move distribution).
>> I'm sure some will believe this observed scalability is short lived but
>> I know of no reason to believe that other than superstition.
>
> i hate to do this, but i'll give you an analogy that i think is relevant.
> if you crawl at 1/2 mph across the desert for 7 years, encounter a
> tiny hill, and manage to scale it, you may say to yourself that you've
> made a massive accomplishment. and you have. but it doesn't
> imply, entail, or otherwise suggest that all future obstacles will be
> of similar size.
>
> honestly, 9x9 doesn't even leave *room* for some of the important
> problems that are critical on a 19x19 board. those problems don't exist on
> a small board because it's a full-on tactical fight from the get-go. this
> is a different kind of problem than being willing to trade 40% of the board
> for a 51% likelihood of getting 41% of the board in exchange. 9x9 is
> about getting a 100% likelihood of winning as soon as possible.
Everyone likes to romanticize this fact. Of course there are a lot of
differences but that has nothing to do with how scalable the problem is.
All you are really saying is that it's more difficult and complicated -
that is totally unrelated to scalability.
These conceptual hills are not barriers, they are hills. These same
barriers were imagined to exist in computer chess too. Many masters
criticized the nature of search and said computers would never be able
to do long term planning and this was certain to create a sudden
standstill and it was "just around the corner" always. But it never
happened.
What DID happen is that there were always some hills the computer
couldn't climb over and there still are, but it had nothing to do with
their improvement rate. Your fallacy is that you believe the
landscape is relatively smooth, but with some monster unscaleable hill
just out of sight. The truth is there are many different hills of all
different sizes. Each improvement will enable the program to climb over
one or two it couldn't before. That's really how you should be
thinking of this. There is no wall around the corner.
>> That's why I believe a super hardware gizmo could easily be built that
>> would be in the DAN range somewhere at 19x19, at least low Dan. I'm
>> not so bold as to predict that it will be at top human levels any time
>> soon though.
>
> i think that we're likely in agreement here. crazy hardware could get you into
> the 1 dan range, but professional play is way, way out of bounds at this point.
> to see why i think this, watch a 7d game on kgs and listen to the 1d kibitz.
> note how ridiculously out-of-touch they are with the game that is going on
> in front of them. pro play is yet another magnitude or two of "out of touch" from
> amateur play.
I think professional play is a long way off too. But I also believe
this is romanticized too much. As I gradually became better at chess I
learned that a lot of concepts were just barely out of reach and not
really that big a deal. With just a little extra understanding a
profound move becomes rather simple but if you don't understand it it
seems like magic. Great players have a LOT of these and we look at
their games and imagine them to be gods.
- - Don
>
> s.
>
>
>
>
>
>
> ____________________________________________________________________________________
> Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out.
> http://answers.yahoo.com/dir/?link=list&sid=396545433
> _______________________________________________
> computer-go mailing list
> compu...@computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFHDuybDsOllbwnSikRAtURAJ9h36+D4GVslJjFToE5mnLE15gN0gCfb5j7
Aso/3/mZrA7YKD4O9IPPbuc=
=//AV
-----END PGP SIGNATURE-----
Dave Dyer
Considering how monte carlo actually works, I think it's plausible
to argue that it works best where the distance to endgame is small.
For a 19x19 board, the playing speed may be only a factor of 4 worse,
but the effective learning speed for an opening position might be
exponentially worse. In other words, doing 4x as many playouts won't
get you to the same quality of play. I'm not aware of any data about
what the scaling exponent is, but I'll wager 1 is not the answer.
alain Baeckeroot
>
> Considering how monte carlo actually works, I think it's plausible
> to argue that it works best where the distance to endgame is small.
>
- Fuseki is done agaisnt a 10k with vague but consistent "cosmic style".
- End game is played agaisnt a high dan opponent ! and you lose ;-)
For me this is the most difficult to manage when playing mogo : i must
force myself to take a huge lead before end-game.
Alain
terry mcintyre
>Considering how monte carlo actually works, I think it's plausible
> to argue that it works best where the distance to endgame is small.
> but the effective learning speed for an opening position might be
> exponentially worse. In other words, doing 4x as many playouts won't
> get you to the same quality of play. I'm not aware of any data about
> what the scaling exponent is, but I'll wager 1 is not the answer.
killed, this can be defended. For endgame moves, there is a method of analysis - if white
plays first , what is the local effect on the score? If black, what then? Who gets sente? That
information is cached, and periodically checked - did such-and-such a play alter the status?
These strategies greatly winnow the search tree. ( I'd be tempted to dynamically add and alter
callback patterns which would trigger appropriately. )
When it comes to opening moves, it might be that programs need to use opening books,
joseki patterns, and rules of thumb to narrow the search process. The evaluator, as some
have suggested, should differ in the opening; instead of playing out to the bitter end, a
rough map of expectations should suffice. Designing such a mapping function would
be an interesting machine learning exercise; self-play could tune the results.
A few days ago, I was playing a teaching game with a 5 dan player. At several points, he used
a form of local null-move analysis, though he didn't call it that. If black plays X, and white ignores
that play, black follows up with Y - with devastating results. Therefore, white must reply to X,
unless white has an even bigger threat. Having sente, and a position slightly altered in his favor,
black then plays Z, which kicks white in the head. But Z before X does not work so well ... move
order often makes the difference between a very strong and a weak play.
A poster recently mentioned 19x19 games and handicap stones. This would help to quickly separate
wheat from chaff. If program A could defeat all contending programs more than half the time with a
two or three stone handicap, we'd take that as clear evidence of superiority. This could spur the development
of much stronger programs. We know that top human players can give the strongest current 19x19 programs a
9 stone handicap and win better than half the time. Future programs, evolved to give current contenders a
large handicap and win, will be a lot closer to beating top human players.
Moody friends. Drama queens. Your life? Nope! - their life, your story.
Play Sims Stories at Yahoo! Games.
steve uurtamo
>
> So this doesn't get too lengthy I'll remove the stuff I'm not responding
> to.
no problem.
> But why would it suddenly go "log" at some point nearby? This is the
> same superstition people had in computer chess for decades! Everyone
> had this gut feeling based on nothing whatsoever.
well, every continuous function is well-approximated by a linear function
at a small enough scale, right? so we should expect to see linearity
over a reasonably small range. if we don't know the function and don't
have datapoints from anywhere other than the beginning of the function,
we can't really say much about datapoints at the end of the function, much
less guess the function itself.
having sparse datapoints from all over the function would give more information
than having really detailed datapoints at the "easy" end of the function.
unfortunately, it's really difficult to get datapoints further down the function.
so i'm not sure that we can extrapolate from one end of the function to the
other. that's all.
in a physics experiment you sample from all over the range where you think
that your fitting function is appropriate. it would be unreasonable to sample
from one end and make claims about the other end.
the number of doublings is relevant here as well -- the valid human ELO
range in chess is quite a bit smaller than the same for go. we can obtain
datapoints from all over the chess ELO range. we don't have the same for go.
> What DID happen is that there were always some hills the computer
> couldn't climb over and there still are, but it had nothing to do with
> their improvement rate. Your fallacy is that you believe the
> landscape is relatively smooth, but with some monster unscaleable hill
> just out of sight. The truth is there are many different hills of all
> different sizes. Each improvement will enable the program to climb over
> one or two it couldn't before. That's really how you should be
> thinking of this. There is no wall around the corner.
that's a good point -- any incremental gain in strength may be by
having the ability to solve a completely different class of subproblems
(described in a completely different way) in the game than the ones that
humans try to solve.
> I think professional play is a long way off too. But I also believe
> this is romanticized too much. As I gradually became better at chess I
> learned that a lot of concepts were just barely out of reach and not
> really that big a deal. With just a little extra understanding a
> profound move becomes rather simple but if you don't understand it it
> seems like magic. Great players have a LOT of these and we look at
> their games and imagine them to be gods.
it's true that people are quite falliable -- i think that someone recently
posted on the list (with youtube video) an example of a big group being in
atari in a professional game and one of the two players not noticing.
this is the kind of error that would simply be impossible for any program
that can count liberties.
s.
____________________________________________________________________________________
Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news, photos & more.
http://mobile.yahoo.com/go?refer=1GNXIC
Chris Fant
steve uurtamo
s.
----- Original Message ----
From: Chris Fant <chri...@gmail.com>
To: computer-go <compu...@computer-go.org>
Sent: Friday, October 12, 2007 10:04:23 AM
Subject: Re: [computer-go] Former Deep Blue Research working on Go
____________________________________________________________________________________
Be a better Heartthrob. Get better relationship answers from someone who knows. Yahoo! Answers - Check it out.
http://answers.yahoo.com/dir/?link=list&sid=396545433
Tapani Raiko
> Ho can I find Go vids on youtube? Searching for "go" obviously does nothing.
>
>
http://www.youtube.com/watch?v=qt1FvPxmmfE
--
Tapani Raiko, <tapani...@tkk.fi>, +358 50 5225750
http://www.cis.hut.fi/praiko/
Peter Drake
steve uurtamo
face. losing the 5 stones is one thing, losing the second eye is
brutal.
s.
----- Original Message ----
From: Tapani Raiko <Tapani...@tkk.fi>
To: computer-go <compu...@computer-go.org>
Sent: Friday, October 12, 2007 10:36:01 AM
Subject: Re: [computer-go] Former Deep Blue Research working on Go
Chris Fant wrote:
> Ho can I find Go vids on youtube? Searching for "go" obviously does nothing.
>
>
Atari was also a good keyword here. There it is:
http://www.youtube.com/watch?v=qt1FvPxmmfE
--
Tapani Raiko, <tapani...@tkk.fi>, +358 50 5225750
http://www.cis.hut.fi/praiko/
_______________________________________________
Ray Tayek
>Chris Fant wrote:
> > Ho can I find Go vids on youtube? Searching for "go" obviously
> does nothing.
> >
> >
>Atari was also a good keyword here. There it is:
>http://www.youtube.com/watch?v=qt1FvPxmmfE
searching for: go baduk weiqi
returns a bunch.
---
vice-chair http://ocjug.org/
Chris Fant
closest I could find was this one which is almost unwatchable.
http://www.youtube.com/watch?v=uArhCnJu7LM
Ray Tayek
>How do I find the ones narrated in English?
not sure, i just found these things/
>Do they exist?
yes
>The
>closest I could find was this one which is almost unwatchable.
>
>http://www.youtube.com/watch?v=uArhCnJu7LM
all of the ones by her that i have seen are in english. searching
for: Guo Juan gives a few hundred! here is a new guy:
http://www.youtube.com/watch?v=zFImtHxZrEw i found searching on: go
baduk weichi.
Harri Salakoski
thanks.
>Do they exist?
I have watched many hilarious youtube stuff, but no clue to search go stuff,
great.
t. harri
----- Original Message -----
From: "Chris Fant" <chri...@gmail.com>
To: "computer-go" <compu...@computer-go.org>
Sent: Saturday, October 13, 2007 2:31 AM
Subject: Re: [computer-go] Former Deep Blue Research working on Go
Harri Salakoski
> Considering how monte carlo actually works, I think it's plausible
> to argue that it works best where the distance to endgame is small.
Build fuseki-joseki-extend scripted engine and change for monte-carlo engine
in middle game?
t. harri
Chris Fant
also what the strongest opener is, the strongest middle-gamer, and the
strongest finisher. It seems like a general consensus that UCT makes
for a strong finisher.
Christoph Birk
Christoph
Don Dailey
assume they are testing it?
- Don
Christoph Birk
> The mogo team is reviving it. Last I heard they had it working - so I
> assume they are testing it?
Do you know the web-page address?
Joshua Shriver
it, and possibly to host it. Though there was another taker so not
sure what it's current status is.
-Josh
Olivier Teytaud
>There was some chatter a while back concerning it. I offered to admin
>it, and possibly to host it. Though there was another taker so not
>sure what it's current status is.
>
>
>
but it is still unstable and under test. I have not mentioned it on the
list because
I wanted to make it stable before:
http://www.lri.fr/~teytaud/cgosStandings.html
If someone wants to test it, the port is 6919 on machine pc5-120.lri.fr.
10 minutes per side. But only try it if you want to take risks, it is
almost surely
not stable yet, and the connection might be refused for an unknown
reason :-)
All comments welcome.
Sincerly yours,
Olivier
Christoph Birk
> http://www.lri.fr/~teytaud/cgosStandings.html
>
> If someone wants to test it, the port is 6919 on machine pc5-120.lri.fr.
> 10 minutes per side. But only try it if you want to take risks, it is almost
> surely
> not stable yet, and the connection might be refused for an unknown reason :-)
Am really curious to see MFGO, Crazystone and Mogo play at 19x19.
But I suggest allowing more time, at least 20 minutes per side.
Christoph
Chris Fant
terry mcintyre
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
Rémi Coulom
> On Tue, 23 Oct 2007, Olivier Teytaud wrote:
>> http://www.lri.fr/~teytaud/cgosStandings.html
>>
>> If someone wants to test it, the port is 6919 on machine pc5-120.lri.fr.
>> 10 minutes per side. But only try it if you want to take risks, it is
>> almost surely
>> not stable yet, and the connection might be refused for an unknown
>> reason :-)
>
> Am really curious to see MFGO, Crazystone and Mogo play at 19x19.
> But I suggest allowing more time, at least 20 minutes per side.
>
> Christoph
Rémi
Don Dailey
Chris,
I think Olivier is using fast games only because he is testing the
server.
I want to see if Mogo can beat Many Faces at a level that at least
resembles what they play the top 19x19 computer Go tournaments.
But Olivier will be running the server, so it's his choice.
- Don
Don Dailey
- Don
Chris Fant wrote:
> What were the time controls for the previous (and short-lived) 19x19 cgos?
Chris Fant
On 10/23/07, Don Dailey <drda...@cox.net> wrote:
>
Olivier Teytaud
Ok for 30 minutes after the testing phase (for the tests
I guess that 10 minutes is too long :-) ).
For the moment I am trying to get the authorization
of opening a port for socket connection -
for the moment I guess only
people in the same laboratory as me can connect to
the machine, what is not a satisfactory behavior :-)
Olivier
David Fotland
fixed search limits, and only does time management if it runs low on time.
It can usually play a game in 10 minutes on the computer I'll use. It will
be slower against Mogo since the games are longer and there might me more
unsettled situations to read. If you do add more time, 15 or 20 minutes per
side should be enough.
David
David Fotland
David
> -----Original Message-----
> From: computer-...@computer-go.org
> [mailto:computer-...@computer-go.org] On Behalf Of
> Christoph Birk
> Sent: Tuesday, October 23, 2007 1:16 PM
> To: olivier...@inria.fr; computer-go
> Subject: Re: [computer-go] 19x19 CGOS
>
>
Jason House
I just tried it, but I can't connect.
That's expected. Past discussion seems to imply there's some kind of firewall (or similar) blocking external access.
Don Dailey
I argue that the matches should be longer, perhaps 30 minutes per
side. They should more closely resemble time controls used in a
serious competition.
Here is the reason I say that. One could argue that with computers it
doesn't matter, they do not need to be constrained as much by our sense
of time - they do not feel pressure or get rattled if they play too fast
and they don't get bored or lose focus if they play too slow. I've
argued that way myself many times.
However, the choice of time control, in my estimation, has a good
chance of influencing the outcome, especially if we view this as a test
of a strong commercial program versus a new experimental technology,
which I think it is. Mogo is a program that clearly performs better
with more time. I suspect that MFGO is a program that is close to
optimal at 10 or 15 minutes. I can't say that for sure, perhaps you
can give us your insights on that.
In such a case what is "fair" depends on the point of view of the
observer. If someone wanted to see Mogo dominate such a match he
would consider short time controls "unfair" and the opposite would be
true if one wanted to see Many Faces win. Of course I could be
wrong, perhaps Many Faces is the one that would benefit more from extra
time - but I'm working from the assumption that Mogo would benefit the
most based on my own knowledge of how UCT works.
Regardless of the time control used another issue is the selection of
hardware. Doubling the computer power effectively doubles the programs
thinking time.
Having considered all of these issues, and also taking into
consideration that this is a contest of sorts, it makes sense that we
should testing at a level that simulates or at least approaches serious
computer chess time-controls. Certainly no faster than 30 minutes
per side. These are levels at which most humans will take the results
seriously.
In addition to this, it makes sense to know what hardware and what
time-setting is being used. Many programs on CGOS were set to play
very fast, often indicated their level in the name of the program
something like "mogo4k" or something similar.
So if we set a liberal time control on CGOS 19x19 we could publish the
identify of the players and draw conclusion based on that. Mogo
could be tested at several levels and/or hardware configurations and so
could Many Faces. It's not difficult to set up a rotating script for
logging off one bot and starting up another. (By the way, the right
way to do this is to select the bot RANDOMLY, not to rotate back and
forth.)
The server does report the time each side spent calculating in the SGF
files, although it's not reported on the web sites, so this is useful
information if we are considering the scalability of programs. My
feeling is that there is likely to be a crossover point - that MFGO will
win at time-controls faster than this and Mogo will win at time-controls
slower than this. That point may be beyond what we can test, or it
may be testable on the CGOS server soon.
By the way, I would probably argue for longer than 30 minutes per
side, but for a server like CGOS that would involve a long wait between
matches.
Anyway, that's my 2 cents.
- Don
David Fotland
play in about 45 minutes on hardware available in 2000. It won't take
advantage of any extra time given. The global search is 1 ply with
quiescence, and always will always complete, and the local search sizes are
fixed at something like 200 nodes per search.
terry mcintyre
Among humans, that would be a brisk pace but not blitz - common time controls are 60 or 90 minutes, and much longer for some pro tournaments.
For computers, 30 minutes should give enough time to bump up the standard of play a few more kyu, while allowing enough games to be statistically interesting.
I'd still like to see handicap games between computers. Some programs, such as Mogo, dominate the field. Some are quite bad. Is the difference one or two stones, or is it nine or 27 stones? The handicap which gives something close to 50-50 ratio would give a useful idea. This would also encourage programs to learn something about how to deal with handicap stones effectively; it would broaden their range of expertise.
David Fotland
rounds over 1 1/2 days.
Don Dailey
get a substantial number of games in, so I think for practical reasons
we shouldn't go that far. Unless we set up a special server just
for Mogo vs ManyFaces. I could do that on my own computer.
I'm not sure what the status of the 19x19 server is, if it looks like
it isn't going to happen I have another option.
Olivier Teytaud
> it isn't going to happen I have another option.
Technically it works, but an authorization (for opening the ports
for computers out of the laboratory) is still missing.
But, if someone else wants to install it, no problem for me :-)
Olivier
Don Dailey
group when I'm ready - probably be tomorrow night.
- Don
steve uurtamo
> dominate the field. Some are quite bad. Is the difference one or two stones, or is it
> nine or 27 stones? The handicap which gives something close to 50-50 ratio would give
> a useful idea. This would also encourage programs to learn something about how to deal
> with handicap stones effectively; it would broaden their range of expertise.
with handicap stones. it'd be a great way for everyone else to learn how, too.
(since it would confuse and obscure many fixed opening book strategies).
s.
Christoph Birk
> I think I'm going to restart CGOS 19x19 on boardspace. I'll ping the
> group when I'm ready - probably be tomorrow night.
Thanks.
Christoph
Hideki Kato
The object I use cgos is to measure my program's performance against
other programs. Cgos is not a tournament in any sense. It should be
a tool for developers, I believe. Then, fairness is not so important
because I can estimate my program's performace at longer time
control easily. Most important thing for me is to know my program's
rating _quickly_.
I'd like to ask shorter time settings.
-Hideki
Olivier Teytaud: <Pine.LNX.4.63.07...@acces.lri.fr>:
--
g...@nue.ci.i.u-tokyo.ac.jp (Kato)
Christoph Birk
> I'd like to ask shorter time settings.
How about a compromise of 20 minutes. That's 4 times the amount
for 9x9 and (about) proportional to the area.
Christoph
Don Dailey
Just kidding.
I once thought about setting up fast games on CGOS that ran in sync with
slow games. The idea is that when a slow game is finished, you can
play 1 or more fast games instead of waiting for the next round. I
would synchronize things so that you were always guaranteed to be able
to play in the next slow game round. It's kind of like playing speed
chess and skittles between rounds of a serious tournament. I assume
that happens with Go too?
They would be rated separately and your bot could choose to play in
either one exclusively or both. The time control for the fast games
would be considerably brisker than for the other, so that your bot
would be busy the majority of the time if that's what you wanted.
If I did such a thing I would probably have 5 minutes per side and 40
minutes per side - scheduling 8 fast rounds during the same time 1 slow
one was being played. Another more conservative way is 10 minutes and
40 minutes or even 10 minutes and any multiple of 10 minutes such as 60
minutes. But I would start a new slow round when all the players
were ready, not necessarily on a fixed schedule.
When I finally get around to fixing the server bug, I will look into
how difficult to add this, if anyone thinks it's an interesting idea.
- Don
Olivier Teytaud
the port 6919 is now opened for all the universe.
The name of the machine is "cgos.lri.fr" (and not pc5-120.lri.fr as
previously).
The port is 6919. It is 19x19, 10 minutes per side for testing; I will
move to something longer later (depending on what people prefer,
I'll do a weighted average of durations suggested on the mailing
list :-) ).
http://www.lri.fr/~teytaud/cgosStandings.html
Unfortunately, I'll be away from my email
from tomorrow to wednesday and will not be able to
correct the troubles that people will almost surely find
in this installation; sorry for that.
The installation is a bit complicated in order to avoid
troubles due to the firewall and I am almost sure that
some troubles will appear very soon :-)
All comments welcome (in particular in the next hours as I am
still close to my computer a few hours :-) ).
olivier...@inria.fr
Olivier Teytaud
connected their bot to the server.
The server seemingly works.
cgos.lri.fr, port 6919.
http://www.lri.fr/~teytaud/cgosStandings.html
19x19, 10 minutes per side (for the moment, to be increased).
Olivier
David Fotland
It ouwld be nice if I can click on a game to see the sgf record. right now
it gives an error.
David
> -----Original Message-----
> From: computer-...@computer-go.org
> [mailto:computer-...@computer-go.org] On Behalf Of
Don Dailey
like this:
---------[ snip ]-------
AddType application/x-go-sgf sgf
---------[ snip ]---------
- Don
Don Dailey
of your games right now.
- Don
David Fotland
I was too conservative with time control so Many Faces is only playing at
level 8 (of 10), and finishing its games in 2 or 3 minutes. But it's
winning them all, so I guess I should prefer short time limits :)
Since Many Faces was originally written for a 12 MHz x286, it works pretty
well at very short time limits.
David
> -----Original Message-----
> From: computer-...@computer-go.org
> [mailto:computer-...@computer-go.org] On Behalf Of Don Dailey
> Sent: Friday, October 26, 2007 6:30 PM
> To: computer-go
> Cc: olivier...@inria.fr
> Subject: Re: [computer-go] 19x19 CGOS
>
>
Don Dailey
Has anyone else tried the windows viewer on the new 19x19 site?
I haven't tried it with windows, but you must pass the site and port
number to the viewer from the command line like this:
cgosview.exe cgos.lri.fr 6919
The viewer is a really nice way to look at games. A 3rd argument
will let you view a specific game number:
cgosview.exe cgos.lri.fr 6919 777
(view game 777)
Don Dailey
worked! I guess wine, the windows emulator has come a long way!
Here is what I did:
cgosview.exe cgos.lri.fr 6919
I did this from a bash shell and it came up just fine on my edgy eft
ubuntu system.
If a windows program runs on linux, it has to work on windows!
- Don