| |
Main
Date: 07 Jul 2004 18:44:28
From: [email protected]
Subject: Ever wonder if the entire tree will be completed?
|
Supposedly there's about 10^120 different possible board positions and
10^75 atoms in the universe.
I _wish_ that one day a computer could find EVERY one of the possible
positions and end the debate about whether or not white _should_ win
b/c of the opening move advantage.
| Free Avlerchess Glass Chess Set - Find out how you can get a free glass chess set from us.
|
| |
Date: 08 Jul 2004 05:45:33
From: Marcel van Kervinck
Subject: Re: Ever wonder if the entire tree will be completed?
|
[email protected] <StallMan > wrote:
> Supposedly there's about 10^120 different possible board positions and
> 10^75 atoms in the universe.
First, your numbers are off,
Second, why would the number of atoms matter for chess?
> I _wish_ that one day a computer could find EVERY one of the possible
> positions and end the debate about whether or not white _should_ win
> b/c of the opening move advantage.
No computer result could ever stop
a debate on usenet.
Marcel
-- _ _
_
|
| | |
Date: 08 Jul 2004 09:22:20
From: Luigi Caselli
Subject: Re: Ever wonder if the entire tree will be completed?
|
"Marcel van Kervinck" <[email protected] > ha scritto nel messaggio
news:[email protected]...
> [email protected] <StallMan> wrote:
> > Supposedly there's about 10^120 different possible board positions and
> > 10^75 atoms in the universe.
>
> First, your numbers are off,
> Second, why would the number of atoms matter for chess?
I think you have to store all the positions somewhere...
> > I _wish_ that one day a computer could find EVERY one of the possible
> > positions and end the debate about whether or not white _should_ win
> > b/c of the opening move advantage.
>
> No computer result could ever stop
> a debate on usenet.
A very true new law...
Luigi Caselli
|
| | | |
Date: 08 Jul 2004 03:49:03
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
Luigi Caselli <[email protected] > says...
>
>"Marcel van Kervinck" <[email protected]> ha scritto
>
>> Second, why would the number of atoms matter for chess?
>
>I think you have to store all the positions somewhere...
You don't have to to store all the positions. I can think
of many ways to reduce the storage requirements. Besides
the obvious rotations, refections, and impossible positions
you could, assuming that your computer can do a N-ply
exhaustive search, store only positions that are N-plies or
more away from a win or draw. It's still a huge amount, but
not a huge as all of the positions.
|
| | | |
Date: 08 Jul 2004 04:19:49
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
Luigi Caselli <[email protected] > says...
>
>"Marcel van Kervinck" <[email protected]> ha scritto...
>
>> why would the number of atoms matter for chess?
>
>I think you have to store all the positions somewhere...
"A [quantum computer] register of say 1500 qubits, if it could be
placed in superposition, could access more states than there are
particles in the universe." -Peter Knight, _Science_, 2000 January
|
| | | |
Date: 08 Jul 2004 11:52:32
From: Anders Thulin
Subject: Re: Ever wonder if the entire tree will be completed?
|
Luigi Caselli wrote:
> I think you have to store all the positions somewhere...
Not necessarily -- not any more than a chess-playing program
has to store all posityions it is evaluating. And if you do
have to store something, why not use photons?
--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
|
| | | | |
Date: 08 Jul 2004 14:15:38
From: Psiloz
Subject: Re: Ever wonder if the entire tree will be completed?
|
"Anders Thulin" <[email protected] > wrote in message
news:[email protected]...
> Luigi Caselli wrote:
>
> > I think you have to store all the positions somewhere...
>
> Not necessarily -- not any more than a chess-playing program
> has to store all posityions it is evaluating. And if you do
> have to store something, why not use photons?
>
> --
> Anders Thulin ath*algonet.se http://www.algonet.se/~ath
Or Winzip!
Psi
|
| | | | | |
Date: 08 Jul 2004 17:02:01
From: Mike Broombridge
Subject: Re: Ever wonder if the entire tree will be completed? aren't you all missing something
|
Even if the computer could look at all the possible positions it might not
be good enough to evaluate correctly which ones are the best.
What is the point in considering every position if your judgement is not
good enough.You still couldn't say whether white or black should win
Is the judgement of a position in chess just opinion anyway??
Anders Thulin <[email protected] > wrote in message
news:[email protected]...
> George wrote:
>
> > I think the possible board positions is much lower. If i remember
> > correctly ~10^43 (+-10^41) is the number.
>
> It's a rough estimate of how many ways you can place the full
> complement of chess pieces on a chess board. That's only remotely
> related to chess positions. Add pawn promotions and you're in the
> neighbourhood of 10^52, but again, no more than a very rough estimate.
>
> --
> Anders Thulin ath*algonet.se http://www.algonet.se/~ath
|
| | | | | | |
Date: 08 Jul 2004 21:14:50
From: David Richerby
Subject: Re: Ever wonder if the entire tree will be completed? aren't you all missing something
|
Mike Broombridge <[email protected] > wrote:
> Even if the computer could look at all the possible positions it might
> not be good enough to evaluate correctly which ones are the best.
> What is the point in considering every position if your judgement is not
> good enough.You still couldn't say whether white or black should win
> Is the judgement of a position in chess just opinion anyway??
No. If you're looking at all the positions then you mark the stalemates
as drawn, checkmates as won, the positions where all legal moves lead to
checkmate as lost in one, the positions where all legal moves lead to a
position where the opponent is lost in one as won in two, and so on.
Dave.
--
David Richerby Moistened Evil Ghost (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a haunting spirit but it's genuinely
evil and moist!
|
| | | | | | |
Date: 08 Jul 2004 15:04:03
From: George
Subject: Re: Ever wonder if the entire tree will be completed? aren't you all missing something
|
"Mike Broombridge" <[email protected] > wrote in message news:<[email protected]>...
> Even if the computer could look at all the possible positions it might not
> be good enough to evaluate correctly which ones are the best.
> What is the point in considering every position if your judgement is not
> good enough.You still couldn't say whether white or black should win
> Is the judgement of a position in chess just opinion anyway??
>
But as i've said, to solve the game of Chess you don't need a
computer to evaluate all possible positions but to play all possible
games of Chess. So when the computer play every possible game, then it
will evaluate the games as +1, 0, -1 (win,draw,loss), and then it
could find a path where white will always wins, or black will always
wins or if there aren't such paths(variations) the game is drawn (with
perfect play).
Of course by having the computer evaluate all possible positions you
could solve the game too, but the word "evaluate" is as you've already
said not very clear and i would say very tricky. To evaluate a
position correctly like a win,loss,draw it needs to play all possible
continuations from this position. So since it has to evaluate all
possible positions, the computer has to do what i've said before: To
play all possible games of Chess.
|
| | | | | | | |
Date: 09 Jul 2004 09:37:06
From: David Richerby
Subject: Re: Ever wonder if the entire tree will be completed? aren't you all missing something
|
George <[email protected] > wrote:
> "Mike Broombridge" <[email protected]> wrote:
>> Even if the computer could look at all the possible positions it might not
>> be good enough to evaluate correctly which ones are the best.
>> What is the point in considering every position if your judgement is not
>> good enough.You still couldn't say whether white or black should win
>> Is the judgement of a position in chess just opinion anyway??
>
> But as i've said, to solve the game of Chess you don't need a
> computer to evaluate all possible positions but to play all possible
> games of Chess. [...]
>
> Of course by having the computer evaluate all possible positions you
> could solve the game too, but the word "evaluate" is as you've already
> said not very clear and i would say very tricky. To evaluate a
> position correctly like a win,loss,draw it needs to play all possible
> continuations from this position. So since it has to evaluate all
> possible positions, the computer has to do what i've said before: To
> play all possible games of Chess.
As I said in my reply[1] to Mike's post, you don't need to play through
all possible games of chess to solve the game. You can `backsolve' it by
starting at the possible final positions (checkmates and stalemates) and
working backwards. This saves an awful lot of time because there are many
more games than positions. Of course, saving time in a process that's
already scheduled to take vastly, vastly longer than the amount of time
that has so far existed doesn't help very much in practical terms.
Endgame tablebases are built up by backsolving. In that case, the final
positions aren't necessarily checkmates and stalemates. For example, in
KP vs K, they'll probably be positions with a pawn on the seventh rank and
its queening square protected; after that, queening the pawn takes you
into the KQ vs K table, which will end at checkmates and stalemates.
Dave.
[1] <kuz*[email protected] >
--
David Richerby Expensive Shack (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ house in the woods but it'll break
the bank!
|
| | | | |
Date: 08 Jul 2004 06:42:44
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
Anders Thulin <[email protected] > says...
>if you do have to store something, why not use photons?
Because it's hard to convince them to stay put? :)
|
| | | | | |
Date: 08 Jul 2004 17:16:03
From: Anders Thulin
Subject: Re: Ever wonder if the entire tree will be completed?
|
Guy Macon wrote:
> Because it's hard to convince them to stay put? :)
... but that's just the idea ...
I forget who it was that proposed a photon memory between
earth and moon: send modulated light there, and reflect it back.
Clean up the signal, and send around again. Readout time is a bit
long, but you get quite a lot of storage. A bit like the
old mercury delay line memory used for Univac I.
--
Anders Thulin ath*algonet.se http://www.algonet.se/~ath
|
| |
Date: 08 Jul 2004 02:46:20
From: George
Subject: Re: Ever wonder if the entire tree will be completed?
|
"[email protected]" <StallMan > wrote in message news:<[email protected]>...
> Supposedly there's about 10^120 different possible board positions and
> 10^75 atoms in the universe.
>
> I _wish_ that one day a computer could find EVERY one of the possible
> positions and end the debate about whether or not white _should_ win
> b/c of the opening move advantage.
I think the possible board positions is much lower. If i remember
correctly ~10^43 (+-10^41) is the number. But for solving Chess you
shouldn't care for the possible number of board positions, but for the
possible Chess games that can be played and this number is MUCH
bigger.
But even if we suppose that 10^50 is the number of possible Chess
games (actually is again MUCH higher) then even if a computer made
1/100000000000000000000 of a second to calculate the result of a whole
Chess game, then it would made 10^40 seconds = 3�10^32 years to solve
Chess game.
So we should forget this approach and do something similar like
V.Allis did for solving Connect-4 7x6.
|
| | |
Date: 08 Jul 2004 04:03:45
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
George <[email protected] > says...
>even if a computer made 1/100000000000000000000 of a second to
>calculate the result of a whole Chess game
You are assuming a conventional computer.
Deep Blue examined 200 million chess positions per second.
If it takes T time to search N items using a conventional
computer, a Quantum Computer can search N^2 items in the
same time. Thus a single quantum processor, with the same
clock rate as Deep Blue, could examine a trillion chess
positions in one second. In two seconds it could examine
four trillion chess positions, in three seconds nine
trillion, in four seconds 16 trillion, in five seconds
25 trillion, and so forth.
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| |
Date: 09 Jul 2004 01:00:11
From: rlsuth
Subject: Re: Ever wonder if the entire tree will be completed?
|
Since this thread has gone way off the beat, here's the simple answer: You
only need to store one line: The one that is a forced win for White from
move one. QED
"[email protected]" <StallMan > wrote in message
news:[email protected]...
> Supposedly there's about 10^120 different possible board positions and
> 10^75 atoms in the universe.
>
> I _wish_ that one day a computer could find EVERY one of the possible
> positions and end the debate about whether or not white _should_ win
> b/c of the opening move advantage.
|
| | |
Date: 09 Jul 2004 09:49:20
From: David Richerby
Subject: Re: Ever wonder if the entire tree will be completed?
|
rlsuth <[email protected] > wrote:
> Since this thread has gone way off the beat, here's the simple answer:
> You only need to store one line: The one that is a forced win for White
> from move one. QED
Simple but wrong. White has a winning first move. You now need to give
the winning move against each possible black reply, of which there are
twenty. Black has about 25 replies to each of those, to which you must
give White's move, and so on.
A winning strategy for White takes roughly the square root of the amount
of storage that the whole game tree would take. I say `roughly' because
the game tree has some paths of about 11000 ply (roughly the point at
which before every game is forced to be a draw by the 50-move rule, as
discussed in a recent thread somewhere in rec.games.chess.*) but the
winning strategy might not involve any lines longer than, say, 200 ply.
But even a 200-ply winning strategy for chess is a tree with order 30^100
nodes if you don't remove the redundancy...
Dave.
--
David Richerby Expensive Slimy Umbrella (TM): it's
www.chiark.greenend.org.uk/~davidr/ like an umbrella but it's covered in
goo and it'll break the bank!
|
| | | |
Date: 09 Jul 2004 12:46:33
From: rlsuth
Subject: Re: Ever wonder if the entire tree will be completed?
|
Of course you are right. To prove that white had a forced win, you'd need to
show every variation that wins, although you could prune the ones that end
in draws, the tree would still be huge.
I guess I shouldn't post right before I go to bed. :)
"David Richerby" <[email protected] > wrote in message
news:Gbo*[email protected]...
> rlsuth <[email protected]> wrote:
> > Since this thread has gone way off the beat, here's the simple answer:
> > You only need to store one line: The one that is a forced win for White
> > from move one. QED
>
> Simple but wrong. White has a winning first move. You now need to give
> the winning move against each possible black reply, of which there are
> twenty. Black has about 25 replies to each of those, to which you must
> give White's move, and so on.
>
> A winning strategy for White takes roughly the square root of the amount
> of storage that the whole game tree would take. I say `roughly' because
> the game tree has some paths of about 11000 ply (roughly the point at
> which before every game is forced to be a draw by the 50-move rule, as
> discussed in a recent thread somewhere in rec.games.chess.*) but the
> winning strategy might not involve any lines longer than, say, 200 ply.
>
> But even a 200-ply winning strategy for chess is a tree with order 30^100
> nodes if you don't remove the redundancy...
>
>
> Dave.
>
> --
> David Richerby Expensive Slimy Umbrella (TM):
it's
> www.chiark.greenend.org.uk/~davidr/ like an umbrella but it's
covered in
> goo and it'll break the bank!
|
| | | | |
Date: 09 Jul 2004 10:05:52
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
rlsuth <[email protected] > says...
>Of course you are right. To prove that white had a forced win, you'd need to
>show every variation that wins, although you could prune the ones that end
>in draws, the tree would still be huge.
If you prune the lines that end in draws, you can't prove that white has
a forced win.
|
| | |
Date: 09 Jul 2004 02:45:32
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
rlsuth <[email protected] > says...
>Since this thread has gone way off the beat, here's the simple answer: You
>only need to store one line: The one that is a forced win for White from
>move one. QED
Assuming white wins, of course. I am guessing draw.
What happens if the opponent doesn't follow the line?
You need a white reply to every possible black response.
The tree just keeps getting bigger and bigger.
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | |
Date: 09 Jul 2004 04:16:26
From: George
Subject: Re: Ever wonder if the entire tree will be completed?
|
"rlsuth" <[email protected] > wrote in message news:<v6mHc.45690$%_6.5724@attbi_s01>...
> Since this thread has gone way off the beat, here's the simple answer: You
> only need to store one line: The one that is a forced win for White from
> move one. QED
No. To be able a computer to play perfect Chess it needs to store ALL
lines.
Even if we accepted that Chess is a White wins game, if Black played a
"non perfect move" then White would not had the answer if it stored
only the best line.
And of course you assume that Chess is a White wins game. Which
hasn't been proven yet.
What do you mean with QED. Is it: "Question Everything Done" ?
>
>
>
> "[email protected]" <StallMan> wrote in message
> news:[email protected]...
> > Supposedly there's about 10^120 different possible board positions and
> > 10^75 atoms in the universe.
> >
> > I _wish_ that one day a computer could find EVERY one of the possible
> > positions and end the debate about whether or not white _should_ win
> > b/c of the opening move advantage.
|
| | | |
Date: 09 Jul 2004 16:56:27
From: Mike Broombridge
Subject: Re: Ever wonder if the entire tree will be completed?
|
I don't see that simply knowing all the possible permutations of moves gives
you the perfect chess playing computer.
Surly it uses judgment to decide with paths to take from the reponse of its
opponent.
Aren't you all over simplyfing how a chess computer works?
George <[email protected] > wrote in message
news:[email protected]...
> "rlsuth" <[email protected]> wrote in message
news:<v6mHc.45690$%_6.5724@attbi_s01 >...
> > Since this thread has gone way off the beat, here's the simple answer:
You
> > only need to store one line: The one that is a forced win for White from
> > move one. QED
>
> No. To be able a computer to play perfect Chess it needs to store ALL
> lines.
> Even if we accepted that Chess is a White wins game, if Black played a
> "non perfect move" then White would not had the answer if it stored
> only the best line.
> And of course you assume that Chess is a White wins game. Which
> hasn't been proven yet.
>
>
>
> What do you mean with QED. Is it: "Question Everything Done" ?
>
> >
> >
> >
> > "[email protected]" <StallMan> wrote in message
> > news:[email protected]...
> > > Supposedly there's about 10^120 different possible board positions and
> > > 10^75 atoms in the universe.
> > >
> > > I _wish_ that one day a computer could find EVERY one of the possible
> > > positions and end the debate about whether or not white _should_ win
> > > b/c of the opening move advantage.
|
| | | | |
Date: 09 Jul 2004 10:17:50
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
Mike Broombridge <[email protected] > says...
>I don't see that simply knowing all the possible permutations
>of moves gives you the perfect chess playing computer.
Nonetheless, it is true.
>Surly it uses judgment to decide with paths to take from the
>reponse of its opponent.
Stop calling me Shirly!
>Aren't you all over simplyfing how a chess computer works?
Nope.
Here is an experiment you can do with a pencil and a pad of paper:
On pages 1 through 9, write down tic-tac-toe boards with the
first move made.
On pages 10-18, write down all possible replies to the page
1 move. repeat for a couple of other moves.
(At this point you might wish to stop and ponder the fact that
there are really only *three* first moves and that the other
six are reflections and/or rotations. You can save yourself
a lot of work by not listing reflections/rotations, but the
answer will be the same either way)
Keep going until you have a complete game tree.
starting from the end positions, work back and label each page
as a win, loss, or draw based on this rule: if all
Now play a game of tic-tac-toe using your notes, and try to find
the spot where you actually have to do some thinking rather than
just looking up moves..
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | |
Date: 09 Jul 2004 18:31:36
From: Mike Broombridge
Subject: Re: Ever wonder if the entire tree will be completed?
|
> >Aren't you all over simplyfing how a chess computer works?
>
> Nope
But modern computers don't have a list of all positions so how does it make
moves without making a judgement on how good a position is?
If this is all there is to solving the game of chess why aren't there
programs running all the time to get closer and closer to solving the
problem?
It might not be able to calculate 10^40 in a few seconds but why not in a
number of years?
It doesn't need to play a game of chess just sit working out all the
permutations.
|
| | | | | | |
Date: 09 Jul 2004 21:51:30
From: Mike Ogush
Subject: Re: Ever wonder if the entire tree will be completed?
|
On Fri, 9 Jul 2004 18:31:36 +0000 (UTC), "Mike Broombridge"
<[email protected] > wrote:
>> >Aren't you all over simplyfing how a chess computer works?
>>
>> Nope
>
>But modern computers don't have a list of all positions so how does it make
>moves without making a judgement on how good a position is?
>
>If this is all there is to solving the game of chess why aren't there
>programs running all the time to get closer and closer to solving the
>problem?
>It might not be able to calculate 10^40 in a few seconds but why not in a
>number of years?
Not any time soon :-(
Using Deep Blue which can evaluate 200 million positions per second,
it would take about 1.6 * 10^24 years to examine 10^40 positions.
Even using a hypothetical quantum deep blue computer mentioned
elsewhere in this thread that could evaluate 4 trillion positions per
second it would still take approximately 8* 10^15 years.
To give some perspective: the age of the universe (from big bang until
now) is only in the 1.1-1.7 * 10^10 years range.
>It doesn't need to play a game of chess just sit working out all the
>permutations.
>
>
|
| | | | | | | |
Date: 09 Jul 2004 20:53:01
From: SethB
Subject: Re: Ever wonder if the entire tree will be completed?
|
> Not any time soon :-(
>
> Using Deep Blue which can evaluate 200 million positions per second,
> it would take about 1.6 * 10^24 years to examine 10^40 positions.
>
> Even using a hypothetical quantum deep blue computer mentioned
> elsewhere in this thread that could evaluate 4 trillion positions per
> second it would still take approximately 8* 10^15 years.
"Quantum DeepBlueGooglePlex^GP-XT" (c) IBM, 65876 AD
Yup, THAT's the one that can make 32-piece Nalimov tablebases!
Now I'm excited!
Though our universe won't be around then, at least in any livable form,
perhaps our surviving robots could transfer the data through a wormhole
to another universe, to continue the calculations, before the last light
goes out in this one, and then in their's, etc. You know, to solve the
game of chess. :-)
|
| | | | | | | | |
Date: 09 Jul 2004 18:39:26
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
SethB <[email protected] > says...
>"Quantum DeepBlueGooglePlex^GP-XT" (c) IBM, 65876 AD
>
>Yup, THAT's the one that can make 32-piece Nalimov tablebases!
Yup. Oddly enough, a quantum computer really can make 32-piece
Nalimov tablebases (and you only need one!)
>Though our universe won't be around then,
You have knowledge that the universe will be gone within minutes
of the invention of a practical quantum computer? :(
Searching 2^N positions in N time: It's an idea who's time has come!
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | | | | | |
Date: 10 Jul 2004 02:11:16
From: none
Subject: Re: Ever wonder if the entire tree will be completed?
|
Guy Macon wrote:
> SethB <[email protected]> says...
>
>
>>"Quantum DeepBlueGooglePlex^GP-XT" (c) IBM, 65876 AD
>>
>>Yup, THAT's the one that can make 32-piece Nalimov tablebases!
>
>
> Yup. Oddly enough, a quantum computer really can make 32-piece
> Nalimov tablebases (and you only need one!)
>
>
>>Though our universe won't be around then,
>
>
> You have knowledge that the universe will be gone within minutes
> of the invention of a practical quantum computer? :(
>
> Searching 2^N positions in N time: It's an idea who's time has come!
>
Yeah i was thinking too linearly. Quantum computing looks like it would
most certainly work for chess.
|
| | | | | | | | | | |
Date: 09 Jul 2004 19:21:53
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
none <[email protected] > says...
>
>Guy Macon wrote:
>
>> Searching 2^N positions in N time: It's an idea who's time has come!
>>
>Yeah i was thinking too linearly. Quantum computing looks like it would
>most certainly work for chess.
It makes you wonder whether a practical quantum computer will ever
be invented, doesn't it? Are we like Babbage, holding the plans
to a new way of computing and waiting for technology to advance
enough for us to implement it? Or is there a dead end in the
future of quantum computing?
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | | | | | | | |
Date: 10 Jul 2004 04:29:13
From: rlsuth
Subject: Re: Ever wonder if the entire tree will be completed?
|
"Guy Macon" <http://www.guymacon.com > wrote in message
news:[email protected]...
>
Or is there a dead end in the future of quantum computing?
>
>
I guess we'll find out the first time both kings exist in the same place at
the same time! :)
|
| | | | | | | | | |
Date: 10 Jul 2004 00:38:04
From: SethB
Subject: Re: Ever wonder if the entire tree will be completed?
|
> You have knowledge that the universe will be gone within minutes
> of the invention of a practical quantum computer? :(
Dark energy and entropy will take care of it all. Sorry for the
sideline. I just couldn't help it - blame my fingers.
|
| | | | | | | |
Date: 09 Jul 2004 18:21:02
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
Mike Ogush <[email protected] > says...
>Using Deep Blue which can evaluate 200 million positions per second,
>it would take about 1.6 * 10^24 years to examine 10^40 positions.
Correct.
>Even using a hypothetical quantum deep blue computer mentioned
>elsewhere in this thread that could evaluate 4 trillion positions per
>second it would still take approximately 8* 10^15 years.
Completely incorrect. You have failed to grasp the nature of
quantum computers being able to search 2^N items in N seconds.
A quantum computer that can evaluate 1 position in one
millisecond (the equivalent of a conventional computer that
can evaluate a thousand positions per second) can:
Evaluate 1 position in 1 millisecond
Evaluate 2 positions in 2 milliseconds
Evaluate 4 positions in 3 milliseconds
Evaluate 8 positions in 4 milliseconds
Evaluate 16 positions in 5 milliseconds
Evaluate 32 positions in 6 milliseconds
Evaluate 64 positions in 7 milliseconds
Evaluate 128 positions in 8 milliseconds
Evaluate 256 positions in 9 milliseconds
Evaluate 512 positions in 10 milliseconds
Evaluate 1 thousand positions in 11 milliseconds
[...]
Evaluate 1 million positions in 20 milliseconds
[...]
Evaluate 1 trillion (10^12) positions in 30 milliseconds
[...]
Evaluate (10^15) positions in 40 milliseconds
[...]
Evaluate (10^18) positions in 50 milliseconds
[...]
Evaluate (10^21) positions in 60 milliseconds
[...]
Evaluate (10^41) positions in 130 milliseconds
You can start with quantum computer that can
evaluate 1 position per second and still solve
chess in a couple of minutes.
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | | | | |
Date: 10 Jul 2004 07:11:41
From: George
Subject: Re: Ever wonder if the entire tree will be completed?
|
Guy Macon <http://www.guymacon.com > wrote in message news:<[email protected]>...
> Mike Ogush <[email protected]> says...
>
> >Using Deep Blue which can evaluate 200 million positions per second,
> >it would take about 1.6 * 10^24 years to examine 10^40 positions.
>
> Correct.
>
> >Even using a hypothetical quantum deep blue computer mentioned
> >elsewhere in this thread that could evaluate 4 trillion positions per
> >second it would still take approximately 8* 10^15 years.
>
> Completely incorrect. You have failed to grasp the nature of
> quantum computers being able to search 2^N items in N seconds.
>
> A quantum computer that can evaluate 1 position in one
> millisecond (the equivalent of a conventional computer that
> can evaluate a thousand positions per second) can:
>
> Evaluate 1 position in 1 millisecond
[...]
> Evaluate (10^41) positions in 130 milliseconds
>
> You can start with quantum computer that can
> evaluate 1 position per second and still solve
> chess in a couple of minutes.
First and i will be more detail on this later (as i think you are
confused) you don't define what evaluate means! Later.....
You are saying that quantum computers are being able to search 2^N
items in N seconds. First i don't understand that why they are able
to search these 2^N items in N SECONDS (i don't understand the
seconds), and i mean why seconds, why not milliseconds or nanoseconds
or hours???? And what items are????
Do you mean this: The quantum computers are being able to compute
F(N) items in N w, where F(N) = K�2^N and K is a constant and N is
the time in w units of time to compute F(N) items and w is a unit of
time.
So since a conventional computer can calculate approximately
1.000.000 positions per second, then it can calculate 1 position per
millisecond. So if we assume item=position=F(N) then we have for the
quantum computer: F(N) = 0.5�2^N (since 1=K�2^1 = > K=0.5 , N in
milliseconds , w=ms). Right?
Now i would tell you, why i believe your whole conclusions are wrong.
I'm reffering to the:
******** A quantum computer that can evaluate 1 position in one
millisecond (the equivalent of a conventional computer that
can evaluate a thousand positions per second) can:
Evaluate 1 position in 1 millisecond
.......
Evaluate (10^41) positions in 130 milliseconds
You can start with quantum computer that can
evaluate 1 position per second and still solve
chess in a couple of minutes. *********
OK the calculations are right, but there is one critical point that
destoys everything. What "evaluate" of a position means? If it means
the conventional meaning, of what todays computers do, that is to just
make judgements about the position by playing 12-20 plies (6-10 moves)
ahead based on their algorithms which are based on criteria such as
bad bishops, weak pawns, King safety,...etc, then even if a computer
EVALUATED all the positions (10^40), it would mean nothing, as we
couldn't in any way be sure if the computer's calculations are valid
since the evaluations would be based on unclear(to their validity)
rules and not in a mathematical proof.
So your conclusion of solving chess in a couple of minutes, is wrong.
So what definition of evaluate would be enough to solve chess by
evaluating all positions?
It's simple: For every position of the 10^40, the quantum computer
has to play ALL moves(all variations) possible and record the results.
Of course as it searches more and more positions, it would meet
previous already analysed positions so it would gain some(much) time.
After doing this for all the positions, it would solve Chess.
That means for EVALUATING one position it has to make a search of a
huge (even higher from the number of positions) number of
moves/variations, since it would play all possible Chess games. That
means to solve Chess it has to play all possible Chess games, except
the reflecting/mirroring positions.
I don't know the time for that but my instinct says:
It can't be less than 10^5 years. Also based on the property of
quantum computers(F(N)=K�2^N) i feel it will not take more than 1
second! These two contradict to each other and i'm confused.....:-(
|
| | | | | | | | | |
Date: 10 Jul 2004 09:03:36
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
George <[email protected] > says...
> You are saying that quantum computers are being able to search 2^N
>items in N seconds. First i don't understand that why they are able
>to search these 2^N items in N SECONDS (i don't understand the
>seconds), and i mean why seconds, why not milliseconds or nanoseconds
>or hours????
My apologies. That was an error. I meant to say that that quantum
computers (if a pratical one is ever invented) will be able to
perform 2^N operations in N time.
> OK the calculations are right, but there is one critical point that
>destoys everything. What "evaluate" of a position means? If it means
>the conventional meaning, of what todays computers do, that is to just
>make judgements about the position by playing 12-20 plies (6-10 moves)
>ahead based on their algorithms which are based on criteria such as
>bad bishops, weak pawns, King safety,...etc,
In the case of our yet-to-be-invented quantum computer, evaluating
a position means playing enough plies as far as they will go, with
the only judgement about the final positions being "Is it a
checkmate?" and ""Is it a draw?" You can do this with the PC on
your desktop - if you are willing to wait for an answer far longer
than the universe has existed. All a quantum computer does is to
(in theory) reduce the amount of time needed.
> So what definition of evaluate would be enough to solve chess by
>evaluating all positions?
> It's simple: For every position of the 10^40, the quantum computer
>has to play ALL moves(all variations) possible and record the results.
>Of course as it searches more and more positions, it would meet
>previous already analysed positions so it would gain some(much) time.
>After doing this for all the positions, it would solve Chess.
I agree
> That means for EVALUATING one position it has to make a search of a
>huge (even higher from the number of positions) number of
>moves/variations, since it would play all possible Chess games. That
>means to solve Chess it has to play all possible Chess games, except
>the reflecting/mirroring positions.
I agree.
> I don't know the time for that but my instinct says:
>It can't be less than 10^5 years. Also based on the property of
>quantum computers(F(N)=K�2^N) i feel it will not take more than 1
>second! These two contradict to each other and i'm confused.....:-(
Everything about quantum theory confuses me, but my tunnel diode
and atomic-decay RNG still work, so it's my mind that is wrong.
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | | | | | | |
Date: 10 Jul 2004 20:55:03
From: [email protected]
Subject: Re: Ever wonder if the entire tree will be completed?
|
>My apologies. That was an error. I meant to say that that quantum
>computers (if a pratical one is ever invented) will be able to
>perform 2^N operations in N time.
>
Just out of curiosity, what is a quantum computer? I've heard about
them, but I don't know much about the idea.
Thanks.
|
| | | | | | | | | | | |
Date: 10 Jul 2004 14:56:21
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
[email protected] <ChessGuy > says...
>
>>My apologies. That was an error. I meant to say that that quantum
>>computers (if a pratical one is ever invented) will be able to
>>perform 2^N operations in N time.
>
>Just out of curiosity, what is a quantum computer? I've heard about
>them, but I don't know much about the idea.
http://www.google.com/
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | | |
Date: 09 Jul 2004 15:10:28
From: George
Subject: Re: Ever wonder if the entire tree will be completed?
|
"Mike Broombridge" <[email protected] > wrote in message news:<[email protected]>...
> > >Aren't you all over simplyfing how a chess computer works?
> >
> > Nope
>
> But modern computers don't have a list of all positions so how does it make
> moves without making a judgement on how good a position is?
But they make judgements on how good a position is . The way of their
play is that they just stop at some moves (they play for 10-20 plies
from the given position based on some rules/criteria/algorithms) from
a given position and based on their algorithms, they make a judgement
about the position and give a number. They make this for all possible
moves at the given position and they just increase the plies every
time. Then they choose the higher number which correspond to a move
that they play.
>
> If this is all there is to solving the game of chess why aren't there
> programs running all the time to get closer and closer to solving the
> problem?
> It might not be able to calculate 10^40 in a few seconds but why not in a
> number of years?
> It doesn't need to play a game of chess just sit working out all the
> permutations.
It's obvious you don't understand how big is 10^40. Make some easy
calculations to see that truth is faaaar away.
|
| | | | | | |
Date: 09 Jul 2004 23:27:03
From: none
Subject: Re: Ever wonder if the entire tree will be completed?
|
Mike Broombridge wrote:
>>>Aren't you all over simplyfing how a chess computer works?
>>
>>Nope
>
>
> But modern computers don't have a list of all positions so how does it make
> moves without making a judgement on how good a position is?
>
> If this is all there is to solving the game of chess why aren't there
> programs running all the time to get closer and closer to solving the
> problem?
> It might not be able to calculate 10^40 in a few seconds but why not in a
> number of years?
> It doesn't need to play a game of chess just sit working out all the
> permutations.
>
>
As has previously been mentioned, the complete game tree of chess would
take literally forever to compute. The point is since the complete game
tree isn't available(It contains ~10^128 nodes of which 10^43 are legal
positions), a smaller search tree is generated instead.
Now since this smaller search tree is by definition incomplete, there is
indeed an evaluation component to search. But, if the complete game tree
(however impossible it is to achieve, let's pretend it is possible) were
available, then there would be no need for an evaluation component.
Now the reason it wouldn't be needed is that chess is a zero sum two
person game with perfect information. It will therefore have a saddle
point and a payoff matrix with an optimal strategy for playing. All you
need to know is that at this point chess would be reduced to a simple
minmax strategy, with absolutely no "strategy" or "evaluation" needed.
But since there is no hope of ever achieving the complete game tree for
chess, you shouldn't worry too much. While all chess playing programs
perform some variant of minmax, a necessary evalutation component is
still needed in the search.
|
| | | | | | | |
Date: 09 Jul 2004 18:26:33
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
none <[email protected] > says...
>As has previously been mentioned, the complete game tree of chess would
>take literally forever to compute.
...unless you have a qauntum computer that searches 2^N positions
in N time rather than a conventional computer that searches 2^N
positions in 2^N time.
>If the complete game tree (however impossible it is to achieve,
...unless you have a qauntum computer that searches 2^N positions
in N time rather than a conventional computer that searches 2^N
positions in 2^N time.
>But since there is no hope of ever achieving the complete game tree for
>chess,
...unless you have a qauntum computer that searches 2^N positions
in N time rather than a conventional computer that searches 2^N
positions in 2^N time.
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | | | | |
Date: 14 Jul 2004 21:06:16
From: David Richerby
Subject: Re: Ever wonder if the entire tree will be completed?
|
Guy Macon <http://www.guymacon.com > wrote:
> none <[email protected]> says...
>> As has previously been mentioned, the complete game tree of chess would
>> take literally forever to compute.
>
> ...unless you have a qauntum computer that searches 2^N positions
> in N time rather than a conventional computer that searches 2^N
> positions in 2^N time.
Not all algorithms are well-suited to a quantum computer, even assuming
you could build one with more than a handful of qbits and have it run for
more than a handful of seconds without decoherence becoming a problem.
Dave.
--
David Richerby Devil Priest (TM): it's like a man of
www.chiark.greenend.org.uk/~davidr/ the cloth that's possessed by Satan!
|
| | | | | | | |
Date: 09 Jul 2004 20:32:05
From: Kenneth Sloan
Subject: Re: Ever wonder if the entire tree will be completed?
|
none <[email protected] > writes:
> ...
> As has previously been mentioned, the complete game tree of chess would
> take literally forever to compute. The point is since the complete game
> tree isn't available(It contains ~10^128 nodes of which 10^43 are legal
> positions), a smaller search tree is generated instead.
This thread misses the point.
The point is that the entire chess game tree *is* available. The
problem is that *access* to it is restricted to traversing the tree.
There is nothing (in principle) that you could do with the entire tree
in memory that you can't do by making pieces of it explicit as you
traverse the tree.
It's not that the tree is not available, or (worse) that it is somehow
"unknown" - the problem is that it is so big that it is impossible to
look at all of it in time to make a move.
We *have* the entire tree...we just don't have the time to use it.
--
Kenneth Sloan [email protected]
Computer and Information Sciences (205) 934-2213
University of Alabama at Birmingham FAX (205) 934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/
|
| | | | | | | | |
Date: 09 Jul 2004 18:57:06
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
Kenneth Sloan <[email protected] > says...
>the problem is that it is so big that it is impossible to
>look at all of it in time to make a move.
...unless you have a quantum computer that searches 2^N positions
in N time rather than a conventional computer that searches 2^N
positions in 2^N time.
Too bad such a thing doesn't exist. There may be reasons why
it will never exist, but as of now it is a theoretical future
possibility. My theory is that the multiverse will see it as
quantum spamming and block it... :)
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | | | | | |
Date: 10 Jul 2004 02:10:19
From: none
Subject: Re: Ever wonder if the entire tree will be completed?
|
Kenneth Sloan wrote:
> none <[email protected]> writes:
>
>
>>...
>>As has previously been mentioned, the complete game tree of chess would
>>take literally forever to compute. The point is since the complete game
>>tree isn't available(It contains ~10^128 nodes of which 10^43 are legal
>>positions), a smaller search tree is generated instead.
>
>
> This thread misses the point.
>
> The point is that the entire chess game tree *is* available.
Hmm, no it most certainly isn't available. If you mean that it exists
than yes that is a truism and trivial.
The
> problem is that *access* to it is restricted to traversing the tree.
The point is if you had the entire game tree there would be no
"traversing" needed.
> There is nothing (in principle) that you could do with the entire tree
> in memory that you can't do by making pieces of it explicit as you
> traverse the tree.
>
Yes nothing, nothing except there would be no need for traversal or
calculation. It would be a simple O(1) lookup in a table.
|
| | | | | | | | |
Date: 10 Jul 2004 00:47:45
From: SethB
Subject: Re: Ever wonder if the entire tree will be completed?
|
> This thread misses the point.
>
> The point is that the entire chess game tree *is* available. The
> problem is that *access* to it is restricted to traversing the tree.
> There is nothing (in principle) that you could do with the entire tree
> in memory that you can't do by making pieces of it explicit as you
> traverse the tree.
>
> It's not that the tree is not available, or (worse) that it is somehow
> "unknown" - the problem is that it is so big that it is impossible to
> look at all of it in time to make a move.
>
> We *have* the entire tree...we just don't have the time to use it.
Succinctly put.
|
| | | | | | |
Date: 09 Jul 2004 17:38:57
From: Guy Macon
Subject: Re: Ever wonder if the entire tree will be completed?
|
Mike Broombridge <[email protected] > says...
>> >Aren't you all over simplyfing how a chess computer works?
>>
>> Nope
>
>But modern computers don't have a list of all positions so how does it make
>moves without making a judgement on how good a position is?
http://www.google.com/search?q=%22chess+computer%22+evaluation
>If this is all there is to solving the game of chess why aren't there
>programs running all the time to get closer and closer to solving the
>problem?
>It might not be able to calculate 10^40 in a few seconds but why not in a
>number of years?
>It doesn't need to play a game of chess just sit working out all the
>permutations.
http://www.google.com/search?q=%22chess+computer%22+tablebase
--
Guy Macon, Electronics Engineer & Project Manager for hire.
Remember Doc Brown from the _Back to the Future_ movies? Do you
have an "impossible" engineering project that only someone like
Doc Brown can solve? My resume is at http://www.guymacon.com/
|
| | | | |
Date: 14 Jul 2004 21:12:16
From: David Richerby
Subject: Re: Ever wonder if the entire tree will be completed?
|
Mike Broombridge <[email protected] > wrote:
> I don't see that simply knowing all the possible permutations of moves
> gives you the perfect chess playing computer.
If every move I make loses, you win the game. So, just as it's possible
to identify a position that is, say, mate in five, it's theoretically (but
not practically) possible to determine that the initial position is mate
in 150, or whatever. (Most people think that chess is a draw with best
play.)
> Surly it uses judgment to decide with paths to take from the reponse of
> its opponent.
That's how an ordinary chess computer works, yes, but ordinary chess
computers aren't perfect: they lose from time to time. In order to make a
computer play perfect chess, you need to produce an algorithmic character-
ization of perfect play (the search and heuristics used by real computers
are just an approximation to this) and, the only such characterization
that people can see at the moment is looking at the full game tree to see
whether a position is a forced win or a draw.
Dave.
--
David Richerby Revolting Composer (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a pupil of Beethoven but it'll turn
your stomach!
|
|
