RE: A story about Python... sort of

Discussion in 'Python' started by Tony Meyer, Jul 7, 2003.

  1. Tony Meyer

    Tony Meyer Guest

    > A chess program
    > is different from a 3D game in that with a 3D game, you can
    > stop at some point and say, "ok, this is fast enough." There
    > is little point in making the game run at 1000 frames per
    > second if no human eye can see more than 60 (or whatever the
    > number is).


    This isn't really true. Sure you can say that the framerate is fast enough,
    but when do you stop and say "the graphics look real enough"? (I'm sure
    there is a point, but it's a distant point, like 'solving' chess).

    =Tony Meyer
     
    Tony Meyer, Jul 7, 2003
    #1
    1. Advertising

  2. Tony Meyer

    John J. Lee Guest

    "Tony Meyer" <> writes:

    > > A chess program
    > > is different from a 3D game in that with a 3D game, you can
    > > stop at some point and say, "ok, this is fast enough." There

    [...]
    > This isn't really true. Sure you can say that the framerate is fast enough,
    > but when do you stop and say "the graphics look real enough"? (I'm sure
    > there is a point, but it's a distant point, like 'solving' chess).


    No matter how distant, it's nowhere near as far off as 'solving' chess
    (which is no doubt physically impossible, at least with classical
    (Turing machine) computation).


    John
     
    John J. Lee, Jul 7, 2003
    #2
    1. Advertising

  3. Tony Meyer

    Bob Gailer Guest

    At 01:48 PM 7/7/2003 +0100, John J. Lee wrote:

    >"Tony Meyer" <> writes:
    >
    > > > A chess program
    > > > is different from a 3D game in that with a 3D game, you can
    > > > stop at some point and say, "ok, this is fast enough." There

    >[...]
    > > This isn't really true. Sure you can say that the framerate is fast

    > enough,
    > > but when do you stop and say "the graphics look real enough"? (I'm sure
    > > there is a point, but it's a distant point, like 'solving' chess).

    >
    >No matter how distant, it's nowhere near as far off as 'solving' chess
    >(which is no doubt physically impossible, at least with classical
    >(Turing machine) computation).


    Physically impossible? or impractical. If it can be solved by Turing
    machine computation then it is physically possible, even though it might
    take more time/resources than anyone cares to expend. But remember "When
    Harley Was One" and he invented the G.O.D.?

    Bob Gailer

    303 442 2625


    ---
    Outgoing mail is certified Virus Free.
    Checked by AVG anti-virus system (http://www.grisoft.com).
    Version: 6.0.492 / Virus Database: 291 - Release Date: 6/24/2003
     
    Bob Gailer, Jul 7, 2003
    #3
  4. Tony Meyer

    Peter Hansen Guest

    Bob Gailer wrote:
    >
    > Physically impossible? or impractical. If it can be solved by Turing
    > machine computation then it is physically possible, even though it might
    > take more time/resources than anyone cares to expend. But remember "When
    > Harley Was One" and he invented the G.O.D.?


    Doesn't the Turing machine involve access to an infinitely long tape?

    If that's so, wouldn't that kind of make Turing machine computation
    discussions merely theoretically possible, but not necessarily
    practically possible?

    -Peter
     
    Peter Hansen, Jul 7, 2003
    #4
  5. "Bob Gailer" <> wrote

    > Physically impossible? or impractical. If it can be solved by Turing
    > machine computation then it is physically possible, even though it might
    > take more time/resources than anyone cares to expend.


    Or more time and resources than anyone has, which would make it impossible,
    for now.

    There are two ways to go about it. One is storing all of the positions and
    their distance to a theoretical result (win in N plies, draw), using a
    retrograde approach. This is how current endgame tablebases work. The other
    is on the fly depth first search. Currently neither are anywhere close to
    producing a practical solution. It's been said that there are more chess
    positions than there are atoms in the universe, so no current technology
    could possibly store the required information, even if we had the time to
    generate all of those positions, which we don't. So that leaves it to the
    search which requires only a tiny amount of information storage.
    Unfortunately, the search increases exponentially as the depth increases.

    A quick estimate, judging from the abilities of current programs and
    estimated hardware in about 18 months (10GHz, Intel), it would take about
    19,365,300,260,498,916 years to search to a depth of 60 ply (30 full moves),
    and it is very unlikely that there is a forced win in the first 30 moves
    anyway, with both sides playing perfectly. So, for now it's impossible and
    impractical.
     
    Russell Reagan, Jul 7, 2003
    #5
  6. >>>>> "Russell Reagan" <> (RR) wrote:

    RR> "Bob Gailer" <> wrote
    >> Physically impossible? or impractical. If it can be solved by Turing
    >> machine computation then it is physically possible, even though it might
    >> take more time/resources than anyone cares to expend.


    The Turing machine will only use a finite part of it, otherwise the
    computation will not finish. However, you don't always now how big that
    part will be.

    RR> Or more time and resources than anyone has, which would make it impossible,
    RR> for now.

    Both problems can be solved by stopping when space is exhausted, waiting
    until technique has evolved enough to upload the state of the computation
    to the new extended hardware etc.

    Of course this still stops it when you (or your successors) have used up
    the whole universe or have reached the end of the universe. In that sense
    it could be physically impossible.
    --
    Piet van Oostrum <>
    URL: http://www.cs.uu.nl/~piet [PGP]
    Private email:
     
    Piet van Oostrum, Jul 8, 2003
    #6
  7. "Greg Ewing (using news.cis.dfn.de)" wrote:

    > Hmmm. So, if the universe is open and contains an infinite
    > amount of matter, then we could solve chess eventually,
    > but we might have to wait a while for the limits of the
    > observable universe to expand sufficiently...


    The problem is the heat death ultimately puts a limit on how much
    computation you can do, at least per unit volume. Lightspeed delays
    might put some dampers on the amount of a single, coherent distributed
    computation you could possibly do, since you have a finite amount of
    computation per unit volume possible so you need to distribute, but you
    need to transmit and collect those results around at only lightspeed.

    --
    Erik Max Francis && && http://www.alcyone.com/max/
    __ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
    / \ There are countless planets, like many island Earths ...
    \__/ Konstantin Tsiolkovsky
     
    Erik Max Francis, Jul 10, 2003
    #7
  8. Piet van Oostrum wrote:
    > Both problems can be solved by stopping when space is exhausted, waiting
    > until technique has evolved enough to upload the state of the computation
    > to the new extended hardware etc.


    Hmmm. So, if the universe is open and contains an infinite
    amount of matter, then we could solve chess eventually,
    but we might have to wait a while for the limits of the
    observable universe to expand sufficiently...

    --
    Greg Ewing, Computer Science Dept,
    University of Canterbury,
    Christchurch, New Zealand
    http://www.cosc.canterbury.ac.nz/~greg
     
    Greg Ewing (using news.cis.dfn.de), Jul 10, 2003
    #8
  9. "Greg Ewing (using news.cis.dfn.de)" <>
    wrote:

    >Hmmm. So, if the universe is open and contains an infinite
    >amount of matter, then we could solve chess eventually,
    >but we might have to wait a while for the limits of the
    >observable universe to expand sufficiently...


    IMO it all depends on the amount of low hanging fruit in the universe.
    For example if at some early stage in the game the Queen could be
    captured cleanly, the rest would be just minor details, unless some
    careless move would give the game away of course.

    For example at the department of informatics in Maastricht, there was
    someone (Victor Allis IIRC) who had a habit of inviting people in a
    most friendly and convincing way into his "torture chamber" where one
    could play a game of "gobang" or "four in a row" or something like
    that (it's a long time ago, I'm not sure about the details anymore)
    against an innocent looking computer program.

    As time went by the program got stronger and stronger and the faces of
    the people leaving the room got more and more somber. Winning a game
    just resulted in the program not making the same mistake next time :)

    In the end he managed to prove that the program was invincible, not
    because he could generate the whole game tree, but because he could
    maneuver the game into some position that was always winnable for the
    computer.

    Anton
     
    Anton Vredegoor, Jul 10, 2003
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Max M

    A story about Python... sort of

    Max M, Jul 3, 2003, in forum: Python
    Replies:
    21
    Views:
    853
    Dave Brueck
    Jul 7, 2003
  2. John J Lee

    Re: A story about Python... sort of

    John J Lee, Jul 7, 2003, in forum: Python
    Replies:
    7
    Views:
    335
    John J. Lee
    Jul 10, 2003
  3. Peter Hansen
    Replies:
    1
    Views:
    340
    Robert Oschler
    Jul 11, 2003
  4. Replies:
    8
    Views:
    365
  5. Navin
    Replies:
    1
    Views:
    767
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page