Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > RE: A story about Python... sort of

Reply
Thread Tools

RE: A story about Python... sort of

 
 
Tony Meyer
Guest
Posts: n/a
 
      07-07-2003
> 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


 
Reply With Quote
 
 
 
 
John J. Lee
Guest
Posts: n/a
 
      07-07-2003
"Tony Meyer" <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
 
Bob Gailer
Guest
Posts: n/a
 
      07-07-2003
At 01:48 PM 7/7/2003 +0100, John J. Lee wrote:

>"Tony Meyer" <(E-Mail Removed)> 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
http://www.velocityreviews.com/forums/(E-Mail Removed)
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

 
Reply With Quote
 
Peter Hansen
Guest
Posts: n/a
 
      07-07-2003
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
 
Reply With Quote
 
Russell Reagan
Guest
Posts: n/a
 
      07-07-2003
"Bob Gailer" <(E-Mail Removed)> 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.


 
Reply With Quote
 
Piet van Oostrum
Guest
Posts: n/a
 
      07-08-2003
>>>>> "Russell Reagan" <(E-Mail Removed)> (RR) wrote:

RR> "Bob Gailer" <(E-Mail Removed)> 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 <(E-Mail Removed)>
URL: http://www.cs.uu.nl/~piet [PGP]
Private email: (E-Mail Removed)
 
Reply With Quote
 
Erik Max Francis
Guest
Posts: n/a
 
      07-10-2003
"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 && (E-Mail Removed) && 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
 
Reply With Quote
 
Greg Ewing (using news.cis.dfn.de)
Guest
Posts: n/a
 
      07-10-2003
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

 
Reply With Quote
 
Anton Vredegoor
Guest
Posts: n/a
 
      07-10-2003
"Greg Ewing (using news.cis.dfn.de)" <(E-Mail Removed)>
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Tell Your Story - Wondershare Released Photo Story Platinum kena Digital Photography 0 06-12-2007 08:42 AM
Newsweek Story just that a Story Mark Test Digital Photography 21 05-22-2005 02:39 PM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM
Re: A story about Python... sort of John J Lee Python 7 07-10-2003 12:51 PM
A story about Python... sort of Max M Python 21 07-07-2003 04:19 PM



Advertisments