Chess is Dead
Russell Easterly
David B. Greene wrote in message <65o115$6f$2...@nntp5.u.washington.edu>...
>It has been six months since Deep Blue, the chess playing computer, beat
>Kasparov, the human chess champion, in their second match.
snip
>Deep Blue has a massively parallel processing architechture that supposedly
>can evaluate 200 million chess positions per second. At about 10 pieces
>per side, each having 10 moves that would only be about four moves deep
>into the game for each side per second - not much.
Most chess programs have special sub-routines for end games.
As you point out, brute force doesn't work very well if you need
to calculate more than a few moves deep.
Yasser Sierwan once told me that he calculated an end game
out to 24 moves (48 ply).
>My own feeling is that chess is nearly exhausted and the computer is only
>making this more so.
>Dave Greene
Computers aren't even close to being able to play great chess.
There are strategies that are very effective against them.
Kasporov proved that after he lost a few "wild" games.
Computers are terrible at long drawn out end games.
They are only dangerous if you get into a tactics war.
Until now, there weren't enough master class chess programs
to make learning how to beat them worthwhile.
Winning one tournament doesn't mean computers have "won".
Russell
-Spot you a knight
David B. Greene
It has been six months since Deep Blue, the chess playing computer, beat
the first. IBM nixed any possible third match in September but now Deep
Blue is to be retired as the programmers go on to other projects. I for
one feel a profound sense of dissappointment as I believe the question of
who is better, man or machine, remains unresolved. I know it remains
unresolved in Kasparov's mind as he feels cheated about a series of
uncharacterisic moves Deep Blue made in the second game although I'm not
sure what the exact basis of his suspicions is.
Deep Blue has a massively parallel processing architechture that supposedly
can evaluate 200 million chess positions per second. At about 10 pieces
per side, each having 10 moves that would only be about four moves deep
into the game for each side per second - not much. So how much time did
Deep Blue get per move? Was abrute force algorithm used that examined all
possible moves or was there some mechanism employed to pare down selections
so as not to waste time on obvious dead end allys? That would make a big
difference in the meaning of "200 million chess positions per second"
claim.
My own feeling is that chess is nearly exhausted and the computer is only
making this more so. When I was young, I was assured by the chess mavens
that the game was inexhaustable as there were so many possible moves that
the number of positions increases expotentially with the number of moves
made. Well I quickly came to realize that at least 90 percent of those
moves were useless which trimmed the number of realistic possitions
considerably although there were still a vast number left. Later I
discovered that on more than one occasion the grandmasters of the game had,
by coincidence, replayed a previous game move for move. The occurances of
duplicate games indicated to me that the game was on its way to ultimate
saturation. But now, with Deep Blue, we have reached that point earlier
than I thought we would. I believe the mystery of chess is gone but I'd
like for Kasparov to have another chance to prove me wrong.
Dave Greene
Rudeboy
[David B. Greene]
>It has been six months since Deep Blue, the chess playing computer,
>I for one feel a profound sense of dissappointment as I believe the
The question is moot. After all, who designed and built the machine?
Humbly yours,
Rudeboy
Trevor Chong
> My own feeling is that chess is nearly exhausted and the computer is only
> making this more so. When I was young, I was assured by the chess mavens
> that the game was inexhaustable as there were so many possible moves that
> the number of positions increases expotentially with the number of moves
> made. Well I quickly came to realize that at least 90 percent of those
> moves were useless which trimmed the number of realistic possitions
> considerably although there were still a vast number left. Later I
> discovered that on more than one occasion the grandmasters of the game
had,
> by coincidence, replayed a previous game move for move. The occurances
of
> duplicate games indicated to me that the game was on its way to ultimate
> saturation.
Not often would a grandmaster reach a previous game, move for move, by
*coincidence*. You will find that, on a professional level, grandmasters
prepare extremely meticulously against their particular opponent. For
example, Mikhail Tal once played a game against Portisch in which he had to
choose between transposing into a technically better position or playing
for an attack. Tal chose the latter. Portisch then asked him why he
hadn't played differently, to which Tal replied that the thought of playing
the move hadn't even entered his mind. Portisch looked at Tal with
astonishment, and said that Tal had already layed this move in an earlier
game. It turned out that Tal had played the move before against Benko at
Curacao. The conscientious preparation of grandmasters is therefore
meticulous.
More importantly, however, and in response to your statement, grandmasters
who are worth their salt know their opponent and their arsenal. If they
are going along a line which they know that their opponent is not partial
towards, they would be stupid in placidly allowing themselves to be drawn
into a lost game. Complications arise. New variations come to light
(usually in preparation).
In addition, lines continually go in and out of fashion, not necessarily
because they have been completely refuted, but usually because of
grandmasters bringing to light newer, sometimes (but not necessarily) more
novel variations. Then the old variations come back in with a veangance,
e.g. Bobby Fischer revived the once ailing King's Gambit. Lines which were
once thought 'bad' and which won only a two page mention in the best of
chess manuals are now considered the norm, e.g. The Scandinavian.
All in all, I put it to you that Chess is far from dead. And, if you would
like more proof of this...
Let's play.
Trevor Chong
tc...@student.monash.edu.au
Jerome A. Schroeder
The occurances of
>duplicate games indicated to me that the game was on its way to ultimate
>than I thought we would. I believe the mystery of chess is gone but I'd
>like for Kasparov to have another chance to prove me wrong.
>
>Dave Greene
>
means is that Chess will return to the hands of the amatuer where it
belongs.
Remember that Big Blue was programmed by humans.
Jerry
Ian Stirling
In alt.folklore.computers Rudeboy <ez01...@boris.ucdavis.edu> wrote:
: [David B. Greene]
:>It has been six months since Deep Blue, the chess playing computer,
:>beat Kasparov, the human chess champion, in their second match. . . .
:>I for one feel a profound sense of dissappointment as I believe the
:>question of who is better, man or machine, remains unresolved. . . .
Unfortunately this has about as little to say on that issue, as of
a pushing contest between a man and a tank.
Sheer brute force.
--
Ian Stirling. Designing a linux PDA, see http://www.mauve.demon.co.uk/
----- ******* If replying by email, check notices in header ******* -----
Money is a powerful aphrodisiac, but flowers work almost as well.
Robert A Heinlein.
Brian McKeever
Rudeboy wrote:
> >question of who is better, man or machine, remains unresolved. . . .
>
> The question is moot. After all, who designed and built the machine?
>
> Humbly yours,
> Rudeboy
This reminds me of a letter to the editor that appeared in the New York Times shortly
after Kasparov lost, and which I thoroughly enjoyed at the time. The quote was along
the lines of (this may not be verbatim, since I could not track down the source on the
NYT web site) "it's been proven only that, in chess, men with computers can beat men
without computers. This should come as no surprise, since men with poles can jump
higher than men without poles."
I think this pretty much sums up my feelings on the subject. Computers are tools, and
we can do more with them than we can do without them. There is no question about "who
is better" --- after all, we don't ask who is better, the decathlete or his pole.
Brian McKeever
Ingrid Voigt
David B. Greene wrote:
> My own feeling is that chess is nearly exhausted and the computer is only
> making this more so. When I was young, I was assured by the chess mavens
> that the game was inexhaustable as there were so many possible moves that
> the number of positions increases expotentially with the number of moves
> made. But now, with Deep Blue, we have reached that point earlier
> than I thought we would. I believe the mystery of chess is gone but I'd
> like for Kasparov to have another chance to prove me wrong.
>
> Dave Greene
Couldn't you have told me this before I spent all evening yesterday
trying to hold this endgame???? I could have told my opponent that
Deep Blue had already solved it and got my draw three hours earlier!
(Couldn't resist)
Ingrid
Yves Gallot
> My own feeling is that chess is nearly exhausted and the computer is only
> making this more so. When I was young, I was assured by the chess mavens
> that the game was inexhaustable as there were so many possible moves that
> the number of positions increases expotentially with the number of moves
> moves were useless which trimmed the number of realistic possitions
> considerably although there were still a vast number left. Later I
> discovered that on more than one occasion the grandmasters of the game
had,
of
> duplicate games indicated to me that the game was on its way to ultimate
> than I thought we would. I believe the mystery of chess is gone but I'd
> like for Kasparov to have another chance to prove me wrong.
It is not exhausted. Today grandmasters are not genious, they are just like
a computer : a large memory and a great logical brain ... were is genius,
nowhere. A real genius grandmaster would be able to play an absolutly
unknown game and win. Perhaps one will be born tomorrow.
Today chess is like physics at the end of the 19th century. A lot of people
think that all is known, we should play like that, impossible to play in a
different way. We just have to refine theories. But Albert Einstein will
come, with a human form or a computer form, this is the real question.
What is sure is that in the future a genius computer will come. When it
will be able to see 50 plies forward, why it would play our simple opening
games ? It will probably play in a different way and beat us. Then we will
learn new chess strategies. But perhaps when seeing that, human mind will
be able to create a more global theory a beat the computer ... and will
program the computer with the new theory and ...
Well, computer is a new great tool. For me, my computer is an extension of
my brain, able to do a lot of boring and long computations and then my
brain can analyse results and imagine a theory, what it is really made for.
Playing a chess game today, without a computer for tactical analyse, is,
for me, a really old point of view. Human mind power is not to be like a
computer ! If we use our computers as tools and not as opponents (the bad
side of human mind : the warrior), chess is not dead.
Yves
Daniel Baechli
> [...] I for
> one feel a profound sense of dissappointment as I believe the question of
> who is better, man or machine, remains unresolved. [...]
> Dave Greene
Many others instead of me might write this comment.
But first, for that it is stated once more:
How can one compare the 'intelligence' of a machine
made by human intelligence so generally with human
intelligence itself?
Secondly, maybe there is another sublime question in the
question. It may or may not, but the question I have in mind
is closely related, and can partially be approached.
Nearly everyone knows the game 'three in a row', played
on a board with 3x3 squares. The one who starts will never
loose if he makes the best moves. He can even win if the
other doesn't choose the best moves. Surely he can also
loose, if he doesn't make the best moves.
This is intuitively and not only intutively clear, as there
are only a finite number of possible games and one can
consider them and will find the best move.
The connection to the chess game is now, that there are
also only finitely many possible games. The possible positions
in a chess game are finite, rudely bounded by 33^64. Every chess
chess game can be forced to end, by the draw-rule for repetion
of the same position, the number of moves is then bounded by
3*33^64. So there is a boundary N for the number of all different
chess games.
Here one cannot consider all the possible resulting different
games in searching the best move. (If one does, there are
more difficult games then chess :-). ) But one can ask similar
questions as before: Is there a first move for White (or in
another position) which asserts him, that nevertheless how
Black replies, he has always a move where there is for every
possible reponse of Black a game he surely wins, or reach
draw at least? Or has he lost from the beginning?
If one could solve this questions, the mystery of chess surely
would have gone, as it is with 'three in a row' after having played
it several times.
But how could one solve this question with a computer?
Given a computer which can calculate 'N games per second',
N as above, it could play the best possible move in any situation.
So in a way it is a matter of speed. But the possibility of
constructing computers in this range is generally answered
as principally no by physical limitations. But there may be
other ways of computing, with nondigital machines.
It's an open question.
This underlies the necessity of finding algorithms which
reduces the number of operations to find the best move.
As they can't calculate always all the way, the formulation
'to find a good move' is mostly more appropriate.
But this 'finding of algorithm' is a difficult work in trying
to define in a computer language what a good move is.
Finally one reaches the point of the impossibility of
generally determing what a program does (Theorem of Rice-
Shapiro). One can informally state this as the fact, that if you
have an algorithm wherefore you think that it calculates the
best move (at least in certain situations) one cannot generally
determine by a machine if it is really the best move (or better
'a best move'). No machine can be considered for solving this
task.
It is here that human capability enters again, as it cannot be
fully replaced by mechanising human ways of analyzing a problem.
A program can do what it is said to do, but it cannot determine itself
if it does what it is intended to do.
(Greetings to Marvin, both of you two.)
- - - - - - -
DBaechli
Mike H
In article <65oh5m$her$1...@mark.ucdavis.edu>, Rudeboy
<ez01...@boris.ucdavis.edu> writes
>[David B. Greene]
>>It has been six months since Deep Blue, the chess playing computer,
>>beat Kasparov, the human chess champion, in their second match. . . .
>
>The question is moot. After all, who designed and built the machine?
>
>Humbly yours,
>Rudeboy
Ever heard of a neural net ? Obselescence awaits us all.
(Mmmm. I'm in a very melancholy mood today. Sorry.)
--
Mike H
"If truth equals concensus and the populace is wrong....
- I am still condemned"
N.B. Remove ".spamless" from address to reply.
Mike H
In article <0000347FF...@mauve.demon.co.uk>, Ian Stirling
<0000347FF...@mauve.demon.co.uk> writes>: [David B. Greene]
>:>It has been six months since Deep Blue, the chess playing computer,
>:>beat Kasparov, the human chess champion, in their second match. . . .
>:>I for one feel a profound sense of dissappointment as I believe the
>:>question of who is better, man or machine, remains unresolved. . . .
>
>
>a pushing contest between a man and a tank.
>Sheer brute force.
>
developed a fixation on the idea that Deep Blue could read his mind as
he could find no other rational reason for it's ability to react so fast
to his well thought out schemes. Big Blue was cold, inhuman, relentless
and utterly alien.
This was almost sufficient alone to break Karparov. What you cannot
understand, you cannot defeat.
nob...@nowhere.on.ca
>It has been six months since Deep Blue, the chess playing computer, beat
>Kasparov, the human chess champion, in their second match. Kasparov won
>the first. IBM nixed any possible third match in September but now Deep
> I believe the mystery of chess is gone but I'd
>like for Kasparov to have another chance to prove me wrong.
>
>Dave Greene
>
Check out a chess conference. Maybe it's still alive there.
hesp...@clark.net
Sam. (s...@greenaum.demon.co.ARSE!ARSE!ARSE!uk) wrote:
: Well seeing as how chess is ultimately a finite state game, there are
: only so many chess setups existing in the universe, it will eventually
: be cracked. Actually I suppose it depends how many possible states
: there are. It may turn out there are so many it's impossible to store
: the data about each possible move without running out of atoms in the
: universe.
Exactly so.
The possible positions have been estimated to be on the order of 10^34,
which makes chess a very tough nut indeed!
But even if chess *were* to be solved by a computer some day, who cares?
Did we stop racing horses when the automobile was invented?
Chess is a game for and between *people*.
It gives us pleasure for gods sakes! Computers derive no more
satisfaction from a long combination than they do from calculating pi.
Besides, if I get into trouble I can always turn the blasted machine off,
a favor which it is (thankfully) unable to return.
#%^>
Bright Blessings
Hesperos, USCF
*-------*-------*
*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*
* "No one has a right to say: this is right, or that is *
* wrong. It isn't just one way." --- Gloria M. Estefan *
*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*~*
Jim Balter
Sam. wrote:
>
> Well seeing as how chess is ultimately a finite state game, there are
> only so many chess setups existing in the universe, it will eventually
> be cracked. Actually I suppose it depends how many possible states
> there are. It may turn out there are so many it's impossible to store
> the data about each possible move without running out of atoms in the
> universe.
Yes, that's the case; chess is theoretically solvable but not
practically solvable.
> You're right about most moves turning out as dead-ends. A simple chess
> program can play reasonably well with a technique called mini-maxing,
No, no program can play "reasonably well" *merely* by minimaxing.
Both very good and very poor programs use minimaxing; that's not
where the strength lies.
> where for each set of moves it assigns a score to the board, with say
> 1 point for every piece of it's own remaining, -1 point for every
> computer piece, and more or less points for special conditions. By
> following those paths which give it the highest score, and it's
> opponent the lowest, it can play a good game and cut out most of the
No, that sort of scoring would result in atrociously bad play.
> processing. These simple techniques work well enough that an Atari
> 2600 with 128 bytes (sic) of RAM can beat me at Video Chess every time
> I try it.
That program most certainly does not score 1 point for every piece,
and the fact that it can beat you every time tells us nothing at
all without knowing how strong a player you are (the fact that you
think a decent game can come from assigning 1 point to pawns as well
as queens suggests that you aren't very good).
> It may be like noughts and crosses, where for a child it's a
> challenge, but for an adult or any old computer, if you play first
> it's impossible to lose, you can always either win or draw. I wonder
> if it's true, given enough power to calculate every possible move,
> that the white player has an advantage like this. It may turn out
It is unknown whether white can force a win or even a draw with best
play, but there is good reason to think that a draw can be forced.
And certainly tournament play results show that white has a distinct
advantage.
> chess isn't evenly balanced, once it's been solved completely, which
> will probably kill it as a game for computers. They'll have to move on
> to Go.
Completely solving chess is pragmatically impossible. Checkers
is another matter, though.
> How many states are there in chess? Is it possible to work it out
> without playing all of them?
Determining the number of chess positions that can be arrived at by
legal play from the starting position would require enumeration (playing
them out).
> It's not as simple as every piece on
> every position, as many positions will be invalid under the rules. Is
> this itself one of those travelling salesmen problems?
Enumerating every legal chess position, no. Finding the shortest
best-played game probably is.
--
<J Q B>
Sam H
Daniel Baechli wrote:
> The connection to the chess game is now, that there are
> also only finitely many possible games. The possible positions
> in a chess game are finite, rudely bounded by 33^64. Every chess
> chess game can be forced to end, by the draw-rule for repetion
> of the same position, the number of moves is then bounded by
> 3*33^64. So there is a boundary N for the number of all different
> chess games.
Yes, there is, but it is far greater than 3*33^64 ~ 10^98,
because the draw rule applies for repetition of three
*consecutive* identical positions.
What bounds the number of moves is the draw rule for fifty
complete (b+w) moves without moving a pawn or taking. Up to
30 pieces may be taken, and each of the 16 pawns may play 6
times. So a game has a maximum length of 2*[(30+6*16)*50] moves,
which equals 12,600.
Then each player has a maximum of 137 different move choices.
So the number of different games can be bounded by
(137)^12600 ~ 10^27000
Anyway, I agree with you that no brute force algorithm
will ever be able to check that many solutions.
--
www
(o O) With best wishes from Sammy
----oOO-(_)-OOo------------------------------------------
Samuel HOCEVAR - élève ECP promo 2ooo
http://www.chez.com/sammy/ mailto:hoce...@cti.ecp.fr
Sam H
Sam. wrote:
> It may be like noughts and crosses, where for a child it's a
> challenge, but for an adult or any old computer, if you play first
> it's impossible to lose, you can always either win or draw. I wonder
> if it's true, given enough power to calculate every possible move,
> that the white player has an advantage like this.
Like what ? There is no advantage given to the white player
at noughts and crosses: both players can always either win
or draw !!!
Szokoli Gabor
On Mon, 1 Dec 1997, Sam H wrote:
(wise things that I have no right to doubt, and:)
>=20
> Anyway, I agree with you that no brute force algorithm
> will ever be able to check that many solutions.
"It is inpossible to construct flying machines that are heavier then air"
"Noone will ever want to use computers in their homes"=20
"640 kBytes of RAM is more than enough for all posiible uses of=20
PCs forever"
(Wise men sid these, too.)
> --=20
> www
> (o O) With best wishes from Sammy
> ----oOO-(_)-OOo------------------------------------------
> Samuel HOCEVAR - =E9l=E8ve ECP promo 2ooo
> http://www.chez.com/sammy/ mailto:hoce...@cti.ecp.fr
>=20
>=20
Sam H
Szokoli Gabor wrote:
> On Mon, 1 Dec 1997, Sam H wrote:
> (wise things that I have no right to doubt, and:)
> > will ever be able to check that many solutions.
> "It is inpossible to construct flying machines that are heavier then air"
> "Noone will ever want to use computers in their homes"
> "640 kBytes of RAM is more than enough for all posiible uses of
> PCs forever"
> (Wise men sid these, too.)
I'm afraid I still do not agree...
I have no figures within reach, but if you built a
computer with all the atoms of the universe, that could
access data at the frequency of the fastest oscillating
atom in the universe, I do not even need a calculator
to guess that the universe has 10^alot times to disappear
before anyone knows the result.
--
www
(o O) With best wishes from Sammy
----oOO-(_)-OOo------------------------------------------
Samuel HOCEVAR - élève ECP promo 2ooo
http://www.chez.com/sammy/ mailto:hoce...@cti.ecp.fr
Jim Balter
Szokoli Gabor wrote:
>
> On Mon, 1 Dec 1997, Sam H wrote:
> (wise things that I have no right to doubt, and:)
>
> >
> > Anyway, I agree with you that no brute force algorithm
> > will ever be able to check that many solutions.
> "It is inpossible to construct flying machines that are heavier then air"
>
> "Noone will ever want to use computers in their homes"
>
> "640 kBytes of RAM is more than enough for all posiible uses of
> PCs forever"
>
> (Wise men sid these, too.)
That's ad hominem. The question isn't whether people who say things
are wise, but what their reasoning was. The reasoning about brute
force algorithms is based upon an approximate calculation of the number
of positions, whereas the "reasoning" in the other cases is mere
guesswork or argumentum ad ignorantiam. OTOH, A claim that no program
will ever be able to beat every human, or that no one will want to
play chess after machines reach such a point (the premise of this
thread), is the same sort of silly prediction, regardless of who says
it.
--
<J Q B>
Ian Woollard
Sam H wrote:
>
> Szokoli Gabor wrote:
> > On Mon, 1 Dec 1997, Sam H wrote:
> > "It is inpossible to construct flying machines that are heavier then air"
> > "Noone will ever want to use computers in their homes"
> > "640 kBytes of RAM is more than enough for all posiible uses of
> > PCs forever"
> > (Wise men sid these, too.)
>
> I have no figures within reach, but if you built a
> computer with all the atoms of the universe, that could
> access data at the frequency of the fastest oscillating
> atom in the universe, I do not even need a calculator
> to guess that the universe has 10^alot times to disappear
> before anyone knows the result.
Yes, but you are assuming that you have to go through all
or most of them before you come up with a solution. That
isn't, in fact, the case.
There is no theoretical reason why it can't be done.
There are plenty of practical ones.
Look at it this way- the four colour theorem applies to
maps of INFINITE extent. Its been proved. You're
worried about a measly, tiny problem like chess? ;-)
> --
> www
> (o O) With best wishes from Sammy
> ----oOO-(_)-OOo------------------------------------------
> Samuel HOCEVAR - élève ECP promo 2ooo
> http://www.chez.com/sammy/ mailto:hoce...@cti.ecp.fr
--
-Ian (wo...@nojunkmail.nortel.co.uk)
"Everbody loves my Baby, but my Baby loves no one but me..."
-Predestination was |-Of course I'm sane. |-Remove freedom of
doomed from the start|The voices tell me so. |speech for censors, now!
mumford
In article <348301...@nojunkmail.nortel.co.uk>,
Ian Woollard <wo...@nojunkmail.nortel.co.uk> wrote:
>Sam H wrote:
>>
>> Szokoli Gabor wrote:
>> > On Mon, 1 Dec 1997, Sam H wrote:
>> > "It is inpossible to construct flying machines that are heavier then air"
>> > "Noone will ever want to use computers in their homes"
>> > "640 kBytes of RAM is more than enough for all posiible uses of
>> > PCs forever"
>> > (Wise men sid these, too.)
>>
>> I'm afraid I still do not agree...
>> I have no figures within reach, but if you built a
>> computer with all the atoms of the universe, that could
>> access data at the frequency of the fastest oscillating
>> atom in the universe, I do not even need a calculator
>> to guess that the universe has 10^alot times to disappear
>> before anyone knows the result.
>
>Yes, but you are assuming that you have to go through all
>or most of them before you come up with a solution. That
>isn't, in fact, the case.
>
>There is no theoretical reason why it can't be done.
>
>There are plenty of practical ones.
>
>Look at it this way- the four colour theorem applies to
>maps of INFINITE extent. Its been proved. You're
>worried about a measly, tiny problem like chess? ;-)
(apologies if this gets posted twice, netcom is having problems)
I assume the ;-) means you know you're being sarcastic about the four
color theorem... right?
The four color theorem was proved with computers because a person
reduced the problem of maps of INFINITE extent to just ~2000 maps that
contained every combination of borders that could be run across, then
a computer went in and colored them with four colors to prove it could
be done.
I'd say chess is a much larger problem than coloring a 2000 page
coloring book. :)
--
Glenn Lamb - mum...@netcom.com. Finger for my PGP Key.
Email to me must have my address in either the To: or Cc: field. All other
mail will be bounced automatically as spam.
PGPprint = E3 0F DE CC 94 72 D1 1A 2D 2E A9 08 6B A0 CD 82
Sam H
Peter Kerr wrote:
> Sam H <hoce...@cti.ecp.fr> wrote:
> > So the number of different games can be bounded by
> > (137)^12600 ~ 10^27000
> > will ever be able to check that many solutions.
> Now that is called pessimism...
Or realism ? :)
Jim Balter
Bill Taylor wrote:
>
> |> > I believe the mystery of chess is gone but I'd
> |> >like for Kasparov to have another chance to prove me wrong.
>
> just what the "mystery of chess" was in the first place?
Even then, it's hard to imagine that something could stop being
unmysterious merely by virtue of Gary Kasparov winning a chess match.
> You're right about a rematch though. Never since Alekhine, has the craven
> lily-livered cowardice of a winner cheated the public so much out of a
> much longed-for spectacle. Pity there isn't some way to boycot IBM for
> this filthy behaviour.
Unlike Capablanca, Kasparov did not lose a title and is not yet dead.
--
<J Q B>
Russell Easterly
Bill Taylor wrote in message <65vsbh$j1n$1...@cantuc.canterbury.ac.nz>...
>|> > I believe the mystery of chess is gone but I'd
>|> >like for Kasparov to have another chance to prove me wrong.
>
>Perhaps we would all make more sense of your article if you would tell us
>just what the "mystery of chess" was in the first place?
>
>
>You're right about a rematch though. Never since Alekhine, has the craven
>lily-livered cowardice of a winner cheated the public so much out of a
>much longed-for spectacle. Pity there isn't some way to boycot IBM for
>this filthy behaviour.
>
>
>Someone re-named their beast "Deep Yellow". How appropriate!
>
The match was not a championship game.
If you are human and you want to play Kasparov for the World Championship,
then you must first win the Olympiad.
This is several months of grueling play against the best players in the
world.
Also, any decent player leaves a record of his play.
You can sure that Deep Blue had every openning that Kasporov ever used in
its openning book.
Deep Thought had a lot of advantages.
Its scoring system could be tuned against Kasparov's style of play.
I doubt it would have done as well against former world champion Karpov.
Kasparov couldn't even use the experience of the first match.
Humans don't completely rewrite their program between tournaments.
If Kasporov had been given a listing of Deep Thought's openning book,
I bet he would have done a lot better.
A computer can't be World Champion until it has beaten all of the world's
best players.
Kasparov did.
Russell
-The threat is more pwerful than the execution
Peter Kerr
Sam H <hoce...@cti.ecp.fr> wrote:
> So the number of different games can be bounded by
> (137)^12600 ~ 10^27000
>
> Anyway, I agree with you that no brute force algorithm
> will ever be able to check that many solutions.
Now that is called pessimism...
--
Peter Kerr bodger
School of Music chandler
University of Auckland NZ neo-Luddite
mumford
In article <65vjpc$duc$1...@sparky.wolfe.net>,
Russell Easterly <logi...@wolfenet.com> wrote:
>mumford wrote in message ...
>>In article <347FF4...@cco.caltech.edu>,
>>Brian McKeever <mcke...@cco.caltech.edu> wrote:
>>>Rudeboy wrote:
>>>
>>>> >question of who is better, man or machine, remains unresolved. . . .
>>>>
>>>>
>>>> Humbly yours,
>>>> Rudeboy
>>>
>>>There is no question about "who
>>>is better" --- after all, we don't ask who is better, the decathlete or
>his pole.
>>
>>decathalon, the computer *is* playing by itself, with only the user (not
>>necessarily the programmer) informing it of the moves (which is comperable
>>to an assistant to a blind chess player). The computer is not the tool of
>>the opponent in chess, the computer is the opponent.
>>
>
>Computers don't play "by themselves".
Oh?
>Most chess programs have extensive "openning books".
>This represents the combined analysis of thousands of master chess players.
Oh? And players don't have the exact same thing? I'd be willing to bet
real money that you could not find a grandmaster in the world that has not
had in his or her posession at one time a copy of Standard Chess Openings.
(If you haven't seen this book recently, btw, it's about the size of your
average unabridged dictionary... complete with small typeface).
Before you say anything about humans not being able to master the openings
to the same extent as the computer, go to a chess tourney... see how many
players open the game masterfully, but then blow it in midgame or endgame
because they've memorized the opening book but don't know how to actually
play the game once it gets going.
>Computers don't "learn" how to play chess.
>They are told how to do so by a human.
Funny, that's *exactly* how people learn (even if they learn from a book...
someone wrote the book).
>The "scoring" system that a computer uses is very much a human invention.
>Usually, the scoring scheme is a closely guarded secret.
Your point? Human's use a scoring system too, if you didn't notice...
King most valuable, then queen, then rook, then knight/bishop, then pawn
(unless the tactics dictate otherwise). These are the exact same tactics
a human uses. Now think back really hard to when you learned the value
of the pieces... did you really learn it on your own, or were you told?
Be honest.
>Comparing a human player to a chess program
>is like comparing a ditch digger with a shovel
>to a ditch digger with an earth mover.
Keep trying.
Peter Kerr
> > > complete (b+w) moves without moving a pawn or taking. Up to
> > > 30 pieces may be taken, and each of the 16 pawns may play 6
> > > times. So a game has a maximum length of 2*[(30+6*16)*50] moves,
> > > which equals 12,600.
> > > Then each player has a maximum of 137 different move choices.
> > > So the number of different games can be bounded by
> > > (137)^12600 ~ 10^27000
> > > Anyway, I agree with you that no brute force algorithm
> > > will ever be able to check that many solutions.
>
> > Now that is called pessimism...
>
Realistically ;-) a large number of those 10^27000 games will have a very
high probability of not existing. OK I agree, a brute force algorithm is
not needed here. It will take subtlety to prioritise the calculations
based on the likelihood of a certain game actually being interesting
enough for a human to play. And since the game was invented by humans and
is played by humans, who don't think or act like computers, this area is
where all the trouble comes from.
How many legal games are there where -no- piece is taken by either player
before a draw is forced? Such games would be far more dead boring and
futile than king-pawn end games, yet must be a good slice of 10^27000.
Bill Taylor
|> > I believe the mystery of chess is gone but I'd
|> >like for Kasparov to have another chance to prove me wrong.
Perhaps we would all make more sense of your article if you would tell us
just what the "mystery of chess" was in the first place?
You're right about a rematch though. Never since Alekhine, has the craven
lily-livered cowardice of a winner cheated the public so much out of a
much longed-for spectacle. Pity there isn't some way to boycot IBM for
this filthy behaviour.
Someone re-named their beast "Deep Yellow". How appropriate!
-------------------------------------------------------------------------------
Bill Taylor W.Ta...@math.canterbury.ac.nz
-------------------------------------------------------------------------------
It isn't the winning that's important, it's the taking apart!
-------------------------------------------------------------------------------
"Never have so many been cheated of so much by so few!"
Perry Friedman
In article <348298EE...@cti.ecp.fr>, Sam H <hoce...@cti.ecp.fr> wrote:
>Sam. wrote:
>> It may be like noughts and crosses, where for a child it's a
>> challenge, but for an adult or any old computer, if you play first
>> it's impossible to lose, you can always either win or draw. I wonder
>> if it's true, given enough power to calculate every possible move,
>> that the white player has an advantage like this.
>
>Like what ? There is no advantage given to the white player
>at noughts and crosses: both players can always either win
>or draw !!!
Well, the first player CAN force the game in tic-tac-toe. X has "tempo"
and O, for the most part, can only respond defensively. In other words,
O has more chances to screw up and lose. On the first move, X can go anywhere
and it can at worst still force a tie, but if X goes in a corner or middle
to start, O can make a LOSING move on it's very first move. Further, if
X goes in a cornet to begin, O has only *1* move that will not lead to a loss
if X plays properly. Consider the following game:
X| |
-----
| |
-----
| |
O MUST move into the middle or else lose. This is left as an exercise.
Now consider
X| |
-----
|O|
-----
| |X
O MUST go on a side (not a corner) or else they will lose. Again, this is
left as an exercise. After that, the game is forced (all blocks of 2 in a
rows) for both players, with still some chances for O to screw up.
Now, if O is perfect, X can never win either, but there are fewer chances
for X to screw up and O to win... so, I do think X has an advantage...
Perry
PS What this has to do with chess is unknown...but to get back to the topic...
Bobby Fisher once stated that he believed that white has an INSURMOUNTABLE
advantage and should be able to WIN every game. Many chess players believe
that white has about a 1/2 point advantage (1/2 pawn) and most believe
that white should at LEAST be able to draw every game. Note that this is
not a given. It seems logical, but there is no given that the white player
has an advantage... It could in fact be that BLACK has the optimal position,
but this is highly unlikely.... Personally, I believe that Bobby Fisher is
probably correct and that if both players play a perfect game, white
probably still has an unsurmountable advantage and can force a victory.
I have a simple proof of this but it is too long to fit in this PS.
Stephen Robert Norris
In article <mumfordE...@netcom.com>,
mum...@netcom.com (mumford) intoned:
> In article <65vjpc$duc$1...@sparky.wolfe.net>,
> Russell Easterly <logi...@wolfenet.com> wrote:
>>The "scoring" system that a computer uses is very much a human invention.
>>Usually, the scoring scheme is a closely guarded secret.
>
> Your point? Human's use a scoring system too, if you didn't notice...
> King most valuable, then queen, then rook, then knight/bishop, then pawn
> (unless the tactics dictate otherwise). These are the exact same tactics
> a human uses. Now think back really hard to when you learned the value
> of the pieces... did you really learn it on your own, or were you told?
> Be honest.
A better term here would be board-evaluation algorithm. The "scoring"
system computers use generates a single value for a given board, depending
on how "good" that board position is.
Humans don't conciously do such a thing - they seem to know how good a
board is without any calculations.
Now, if there was a neural net that played chess, that would be
interesting.
Stephen
bme...@bruce.cs.monash.edu.au
p.k...@auckland.ac.nz (Peter Kerr) writes:
>Sam H <hoce...@cti.ecp.fr> wrote:
>> Or realism ? :)
>Realistically ;-) a large number of those 10^27000 games will have a very
>high probability of not existing.
Not to mention that the history of a game doesn't matter at any given point,
just the position of pieces on the board and who's move it is. Thus, you
could consider the "problem of chess" as a graph, with nodes being positions
and connections between nodes existing if it is possible to create one
position from another by the move of a single piece.
There are 32 pieces, of which 30 can be either on or off the
board. 2^30=10^9 When all pieces are on the board (and assuming that
each piece can be at each position), you get 64!/48!=10^61 ways of
arranging them. However, the pawns, knights, castles and rooks are
interchangable (in the case of rooks not really, but then, they can't
really be at each possible position, either). That reduces the number
by a factor of 8!*2!*2!*2! for each side, or 10^11.
Obviously, the number of possible ways of arranging _all_ pieces is an
upper bound for the number of ways of arranging _any set_ of pieces, so
we get an upper limit for the number of positions as
2*10^9*10^61/(10^11)=2*10^59.
Actually calculating the number of possible placings individually for
each possible set of pieces brings this number down to 2*10^43. This still
ignores the movement rules (but also promotion of pawns).
Compare this to the "four in a row" game, for which there are 7*10^13
possible positions (assuming a 7x6 grid --- what grid is it usually played
on?), ignoring the only "movement" rule in that game, which is "when one
side has won, the game stops".
The "four in a row" game has been solved a few years back --- It has been
shown that the player making the first move can always win, given the
right strategy.
The difference between these games is a factor of about 10^30, or 2^100.
Even ignoring improvements in algorithms, at the current rate of progress
that's about 150 years. I.e. pretty soon.
Anybody want to make a wager on whether chess is going to be solved in my
lifetime? ;-)
Bernie
--
============================================================================
"It's a magical world, Hobbes ol' buddy...
...let's go exploring"
Calvin's final words, on December 31st, 1995
chris boebel
In article <348301...@nojunkmail.nortel.co.uk>,
wo...@nojunkmail.nortel.co.uk says...
> Look at it this way- the four colour theorem applies to
> maps of INFINITE extent. Its been proved. You're
> worried about a measly, tiny problem like chess? ;-)
Please pardon my ignorance, but what is the four-column theorem?
--
Chris Boebel
Director, Information Systems
The Advantage Co.
Helge Moulding
chris boebel wrote:
> Please pardon my ignorance, but what is the four-column theorem?
The "Four Color Theorem" is a recently proved theorem that to "color"
an infinitely extending plane so that no two adjacent areas are the
same color you need no more than four different colors.
Differently shaped surfaces require different numbers of colors. And
I have no idea if the FCT was proved for a more general case - I
think that the proof is currently restricted to the plane, and maybe
to some related curved surfaces.
--
Helge "top o' the logy to ye!" Moulding
mailto:helge.moulding@unisyscom Just another guy
(insert dot before com to email me) with a weird name
http://www.geocities.com/Athens/1401
Paul Haves
Post the simple proof referred to in the last sentence, please.
Perry Friedman wrote:
--
Yours
Paul Haves
Intercede Ltd.
pha...@intercede.co.uk
http://www.intercede.co.uk/
chris boebel
In article <34841D...@unisys.nicht.spammen.bitte.com>,
helge.m...@unisys.nicht.spammen.bitte.com says...
> The "Four Color Theorem" is a recently proved theorem that to "color"
> an infinitely extending plane so that no two adjacent areas are the
> same color you need no more than four different colors.
Oh jeeze. I read it wrong.
While we're on the subject, though, was a proof ever generated to
substantiate the theorem? I remember reading that they "proved it" by
generating many examples to show that the theorem was correct. If it was
proven, is there a place on the net where more information can be found?
Thanks.
--
Chris Boebel
Director, Information Systems
The Advantage Co.
Jim Balter
chris boebel wrote:
>
> In article <34841D...@unisys.nicht.spammen.bitte.com>,
> helge.m...@unisys.nicht.spammen.bitte.com says...
>
> > The "Four Color Theorem" is a recently proved theorem that to "color"
> > an infinitely extending plane so that no two adjacent areas are the
> > same color you need no more than four different colors.
>
> Oh jeeze. I read it wrong.
>
> While we're on the subject, though, was a proof ever generated to
> substantiate the theorem? I remember reading that they "proved it" by
> generating many examples to show that the theorem was correct.
You apparently misunderstood what you read. It was proved that all
maps can be fit into a finite number of categories. Since that number
was too large to handle by hand, a computer was used to prove that
each of the categories is colorable. Thus no scare quotes are needed;
it really was proved.
> If it was
> proven, is there a place on the net where more information can be found?
Why not learn to learn to locate information on the web/net yourself?
I would have thought that a "Director, Information Systems" would
be familiar with the available sources or know how to become familiar
with them. Just to help you along, a search for "four color theorem"
at www.altavista.digital.com yields 318 hits.
--
<J Q B>
Martin Schlottmann
Sam H wrote:
>
> Daniel Baechli wrote:
> > The connection to the chess game is now, that there are
> > also only finitely many possible games. The possible positions
> > in a chess game are finite, rudely bounded by 33^64. Every chess
> > chess game can be forced to end, by the draw-rule for repetion
> > of the same position, the number of moves is then bounded by
> > 3*33^64. So there is a boundary N for the number of all different
> > chess games.
>
> Yes, there is, but it is far greater than 3*33^64 ~ 10^98,
> because the draw rule applies for repetition of three
> *consecutive* identical positions.
> complete (b+w) moves without moving a pawn or taking. Up to
> times. So a game has a maximum length of 2*[(30+6*16)*50] moves,
<snip>
This is not true, the draw rule for repetition does _not_ demand
consecutive repetition, see the following quotation of the FIDE rules
of 1993:
10.10 The game is drawn, upon a claim by the player having the move,
when
the same position, for the third time:
(a) is about to appear, if he first writes the move on his
scoresheet
and declares to the arbiter his intention of making this
move; or
(b) has just appeared, the same player having the move each time.
The position is considered the same if pieces of the same kind and
colour occupy the same squares, and if all the possible moves of
all
the pieces are the same, including the rights to castle [at some
future time] or to capture a pawn "en passant".
Also the number of moves without moving a pawn or capturing which
forces a draw is not always equal to 50:
10.12 The game is drawn when a player having the move claims a draw and
demonstrates that at least [the last?] 50 consecutive moves have
been
made by each side without the capture of any piece and without the
movement of any pawn. This number of 50 moves can be increased for
certain positions, provided that this increase in number and these
positions have been clearly announced by the organisers before the
event starts.
[The claim then proceeds according to 10.13. The most extreme case
yet known of a position which might take more than 50 moves to win
is
king, rook and bishop against king and two knights, which can run
for
223 moves between captures!]
So, if somebody discovers a winning end game which needs a number n
of moves, it is likely that the rules will be modified to allow n moves
for this position. AFAIK, there is no bound for the number of moves
a winning end game may need.
Therefore, the only clear-cut rule which makes chess a finite game
is the draw rule for three repetitions.
--
Martin Schlottmann <martin_sc...@math.ualberta.ca>
Department of Mathematical Sciences, CAB 583
University of Alberta, Edmonton AB T6G 2G1, Canada
Jim Balter
bme...@bruce.cs.monash.edu.au wrote:
>
> p.k...@auckland.ac.nz (Peter Kerr) writes:
> >Sam H <hoce...@cti.ecp.fr> wrote:
>
> >> Or realism ? :)
>
> >Realistically ;-) a large number of those 10^27000 games will have a very
> >high probability of not existing.
>
> Not to mention that the history of a game doesn't matter at any given point,
> just the position of pieces on the board and who's move it is.
It also matters whether the kings and rooks have moved, and whether
the previous move was a 2 square pawn move, and for the draw rules what
positions have existed and how long it has been since
a capture or a pawn move. But basically you are right about
> Thus, you
> could consider the "problem of chess" as a graph, with nodes being positions
> and connections between nodes existing if it is possible to create one
> position from another by the move of a single piece.
> The difference between these games is a factor of about 10^30, or 2^100.
> Even ignoring improvements in algorithms, at the current rate of progress
> that's about 150 years. I.e. pretty soon.
This is a Malthusian myth. Exponential trends only remain exponential
as long as resources are not a limiting factor.
> Anybody want to make a wager on whether chess is going to be solved in my
> lifetime? ;-)
As long as "solved" means a *proof* that some strategy
yields the best possible outcome, then I would gladly bet against it.
--
<J Q B>
David A. Lamb
Martin,
An upper bound exists, though the least such upper bound may not be
known. Clearly the three repetition rule for a draw places a finite
limit on the length of any Chess game. Because of this, there is an
upper bound on the length on any winning end game. One such upper bound,
for example, is clearly 2*N + 1 where N equals the number of legal
positions in the game. Now... this is not likely to be the least upper
bound, which is a much harder problem, but it is an upper bound.
In fact, given the number of legal positions, N, and the 3 repetition
draw rule: all possible legal chess games can be described as branches
of a subtree of the following tree: Let T be a tree with root being the
starting position of the Chess game, and each node of the tree has N
children (one for each legal Chess position) except nodes on level 2*N+1
which are leaves of the tree (no children).
I intentionally made this tree much larger than necessary, so please
don't bother to point that out to me. Clearly, only a small fraction of
this tree is actually needed, but as I said, there is some appropriate
subtree where all possible legal Chess games are branches through the
subtree. Since the above tree is finite (very very large, but still
finite), Chess itself must be a finite and hence a solvable game.
Unfortunately, the size of the subtree we need makes the solution
unfeasible to compute using known methods in any reasonable time. We
need a shortcut, if we want to solve the game for real.
(Note: I glossed over the computation of N, the number of legal
positions, but that is IMHO a simple combinatorial problem which others
have already addressed.)
David A. Lamb, Ph.D.
Martin Schlottmann wrote:
>
> Also the number of moves without moving a pawn or capturing which
> forces a draw is not always equal to 50:
>
< *snip* >
<here Martin quotes rule 10.12 of Chess, about the 50 move draw, along
with the exception about certain known positions which extend the draw
beyond 50 moves... this citation of the rule is snipped for brevity>
Mark VanTassel
>> PS What this has to do with chess is unknown...but to get back to the topic...
>> Bobby Fisher once stated that he believed that white has an INSURMOUNTABLE
>> advantage and should be able to WIN every game. Many chess players believe
>> that white has about a 1/2 point advantage (1/2 pawn) and most believe
>> that white should at LEAST be able to draw every game. Note that this is
>> not a given. It seems logical, but there is no given that the white player
>> has an advantage... It could in fact be that BLACK has the optimal position,
>> but this is highly unlikely.... Personally, I believe that Bobby Fisher is
>> probably correct and that if both players play a perfect game, white
>> probably still has an unsurmountable advantage and can force a victory.
>> I have a simple proof of this but it is too long to fit in this PS.
When I was in high school, our computer system had a pseudo-game
called "hexapawn", basically chess on a 3x3 board - each player starts
with three pawns on the back row, and pawns move just as in chess.
First one to get to the opponent's back row wins. The interesting
thing is that the first player ("white") always LOSES!
P.S. I may have the rules slightly wrong, so don't kill me if the
game doesn't play out as described.
Jim Balter
Martin Schlottmann wrote:
> AFAIK, there is no bound for the number of moves
> a winning end game may need.
If it isn't bounded, then it isn't a winning endgame (there is no
forced win). In order for it to be a winning endgame, the player
with advantage must be able to reduce the longest path to a checkmate
with each move. And clearly the longest path to a checkmate in a
winnable position is bounded by the total number of reachable positions.
--
<J Q B>
Karl Brace
chris boebel wrote:
> While we're on the subject, though, was a proof
> ever generated to
> substantiate the theorem? I remember reading that
> they "proved it" by
> generating many examples to show that the theorem
> proven, is there a place on the net where more
> information can be found?
Use the web!
I searched http://www.altavista.digital.com
for "the four color theorem" and found gobs of stuff.
One that includes a proof is:
http://www.math.gatech.edu/~thomas/FC/fourcolor.html
This page also includes some nice history of the problem
and other references to work on the problem.
Karl Brace
Brian McKeever
mumford wrote:
>
> In article <347FF4...@cco.caltech.edu>,
> Brian McKeever <mcke...@cco.caltech.edu> wrote:
> >I think this pretty much sums up my feelings on the subject. Computers are tools, and
> >we can do more with them than we can do without them. There is no question about "who
> >is better" --- after all, we don't ask who is better, the decathlete or his pole.
>
> A nice quote that doesn't apply. The pole by itself is not jumping in the
> decathalon, the computer *is* playing by itself, with only the user (not
> necessarily the programmer) informing it of the moves (which is comperable
> to an assistant to a blind chess player). The computer is not the tool of
> the opponent in chess, the computer is the opponent.
Naturally, I disagree. The real opponent is computer+program. By itself, the computer
couldn't play chess, and one of the biggest secrets is the particulars of this
algorithm. In fact, I think I would maintain that it was really this algorithm that
beat Kasparov (though Deep Blue was essential in getting it to run in real time).
Brian McKeever
Bob McQueer
Helge Moulding wrote:
> Differently shaped surfaces require different numbers of colors. And
> I have no idea if the FCT was proved for a more general case - I
> think that the proof is currently restricted to the plane, and maybe
> to some related curved surfaces.
Interesting point - the related theorem for spheres with positive numbers
of handles was proved years ago. I forget the expression for the
neccesary and sufficient number of colors needed for a map drawn on a
sphere with N handles, N > 0 (it yields 7 colors for spheres with 1
handle, ie. the torus), but I presented that proof to a class as an
undergraduate, many years ago (just the sufficiency part). The general
sufficiency result for spheres with a positive number of handles is
called the "Heawood Coloring Theorem", demonstrated by Heawood in the
late 19th century. He also found the error in an accepted early proof of
the 4 color theorem, and until recently the best anybody could prove for
the 0 handles case (the sphere, which is equivalent to the plane) was
that 5 colors was sufficient. And the "necessary" end of the Heawood
result wasn't proved until the 1950's, but still long before the proof of
the FCT.
BTW, 6 colors is necessary and sufficient on a Moebius Strip.
--
| and with these words
Bob McQueer | we parted each feeling
m...@netcom.com | superior to the other and is not that
| feeling after all one of the great
| desiderata of social intercourse
| archy
Jim Balter
Well, Kasparov couldn't play chess without his memory and his
strategies, either, but we don't talk about human+memory or
human+strategies.
A computer, like a human, is just a hunk of matter in a particular
state. One need not add a program to the computer, since it is
already busy instantiating one. "computer+algorithm" is a category
mistake. Of course, a computer could start instantiating another
algorithm, just like Kasparov could start playing a different sort
of chess, or a different game altogether. In fact, part of why
Kasparov lost is because he played a different sort of chess than he
usually does, based upon false assumptions about computers and how
they *can* play, assumptions about as useful with Deep Blue as the
turkey's assumption that, because the pigs and cows get slaughtered
daily but he's been living the life of Riley throughout most of the
year, things are going to stay that way.
--
<J Q B>
Jim Balter
Mark VanTassel wrote:
>
> >> PS What this has to do with chess is unknown...but to get back to the topic...
> >> Bobby Fisher once stated that he believed that white has an INSURMOUNTABLE
> >> advantage and should be able to WIN every game.
Bobby Fisher was also a nut who gave most of his money to Garner Ted
Armstrong. While his chess play was superb and authoritative,
his opinions, even on matters of chess, are not necessarily so.
> Many chess players believe
> >> that white has about a 1/2 point advantage (1/2 pawn) and most believe
> >> that white should at LEAST be able to draw every game.
Yes, but 1/2 pawn is not generally considered enough to win.
> Note that this is
> >> not a given. It seems logical,
Not logical, merely likely. White's moving first creates weaknesses
that are potentially exploitable by Black, but his gains in time,
and space seem more than sufficient in return.
> but there is no given that the white player
> >> has an advantage...
You are equivocating over "advantage". A 1/2 point advantage is not
necessarily equivalent to a game advantage.
> It could in fact be that BLACK has the optimal position,
> >> but this is highly unlikely.... Personally, I believe that Bobby Fisher is
> >> probably correct and that if both players play a perfect game, white
> >> probably still has an unsurmountable advantage and can force a victory.
Why, when 1/2 pawn is not generally enough to win?
> >> I have a simple proof of this but it is too long to fit in this PS.
If you had a proof, it wouldn't be simple.
> When I was in high school, our computer system had a pseudo-game
> called "hexapawn", basically chess on a 3x3 board - each player starts
> with three pawns on the back row, and pawns move just as in chess.
> First one to get to the opponent's back row wins. The interesting
> thing is that the first player ("white") always LOSES!
>
> P.S. I may have the rules slightly wrong, so don't kill me if the
> game doesn't play out as described.
As stated, White can draw, but Black has a win if a player who can't
move loses. In any case, White can win if Black plays badly,
so White doesn't *always* lose.
--
<J Q B>
Martin Schlottmann
David A. Lamb wrote:
>
> Martin,
>
> An upper bound exists, though the least such upper bound may not be
Sure. I only wanted to point out that the 3 reps draw rule
applies not only for _consecutive_ repetitions and, therefore,
suffices for making the game finite. It would _not_ suffice
in the consecutive form.
Martin Schlottmann
You are right, I was a little bit sloppy at this point.
I only wanted to point out that the 3 reps draw rule
applies not only for _consecutive_ repetitions and that the
50 moves draw rule subject to modification if needed.
Guy T. Rice
On Sat, 29 Nov 1997, David B. Greene wrote:
|It has been six months since Deep Blue, the chess playing computer, beat
|Kasparov, the human chess champion, in their second match. Kasparov won
|the first. IBM nixed any possible third match in September but now Deep
|Blue is to be retired as the programmers go on to other projects. I for
|one feel a profound sense of dissappointment as I believe the question of
|who is better, man or machine, remains unresolved.
Really? Do you wonder who is faster, man or machine? Have you heard of
automobiles yet? Do you wonder who is stronger, men or forklifts?
Chess is a problem that can be presented and analyzed in a precise,
mathematical manner. Computers were created to do math better than
people. It was as inevitable that eventually we would build computers
with the power to beat humans at chess as it was that we would eventually
build cars that can go faster than people can run. I'm baffled by how
many people were surprised by this.
Give it a few more years, and you'll probably have a computer on your own
desktop that could easily crush either Deep Blue or Gary Kasparov in a
game of chess. (How many more years it debateable, although I'd be
surprised if it's more than a decade.)
Cars were created to go faster than people, and forklifts were created to
be able to lift more than people. Have we stopped holding weightlifting
competitions and footraces because we've invented forklifts and cars?
Some people worry too much...
Jim Balter
David A. Lamb wrote:
>
> Martin,
>
> An upper bound exists, though the least such upper bound may not be
> limit on the length of any Chess game. Because of this, there is an
> upper bound on the length on any winning end game.
The three repetition rule has no bearing on the length of a *winning*
end game, since if a repetition occurs with *best* play, there is no
forced win. It would be different if one weren't *allowed* to repeat
for the third time; then some drawn endgames might become wins.
But as it is, if the "winner" cannot prevent repetition, then s/he
is only a "drawer".
--
<J Q B>
Brian McKeever
Jim Balter wrote:
>
> Brian McKeever wrote:
> >
> > mumford wrote:
> > >
> > > In article <347FF4...@cco.caltech.edu>,
> > > Brian McKeever <mcke...@cco.caltech.edu> wrote:
> >
> > > >I think this pretty much sums up my feelings on the subject. Computers are tools, and
> > > >we can do more with them than we can do without them. There is no question about "who
> > > >is better" --- after all, we don't ask who is better, the decathlete or his pole.
> > >
> > > A nice quote that doesn't apply. The pole by itself is not jumping in the
> > > decathalon, the computer *is* playing by itself, with only the user (not
> > > necessarily the programmer) informing it of the moves (which is comperable
> > > to an assistant to a blind chess player). The computer is not the tool of
> > > the opponent in chess, the computer is the opponent.
> >
> > Naturally, I disagree. The real opponent is computer+program. By itself, the computer
> > couldn't play chess, and one of the biggest secrets is the particulars of this
> > algorithm. In fact, I think I would maintain that it was really this algorithm that
> > beat Kasparov (though Deep Blue was essential in getting it to run in real time).
>
> Well, Kasparov couldn't play chess without his memory and his
> strategies, either, but we don't talk about human+memory or
> human+strategies.
Technically correct, but I don't think that anyone uses "Garry Kasparov"
to refer to the meat and bones of that particular human. At least when I
use the name, I mean to include his memory, intellect and chess insight.
> A computer, like a human, is just a hunk of matter in a particular
> state. One need not add a program to the computer, since it is
> already busy instantiating one. "computer+algorithm" is a category
> mistake.
Alright, if you want to pick nits, this is true, but I don't think it
invalidates my comment, if one takes the objects to be in the categories
I intended them to be in. But perhaps I should refine a little, since
clearly an algorithm by itself can't beat Kasparov in a game of chess.
In any event, my point was that as far as I know, there is nothing
special about Deep Blue (besides its speed) that makes it a good chess
playing computer, except that it was running this really great algorithm
for determining what move to make next. So it's the algorithm that really
deserves the credit, and the algorithm was (AFAIK) written totally by humans.
QED.
> Of course, a computer could start instantiating another
> algorithm, just like Kasparov could start playing a different sort
> of chess, or a different game altogether. In fact, part of why
> Kasparov lost is because he played a different sort of chess than he
> usually does, based upon false assumptions about computers and how
> they *can* play, assumptions about as useful with Deep Blue as the
> turkey's assumption that, because the pigs and cows get slaughtered
> daily but he's been living the life of Riley throughout most of the
> year, things are going to stay that way.
I'm not sure I understand the relevance.
> --
> <J Q B>
Brian McKeever
bme...@bruce.cs.monash.edu.au
Jim Balter <j...@sandpiper.com> writes:
>bme...@bruce.cs.monash.edu.au wrote:
>> Anybody want to make a wager on whether chess is going to be solved in my
>> lifetime? ;-)
>As long as "solved" means a *proof* that some strategy
>yields the best possible outcome, then I would gladly bet against it.
"Solved" means that either it has been shown that one side (I'd expect it
to be white, but you never know) can win every game, no matter what the
opposing side comes up with, OR that each game will end in a draw unless
at least one side makes a mistake (the tic-tac-toe case).
Bernie
P.S.: Oh, and I couldn't lose. Either I win, or I die before the wager is
due ;-)
Andrew Lewis
Bill Taylor wrote:
> [...]
> You're right about a rematch though. Never since Alekhine, has the craven
> lily-livered cowardice of a winner cheated the public so much out of a
> much longed-for spectacle. Pity there isn't some way to boycot IBM for
> this filthy behaviour.
I have heard that IBM was reacting to criticism of it being both
player and sponsor. Indeed, Kasparov himself said, "The IBM team was
at once a player, organizer, arbitrator and sponsor of the event,
which left me at a terrible disadvantage."
In addition, some reports suggested that IBM, and the Deep Blue
team, were offended by other of his comments. Consider:
After the first match:
"While success against the world champion would have been gratifying,
failure was instructive, too," a spokesperson said.
After the second match:
"I personally assure you that if it starts to play competitive chess,
put it in a fair contest, and I ... will tear it to pieces."
> Someone re-named their beast "Deep Yellow". How appropriate!
Ah, I see you subscribe to this latter idea of sportsmanship.
Andrew
Kirk Is
Russell Harper (rha...@intouchsurvey.com) wrote:
: I remember reading an article about Deep Blue (or an earlier prototype) in
: Scientific American written by the supervisors of the project.
: Unfortunately, I can't remember off the top of my head the month of the
: issue or the title of the article. One important idea stuck however, which
: is that it really isn't valid to compare man vs. machine, but instead to
: compare the capabilities of one person with an exceptional ability vs. many
: people with an average ability. Deep Blue is simply the best tool so far to
: combine all their talents.
Good point, as long as you mean "average ability" in chess only-- those
guys were probably above-par progogrrammers and theorists. Also, the ideal
is a little diminished by the help the team got from that one chess
master.
What if there were some way to *augment* a grand-master's ability via a
machine? To come up with the UI that could let the human's intuition take
advantage of the machine's brute force in a timely way? Would that be
more promising than efforts to round out brute-force techniques with more
human like strategies?
I suspect chess might just be a very grand pattern recognition problem.
SUpposedly, grand-masters see the board in 'chunks' of pieces anyway
--
Kirk Israel - kis...@cs.tufts.edu - http://www.alienbill.com
Here I am; I'm here-- in my mind, and yours, it seems.
Please don't hold me too dear. Some dreams are unrealized.
John Payson
[note: some sci.* groups snipped; posting in a.f.u where this doesn't really
belong but it's the only of the remaining groups I read. If followups are
posted elsewhere, please e-mail them to me as well. Thanks.]
>Perry Friedman wrote:
>> Well, the first player CAN force the game in tic-tac-toe. X has "tempo"
>> and O, for the most part, can only respond defensively.
>> Now, if O is perfect, X can never win either, but there are fewer chances
>> for X to screw up and O to win... so, I do think X has an advantage...
A tic-tac toe game (2 dimensional, 3x3) will always be a draw if played by
competent players; that being the case, it's hard to ascribe any "advantage"
to going first. In the 3x3x3 variation, the game is always a very easy win
for the first player (since the center is involved with 13 different lines,
taking it imparts an overwhelmong advantage). If the first player is for-
bidden to take the center but the second player isn't, the second player will
have an easy win; if neither player is allowed the center, the first player
has an easy win.
>> Many chess players believe
>> that white has about a 1/2 point advantage (1/2 pawn) and most believe
>> that white should at LEAST be able to draw every game. Note that this is
>> not a given. It seems logical, but there is no given that the white player
>> has an advantage... It could in fact be that BLACK has the optimal position,
>> but this is highly unlikely....
>> I have a simple proof of this but it is too long to fit in this PS.
Especially early in the game, both sides have many opportunities for "stall-
ing" moves. While many endgames end in situations where a player is forced
to make a "bad" move (whereas doing nothing--if permissible--would be okay)
the opening and middlegame allow many opportunities for stalling.
Consequently, it would be essentially impossible for Black to have a forced
win; if White's extra move in the opening were a disadvantage, he could play
a "stalling" move when convenient to give Black the tempo. Of course, if
that were bad for Black, then Black could himself play a stalling move and
give White the tempo. If neither side has anything better to do than play
"stalling" moves, then the game is drawn by default. Ergo, unless there is
some very wierd opening line that Black can force before White can play a
"stalling" move (which would--if it existed--almost certainly have been found
by now) there is no way Black can win if White plays optimally.
--
-------------------------------------------------------------------------------
supe...@mcs.com | "Je crois que je ne vais jamais voir... | J\_/L
John Payson | Un animal aussi beau qu'un chat." | ( o o )
Clive D.W. Feather
In article <34841D...@unisys.nicht.spammen.bitte.com>, Helge
Moulding <helge.m...@unisys.nicht.spammen.bitte.com> writes
>The "Four Color Theorem" is a recently proved theorem that to "color"
>an infinitely extending plane so that no two adjacent areas are the
>same color you need no more than four different colors.
>
>I have no idea if the FCT was proved for a more general case - I
>think that the proof is currently restricted to the plane, and maybe
>to some related curved surfaces.
The proof was related to the plane and sphere (which are equivalent).
I understand that there is a simple proof that the maximum number of
colours required is 5 + 2H - T, where:
H is the number of holes in the surface
T is the twist of the surface (0 or 1)
and obvious maximum examples exist for all surfaces except the sphere.
Thus a torus (one hole) needs 7 colours, and a Klein bottle (one hole
and twisted) needs 6; I have seen a 7-coloured torus where all 7 areas
touch the other 6.
--
Clive D.W. Feather | Director of Software Development | Home email:
Tel: +44 181 371 1138 | Demon Internet Ltd. | <cl...@davros.org>
Fax: +44 181 371 1037 | <cl...@demon.net> |
Written on my laptop; please observe the Reply-To address |
Clive D.W. Feather
In article <660qoa$c...@wombat.cs.monash.edu.au>,
bme...@bruce.cs.monash.edu.au writes
>There are 32 pieces, of which 30 can be either on or off the
>board. 2^30=10^9 When all pieces are on the board (and assuming that
>each piece can be at each position), you get 64!/48!=10^61 ways of
>arranging them. However, the pawns, knights, castles and rooks are
>interchangable (in the case of rooks not really, but then, they can't
>really be at each possible position, either). That reduces the number
>by a factor of 8!*2!*2!*2! for each side, or 10^11.
You also need to allow for promotion of pawns, allowing up to 9 queens
or 10 rooks/bishops/knights on each side.
As someone else pointed out, the knowledge of which sides are allowed to
castle and whether en passant is allowed adds another multiple of 16 (or
64 if I've forgotten a case).
Jim Balter
bme...@bruce.cs.monash.edu.au wrote:
>
> Jim Balter <j...@sandpiper.com> writes:
> >bme...@bruce.cs.monash.edu.au wrote:
>
> >> Anybody want to make a wager on whether chess is going to be solved in my
> >> lifetime? ;-)
>
> >As long as "solved" means a *proof* that some strategy
> >yields the best possible outcome, then I would gladly bet against it.
>
> "Solved" means that either it has been shown that one side (I'd expect it
> to be white, but you never know) can win every game, no matter what the
> opposing side comes up with, OR that each game will end in a draw unless
> at least one side makes a mistake (the tic-tac-toe case).
That's what I said.
> Bernie
>
> P.S.: Oh, and I couldn't lose. Either I win, or I die before the wager is
> due ;-)
Since the money would be put in escrow, you would lose it at the
time of the wager, not after your death. In more abstract terms, you
lose if your statement is false, regardless of whether you are alive at
the time that is determined.
--
<J Q B>
Dave Budd
Perry Friedman wrote:
!
>
> Well, the first player CAN force the game in tic-tac-toe.
Any ideas about tictactoe on a 4x4x4x4 board with lines 4 elements long
and a win defined as 'at least 4 lines with a lead of at least 2 lines'?
I wrote a program to play this (and in fact many other variations) and a
very simple algorithm for board evaluation seems to make it rather
better than I am (but maybe I just don't try hard enough).
--
Sent me email but no reply? You may have forgotten to edit out
the antispam part of the address, or perhaps you'd like to try
zlsiida @ fs1.mcc.ac.uk instead. http://www.man.ac.uk/~zlsiida
The UK private poker game & player registries need more data:
http://www.man.ac.uk/~zlsiida/gambling/poker
Dave Seaman
In article <34849E...@math.ualberta.ca>,
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>Jim Balter wrote:
>>
>> Martin Schlottmann wrote:
>>
>> > AFAIK, there is no bound for the number of moves
>> > a winning end game may need.
>>
>> If it isn't bounded, then it isn't a winning endgame (there is no
>> forced win). In order for it to be a winning endgame, the player
>> with advantage must be able to reduce the longest path to a checkmate
>> with each move. And clearly the longest path to a checkmate in a
>> winnable position is bounded by the total number of reachable positions.
>>
>> --
>> <J Q B>
>
>You are right, I was a little bit sloppy at this point.
>I only wanted to point out that the 3 reps draw rule
>applies not only for _consecutive_ repetitions and that the
>50 moves draw rule subject to modification if needed.
Not so fast. Perhaps it's not what you meant, but to my ears, the
statement
There is no bound for the number of moves a winning end game
may need. (1)
is analogous to the statement
There is no bound on the size an integer may have. (2)
where the latter statement, to me, means the same as
The set of integers is unbounded. (3)
Someone may claim that (2) is false, on the grounds that each integer n
is bounded by |n|+1, but that is a counterexample to a different
statement, namely
There exists an integer that is unbounded. (4)
I claim that (2) is a true statement, even though (4) is false. By the
same token, I claim that (1) is at least possibly true, but
There is a winning position that cannot be won in any finite
number of moves. (5)
is false. No contradiction -- they are different statements.
--
Dave Seaman dse...@purdue.edu
++++ stop the execution of Mumia Abu-Jamal ++++
++++ if you agree copy these lines to your sig ++++
++++ see http://www.xs4all.nl/~tank/spg-l/sigaction.htm ++++
Mark VanTassel
On Tue, 02 Dec 1997 20:53:01 GMT, ma...@techie.com__fool.the.robots
(Mark VanTassel) wrote:
>When I was in high school, our computer system had a pseudo-game
>called "hexapawn", basically chess on a 3x3 board - each player starts
>with three pawns on the back row, and pawns move just as in chess.
>First one to get to the opponent's back row wins. The interesting
>thing is that the first player ("white") always LOSES!
>
>P.S. I may have the rules slightly wrong, so don't kill me if the
>game doesn't play out as described.
Several of you have pointed out that the game doesn't work as
described. (I knew if there was a hole, someone would find it!)
Now that I think about it, maybe the winner was the last player to
make a legal move (I don't recall what happens to pawns that reach
the far side - I don't think they become queens - maybe they just
get stuck there).
David A. Lamb
Jim,
I'm not sure I understand you, so if I may, I'll echo what you said in
my own words. If I got your idea wrong, let me know.
You are saying that a winning endgame should never repeat a position
even once, and hence the third repetition rule has no bearing on winning
endgames, but can only affect the length of drawing endgames.
Is this your point? If so, then I agree. In fact the length of a winning
endgame should be bounded above by N+1, where N is the total number of
possible positions in Chess (as used in my earlier post). By extension,
the third repetition rule is too generous, because we could declare a
draw on the first repetition without eliminating any forced wins.
However, I used the third repetition rule as stated in the official
rules of Chess to avoid arguments about why I picked that number. Also,
I never said that I had a least upper bound, I only said I had an upper
bound and that the 'least' part would be a lot harder in practice to
find. Your response gives a lower upper bound than mine, but even yours
is not the 'least' upper bound.
I don't think we disagree, but I wanted to make sure I understood your
point correctly.
David A. Lamb, Ph.D.
R. Serena Wakefield
My spies inform me that, on Wed, 3 Dec 1997 08:28:50 +0000, "Clive
D.W. Feather" <cl...@on-the-train.demon.co.uk>, hiding under the
bedcovers, scribbled in the following in their diary:
>In article <660qoa$c...@wombat.cs.monash.edu.au>,
>bme...@bruce.cs.monash.edu.au writes
>>There are 32 pieces, of which 30 can be either on or off the
>>board. 2^30=10^9 When all pieces are on the board (and assuming that
>>each piece can be at each position), you get 64!/48!=10^61 ways of
>>arranging them. However, the pawns, knights, castles and rooks are
>>interchangable (in the case of rooks not really, but then, they can't
>>really be at each possible position, either). That reduces the number
>>by a factor of 8!*2!*2!*2! for each side, or 10^11.
>You also need to allow for promotion of pawns, allowing up to 9 queens
>or 10 rooks/bishops/knights on each side.
>As someone else pointed out, the knowledge of which sides are allowed to
>castle and whether en passant is allowed adds another multiple of 16 (or
>64 if I've forgotten a case).
Just as a side note, I've found that at least one computer program
DOESN'T take into account extremely strange possibilities. Once, for
fun, I used the "set up board" command to put 8 queens on each side.
Now, I am in no way a skillful chess player. My chess ability
basically stops at terminology and knowing how the horsie movies.
Nevertheless, I was able to mate the computer with ease.
Is this evidence that the computer was doing pattern-searching, and
was as confused by that position as a grandmaster might be? Or was it
just unable to handle the number of different possibilities created by
16 super-mobile pieces?
--
R. Serena Wakefield
rai...@pretensions.gate.net (drop pretensions to e-mail)
Serena's Sanctuary: http://www.gate.net/~raistw
Daniel Baechli
David B.Greene wrote:
> It has been six months since Deep Blue, the chess playing computer, beat
> Kasparov, the human chess champion, in their second match. Kasparov won
> the first. IBM nixed any possible third match in September but now Deep
> Blue is to be retired as the programmers go on to other projects.
> Deep Blue has a massively parallel processing architechture that
> supposedly can evaluate 200 million chess positions per second.
> [...]
I say this on hypothesis, so please don't insist on the
argument, if the hypothesis turns out to be improbable.
From the mentioned above, I conclude that ' Deep Blue'
dedends from special hardware constructions. This hardware
has been made mostly by IBM. Therefore one cannot exclude
the possibility, that a device for including external information
has been included. To make it dramatically, say 'connected to
a room with grandmasters'.
Therefore, many conclusions for answering the question if chess
computers have become better than human chess players, would
not stay on steady ground.
--
I thought this was the point Kasparov had in mind when saying,
that the machine played some moves, wherefore he thinks that a
machine would never play (He might be referring to the old problem
of determing the dis/-advantage of a position), in indirectly saying,
I interpret, the moves has been worked out directly by human minds.
Personally, I'm a great fan of the game of Kasparov, so I tend to
not excluding this possibility. Also because I think, that nowadays,
chess computers have not reached the strength of the great chess-
players, specially after the weak points have been found out.
- - - - - - -
DBaechli
Mike H
In article <6607mq$3h0$1...@sparky.wolfe.net>, Russell Easterly
<logi...@wolfenet.com> writes
>
>Deep Thought had a lot of advantages.
>Its scoring system could be tuned against Kasparov's style of play.
>I doubt it would have done as well against former world champion Karpov.
>Kasparov couldn't even use the experience of the first match.
>Humans don't completely rewrite their program between tournaments.
>If Kasporov had been given a listing of Deep Thought's openning book,
>I bet he would have done a lot better.
>A computer can't be World Champion until it has beaten all of the world's
>best players.
>Kasparov did.
>
>Russell
>-The threat is more pwerful than the execution
>
Hold on a minute !
Wasn't Deep Thought the computer from 'The Hitch Hikers Guide To The
Galaxy' - the one that proved that the meaning of life, the universe and
everything was in fact.......42 ?
If Kasparov played against that, no wonder he lost :)
--
Mike H
"If truth equals concensus and the populace is wrong....
- I am still condemned"
N.B. Remove ".spamless" from address to reply.
John C Green Jr
da...@XOUT.u.washington.edu (David B. Greene) wrote:
>It has been six months since Deep Blue, the chess playing
>computer, beat Kasparov, the human chess champion, in their
>second match. Kasparov won the first. IBM nixed any
>possible third match in September but now Deep Blue is to be
>retired as the programmers go on to other projects
I believe it will be a long time before there is any
improvement on Deep Blue's performance by any computer chess
team. Consider the analogy of the America's Cup.
Years ago America's Cup contenders were amateurs funded by a
millionaire. Now with corporate sponsorship you see $20
Million bankrolls to allow:
* Every person on the team (except the captain) is a trained
athelete paid a salary for over a year as they meld
themselves into a crack team
* Hundreds of thousands of dollars of supercomputer time on
design of the hull shape
* Every conceivable areospace material (carbon fiber,
titanium, etc.) used at ludicrous cost
In '61 Alan Kotok and three other MIT undergraduates wrote a
the first computer program that could play a complete game of
chess (knew about en passant, under promotion, etc.). It was
done with a few hundreds of hours of IBM 709 time, no special
hardware, and no paid programmers.
In '66 Ricky Greenblatt wrote MACHACK IV (Project MAC Hack on
DEC PDP-6), the first program to enter a USCF tournament.
One month later it was the first program to draw a human in a
tournament. One month later it was the first program to beat
a human in a tournament. One month later it won a prize for
the most improved Class D player. Its top rating was about
1500. It was done on a PDP-6 with 256K words of 5
microsecond core, no special hardware, and one paid
programmer.
IBM has raised the bar with corporate sponsorship. They
claim to have spent $90 Million on the project. That
probably includes the kitchen sink and only God knows whose
salaries going all the way back to Hans Berliner.
If you want to have a good chance of bettering Deep Blue's
performance plan on the following:
* Assemble corporate sponsorship of at least $100 Million to
be spent over a ten year period
* Assemble a team of 5 to 10 of the world's best programmers
and 5 to 10 VLSI custom chip designers who are willing to
commit 10 years of their career to the project
* Select a commercial parallel processor from a vendor. Try
to select a vendor that will be committed to high end
parallel processing for at least ten years. Try to select
an architecture that will be available for at least ten
years.
* Buy a large configuration. Perhaps 128 processors and $2.5
Million
* Commission the design of the first generation add on custom
VLSI 'Chess machine' enhancements. It might be a move
generator/function evaluator. 1 to 8 cards to be added to
each of the 128 processors.
* Program for three years. Three years later:
* Buy a large configuration of the next generation CPU.
Install the next generation VLSI or perhaps ULSI add on
Chess machine cards
* Program for three years. Three years later:
* Buy a large configuration of the third generation CPU.
Install the third generation of custom 'Chess machine'
enhancements.
* Program for three years. Three years later:
* Buy a large configuration of the fourth generation CPU.
Install the fourth generation of custom 'Chess machine'
enhancements.
* Tune and debug the program for a few months
* Challenge the world champion to a match
* Tune and debug the program for a few months
* Hold the match
The days of a few Northwestern students using a few hundred
hours of supercomputer time to write a world class program
are gone. There is no hope of anyone using the hottest PC to
develop a world class program. It will take $100 Million of
corporate sponsorship to better Deep Blue's performance in
the near future.
The alternate is to wait perhaps 20 to 40 years until Moore's
Law gives us Deep Blue's performance on a desktop with
standard hardware. Then maybe a year or two of a Ricky
Greenblatt style hacker's time will top its performance.
--
John C Green Jr
Internet Marketing and Business Development
Website Development and Project Management
21483 Old Mine Rd (408)353-1870
Los Gatos CA 95030 JCG...@ix.netcom.com
Jan Bielawski
In article <mumfordE...@netcom.com> mum...@netcom.com (mumford) writes:
[Somebody writes:]
< >This reminds me of a letter to the editor that appeared in the New York Times shortly
< >after Kasparov lost, and which I thoroughly enjoyed at the time. The quote was along
< >the lines of (this may not be verbatim, since I could not track down the source on the
< >NYT web site) "it's been proven only that, in chess, men with computers can beat men
< >without computers. This should come as no surprise, since men with poles can jump
< >higher than men without poles."
< >
< >I think this pretty much sums up my feelings on the subject. Computers are tools, and
< >we can do more with them than we can do without them. There is no question about "who
< >is better" --- after all, we don't ask who is better, the decathlete or his pole.
<
< A nice quote that doesn't apply. The pole by itself is not jumping in the
< decathalon, the computer *is* playing by itself,
The computer is not playing by itself, the encapsulated wisdom of the
programmers is.
< with only the user (not
< necessarily the programmer) informing it of the moves (which is comperable
< to an assistant to a blind chess player). The computer is not the tool of
< the opponent in chess, the computer is the opponent.
Ditto.
--
Jan Bielawski )\._.,--....,'``.
Molecular Simulations, Inc. /, _.. \ _\ ;`._ ,.
San Diego, CA fL `._.-(,_..'--(,_..'`-.;.'
j...@msi.com http://www.msi.com
-disclaimer-
unless stated otherwise, everything in the above message is personal opinion
and nothing in it is an official statement of molecular simulations inc.
Jim Balter
Daniel Baechli wrote:
>
> David B.Greene wrote:
> > It has been six months since Deep Blue, the chess playing computer, beat
> > Kasparov, the human chess champion, in their second match. Kasparov won
> > the first. IBM nixed any possible third match in September but now Deep
> > [...]
> > Deep Blue has a massively parallel processing architechture that
> > supposedly can evaluate 200 million chess positions per second.
> > [...]
>
> I say this on hypothesis, so please don't insist on the
> argument, if the hypothesis turns out to be improbable.
>
> From the mentioned above, I conclude that ' Deep Blue'
> dedends from special hardware constructions. This hardware
> has been made mostly by IBM. Therefore one cannot exclude
> the possibility, that a device for including external information
> has been included.
Nor can we exclude the possibility that Garry Kasparov has a radio
transceiver in his head via which he receives chess instructions from
a distant galaxy.
> To make it dramatically, say 'connected to
> a room with grandmasters'.
Given the time limits of tournament play, a room full of grandmasters
will not generally do better than the best among them. However,
a single grandmaster in a room, able to move the pieces around on
multiple boards and with a computer to check for tactics, could
certainly outplay GK. But then we need to explain why DB made so
many inferior "computer-like" moves against GK.
> Therefore, many conclusions for answering the question if chess
> computers have become better than human chess players, would
> not stay on steady ground.
A careful examination of the games reveals that there is steady ground
for the answer "not yet". DB would have lost the match had GK played
his normal openings, normal style, and had not psychologically
collapsed.
> I thought this was the point Kasparov had in mind when saying,
> that the machine played some moves, wherefore he thinks that a
> machine would never play (He might be referring to the old problem
> of determing the dis/-advantage of a position), in indirectly saying,
> I interpret, the moves has been worked out directly by human minds.
This is argumentum ad ignorantiam. There is no technical reason why
a computer cannot play any particular move. Computers sometimes play
very good moves for not very good reasons, as do humans. And the
advantage to be gained from looking at 200 million *quiescent* positions
per second is hard to fathom. GK's opinions about what chess programs
can do are not particularly authoritative.
> Personally, I'm a great fan of the game of Kasparov, so I tend to
> not excluding this possibility.
Why is Kasparov more respectable if he lost to some human than to
a machine that can evaluate 200 million positions per second?
GK is the strongest human chess player in the world by quite a margin.
Just who are these grandmasters in a room who not only could beat him,
but could do so by making many bizarre moves much more common in
computer play than human play? GK broke down psychologically
during the match and played some chess quite beneath his capabilities.
If you are looking for paranoid fantasies, it would be more plausible to
imagine, as Bobby Fischer used to, that he was being bombarded
with subsonic noise or drugs.
> Also because I think, that nowadays,
> chess computers have not reached the strength of the great chess-
> players, specially after the weak points have been found out.
That is quite circular. If DB can beat great chessplayers regularly,
then it *has* reached their strength. If it still has fatal weak
points, then that is not relevant here, since GK was playing against
what he thought were its weak points based upon past experience,
including previous versions of DB and DT, experience which turned
out not to be entirely applicable to the latest version.
--
<J Q B>
Sam H
R. Serena Wakefield wrote:
> Just as a side note, I've found that at least one computer program
> DOESN'T take into account extremely strange possibilities. Once, for
> fun, I used the "set up board" command to put 8 queens on each side.
>
> was as confused by that position as a grandmaster might be? Or was it
> just unable to handle the number of different possibilities created by
> 16 super-mobile pieces?
I think the computer just knew that for a pawn to promote there
has to be at least one piece taken for each promotion, which is
quite easily proved since opposite pawns are in front of each
other and cannot jump.
However, if the only pieces are eight queens and a king on both
sides, then the computer shouldn't be confused.
--
www
(o O) With best wishes from Sammy
----oOO-(_)-OOo------------------------------------------
Samuel HOCEVAR - élève ECP promo 2ooo
http://www.chez.com/sammy/ mailto:hoce...@cti.ecp.fr
Sam H
Sam H wrote:
> [complete nonsense]
Sorry, I had misread what you posted.
Excuse me and forget my message.
mumford
In article <EKMxr...@msi.com>, Jan Bielawski <j...@iris8.msi.com> wrote:
>In article <mumfordE...@netcom.com> mum...@netcom.com (mumford) writes:
> [Somebody writes:]
>
>< >This reminds me of a letter to the editor that appeared in the New
>York Times shortly
>< >after Kasparov lost, and which I thoroughly enjoyed at the time. The
>quote was along
>< >the lines of (this may not be verbatim, since I could not track down
>the source on the
>< >NYT web site) "it's been proven only that, in chess, men with
>computers can beat men
>< >without computers. This should come as no surprise, since men with
>poles can jump
>< >higher than men without poles."
>< >
>< >I think this pretty much sums up my feelings on the subject.
>Computers are tools, and
>< >we can do more with them than we can do without them. There is no
>question about "who
>< >is better" --- after all, we don't ask who is better, the decathlete
>or his pole.
><
>< A nice quote that doesn't apply. The pole by itself is not jumping in the
>< decathalon, the computer *is* playing by itself,
>
>The computer is not playing by itself, the encapsulated wisdom of the
>programmers is.
>
So the player is not playing either, but instead the encapsulated wisdom
of the people who taught him? I think not.
In this case, you really could not be more wrong. The programmers for deep
thought really are bad chess players, so there is no encapsulated wisdom.
The programmers have given the computer knowledge of the rules (the same
as a human teacher gives a student), a concept of what is important and
what isn't (again as a human teacher gives a student), and then the computer
is left to play on its own, with only the programmer left to enter the moves.
--
Glenn Lamb - mum...@netcom.com. Finger for my PGP Key.
Email to me must have my address in either the To: or Cc: field. All other
mail will be bounced automatically as spam.
PGPprint = E3 0F DE CC 94 72 D1 1A 2D 2E A9 08 6B A0 CD 82
Chris Thompson
[Again, followups set to sci.math]
In article <NScOoLAJ...@on-the-train.demon.co.uk>,
Clive D.W. Feather <cl...@demon.net> wrote:
[...]
>
>The proof was related to the plane and sphere (which are equivalent).
>
>I understand that there is a simple proof that the maximum number of
>colours required is 5 + 2H - T, where:
> H is the number of holes in the surface
> T is the twist of the surface (0 or 1)
>and obvious maximum examples exist for all surfaces except the sphere.
>Thus a torus (one hole) needs 7 colours, and a Klein bottle (one hole
>and twisted) needs 6; I have seen a 7-coloured torus where all 7 areas
>touch the other 6.
I don't know where you go that formula from... What you want is
floor [ (7 + sqrt (1 + 48H + 24T)) / 2 ]
for a sphere with H handles and T cross-caps. Heawood's argument from 1890
shows that this is an upper bound for H+T > 0 [although I think Heawood only
explicitly considered the orientable case T=0], and subsequent work on the
embedding of complete graphs showed that the formula is exact *except* in
the case of the Klein bottle (H=0,T=2), for which 6 colours suffice where
the formula gives 7. Note that three cross-caps == one handle + one cross-cap
topologically.
It so happens that the formula gives 4 for H=T=0. "So happens" because the
known methods of proof for the 4CT bear no particular resemblence to those
for the Heawood Map Colour Theorem.
Chris Thompson
Email: ce...@cam.ac.uk
bme...@bruce.cs.monash.edu.au
Eric Cole <emc...@julian.uwo.ca> writes:
>bme...@bruce.cs.monash.edu.au wrote:
>> OR that each game will end in a draw unlessat least one side makes a mistake
>> (the tic-tac-toe case).
>>
> I think this is true by definition...
It _is_ true for tic-tac-toe. It is _not_ true for four-in-a-row (the player
making the first move can always win, no matter what the other player does).
For chess, the question is still unanswered. I'd suspect checkers to be the
next "major" game to be solved.
Bernie
Chris Thompson
[The newsgroup list is ridiculously long: followups set to sci.math]
In article <34849187...@netcom.com>, Bob McQueer <m...@netcom.com> wrote:
[...]
> The general
>sufficiency result for spheres with a positive number of handles is
>called the "Heawood Coloring Theorem", demonstrated by Heawood in the
>late 19th century. He also found the error in an accepted early proof of
>the 4 color theorem, and until recently the best anybody could prove for
>the 0 handles case (the sphere, which is equivalent to the plane) was
>that 5 colors was sufficient. And the "necessary" end of the Heawood
>result wasn't proved until the 1950's, but still long before the proof of
>the FCT.
Actually the proof was not completed until the winter of 1967-1968. The
chronology in Ringel's book gives the last special case (embedding of K_30
in the surface of appropriate genus) as "solved by Mayer at the the end of
February and independently by Youngs in March 1968". The details of the
various cases were published in a series of papers by Ringel & Youngs
in the Journal of Combinatorial Theory during 1969.
Whether you still want to call that "long before the proof of the 4CT"
no doubt depends on one's perspective.
Maybe you were thinking of the *non*-orientable case, which was finished
off by Ringel in 1954 (although the proofs were subsequently much simplified).
Chris Thompson
Email: ce...@cam.ac.uk
keith green (simctr)
Andrew Lewis (and...@qpsf.edu.au) wrote:
: I have heard that IBM was reacting to criticism of it being both
: player and sponsor. Indeed, Kasparov himself said, "The IBM team was
: at once a player, organizer, arbitrator and sponsor of the event,
: which left me at a terrible disadvantage."
I think this is a legitimate criticism. There were better ways of
going about this. People will pay money to see this sort of
spectacle. No reason some other group couldn't have done it and
turned a small profit for there efforts (or at least broken even).
OTOH, nothing said that GK had to accept the offer. In fact, I'm
kinda surprised that he would considering how GMs are notoriously
meticulous about things being 'just right.'
I remember back during the Fisher-Spassky matches (at least I think
I remember...it's back when I first started playing)....in any case,
I vaguely recall there being a big deal made about the exact size
of the board and the relative sizes of the pieces to that board.
At the time I thought it was pretty kooky, but now it makes sense
to me. (Or maybe I've just become innured to nutty behavior from
GMs.)
: In addition, some reports suggested that IBM, and the Deep Blue
: team, were offended by other of his comments. Consider:
: After the first match:
: "While success against the world champion would have been gratifying,
: failure was instructive, too," a spokesperson said.
Admirable. Really. No sarcasm. More than sportsmanlike. Professional.
Wise, even.
: After the second match:
: "I personally assure you that if it starts to play competitive chess,
: put it in a fair contest, and I ... will tear it to pieces."
I can understand that coming from a person who had been shocked into
awareness of his own fallibility. Doesn't make it right, but it is
understandable. Much more unsportsmanlike was his tendency to go on
and on about this for so long. I doubt GK's initial annoyance had
anything to do with the IBM team's later decisions. But the continual
badgering had to take a toll.
: > Someone re-named their beast "Deep Yellow". How appropriate!
: Ah, I see you subscribe to this latter idea of sportsmanship.
Fair point. However, I think much of the conflict could have been
avoided had some of these problem areas been acknowledged and fixed
prior to the match.
Btw, I don't think that every point that GK made was legitimate, but
they're all points that ought to have been adjudicated by an outside
party. For example, I don't think it's necessary that the IBM team
produce a decision tree showing the reasoning behind each move.
1) That's not necessary for that level of 'experiment,' after all it
was IBM's 'experiment', and not GK's.
2) It's probably not useful in the timeframe.
3) GK was pretty clearly getting at something else. He seemed to feel
that another human GM was working in collusion with the IBM team (and
not just in the preparatory phase, but in the actual play)...there are
better (and easier) ways of verifying fair play in this instance,
although they might be a little human intensive.
k
--
My employers disagree with everything I say, keith green, nan
write, think, believe, feel, do, or plan to do. <kgr...@ida.org>
http://www.geocities.com/Athens/8994/ <thef...@geocities.com>
keith green (simctr)
Kirk Is (kis...@allegro.cs.tufts.edu) wrote:
: What if there were some way to *augment* a grand-master's ability via a
: machine? To come up with the UI that could let the human's intuition take
: advantage of the machine's brute force in a timely way?
And vice versa.
: Would that be
: more promising than efforts to round out brute-force techniques with more
: human like strategies?
Such a technology could be extremely useful and potentially productive
in a broader sense -- not to mention profitable.
: I suspect chess might just be a very grand pattern recognition problem.
No more so than many other grand pattern recognition problems that we
humans face during our sojourn on this whirling, celestial mote.
: SUpposedly, grand-masters see the board in 'chunks' of pieces anyway
That's true, and there's a fair amount of research showing that to
be the case. It's been about 15 years since I read any of it, but
one experiment comes to mind:
They (the experimenters whom I've forgotten) took two sets of people,
one consisting only of chess players, the other of non-chessplayers.
They put a set of chess positions on the board and showed it to the
people from each group for a few seconds (3 or 5 or something like that)
and asked the people to reconstruct the position they saw on a different
board. Guess who did very well (almost perfectly) and guess who did not.
Then they changed the game. Instead of showing them positions from
real games, they showed them 'positions' from random positioning of
the pieces on the board. And the result this time was that chess
players didn't do significantly better (or possibly any better -- again
my memory is being strained) than the non-chessplayers.
Those things that we remember are called 'thunks' and there's a limit
to the number of those thunks we can hold in our short term memory
(what's used here in this experiment). [Clearly everyone's memory
is a little different and some people have very remarkable short term
memories. But that doesn't describe the general population, nor does
it describe the general chessplayer.] I forget how many thunks we
can handle, but it's a surprisingly small number like 3 or 5 or 7.
The good thing is that those thunks can be dedicated to either small
pieces of information (like recalling a single digit, or a single bit
of information) or they they can be used to identify complex patterns
in long term memory (like king side castling with fianchettoed bishop,
assuming, of course, that one already has that pattern in long term
memory).
Karl Brace
keith green (simctr) wrote:
> They (the experimenters whom I've forgotten) took two sets of people,
> one consisting only of chess players, the other of non-chessplayers.
> They put a set of chess positions on the board and showed it to the
> people from each group for a few seconds (3 or 5 or something like that)
> and asked the people to reconstruct the position they saw on a different
> board. Guess who did very well (almost perfectly) and guess who did not.
>
> Then they changed the game. Instead of showing them positions from
> real games, they showed them 'positions' from random positioning of
> the pieces on the board. And the result this time was that chess
> players didn't do significantly better (or possibly any better -- again
> my memory is being strained) than the non-chessplayers.
I too remember reading this research, and I remember the
results exactly as you described, except that I thought
they let the subject study the board for more than 3-5
seconds -- maybe 30 seconds. They guessed that expert
chess players didn't simply remember patterns of pieces
better, but rather they formed in their mind the entire
tactical positions of each side and strategies that each
would use to move forward from that point, and then when
reconstructing the board later they could use those
high-level "facts" to help them reconstruct the details so
that those tactical situations were duplicated.
This explains why the expert players had no advantage
remembering a random board. Since nothing made tactical
sense, they were reduced to remembering positions of
pieces, and had no advantage over non-experts.
It must have been reported in Discover magazine or Science
News, but I don't remember who did the work.
Karl Brace (who knows the rules to chess, but not much more)
Eric Cole
bme...@bruce.cs.monash.edu.au wrote:
> OR that each game will end in a draw unlessat least one side makes a mistake
> (the tic-tac-toe case).
>
I think this is true by definition...
--
Eric Cole http://publish.uwo.ca/~emcole
David Mertz
Jim Balter <j...@sandpiper.com> wrote previously:
|GK is the strongest human chess player in the world by quite a margin.
While I agree with the jist of this post, I must take strong exception
to the above remark. Karpov IS, after all, the current FICA world
champion, not Kasparov. Karpov is also, FWIW, the "winningest" player
in the history of Chess, not Kasparov.
I realize that GK decided to withdraw from FICA play for rather
headstrong reasons. Had he not, he might well have been able to keep
the world championship he once held. But then again, he might well not
have. GK is, no question, ONE of the world's strongest players... but
it is far from clear that he is THE strongest, and certainly not be any
large margin.
|Just who are these grandmasters in a room who not only could beat him,
|but could do so by making many bizarre moves much more common in
|computer play than human play?
This latter is absolutely correct.
Yours, Lulu...
quilty _/_/_/_/_/_/_/ THIS MESSAGE WAS BROUGHT TO YOU BY:_/_/_/_/ v i
@ibm. _/_/ Postmodern Enterprises _/_/ s r
net _/_/ MAKERS OF CHAOS.... _/_/ i u
_/_/_/_/_/ LOOK FOR IT IN A NEIGHBORHOOD NEAR YOU_/_/_/_/_/ g s
mumford
In article </gwh0kKkX...@ibm.net>, David Mertz <qui...@ibm.net> wrote:
>Jim Balter <j...@sandpiper.com> wrote previously:
>|GK is the strongest human chess player in the world by quite a margin.
>
>While I agree with the jist of this post, I must take strong exception
>to the above remark. Karpov IS, after all, the current FICA world
>champion, not Kasparov. Karpov is also, FWIW, the "winningest" player
>in the history of Chess, not Kasparov.
>
>I realize that GK decided to withdraw from FICA play for rather
>headstrong reasons. Had he not, he might well have been able to keep
>the world championship he once held. But then again, he might well not
>have. GK is, no question, ONE of the world's strongest players... but
>it is far from clear that he is THE strongest, and certainly not be any
>large margin.
Just to take the other side in this discussion. Karpov is the FICA world
champ, and may be the winningest player in the history of chess, but he
had *yet* to beat Kasparov in a championship (and how many times did they
meet in the championship? 3? 4?) Karpov is champ because the title fell
to him, not because he earned it.
Jim Balter
David Mertz wrote:
>
> Jim Balter <j...@sandpiper.com> wrote previously:
> |GK is the strongest human chess player in the world by quite a margin.
>
> While I agree with the jist of this post, I must take strong exception
> to the above remark. Karpov IS, after all, the current FICA world
> champion, not Kasparov. Karpov is also, FWIW, the "winningest" player
> in the history of Chess, not Kasparov.
>
> I realize that GK decided to withdraw from FICA play for rather
> headstrong reasons. Had he not, he might well have been able to keep
> the world championship he once held. But then again, he might well not
> have. GK is, no question, ONE of the world's strongest players... but
> it is far from clear that he is THE strongest, and certainly not be any
> large margin.
Elo points matter, titles don't.
--
<J Q B>
Jim Balter
Eric Cole wrote:
>
> bme...@bruce.cs.monash.edu.au wrote:
>
> > OR that each game will end in a draw unlessat least one side makes a mistake
> > (the tic-tac-toe case).
> >
>
> I think this is true by definition...
It's not true generally, and even if it were, it certainly wouldn't
be "by definition". It seems as though you have encountered that
phrase and are applying it by rote rather than understanding it,
sort of like when people say "I'm literally as hungry as a horse".
--
<J Q B>
john baez
In article <MPG.eee0c084...@news.pcom.net>,
chris boebel <z...@theadvantage.com> wrote:
>While we're on the subject, though, was a proof ever generated to
>substantiate the theorem?
Yes, that's why it's a theorem. A theorem, in mathematics,
is a result that has been proved. Before they proved it,
it was called the four color conjecture.
(A counterexample: "Fermat's last theorem" was called a
theorem even before it was proved by Wiles. But this was
probably because Fermat *claimed* to have proved it.)
>I remember reading that they "proved it" by
>generating many examples to show that the theorem was correct.
They really did prove it, no quotes necessary. Apfel and Haken
did it, with the help of a computer (and also their kids):
Every Planar Map is Four Colorable, by Kenneth Appel and Wolfgang Haken,
Contemporary Mathematics (American Mathematical Society), v. 98, 1989.
They did not simply generate lots of examples, which of course would
never suffice to rigorously prove the result. They broke the proof
down into hundreds of cases and used a computer to separately prove
each case.
See also:
The Four-Color Problem: Assault and Conquest, by Thomas L. Saaty and
Paul C. Kainen, McGraw-Hill, 1977, ISBN 0-07-054382-8.
>If it was
>proven, is there a place on the net where more information can be found?
The above references are available in archaic "book" form. Some
information about a more recent proof, also computer-aided, can be
found on the web at:
Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas, A new
proof of the four-colour theorem, Electronic Research Announcements of
the American Mathematical Society 2 (1996), 17-25. Available at
Jim Balter
Kevin D. Quitt wrote:
>
> On Tue, 02 Dec 1997 15:10:10 -0500, "David A. Lamb"
> <la...@cc.tacom.army.mil> wrote:
> Clearly the three repetition rule for a draw places a finite
> >limit on the length of any Chess game.
>
What in the heck is "less of a finite limit"? If it's finite, it's
finite; there is nothing that is "less finite" than finite other than
non-finite.
> If the dynamics of the game are not the same,
> then it's not the same position even if the pieces are all in the same
> place.
What "dynamics"? The only things relevant other than the position
of the pieces are the player on the move, whether the kings and rooks
have moved, and what the last move was if it was a two-square pawn move,
and those are hardly "dynamics", which usually refers to tension
in the position and so on.
For the draw rules there is also the number of moves since a capture
and the entire set of positions reached during the game for the
repetion rule, but those have nothing to do with the position per se
and certainly aren't "dynamics".
It was pointed out me recently when I claimed that chess is
a finite game that it *isn't* by FIDE rules, since a draw has to
be *claimed* by a player, and the players could simply refrain
from such a claim and repeat positions to their hearts' content.
That does indeed make the repetition rule "less of" a finite one
than many people (including me, formerly) think, but it isn't a matter
of "dynamics".
--
<J Q B>
Aaron Boyden
Jim Balter wrote:
> In fact, part of why
> Kasparov lost is because he played a different sort of chess than he
> usually does, based upon false assumptions about computers and how
> they *can* play, assumptions about as useful with Deep Blue as the
> turkey's assumption that, because the pigs and cows get slaughtered
> daily but he's been living the life of Riley throughout most of the
> year, things are going to stay that way.
I understand that, when looking at what moves are actually made, chess experts are quite bad,
and computer experts are quite good, at distinguishing human from computer players. The reason
is apparently that chess experts look for stupid mistakes that only a computer could make, and
they really don't know what those are despite their preconceptions. Indeed, there are probably
no mistakes a computer would make which wouldn't also be made by plenty of humans. Computer
experts, on the other hand, look for stupid mistakes that only a human would make, and being
human, they have a bit of insight into those.
Really, the only mistake a computer can reliably be counted on to make is one to which human
players are if anything far more susceptible in general (the grand masters being the few
exceptions); computers cannot anticipate positional advantages which a present move might
entail far in the future (unless the programmers know about them and build them in; in that
respect, even the grand masters are equally susceptible, as it is their familiarity with a wide
variety of long-term strategies which enables them to counter such strategies). A computer
program I spent some time playing (Fritz 2) inevitably slaughtered me when I played black,
because I have no general strategy for black, except to look for obvious mistakes by my
opponent and exploit them. That strategy, while effective against a wide range of human
opponents, is completely useless against a computer, which never makes obvious mistakes. When
I played white, I could give it as long as it liked to think (within sanity; if I'd given it
weeks to think, maybe that would have been enough, but I do not have such patience) and still
win; the Stonewall variation that I played involved making current moves on the basis of much
later positional advantages it simply could not recognize until it was already too late.
Deep Blue would have sneered at me, of course; I assume the programmers taught it to recognize
the Stonewall variation I use, and taught it how to crush me (as plenty of human players are
able to do). A novel strategy which was equally forward-looking could have created problems
for it, and if anybody could have come up with such strategies, it would be a chess
grandmaster. Kasparov apparently didn't do his homework.
--
---
Aaron Boyden
"It is wrong always, everywhere and for anyone, to believe anything upon
insufficient evidence." W. K. Clifford
bme...@bruce.cs.monash.edu.au
Ke...@Quitt.net (Kevin D. Quitt) writes:
>On 2 Dec 1997 22:17:30 +1100, bme...@bruce.cs.monash.edu.au wrote:
>>Not to mention that the history of a game doesn't matter at any given point,
>>just the position of pieces on the board and who's move it is.
>Sorry to be pedantic, but there are game dynamics that need to be part of
>the state as well: Castling privileges to king- and queen-side for each
>color, information to allow/exclude an en-passant capture based on the
>last move and pawn positions,
True. I suspect, however, that the influence of these is, for all practical
purposes, negligible towards the number of possible positions.
>the number of times this position has occurred, to name some.
This one I disagree with. When all you are interested in is whether there
is a way for either side from the starting position to a winning position,
this doesn't matter --- because if such a way exists, and visits a position
twice, then you can construct another such way that does not do this simply by
removing all moves played between the first and the second time the position
was reached.
Ben Walsh
john baez wrote:
> They did not simply generate lots of examples, which of course would
> never suffice to rigorously prove the result. They broke the proof
> down into hundreds of cases and used a computer to separately prove
> each case.
This doesn't make any sense. They broke the *proof* down into hundreds
of *cases*? Are those examples or not? They proved lots of examples?
ben "huh?" w.
--
------------------------------------------------------------------------
"If you name me a street | ben walsh
Then I'll name you a bar | benw at iona dot com
And I'll walk right through Hell | http://bounce.to/heretic
Just to buy you a jar" -- shane |
Keith Willis
On Mon, 01 Dec 1997 12:01:02 +0100, Sam H <hoce...@cti.ecp.fr> wrote:
>Sam. wrote:
>> It may be like noughts and crosses, where for a child it's a
>> challenge, but for an adult or any old computer, if you play first
>> it's impossible to lose, you can always either win or draw. I wonder
>> if it's true, given enough power to calculate every possible move,
>> that the white player has an advantage like this.
>
>Like what ? There is no advantage given to the white player
>at noughts and crosses: both players can always either win
>or draw !!!
Complete bollocks. Every school-kid knows that assuming no mistakes
on either side, the player who goes first ('white') will always win or
draw in standard 3x3 noughts and crosses. Black _cannot_ win.
----------------------------------------------------------------------
The above message reflects my own views, not those of Hewlett Packard.
When emailing me, please note that there is no '.junk' in my address.
Helge Moulding
Ben Walsh wrote:
> This doesn't make any sense. They broke the *proof* down into hundreds
> of *cases*? Are those examples or not? They proved lots of examples?
Imagine a theorem about all integers. You can prove it for zero. You
can prove it for all negative numbers. You can prove it for all
positive even numbers. And finally, you prove it for all positive odd
numbers. Now you've proved the theorem, by breaking the proof down
into "smaller" cases.
--
Helge "One spoonful at a time." Moulding
mailto:helge.moulding@unisyscom Just another guy
(insert dot before com to email me) with a weird name
http://www.geocities.com/Athens/1401
Karl Brace
I previously posted this reference to interesting
information on the four color theorem, but not to so
many newsgroups. It includes historical information
about previous attempts to prove the theorem, and an
easy to follow description of the most recent proof.
http://www.math.gatech.edu/~thomas/FC/fourcolor.html
I found it by searching at http://www.altavista.digital.com,
advanced search, for title:"that four color theorem"
or title:"that four colour theorem"
Somebody at
http://allserv.rug.ac.be/~pruyss/cgi-bin/4CT.cgi
thinks he has a simpler proof and is asking people to
review his manuscript.
http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html
also has a very complete historical description of past
work in this area.
http://www.math.columbia.edu/~cormac/p4.html also has a
VERY simple proof that is VERY easy to understand, but
contains a flaw (and the author Cormac O' Sullivan
challenges you to find the flaw).
Karl Brace
Leif Magnar Kj|nn|y
In article <3489ff69...@elf.bri.hp.com>,
Keith Willis <keith_wi...@non-hp-unitedkingdom-om1.om.hp.com> wrote:
>
>Complete bollocks. Every school-kid knows that assuming no mistakes
>on either side, the player who goes first ('white') will always win or
>draw in standard 3x3 noughts and crosses. Black _cannot_ win.
More accurately, assuming no mistakes on either side, *every* game will
end in a draw; neither side can win unless the other side makes a mistake.
--
Leif Kj{\o}nn{\o}y | Skyclad: "Life's just a process of delamination,
www.pvv.org/~leifmk| stripping your hopes, dissecting them gently.
Math geek and gamer| I've opened my heart and to my consternation
GURPS, Harn, CORPS | when I peered inside it was small, dark and empty."
Ilias Kastanas
Here are some statements made in this thread... and the reasons
I disagree with them.
"DB did not outplay GK, except for game #2"
"GK had valid grounds for his complaints"
Overall, I think it did, and I think he didn't.
Game #1 was a "dream come true" for GK: White sacrifices material
but gains the advantage, owing to long-term effects... perceptible by a
human, but beyond DB's horizon. Yes, it was GK who outplayed DB here.
In game #2 GK with Black played a standard Ruy line. Theory says
"White is slightly better". But the position is complicated; strong players
often enter such lines against a less strong opponent, fully expecting they
will soon reach equality... and they usually do. DB, though, did not lose
its way; instead, and to GK's dismay, it proceeded to apply a "grandmaster
squeeze" in the best tradition! Moreover, in a position with a seemingly
winning tactical continuation, DB realized it wasn't in fact so, spent extra
time ("panic mode"), and came up with the positional, prophylactic Be4! --
a move that "spooked" GK. DB outplayed him.
In games #3, 4 and 5 GK reached what looked like better endgames.
They are just the kind he is accustomed of winning against humans, due to
his ability to calculate, knowledge, and experience. And he did expect to
win -- at least some of them. But DB drew them all, finding resources GK
did not expect... again and again. For GK, this was failure. The score
said 1/2-1/2, but he was being outplayed.
Thus gradually eroded, GK suffered a clear defeat in game #6. It
is totally irrelevant whether DB's sacrifice was book or not. DB dispatched
GK in nice style.
GK's complaints and accusations, baseless and with a touch of the
paranoid, harmed him apart for embarrassing him. They show lack of under-
standing of computer chess; that is his, and his advisors' fault.
"GK would have won had he played his usual openings and in his
usual style"
I don't think so. I believe GK was right in avoiding sharp Najdorfs
and the like. DB might possibly slip up in combinations involving long-
term features for correct evaluation -- as in game #1. But DB would play
purely tactical ones almost perfectly... and up to 5- or 6-move ones at
least, it sees literally everything. GK found that out when he lost the
first game of the prior match.
Moreover, who is to say what innovations DB might have sprung upon
him in standard book lines? It was not worth taking such a chance.
A strong player is normally able to overcome emotional and other
distractions, and just focus on the position before him. GK is certainly
capable of that; he wouldn't have become World Champion otherwise. It
was a fair match, and GK lost.
Ilias
David Wragg
Ben Walsh <be...@iona.nospam.please.we'reirish.com> writes:
> john baez wrote:
>
> > They did not simply generate lots of examples, which of course would
> > never suffice to rigorously prove the result. They broke the proof
> > down into hundreds of cases and used a computer to separately prove
> > each case.
>
> This doesn't make any sense. They broke the *proof* down into hundreds
> of *cases*? Are those examples or not? They proved lots of examples?
>
The cases were not examples.
They had a theorem, which they proved in the normal by-hand way,
saying that if all of the finite number of cases had a certain
property then any map could be 4 colored (the reasoning being, I seem
to dimly remember, that you could break any map down into a
combination of instances of these cases).
Then they gave the computer the task of checking the cases.
Of course, breaking down a problem into cases, and then solving all
the cases, is a common proof technique. The difference here was that
the number of cases was too large to be checked by humans.
--
David Wragg
Duncan Richer
Ben Walsh wrote:
> john baez wrote:
> > They did not simply generate lots of examples, which of course would
> > never suffice to rigorously prove the result. They broke the proof
> > down into hundreds of cases and used a computer to separately prove
> > each case.
> This doesn't make any sense. They broke the *proof* down into hundreds
> of *cases*? Are those examples or not? They proved lots of examples?
>
Simple, Ben. Just prove that all graphs can be broken up into subgraphs
which fit one of the hundreds of cases, and that gluing them back up
together again won't make the colours run.
Matter of fact - I'm trying to do that now with a bi-coloured K4
problem. It can work, trust me. You just have to know _which_ examples
to choose.
--
Duncan "now foolish enough to put internym in .sig" Richer aka
Duncan C. Richer - aka Slakko the Lost Warner Brother - Now Really Lost!
Queens' College -- PhD, Pure Maths, Graph Theory -- Cambridge University
Andre Engels
Ian Woollard wrote:
>
> Sam H wrote:
> >
> > Szokoli Gabor wrote:
> > > On Mon, 1 Dec 1997, Sam H wrote:
> > > "It is inpossible to construct flying machines that are heavier then air"
> > > "Noone will ever want to use computers in their homes"
> > > "640 kBytes of RAM is more than enough for all posiible uses of
> > > PCs forever"
> > > (Wise men sid these, too.)
> >
> > I'm afraid I still do not agree...
> > I have no figures within reach, but if you built a
> > computer with all the atoms of the universe, that could
> > access data at the frequency of the fastest oscillating
> > atom in the universe, I do not even need a calculator
> > to guess that the universe has 10^alot times to disappear
> > before anyone knows the result.
>
> Yes, but you are assuming that you have to go through all
> or most of them before you come up with a solution. That
> isn't, in fact, the case.
If we go one step further back in the thread, we see that Szokoli
Gabor reacted to:
> Anyway, I agree with you that no brute force algorithm
> will ever be able to check that many solutions.
So he reacted not to 'chess cannot be solved' but 'chess
cannot be solved by brute force, checking each possible
game'. The first statement is doubtful, but the second
seems to be quite reasonable.
--
Andre Engels, eng...@win.tue.nl
http://www.win.tue.nl/cs/fm/engels/index_en.html
There is no limit to human stupidity and the universe,
although I am not sure about the latter. -- Albert Einstein
Andre Engels
Kevin D. Quitt wrote:
>
> On Tue, 02 Dec 1997 15:10:10 -0500, "David A. Lamb"
> <la...@cc.tacom.army.mil> wrote:
> Clearly the three repetition rule for a draw places a finite
> >limit on the length of any Chess game.
>
> then it's not the same position even if the pieces are all in the same
> place.
But the number of factors in the dynamics of the game, and the number
of values each factor can have, are both finite, so there is still
a finite limit, it's just some orders of magnitude larger.
Andre Engels
Keith Willis wrote:
> >Like what ? There is no advantage given to the white player
> >at noughts and crosses: both players can always either win
> >or draw !!!
>
> Complete bollocks. Every school-kid knows that assuming no mistakes
> on either side, the player who goes first ('white') will always win or
> draw in standard 3x3 noughts and crosses. Black _cannot_ win.
Complete bollocks. Every school-kid knows that assuming no mistakes
on either side, the player who goes second ('black') will always win or
draw in standard 3x3 noughts and crosses. White _cannot_ win.