Chess is anyway finite! One day computer will definitely beat humans
Somenath Bandyopadhyay
Number of all possible games of chess is finite. Its a huge finite
number, but its finite. So one day ( I don't know how soon ) computers
will definitely beat human beings in all chess games.
So what's the big deal about this Kasparov vs. Deep Blue match?
thanks, som.
--
+------------------------------------------------------------+
|Somenath Bandyopadhyay sba...@novell.com |
| |
|These are absolutely my opinions. |
|My opinions *DO NOT* represent those of my employer. |
+------------------------------------------------------------+
Rob Jellinghaus
In article <336E2B...@novell.com>,
Somenath Bandyopadhyay <sba...@novell.com> wrote:
>Number of all possible games of chess is finite. Its a huge finite
>number, but its finite.
The same is arguably true of the entire universe's quantum configurations.
So?
>So one day computers
>will definitely beat human beings in all chess games.
I believe this, but not because computers will one day be able to
completely search the tree of all chess games. Care to do some math?
Care to estimate how many moves there are in the entire chess tree?
A VERY VERY VERY rough guess is about 30 to the 40th power or so. Care
to estimate when a computer would be able to exhaustively search this
tree? I'm sure we'll all find your estimates quite illuminating. Or
rather, I'm sure _you_ will find your estimates quite illuminating. Do
the math before tossing about glibness like this.
>So what's the big deal about this Kasparov vs. Deep Blue match?
Computers' eventual victory in chess may be inevitable... but that
doesn't mean it won't be an epochal moment when it comes! Kasparov
vs. Deep Blue is history in the making, since DB is playing undisputedly
at Grandmaster level. Deeper Blue is already making its mark in chess
history, and one week from now, it may be the winner of the match....
Kamp
Somenath Bandyopadhyay <sba...@novell.com> wrote in article
<336E2B...@novell.com>...
> Number of all possible games of chess is finite. Its a huge finite
> number, but its finite. So one day ( I don't know how soon ) computers
> will definitely beat human beings in all chess games.
>
> So what's the big deal about this Kasparov vs. Deep Blue match?
>
> thanks, som.
Chess is only of secondary importance in the Kasparov vs. Deep Blue match.
The question is, if mankind is able to create artificial intelligence
strong enough to defeat ourselves. Kasparov said that maybe God's biggest
triumph will be to see his creations recreate themselves.
Kamp.
Eran
You cannot prove that Chess is finite!! :)
carsten....@nrw-online.de
Eran <mr...@earthlink.net> wrote:
> You cannot prove that Chess is finite!! :)
Yes you can. In any position only a finite number of candidate moves is
available, and the length of a game is limited by rules such as the 50
move rule and the draw by repetition rule. The longest possible game is
5899 moves (think on that ;)
--
Carsten Kossendey (carsten....@nrw-online.de)
Somenath Bandyopadhyay
Adam Whiteson wrote:
>
> Eran wrote:
> >
> > You cannot prove that Chess is finite!! :)
>
> a gross overestimate). At any position in a game there cannot be more
> than 32*64 possible moves - thus there are no more than (32*64)^1000 =
> 10^500 possible chess games. QED
>
> Actually the number of chess games is very much smaller than this - but
> since we are just trying to establish that chess is finite there is no
> need to do extra work to refine the estimate.
There are many reference material available on this..I mean on
"Finiteness of Chess" or on "Number of all possible Games of chess".
Refer to the book: "Pure Mathematics " by Prof Hardy of Oxford
University. In the chapter on "Convergent Sequences" he gave the
solution as a number equal to 2**2**64 ( if my memory is correct )..
He solved it by creating a convergent sequence of numbers.
Its a huge number to store all games in a computer. But the way the
technology has improved in last 10 years (12 Mhz PC to 300 MHZ pc..more
powerful with Parallel processing, 10MB disk space to Terrabytes of disk
) ..it looks reachable one day.
thanks, som.
Somenath Bandyopadhyay
Adam Whiteson wrote:
>
> Eran wrote:
> >
> > You cannot prove that Chess is finite!! :)
>
> ummm..... The longest possible game of chess is less than 10000 moves (
> a gross overestimate).
Why 10,000 moves? How do you prove that?
thanks, som.
carsten....@nrw-online.de
Adam Whiteson <"<Death"@To.Spammers> wrote:
> Eran wrote:
> >
> > You cannot prove that Chess is finite!! :)
>
>
> ummm..... The longest possible game of chess is less than 10000 moves (
5899
> a gross overestimate). At any position in a game there cannot be more
> than 32*64 possible moves - thus there are no more than (32*64)^1000 =
(32*64)^10000 you mean, but that's VERY rough
a) every player has no more than 16 pieces (not 32)
b) the queen is the most mobile piece, with a maximum of 28 candidate
moves
so we have (remember, still only a rough approximation) (16*28)^5899
moves .... much less than your approximation but still an impressive
number
> 10^500 possible chess games. QED
just a guess ... (32*64)^1000 is still slightly higher than 10^500, no?
> Actually the number of chess games is very much smaller than this - but
> since we are just trying to establish that chess is finite there is no
> need to do extra work to refine the estimate.
>
>
> ********************************************
> Adam Whiteson <whit...@ix.netcom.com>
> ********************************************
--
Carsten Kossendey (carsten....@nrw-online.de)
jd...@bingo.baynet.de
Somenath Bandyopadhyay wrote:
>
> Adam Whiteson wrote:
> >
> > Eran wrote:
> > >
> > > You cannot prove that Chess is finite!! :)
> >
> > ummm..... The longest possible game of chess is less than 10000 moves (
>
> Why 10,000 moves? How do you prove that?
>
> thanks, som.
Hello som.,
the limitation of moves is a result of the FIDE rules, which demands
that every 50 moves there has to be a move of a pawn or a capture. since
there are 8 pawns each, each able to move 6 times before they promote,
there are 8 x 2 x 6 x 50 = 4.800 moves.
every side owns 7 pieces + 8 promoted pieces ( 7 pieces, because the
king can't be captured). if there is not a pawn capture during the last
50 moves, one of them has to be captured every 50 moves to get a legal
game according to the rules of FIDE. this is another 15 x 2 x 50 = 1.500
moves.
finally the last two remaining kings are able to move 49 times before
the games will be a draw.
so the maximum number of moves in a game is limitated to 4.800 + 1.500
+49 = 6349 moves in my oppinion.
regards jd
Matthew S. Klahn
In article <1997051712...@ckossend.nrw-online.de>,
carsten....@nrw-online.de wrote:
>available, and the length of a game is limited by rules such as the 50
>move rule and the draw by repetition rule. The longest possible game is
>5899 moves (think on that ;)
>
particular one. Oh, well!)
Of course the number of chess games is finite. The set of chess games is
finite. However, to say that because the set of chess games is finite chess
computers will one day become unbeatable is silly. Chess computers may
someday become superior to any human chess player, but not because there are a
finite number of chess games/positions. The number of games/positions can be
finite and still really, really, really large (such as the numbers being
quoted in this thread, i.e. 10^500) and probably could not be calculated in a
brute force method. I think that everyone realizes this, and most programs
now use algorithmic calculation to choose their moves.
I think that it's interesting that people choose to look at chess as a
calculation to solve, rather than a game to play. Even if chess is a
calculation, does this limit the number of solutions (wins) to 1? Could there
be a single, perfect chess game? I find the idea ridiculous. Rather, I think
that because people want to find perfection, they set limits on complex
systems like chess, where limits are not evident. Could there be a perfect
baseball, soccer, or basketball game? Or does the concept of perfection in
those settings become meaningless?
Let me ask a simpler question than has been asked here. Can the move
1. e4 be proven to be better than 1. d4, 1. c4 or any other opening move that
does not transpose into an 1.e4 opening? What does better mean in my
question? 1. e4 may be better than 1. h3 because of the ideas behind the
chess openings, and what we believe to lead to better games, but who is to say
that our ideas are the best or that best has any meaning in this context. Was
1. d4 Nf6 2. c4 g6 3. Nc3 Bg7 4. e4 d6 thought of as a good opening the first
few times it was played in international tournaments? Or was it thought to be
radical, laughable, and wrong? What about 1. e4 Nf6, an opening that is
played at the highest levels in chess? The hypermodern revolution brought new
ideas to chess, and who is to say that there won't be another revolution in
chess thinking which states that 1. h3 is much better than 1. e4? My point is
not that 1. h3 could be better than 1. e4 (whatever that means), but that
better is a subjective assessment rather than an objective assessment. It is
true that 1. e4 controls the center, allows the king bishop to be developed,
and the queen to control kingside space while 1. h3 does none of these, and
potentially weakens the pawn structure around where the king may castle to,
but these assessments are made using ideas that we hold true which are not
true in an objective sense.
Anyways, in my opinion, even if computers do become the dominant chess
force for the rest of human history, this does not mean that chess is a
solvable calculation. It shows us that one system of chess principles can be
applied to win or draw a game of chess, not that that system of principles is
the best possible set of principles.
Will there ever be a series of moves that forces mate or a draw from
the starting position? I doubt that one will be found (by this I mean
calculated by a chess computer or human player), and I _really_ doubt that
there could be only one such series of moves. Even if two series of moves are
found that lead to forced mate and one takes 20 moves and the other takes 21,
is the 20 move series better than the 21 move series?
Regards,
Matthew Klahn
m-klahn@remove_before_reply.nwu.edu
[Just cut the remove-before-reply part from my email address.
Matthew S. Klahn
Northwestern University, Evanston, IL. USA
m-k...@merle.acns.nwu.edu
Adam Whiteson
If this is a duplicate post, I apologize - I have been getting some NNTP errors and this is my second attempt to post this.
If I am repeating myself, I apologize.
If I am repeating myself, I apologize.
Also, this topic was just discussed in rec.games.chess.misc and what follows is a summary of comments made by
myself and other posters.
Somenath Bandyopadhyay wrote:
> Its a huge number to store all games in a computer. But the way the
> technology has improved in last 10 years (12 Mhz PC to 300 MHZ pc..more
> powerful with Parallel processing, 10MB disk space to Terrabytes of disk
> ) ..it looks reachable one day.
IMO there is no doubt that a computer will soon be the strongest chess player in the world. But as for storing all the
games on a computer - no way! Not ever! There are about 10^40 possible chess positions and vastly more possible
chess games - estimates are usually about 10^120.
Even a computer one BILLION times faster than Deep Blue which began calculating at the time of the Big Bang, would
not yet have made dent in the problem! (10^40 positions at 10^11 positions per second requires 10^29 seconds ). Any
database to store all these games would be bigger than a galaxy - perhaps bigger than the whole universe! Access
times being limited by the speed of light would take millions of years.
Adam
+++++++++++++++++++++++++++++++++++++++++++++++++
+ Adam Whiteson <whit...@ix.netcom.com> +
+++++++++++++++++++++++++++++++++++++++++++++++++
Shawn K. Quinn - NOT for spam
On Sun, 18 May 1997 11:47:02 +0200, jd...@bingo.baynet.de
<jd...@bingo.baynet.de> wrote:
>Hello som.,
>
>the limitation of moves is a result of the FIDE rules, which demands
>that every 50 moves there has to be a move of a pawn or a capture. since
>there are 8 pawns each, each able to move 6 times before they promote,
>there are 8 x 2 x 6 x 50 = 4.800 moves.
>
>every side owns 7 pieces + 8 promoted pieces ( 7 pieces, because the
>king can't be captured). if there is not a pawn capture during the last
>50 moves, one of them has to be captured every 50 moves to get a legal
>game according to the rules of FIDE. this is another 15 x 2 x 50 = 1.500
>moves.
>
>finally the last two remaining kings are able to move 49 times before
>the games will be a draw.
PMI, but I thought the game is automatically a draw as soon as neither side
has mating material? Besides there is little point in shuffling two kings
around at the end...
>so the maximum number of moves in a game is limitated to 4.800 + 1.500
>+49 = 6349 moves in my oppinion.
making the maximum only 6300 instead of 6349.
--
Shawn K. Quinn - skq...@brokersys.com - http://www.brokersys.com/~skquinn/
Whee Ky Ma
jd...@bingo.baynet.de wrote:
:
: Hello som.,
:
: the limitation of moves is a result of the FIDE rules, which demands
: that every 50 moves there has to be a move of a pawn or a capture. since
: there are 8 pawns each, each able to move 6 times before they promote,
: there are 8 x 2 x 6 x 50 = 4.800 moves.
:
: every side owns 7 pieces + 8 promoted pieces ( 7 pieces, because the
: king can't be captured). if there is not a pawn capture during the last
: 50 moves, one of them has to be captured every 50 moves to get a legal
: game according to the rules of FIDE. this is another 15 x 2 x 50 = 1.500
: moves.
:
: finally the last two remaining kings are able to move 49 times before
: the games will be a draw.
: so the maximum number of moves in a game is limitated to 4.800 + 1.500
: +49 = 6349 moves in my oppinion.
: regards jd
Three remarks to this:
1. If you want to promote ALL pawns, you have to free lines by letting
pawns make 8 captures. But then you have a pawn move and a capture at
the same time, so you lose 8 x 50 = 400 moves.
2. The two remaining kings will be able to move fifty times. At the
50th move the game is a draw.
3. The first "action" in the game has to be taken by Black, at his
49th move. Of course, Black cannot remain the only "active"
(i.e. capturing and pawn-moving) party. If you think a little bit, you
find that there are four stages, so three switches are necessary. For example:
* Black opens 4 lines.
* White opens 4 lines, promotes all his pawns and captures all black pieces (not pawns).
* Black promotes all his pawns and captures all white pieces.
* White captures all black pieces and the kings move on for a while.
This yields a `loss' of 3 x 0.5 = 1.5 move.
So the correct answer is:
4800 + 1500 - 400 + 50 - 1.5 = 5948.5 moves. White makes the last move.
Andreas Stabel
Nice posts - though of course I have something to add :)
In article <5m0r4b$l...@info.service.rug.nl>, m...@th.rug.nl says...
>
>jd...@bingo.baynet.de wrote:
>:
>: Hello som.,
>:
>: the limitation of moves is a result of the FIDE rules, which demands
>: that every 50 moves there has to be a move of a pawn or a capture. since
>: there are 8 pawns each, each able to move 6 times before they promote,
>: there are 8 x 2 x 6 x 50 = 4.800 moves.
>:
>: every side owns 7 pieces + 8 promoted pieces ( 7 pieces, because the
>: king can't be captured). if there is not a pawn capture during the last
>: 50 moves, one of them has to be captured every 50 moves to get a legal
>: game according to the rules of FIDE. this is another 15 x 2 x 50 = 1.500
>: moves.
>:
>: finally the last two remaining kings are able to move 49 times before
>: the games will be a draw.
>:
>: so the maximum number of moves in a game is limitated to 4.800 + 1.500
>: +49 = 6349 moves in my oppinion.
>:
>: regards jd
>
>
>Three remarks to this:
>
>1. If you want to promote ALL pawns, you have to free lines by letting
>pawns make 8 captures. But then you have a pawn move and a capture at
>the same time, so you lose 8 x 50 = 400 moves.
>
This is not correct. Black starts the action by capturing white pieces thus
opening lines without losing moves. Later on white does the same.
>2. The two remaining kings will be able to move fifty times. At the
>50th move the game is a draw.
>
>3. The first "action" in the game has to be taken by Black, at his
>49th move. Of course, Black cannot remain the only "active"
50th
>(i.e. capturing and pawn-moving) party. If you think a little bit, you
>find that there are four stages, so three switches are necessary. For
example:
>
>* Black opens 4 lines.
>* White opens 4 lines, promotes all his pawns and captures all black pieces
(not pawns).
>* Black promotes all his pawns and captures all white pieces.
>* White captures all black pieces and the kings move on for a while.
>
>This yields a `loss' of 3 x 0.5 = 1.5 move.
This is not correct because black and white does not have to open four lines
each. As an example consider the following pawn moves by black:
b7xa6, c7xb6, b6xa5, d7xc6, c6xb5, b5xa4
Now there are five black pawns in the a column, and after white a pawn has
hit a black piece, all five pawns may be promoted.
>
>So the correct answer is:
>
>4800 + 1500 - 400 + 50 - 1.5 = 5948.5 moves. White makes the last move.
>
>
If we look at the first post, we get approximately 6350 moves, but from the
argument above we loose some moves because some times during the game, black
and white has to switch beeing the one to do the "action" moves. If we do not
consider the tempo moves, but just the action moves we get approximately
126 moves = 6350/50 - 1. The minus one because of the tempo moves made by the
kings at the end. Or to put it another way 8 x 2 x 6 + 15 x 2.
This number is small enough for us to list them.
The challenge now is who can come up with the approximately 126 move sequence
requiring the smallest number of switches between black and white.
Regards Andreas Stabel
Dennis Breuker
(from http://www.clark.net/pub/pribut/chessfaq.html#A1.24)
Subject: [24] Trivia
How long is the longest possible chess game?
The basic idea is a player may claim a draw if fifty moves elapse
without a capture or a pawn advance. Ignoring the special cases where
more than 50 moves
are allowed by the rules, the answer is after Black's 5948th move, White
is able to claim a draw. The simple calculation is ( + - + ) * , or
(16*6 + 30 - 8 + 1) *
50 = 5950; we're able to trim two moves from this total by observing
that sequences of Captures/Pawn_moves must have (at least) 4
alternations between the
two players.
Dennis.
Andreas Stabel
In article <338449...@cs.unimaas.nl>, bre...@cs.unimaas.nl says...
Sorry - I was obviously wrong in my reasoning about loosing the 400 moves.
Regards Andreas Stabel
Ed Hummel
jd...@bingo.baynet.de wrote:
> the limitation of moves is a result of the FIDE rules, which demands
> that every 50 moves there has to be a move of a pawn or a capture. since
> there are 8 pawns each, each able to move 6 times before they promote,
> there are 8 x 2 x 6 x 50 = 4.800 moves.
I apologize for adding to this thread, but I can't resist. It is
trivial
to contruct an infinite single game of chess.
for all integer n > 0.
White move n:
if n odd: Ng1-f3,
if n even: Nf3-g1;
Black move n:
if n odd: Ng8-f6
if n even: Nf6-g8.
The point is that three 50-move and the 3-fold repetition rules
do not end the game unless a player CHOOSES to exercise the rule.
FIDE rules DO NOT "demand" a pawn move or capture every 50 moves.
In fact the rule is clear that a claim is needed. The same is true
of the USCF rules, and every other association rules of which I am
aware.
If you like you may define a new game (chess-2) in which it is
MANDATORY to declare the game ended when there is a 3-fold repetition
or 50 moves without a capture or pawn move. You can calculate
the number of possible moves in the longest chess-2 game.
This does not in and of itself make chess an infinite game. There
are a finite number of arrangements of the pieces. Nor does it
imply computers will have a harder time solving the question of
whether white can force a win from the initial position.
The questions of the finiteness of chess and of the solvability of
chess are not as trivial as they seem if you are trying to make
formal, provable statements. The topic is a bit esoteric for this
newsgroup, but if anyone would like to have a limited discussion
by email please feel free to write to me.
Ed Hummel
ehu...@lucent.com
jd
Hello Whee Ky Ma,
There are some nice improvements over my first approach indeed, but If
YOU also think a little bit (congratulations, your answer nearly ever
oversteps the boundaries of politeness), you will realize, that you
can't have the correct solution, due to two aspects:
1) There are of course no half moves. A game, in which white moves 19
times and black only 18 times for example is a game of 19 moves and not
a game of 18 moves (look at the sixt Kasparov-Deep Blue game: did you
ever hear, kasparov loses in 18.5 moves ?)
2) A game is drawn by claiming of one player. According to the
FIDE-rules he informs his opponent or the arbiter, that he is able, to
fulfill the 50 moves (or 3 times-repetition-rule) with his NEXT move.
The arbiter will prove this claim and declare the game as drawn. So,
IMHO, it's still + 49 moves instead of 50 moves.
Regards, jd
Pierre G. Boutquin
Ed Hummel <ehu...@lucent.com> wrote in article
<3384B2...@lucent.com>...
> jd...@bingo.baynet.de wrote:
[snip]
> The questions of the finiteness of chess and of the solvability of
> chess are not as trivial as they seem if you are trying to make
> formal, provable statements. The topic is a bit esoteric for this
> newsgroup, but if anyone would like to have a limited discussion
> by email please feel free to write to me.
They are. Game theory is a math branch that deals with this topic and it
proves that chess has an optimal strategy. (The drawback is that it cannot
determine what it is neither whether it results in a win or a draw.)
Bjarke Dahl Ebert
>They are. Game theory is a math branch that deals with this topic and it
>proves that chess has an optimal strategy. (The drawback is that it cannot
>determine what it is neither whether it results in a win or a draw.)
Can it be *proven* that an optimal strategy does not result in a loss
for white?
Some questions on the 50-move rule and repetition rule:
These are mostly of theoretical interest, and for making an endgame
database exact (w.r.t. 50-move rule). It's a typical computer science
+/- 1 counting problem :-)
1) What if the last of 100 halfmoves without captures and pawn moves is a
check mating move? Is it a draw or a win?
2) What is a "repetition"? Does castling rights or en passant capture
possibility count as part of the position?
For example: If one player castles, and later returns to the
"uncastled" position, you could argue that this is not the same
position, since that player now cannot castle again.
3) Who can claim a draw? The one who just moved? The other one? Both?
Regards,
Bjarke Dahl Ebert
--
---------------------------------------+------------------------------
Bjarke Dahl Ebert | If it works, it's obsolete
<URL: http://www.daimi.aau.dk/~bde/> |
---------------------------------------+------------------------------
Ed Hummel
> > chess are not as trivial as they seem if you are trying to make
> > formal, provable statements. The topic is a bit esoteric for this
> > newsgroup, but if anyone would like to have a limited discussion
> > by email please feel free to write to me.
> proves that chess has an optimal strategy. (The drawback is that it cannot
> determine what it is neither whether it results in a win or a draw.)
If you think you have such a proof I'd be thrilled to see it. The
theoretical discussions I've seen always make some simplifying
assumption(s).
Again I suggest this topic is better taken off-line in email. Please
write to me if you are interested.
Ed Hummel
ehu...@lucent.com
DepThought
In article <338AFA...@lucent.com>, Ed Hummel <ehu...@lucent.com>
writes:
>If you think you have such a proof I'd be thrilled to see it. The
>theoretical discussions I've seen always make some simplifying
>assumption(s).
>
>Again I suggest this topic is better taken off-line in email. Please
>write to me if you are interested.
I'd rather see it online, thank you. I tend to agree with Ed -- game
theory tends to oversimplify the problem -- but I'm only a lowly engineer,
and so my math skills are more practical than theoretical ;) Educate me
(us).
Pat King
DepTh...@aol.com (no relation)
Michael Huemer
Ed Hummel <ehu...@lucent.com> writes:
>Again I suggest this topic is better taken off-line in email. Please
>write to me if you are interested.
Please keep it on the newsgroup so other people can read it!
--
^-----^
Michael Huemer <o...@rci.rutgers.edu> / O O \
http://www.rci.rutgers.edu/~owl | V |
\ /
Michael Huemer
m-klahn@remove_before_reply.nwu.edu (Matthew S. Klahn) writes:
>Of course the number of chess games is finite. The set of chess games is
>finite. However, to say that because the set of chess games is finite chess
>computers will one day become unbeatable is silly. Chess computers may
>someday become superior to any human chess player, but not because there are a
>finite number of chess games/positions. The number of games/positions can be
>finite and still really, really, really large (such as the numbers being
That's true. At some point you run into limitations like the size of
the earth and the time remaining before our sun explodes. (I.e., to
list all the possible chess games in the time remaining before our
solar system is destroyed would probably require a computer larger
than the earth.) The calculations I've seen on this ng indicate that
the longest possible chess game is somewhere around 6000 moves (well,
at least that's an upper bound; probably it's much less). If that's
right, an upper bound for the number of possible games could be set by
reasoning that, each move, each player has at most 64 possible places
to go. So the number of possible games is at most (64*64)^6000, or
10^21674. Unless the universe is infinite, that's almost certainly
more than the number of elementary particles in the universe.
Granted, this is also surely a very large overestimate of the number
of possible games.
>calculation to solve, rather than a game to play. Even if chess is a
>calculation, does this limit the number of solutions (wins) to 1? Could there
>be a single, perfect chess game? I find the idea ridiculous. Rather, I think
No, there are probably multiple possible ways for one side to play a
perfect game. (I say "one side" because if the perfect player as
white is destined to beat black no matter what black does, then it's
difficult to understand what perfect play on the part of black would
be. Resign at move 1?)
> Let me ask a simpler question than has been asked here. Can the move
>1. e4 be proven to be better than 1. d4, 1. c4 or any other opening move that
>does not transpose into an 1.e4 opening? What does better mean in my
Depends on your standards for 'proof,' and on the sense of 'can' you
mean. If you mean "proof" in the sense of formal logic, and "can" in
the sense of "realistically possible, given limitations like the size
of computers that we could build on the earth," then the answer is no.
But if you mean "can" in the sense of purely theoretical possibility,
then the answer may well be yes (or it may be that e4 could be proven
to be worse than c4). At any rate, you haven't given any reason for
denying that it could.
Also, if you mean "prove" in a looser sense, in the sense of giving
adequate grounds for believing something, which are not subject to
serious debate, then it has already been 'proven' that 1. e4 is
superior to, say, 1.h3.
>question? 1. e4 may be better than 1. h3 because of the ideas behind the
>chess openings, and what we believe to lead to better games, but who is to say
>that our ideas are the best or that best has any meaning in this context. Was
I don't understand your argument here. You haven't given any reason
at all for doubting that 1.e4 is objectively better than 1.h3. Your
only argument seems to consist in rhetorical questions like "Who's to
say that it is?" (which is pretty meaningless as far as I can tell)
and merely asserting that it isn't.
>chess thinking which states that 1. h3 is much better than 1. e4? My point is
>not that 1. h3 could be better than 1. e4 (whatever that means), but that
>better is a subjective assessment rather than an objective assessment. It is
Why is is 'subjective', and what do you mean by that anyway?
If you try playing 1.h3 in a bunch of tournaments, I bet you will do
worse (when the other factors that we 'subjectively' consider relevant
to quality of play are controlled) than if you play 1.e4 openings.
This 'doing worse' is as 'objective' as I can imagine anything being.
You'll lose more games -- why isn't that 'objective'?
>true that 1. e4 controls the center, allows the king bishop to be developed,
>and the queen to control kingside space while 1. h3 does none of these, and
>potentially weakens the pawn structure around where the king may castle to,
>but these assessments are made using ideas that we hold true which are not
>true in an objective sense.
Why aren't they 'true in an objective sense'?
> Will there ever be a series of moves that forces mate or a draw from
>the starting position? I doubt that one will be found (by this I mean
>calculated by a chess computer or human player), and I _really_ doubt that
So do I. I'd go further -- I think it's a virtual certainty that no
such sequence will ever be found.
Chris Jason Richards
In article <5n9jmr$3...@erebus.rutgers.edu>,
o...@rci.rutgers.edu (Michael Huemer) writes:
> m-klahn@remove_before_reply.nwu.edu (Matthew S. Klahn) writes:
>
>>Of course the number of chess games is finite. The set of chess games is
>>finite. However, to say that because the set of chess games is finite chess
>>computers will one day become unbeatable is silly. Chess computers may
>>someday become superior to any human chess player, but not because there are a
>>finite number of chess games/positions. The number of games/positions can be
>>finite and still really, really, really large (such as the numbers being
>
I agree. This is a little snippet of info I gathered from my AI studies.
o Chess has an average branching factor of ~35. Games generally are
played to 50 moves/player (100 total moves). Therefore the search
tree has about 35^100 nodes. Keep in mind there only about 10^40
*different* legal positions.
o We are able to search 200 million nodes/second w/ current technology.
With this speed, it would still take 4E138 years to calculate
out to completion. Even if a computer could calculate 1000 trillion-
trillion nodes/second (1E27) it would still take 8.1E119 years to
traverse the tree.
Major movements in AI research will be the determining factor that leads
to a chess (sentient?) machine that will be able to beat a human 100%
of the time. I do expect to see that in my life time.
This is what makes chess (and other games) and real world problems so
incredibly fascinating. Chess has a mere 6 operators (the chess pieces)
and yet it is so complex ;)
Cheers,
cjr
--
_______________________________________________________________________
Chris Richards rich...@tamu.edu | Texas A&M University
Project Coordinator | Department of Computer Science
http://www.cs.tamu.edu/people/richards | Internet Publishing Services
A bus stops at a bus station; a train stops at a train station.
On my desk I have a workstation...
carsten....@nrw-online.de
Michael Huemer <o...@rci.rutgers.edu> wrote:
> m-klahn@remove_before_reply.nwu.edu (Matthew S. Klahn) writes:
>
> >Of course the number of chess games is finite. The set of chess games is
> >finite. However, to say that because the set of chess games is finite
> >chess computers will one day become unbeatable is silly. Chess computers
> >may someday become superior to any human chess player, but not because
> >there are a finite number of chess games/positions. The number of
> >games/positions can be finite and still really, really, really large
> >(such as the numbers being
>
> That's true. At some point you run into limitations like the size of the
> earth and the time remaining before our sun explodes. (I.e., to list all
> the possible chess games in the time remaining before our solar system is
> destroyed would probably require a computer larger than the earth.) The
> calculations I've seen on this ng indicate that the longest possible chess
> game is somewhere around 6000 moves (well, at least that's an upper bound;
> probably it's much less). If that's right, an upper bound for the number
> of possible games could be set by reasoning that, each move, each player
> has at most 64 possible places to go. So the number of possible games is
> at most (64*64)^6000, or 10^21674. Unless the universe is infinite,
> that's almost certainly
Where does that (64*64)^6000 come from?
One would think that each player has at maximum 32 pieces. One of those
is the king which has at maximum 8 moves in a position. The rest can be
at maximum 9 queens (1 + 8 promoted pawns), and a queen has a maximum
mobility of 28 moves. The rest is at maximum 2 rooks and 2 bishops, each
of which has a maximum mobility of 14, and 2 knights, each of which have
8 possible moves at maximum (don't waste your time on minorpromotions
and stuff, the limiting factor is the number of queens.)
So the maximum number of legal moves in a given legal position is
8 + 9 * 28 + 4 * 14 + 2 * 8 = 332, which is _slightly_ less than 64 *
64 = 4096 ...
The 6000 is almost correct (5899, see my earlier post), so we come up
with 332^5899 which is around 10^14722 as opposed to your 10^21674 ...
Numbers are getting smaller fast, eh?
Now of course this is still the most nonsensic since
a) if one player has such huge possibilities the other must by
definition have much less possibilities (for example for each pawn you
want to promote, either you or your opponent must capture at least once)
b) The number of games with those 5899 moves is VERY small. If a game is
not decided by move 1000 we can pretty much consider it drawn anyway.
c) We're not really interested in the total number of possible games at
all since the use of hash tables and endgame tablebases will eliminate
LOTS of transpositions and cut off most other games early.
Factoring in that and some other stuff I'd say that less than 10^2000
nodes would have to be searched to solve chess (given an enormous amount
of memory of course). Like 30 years ago computers did around 500
nodes/sec. Today's Deep Blue (256 chess processors) does 200,000,000
nodes/sec. If they built the largest possible Deep Blue (using the same
hardware design) we'd come up with 512 SP/2 nodes * 6 PCI slots * 8
processors per board = 24576 chess processors or 9,600,000,000
nodes/sec. That's a factor of around 20,000,000 compared to 30 years
ago. In 30 years from now we will most likely have another
20,000,000-fold increase in processing speed, or around 1.92*10^17 nodes
per second, or 1.65*10^22 nodes/day, or 6.05*10^24 nodes/year. If the
machine is not modified further, that machine would still take 10^1974
years, and we don't want to wait for that to finish ;)
So if we wait another 300 years we will get another (20,000,000^10)-fold
increase in processing power (around 10^73) which leaves us with 10^1900
years to solve chess from then on. For every 300 years we wait before we
start the computation, the solving time will reduce by the same factor
10^73 ... If we start in 5297 a.d. it will take around 10^1170 years. If
we start in 8297 a.d., 10^440 years. If we start in 11297 a.d., chess
will take LESS THAN A YEAR to solve given the increase in computanional
power can be kept up. So I'll just keep pretending chess will be solved
within the next 10,000 years, as opposed to not being able to solve it
within the lifetime of the universe ...
Of course, the universe still might stop existing within the next 10,000
years, but I don't think this assumption is justified.
Also of course still the above is just toying with numbers. The machine
described above is by no means the fastest possible. Given (quasi)
unlimited funds one might easily build a machine with 1,000,000
processors TODAY (by connecting a respective number of smaller machines
via high-speed busses) which is another factor 40,000 compared to the
above and which would move the date when we can finally start solving
chess to around 7997 a.d. ... We'd be able to do the task in around 8
hours from then on ;)
You will of course pretend that some of the above assumptions are wrong
but still there's a great chance of solving chess within the next 50,000
years. If time travel is possible, of course someone from like 50,000
years from now might actually send us the solution back to 1997 as well
...
Just my $.20 worth ;)
-- Carsten Kossendey (carsten....@nrw-online.de)
"Life is too short for the game of chess" - Lord Henry Byron
carsten....@nrw-online.de
Michael Huemer <o...@rci.rutgers.edu> wrote:
> m-klahn@remove_before_reply.nwu.edu (Matthew S. Klahn) writes:
>
> >Of course the number of chess games is finite. The set of chess games is
> >finite. However, to say that because the set of chess games is finite
> >chess computers will one day become unbeatable is silly. Chess computers
> >may someday become superior to any human chess player, but not because
> >there are a finite number of chess games/positions. The number of
> >games/positions can be finite and still really, really, really large
> >(such as the numbers being
>
> That's true. At some point you run into limitations like the size of the
> earth and the time remaining before our sun explodes. (I.e., to list all
> the possible chess games in the time remaining before our solar system is
> destroyed would probably require a computer larger than the earth.) The
> calculations I've seen on this ng indicate that the longest possible chess
> game is somewhere around 6000 moves (well, at least that's an upper bound;
> probably it's much less). If that's right, an upper bound for the number
> of possible games could be set by reasoning that, each move, each player
> has at most 64 possible places to go. So the number of possible games is
> at most (64*64)^6000, or 10^21674. Unless the universe is infinite,
> that's almost certainly
Where does that (64*64)^6000 come from?
KMan
On 30 May 1997 12:59:24 GMT, depth...@aol.com (DepThought) wrote:
>In article <338AFA...@lucent.com>, Ed Hummel <ehu...@lucent.com>
>writes:
>
>>If you think you have such a proof I'd be thrilled to see it. The
>>theoretical discussions I've seen always make some simplifying
>>assumption(s).
>>
>>Again I suggest this topic is better taken off-line in email. Please
>>write to me if you are interested.
>
>I'd rather see it online, thank you. I tend to agree with Ed -- game
>theory tends to oversimplify the problem -- but I'm only a lowly engineer,
>and so my math skills are more practical than theoretical ;) Educate me
>(us).
>
>Pat King
>DepTh...@aol.com (no relation)
I've read all these threads- about Finite moves and 10,000 moves
maximum and all that jazz, and all I can say is that you guys should
start posting to Alt.Chess.Bullshit. The computer will "never" become
a grand master over a human. There's more to chess than being able to
see moves in advance. Jeez.
KMan "The cat's raaaaaaaaaaaaaaaaahh outta the bag!"