Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Darren Cook]

I enjoyed that long read, GCP!

> There is a secondary argument whether the methods used for Deep Blue>
> generalize as well as the methods used for AlphaGo. I think that 
> argument may not be as simple and clear-cut as Kasparov implied,
> because for one, there are similarities and crossover in which
> methods both programs used.
> 
> But I understand where it comes from. SL/RL and DCNN's (more
> associated with AlphaGo) seem like a broader hammer than tree search
> (more associated with Deep Blue).

That was my main thought, on reading the Kasparov interview, too. I'd
include MCTS under tree search. Most interesting AI problems cannot be
phrased in a way that all the wonderfully clever ways we have for
searching 2-player trees can be used.

The really clever bit of both Deep Blue and AlphaGo, was taking an order
of magnitude more computing power than what had gone before, and
actually getting it to work. Not crashing into the wall of diminishing
returns.

> My objection was to the claim that making Deep Blue didn't require any
> innovation or new methods at all...

The other thing that struck me: Deep Blue has been regarded as
"brute-force" (often in a derogatory sense) all these years, dumb
algorithms that were just hardware-accelerated. But I remember an
interview with Hsu (which sadly I cannot find a link to) where he was
saying that Deep Blue contained most of the sophisticated chess
knowledge and algorithms of the day: it wasn't just alpha-beta in there.

So seeing Deep Blue described as "chess algorithms" rather than as
"brute-force" was interesting.

Darren

P.S. I feel I didn't quote enough of the interview - do try and find it.
E.g. Saying how he didn't realize how badly Deep Blue had played until
he analyzed the games with modern chess computers. That is an amazing
thing to hear from the mouth of Kasparov! The book he is plugging is
here - I just skimmed the reviews, and it actually sounds rather good:
https://www.amazon.co.uk/Deep-Thinking-Machine-Intelligence-Creativity/dp/1473653517


-- 
Darren Cook, Software Researcher/Developer
My New Book: Practical Machine Learning with H2O:
  http://shop.oreilly.com/product/0636920053170.do
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Gian-Carlo Pascutto]

On 18/08/2017 23:07, uurtamo . wrote:
> They run on laptops. A program that could crush a grandmaster will run
> on my laptop. That's an assertion I can't prove, but I'm asking you to
> verify it or suggest otherwise.

Sure.

> Now the situation with go is different.

For what it's worth, I would expect the next release of Zen to make this
achievable as well. Especially if it supports GPU acceleration, and you
have one of those laptops with a GTX 1080 in it :-) But yes, chess is
comparatively further ahead against humans.

> But if we do agree that the problem itself is fundamentally harder,
> (which I believe it is) and we don't want to ascribe its solution simply
> to hardware (which people tried to do with big blue), then we should
> acknowledge that it required more innovation.
> 
> I do agree, and hope that you do, that this innovation is all part of a
> continuum of innovation that is super exciting to understand.

Of course I do. That is the whole point I was making with "appreciating
the sharpened tools".

My objection was to the claim that making Deep Blue didn't require any
innovation or new methods at all. They beat Kasparov in 1997, not 2017!

There is a secondary argument whether the methods used for Deep Blue
generalize as well as the methods used for AlphaGo. I think that
argument may not be as simple and clear-cut as Kasparov implied, because
for one, there are similarities and crossover in which methods both
programs used.

But I understand where it comes from. SL/RL and DCNN's (more associated
with AlphaGo) seem like a broader hammer than tree search (more
associated with Deep Blue).

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

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Gian-Carlo Pascutto]

On 18/08/2017 20:34, Petr Baudis wrote:
>   You may be completely right!  And yes, I was thinking about Deep Blue
> in isolation, not that aware about general computer chess history.  Do
> you have some suggested reading regarding Deep Blue and its lineage and
> their contributions to the field of AI at large?

I sure do. I *love* Hsu's papers, although it's hard now to imagine the
context some of his statements were made in, 30 year ago, because we
know the outcome. Back then, I'm sure many people thought he was a
raving lunatic.

His key idea was that, given ample of evidence program strength scaled
fairly well with computer speed, we should make the programs faster. He
did so by converting chess search to a literal hardware circuit, in an
implementation that was both algorithmically more efficient, and faster,
achieving about *3 orders of magnitude* improvement over what was then
the state of the art. And then designing a parallel search that worked
with it and scaled well enough.

Saying that these "implemented existing methods" is factually wrong, and
betrays a deep misunderstanding of the importance of computing power in
AI research. But I'll get back to this, later.

The original paper, "A Two-Million Moves/s CMOS Single-Chip Chess Move
Generator" was published in 1987. In the conclusion, it states "The best
chess machine now in existence is still about 400 to 500 rating points
below the Human World Chess Champion. Earlier experimental evidence
shows that each doubling in machine speed roughly corresponds to a 100
rating points increase...It is questionable that this remains true at
high level play. But nonetheless with a potential 100-1000 fold speed-up
at the door, *something interesting is probably about to happen*."

In this PhD thesis, he goes further, and draws the scaling graph with
Kasparov on it, at the end, and says in the introduction: "This
dissertation is mainly a collection of exploratory work on what I call
the "ultimate" chess machine - a chess machine that is capable of
searching at least 100 million nodes per second and possibly beyond 1
billion nodes per second. Current evidence seems to indicate that such a
machine will have an overwhelming chance of defeating the human World
Chess Champion."

He wrote that in 1989!

Kasparov, the same expert whose claims about Go and chess started this
very thread, had said the year before that no Grandmaster would be
defeated in tournament play before the year 2000. That gives you some
idea how outlandish Hsu's ideas seemed at the time. Or, for that matter,
how reliable Kasparov's opinion is in these matters.

Hsu achieved his goal in 1997, with 3 years to spare. Kasparov's
response was to call him a cheater.

Now, now, you might be thinking, was it all about speed? It was not -
the above was just Hsu's shtick, who was one member of the team. But, do
not for a moment make the mistake of underestimating just how important
speed is.

Do you know why, decades after having discarded them, we suddenly
started using neural networks again, and, well, do they turn out to work
well for Go now?

It's because we have several orders of magnitude more computing power.
Made possible by dedicated chips for neural network computations (OK, so
maybe they were intended for computer games - turns out the functions
are pretty similar, not to speak of TPUs).

And Hsu? He's working on FPGA's at Microsoft, who're mainly using them
to accelerate AI research and applications. In one of his last
interviews, in 2007, he predicted that "world-champion-level Go machine
can be built within 10 years." He got the details of the approach wrong,
though.

Others members also published several papers, i.e. Murray Campbell,
Thomas Anantharaman and Andreas Nowatzyk.

Nowatzyk has published the original automated evaluation tuning code
used by Deep Though. It's available, together with an explanation, at
http://www.tim-mann.org/deepthought.html

This was significant, because software based programs at the time had to
trade off evaluation terms for speed, so they mostly didn't have very
few, and could rely on manual tuning. Existing methods, you say?

Anantharaman's most known work is the publication of Singular
Extensions. The contribution of this method is somewhat hazy - with Hsu
admitting that they overestimated the initial gain from them due to
measurement errors - but improved methods are in fact in use in current
top of the line chess engines.

Campbell has published on a bunch of subjects. A ton on parallel game
tree search, and a method for biasing the tree search based on human
games. We call that a policy net, nowadays. Ok, maybe I'm stretching a
bit here.

Now, in as to how these methods "contributed to the AI field at large",
which I interpret as asking how well they generalize, that's an
interesting question. But it's also an interesting question that you can
ask of AlphaGo's contributions. Doing move prediction with a DCNN was
first done by Clark and Storkey of the 

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[uurtamo .]

Gian-Carlo,

I only ask, not to be snippy or impolite, but because I have just exactly
enough knowledge to be dangerous enough to have no freaking idea what I'm
talking about wrt chess research, and by way of introduction, let me say
that I've seen some people talk about (and a coworker at my former
university worked with) strong chess programs and I've done some analysis
with them. I think of them generally as black boxes whose strength gets
more and more complicated to measure since they can only essentially play
themselves anymore in an interesting way. Eventually I imagine it will take
more analysis on our part to understand their games then they are going to
give us. Which I'm fine with.

But.

They run on laptops. A program that could crush a grandmaster will run on
my laptop. That's an assertion I can't prove, but I'm asking you to verify
it or suggest otherwise.

Now the situation with go is different.

Perhaps it's that the underlying problem is harder. But "those old methods"
wouldn't work on this problem. I only mean that in the sense that the exact
code for chess, working with the rules of go, adapated using some
first-pass half-assed idea of what that means, would fail horribly.
Probably both because 64 << 169 and because queen >> 1 stone and for god
only knows how many other reasons.

So let's first get out of the way that this was probably a much harder
problem (the go problem).

I agree that the sharp definition of "machine learning", "statistics",
"AI", "blah blah blah" don't really matter toward the idea of  "computer
game players", etc.

But if we do agree that the problem itself is fundamentally harder, (which
I believe it is) and we don't want to ascribe its solution simply to
hardware (which people tried to do with big blue), then we should
acknowledge that it required more innovation.

I do agree, and hope that you do, that this innovation is all part of a
continuum of innovation that is super exciting to understand.

Thanks,

steve


​

On Fri, Aug 18, 2017 at 1:31 PM, Gian-Carlo Pascutto  wrote:

> On 18-08-17 16:56, Petr Baudis wrote:
> >> Uh, what was the argument again?
> >
> >   Well, unrelated to what you wrote :-) - that Deep Blue implemented
> > existing methods in a cool application, while AlphaGo introduced
> > some very new methods (perhaps not entirely fundamentally, but still
> > definitely a ground-breaking work).
>
> I just fundamentally disagree with this characterization, which I think
> is grossly unfair to the Chiptest/Deep Thought/Deep Blue lineage.
> Remember there were 12 years in-between those programs.
>
> They did not just...re-implement the same "existing methods" over and
> over again all that time. Implementation details and exact workings are
> very important [1]. I imagine the main reason this false distinction
> (i.e. the "artificial difference" from my original post) is being made
> is, IMHO, that you're all aware of the fine nuances of how AlphaGo DCNN
> usage (for example) differs compared to previous efforts, but you're not
> aware of the same nuances in Chiptest and successors etc.
>
> [1] As is speed, another dirty word in AI circles that is nevertheless
> damn important for practical performance.
>
> --
> GCP
> ___
> Computer-go mailing list
> Computer-go@computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Petr Baudis]

On Fri, Aug 18, 2017 at 06:31:54PM +0200, Gian-Carlo Pascutto wrote:
> On 18-08-17 16:56, Petr Baudis wrote:
> >> Uh, what was the argument again?
> > 
> >   Well, unrelated to what you wrote :-) - that Deep Blue implemented
> > existing methods in a cool application, while AlphaGo introduced
> > some very new methods (perhaps not entirely fundamentally, but still
> > definitely a ground-breaking work).
> 
> I just fundamentally disagree with this characterization, which I think
> is grossly unfair to the Chiptest/Deep Thought/Deep Blue lineage.
> Remember there were 12 years in-between those programs.
> 
> They did not just...re-implement the same "existing methods" over and
> over again all that time. Implementation details and exact workings are
> very important [1]. I imagine the main reason this false distinction
> (i.e. the "artificial difference" from my original post) is being made
> is, IMHO, that you're all aware of the fine nuances of how AlphaGo DCNN
> usage (for example) differs compared to previous efforts, but you're not
> aware of the same nuances in Chiptest and successors etc.

  You may be completely right!  And yes, I was thinking about Deep Blue
in isolation, not that aware about general computer chess history.  Do
you have some suggested reading regarding Deep Blue and its lineage and
their contributions to the field of AI at large?

  Thanks,

-- 
Petr Baudis, Rossum
Run before you walk! Fly before you crawl! Keep moving forward!
If we fail, I'd rather fail really hugely.  -- Moist von Lipwig
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Petr Baudis]

On Fri, Aug 18, 2017 at 09:06:41AM +0200, Gian-Carlo Pascutto wrote:
> On 17-08-17 21:35, Darren Cook wrote:
> > "I'm sure some things were learned about parallel processing... but the
> > real science was known by the 1997 rematch... but AlphaGo is an entirely
> > different thing. Deep Blue's chess algorithms were good for playing
> > chess very well. The machine-learning methods AlphaGo uses are
> > applicable to practically anything."
> > 
> > Agree or disagree?
> 
> Deep Thought (the predecessor of Deep Blue) used a Supervised Learning
> approach to set the initial evaluation weights. The details might be
> lost in time but it's reasonable to assume some were carried over to
> Deep Blue. Deep Blue itself used hill-climbing to find evaluation
> features that did not seem to correlate with strength much, and improve
> them.
> 
> A lot of the strength of AlphaGo comes from a fast, parallelized tree
> search.
> 
> Uh, what was the argument again?

  Well, unrelated to what you wrote :-) - that Deep Blue implemented
existing methods in a cool application, while AlphaGo introduced
some very new methods (perhaps not entirely fundamentally, but still
definitely a ground-breaking work).

  And I completely agree with that argument.  Nonwithstanding, it's
clear that AlphaGo's methods take advantage of many convenient
properties of Go and there's still a lot to do.  I liked Andrej
Karpathy's summary on this:

https://medium.com/@karpathy/alphago-in-context-c47718cb95a5

-- 
Petr Baudis, Rossum
Run before you walk! Fly before you crawl! Keep moving forward!
If we fail, I'd rather fail really hugely.  -- Moist von Lipwig
___
Computer-go mailing list
Computer-go@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Ingo Althöfer]

GCP wrote: 
> Maybe we should stop inventing artificial differences and appreciate
> that the tools in our toolbox have become much sharper over the years.

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

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Gian-Carlo Pascutto]

On 17-08-17 21:35, Darren Cook wrote:
> "I'm sure some things were learned about parallel processing... but the
> real science was known by the 1997 rematch... but AlphaGo is an entirely
> different thing. Deep Blue's chess algorithms were good for playing
> chess very well. The machine-learning methods AlphaGo uses are
> applicable to practically anything."
> 
> Agree or disagree?

Deep Thought (the predecessor of Deep Blue) used a Supervised Learning
approach to set the initial evaluation weights. The details might be
lost in time but it's reasonable to assume some were carried over to
Deep Blue. Deep Blue itself used hill-climbing to find evaluation
features that did not seem to correlate with strength much, and improve
them.

A lot of the strength of AlphaGo comes from a fast, parallelized tree
search.

Uh, what was the argument again?

Maybe we should stop inventing artificial differences and appreciate
that the tools in our toolbox have become much sharper over the years.

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

Re: [Computer-go] Deep Blue the end, AlphaGo the beginning?

[Robert Jasiek]

On 17.08.2017 21:35, Darren Cook wrote:

The machine-learning methods AlphaGo uses are applicable to practically 
anything."


They (alone) are not good for guaranteed avoiding of mistakes (as is 
achieved by theorems), or for guaranteed permanent execution by their 
software, hardware, power supply and circumstances of natural forces.


They (alone) are not enough for GAI also because many applications need 
some interface between the machine-learning methods and the 
domain-specific requirements.


They are inapplicable to what is proven to be, or their application can 
be unpredictable in some sense for what is proven to be non-deterministic.


They can pretend to simulate but cannot replace religion, meta-physics, 
ethics, emotions. However, it may be an open debate whether they can 
assume self-consciousness some time.


If we give them too much power (incl. self-regulated access to physical 
ressources), they can render extinct mankind.


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