[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Computer Go tournament at EGF
On Mon, 14 Feb 2005 12:23:29 -0600, Robin Kramer <robin@xxxxxxxxxxxxxxxxx> wrote:
> I was thining about this the other day. The turing machine came out of
> the research conducted during world war II in the effort to break german
> encryption techniques. However, to dupe the germans we used an arcane
> language "Navajo". Does the difference in Go playing strengths pose a
> potential security problem.
Have to react to this.... The Turing machine was conceived of *before*
and *completely independent of* WW II cryptography methods. (The paper
in which the idea appeared is: Turing, A. M., 1936-7, 'On computable
numbers, with an application to the Entscheidungsproblem' )
By the way, this was British research. Breaking the enigma was British
research, too (based on original effots by Polish scientists). Navajo
was used as an encryption technique by the USA.
> Could China use Go games as an encryption technique, by using high
> ranking Dan's to encode messages as Go problems sufficiently difficult
> so as to prevent the highest ranking player in the west from reading
> them out properly, but also concrete enough such that anyone of an
> equivalent rank in the east would immeadiately see the answer?
>
> Don, what about Amdahl's law "No matter how much you speed up some part
> of the process, the time the entire process takes is equivalent to the
> sum of the individual times". The speed of light is a constant for our
> purposes the distance light travels in a nanosecond(a theoretical
> maximum speed) = 1/3 of a meter.
>
> The distances between the computers will be inherently farther and
> therefore take more time than the computations within the same computer.
>
> Cheers,
>
> Robin
>
> Don Dailey wrote:
>
> >Hi Rich,
> >
> >I think you are getting hung up on the analogy I used and not getting
> >the deeper point. I think most of the group understood it was about the
> >relationship between computing power and GO playing strength.
> >
> >You see, the computer is purely hypothetical. It is not something you
> >are supposed to try to build. Think of it like you might think of a
> >"plane" in geometry, not a real physical object, just a mathematical
> >concept.
> >
> >When I was in high school the teacher made the mistake of comparing a
> >"plane" to a "very large flat sheet of paper" and several of the
> >children couldn't get past the physical properties of a piece of
> >paper!
> >
> >In computer science, there is a device called a "Turing machine." A
> >turing machine is a hypothetic gadget that can never be built. A pure
> >turning machine has infinite memory and this is probably the point
> >that probably would confuse some of us. It is like the "plane" in the
> >sense that it is an abstraction, not an actual device or physical
> >object.
> >
> >But nevertheless, it is an incredibly useful little gadget. It is
> >used much as I tried to use the hypothetical Go playing engine, to
> >prove things via the use of thought experiements.
> >
> >So anything you described about the physical properties of computers,
> >the age of the universe, the speed of light, number of grains of sand
> >on the seashore, isn't really very interesting or relevant, these are
> >facts everyone on this group probably are aware of and has nothing to
> >do with my argument.
> >
> >Let me try to dumb this down in a way that requires less imagination:
> >
> > 1. Imagine a real machine that consists of a network of workstations.
> >
> > 2. Imagine taking GnuGo and running a copy of it on each workstation.
> >
> > 3. Imagine software that builds a big networked search based on the
> > move generation and evaluation algorithms of GnuGo on this network.
> >
> > 4. Try to envision the possiblity that such a beast would play much
> > better than GnuGo run by itself. Perhaps even being able to give
> > GnuGo a several stone handicap.
> >
> > 5. Don't forget that such a machine cannot work without consuming
> > significantly more resources than GnuGo running on a single computer.
> >
> >In my opinion, such a machine would be a wonderful invention. Would
> >you say that such a machine demonstrates the relationship between
> >computing power and Go playing strength?
> >
> >If I haven't stretched anyones imagination too much, could it be
> >possible that a far bigger machine might be capable of playing even
> >better? It doesn't have to be so big it can't fit in our physical
> >universe, I know this concept would be too much for some of us to deal
> >with.
> >
> >
> >
> >- Don
> >
> >
> >
> >
> >
> >
> > Don Dailey wrote:
> >
> > > The point he is making is that you can't isolate the execution time of
> > > the algorithm from the playing strength. It IS in fact easy to write
> > > a perfect go program given no time constraints (just search until
> > > solution.) The issue isn't how GOOD your program is, it is how good
> > > it is in a given amount of time.
> >
> > I've heard that assertion many times before, that "It IS in fact easy
> > to write a perfect go program given no time constraints (just search
> > until solution.)"
> >
> > But there is an _inherent_ time constraint: It's the age (and the
> > expected age) of the universe. It has been shown that it would take
> > longer than the duration of the universe to perform the search, even
> > if there were enough storage.
> >
> > Furthermore, the number of go positions one would have to store is
> > larger than the (finite) number of atomic particles in the universe,
> > so even if there were an _infinite_ amount of time (which there isn't,
> > because the universe does have an age) there isn't enough storage
> > space to keep track of the results.
> >
> > Similarly, even if there were an _infinite_ amount of storage, (which
> > there isn't, because the number of atomic particles in the universe
> > is finite) there isn't enough time to perform the search!
> >
> > Such problems -- those that require a longer time than the age of the
> > universe, or that require more storage than the number of atomic
> > particles in the universe are called "inherently intractable".
> >
> > And that's why _not_even_ brute-force will work. It is _NOT_ possible.
> >
> > The assertion that it is "easy to write a perfect go program given no
> > time constraints" is simply not true.
> >
> > Not even theoretically.
> >
> > That said, I _still_ think that a program that can play a perfect
> > game given a week is of more intrinsic value than one that can play
> > a flawed game in an hour. It all depends upon what is considered
> > truly important for the program to be able to do.
> >
> > Thus we see that the issue is entirely subjective.
> >
> > What is _not_ subject to interpretation, is whether it is theoretically
> > possible to write a perfect program that uses brute force, "given enough
> > time" or "given enough storage". It absolutely is not possible, let
> > alone "easy".
> >
> > --
> > Rich
> >
> >_______________________________________________
> >computer-go mailing list
> >computer-go@xxxxxxxxxxxxxxxxx
> >http://www.computer-go.org/mailman/listinfo/computer-go/
> >
> >
> >
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/