computer chess

128 views
Skip to first unread message

Paul W Celmer

unread,
Sep 9, 1993, 2:44:52 PM9/9/93
to

Question: how will chess players feel when their noble game becomes
dominated by a computer? That is, when a computer can beat the world
champion, will chess lose its appeal, to become a boring solved game
like tick-tac-toe??

t.roger.kiang

unread,
Sep 10, 1993, 8:10:17 AM9/10/93
to
>From: pcf...@unity.ncsu.edu (Paul W Celmer)

This question keeps on coming up again and again, perhaps
a collected response should be included in the FAQ?

But, I would like to counter this question with the following:
A horse can run faster than a human, so, do we stop foot race?
A car runs faster than a horse, so, so we stop horse racing?
An airplane can...

Well, you get the picture, right?

Roger Kiang
t...@mt747.att.com

J R Partington

unread,
Sep 10, 1993, 9:17:52 AM9/10/93
to

My car can play chess better than your horse, so there!
Or have I misunderstood?
JRP


--
| Dr Jonathan R. Partington, Tel: UK: (0532) 335123. Int: +44 532 335123. |
| School of Mathematics, Fax: UK: (0532) 429925. Int: +44 532 429925. |
| University of Leeds, Email: pmt...@leeds.ac.uk (or @uk.ac.leeds) |
| Leeds LS2 9JT, U.K. |

paul.h.nelson

unread,
Sep 10, 1993, 10:04:06 AM9/10/93
to
However, one dimension of the chess computer discussion where the horse/foot
race analogy doesn't hold:

What happens when the computer reveals to us new knowledge about the game?
i.e., it finds a certain opening, mid or end game strategy is always the
best. Do we restrict tournament rules such that the canned openings or
endings can't be used? Swap bishop and knight in the setup?

Granted, I wouldn't expect this to happen anytime soon, but hasn't the
computer revealed to us that certain endgames that were taken as draws or
wins weren't, or that the 50-move rule wasn't sufficient in certain cases?

From the experts, what else have computers TAUGHT us about the game, and
what are they likely to uncover in the near future? (I don't think we
can expect to find THE opening any time soon, but I do see the endgame
becoming more of a closed set all the time).

Paul Nelson
Bell Labs
Naperville ,IL

Jered M. Moses

unread,
Sep 10, 1993, 11:54:09 AM9/10/93
to

In a previous article, tr...@cbnewsm.cb.att.com (t.roger.kiang) says:

>>From: pcf...@unity.ncsu.edu (Paul W Celmer)
>>
>> Question: how will chess players feel when their noble game
>> becomes
>> dominated by a computer? That is, when a computer can beat the
>> world
>> champion, will chess lose its appeal, to become a boring solved
>> game
>> like tick-tac-toe??

>A horse can run faster than a human, so, do we stop foot race?


>A car runs faster than a horse, so, so we stop horse racing?
>An airplane can...
>
>Well, you get the picture, right?

Ummm... honestly? No, I don't.

Here's why: I can't look at a horse and say, "Gosh, that's how *I* should
run! Gee, why didn't I think of that?"

Chess is a (*very* large) finite set (finite space, finite number of
pieces, and finite repetitions of position). Further, there is no random
element in chess. Any series of moves can be repeated each game, legally
(for white and black combined, of course). For any given move of white,
black can always play the same response.

In short, your analogy is trash.
No offense intended.

--Kid Kibbitz
--
jm...@po.cwru.edu | "From childhood's hour I have not been | Quote from
jmoses@heartland. | As others were -- I have not seen | "Alone," a
bradley.edu | As others saw -- I could not bring | poem by
KidKibbitz on ICS | My passions from a common spring." | Edgar Allen Poe

Paul Hsieh

unread,
Sep 11, 1993, 10:25:20 PM9/11/93
to
Paul.H.Nelson writes:

>What happens when the computer reveals to us new knowledge about the game?
>i.e., it finds a certain opening, mid or end game strategy is always the
>best. Do we restrict tournament rules such that the canned openings or
>endings can't be used? Swap bishop and knight in the setup?
>
>Granted, I wouldn't expect this to happen anytime soon, but hasn't the
>computer revealed to us that certain endgames that were taken as draws or
>wins weren't, or that the 50-move rule wasn't sufficient in certain cases?

Indeed. K+Q vs. K+B+B is a win for the Q (who would have thought?) in most
cases (as found by a computer). K+Q vs. K+R is a win however its not nearly
as simple as has been described in some elementary endgame books. And there
was an extremely complex one involving a rook and a bishop versus two bishops
and a knight or something like that which has a winning sequence that might
be as long as 243 moves.

>From the experts, what else have computers TAUGHT us about the game, and
>what are they likely to uncover in the near future? (I don't think we
>can expect to find THE opening any time soon, but I do see the endgame
>becoming more of a closed set all the time).

At the Biel interzonal either Lautier or Polugayevsky (?? can't really
remember) used an opening innovation found by the FRITZII program. I have
played against very strong experts who learnt simply by playing against a
computer program. I personally went over a game between Short and Kramnick
(from the Euwe memorial) using MChess, and according to MChess both players
missed a lot of best moves right following an innovation by Short. Of
course I cannot be 100% sure of MChess' analysis, but playing out some of
its ideas indicate that the machine seemed to understand the position
pretty well. As Short has said himself, computer can be very good aids.
And like it or not they are here and will be (have been) helping shape the
future of chess.

Paul Hsieh

Andy Duplain

unread,
Sep 13, 1993, 4:52:04 AM9/13/93
to
In article <1993Sep10.1...@gps.leeds.ac.uk>,

J R Partington <pmt...@gps.leeds.ac.uk> wrote:
>In article <CD50H...@cbnewsm.cb.att.com> tr...@cbnewsm.cb.att.com (t.roger.kiang) writes:
>>>From: pcf...@unity.ncsu.edu (Paul W Celmer)
>>>
>>> Question: how will chess players feel when their noble game
>>> becomes
>>> dominated by a computer? That is, when a computer can beat the
>>> world
>>> champion, will chess lose its appeal, to become a boring solved
>>> game
>>> like tick-tac-toe??
>>
>>This question keeps on coming up again and again, perhaps
>>a collected response should be included in the FAQ?
>>
>>But, I would like to counter this question with the following:
>>A horse can run faster than a human, so, do we stop foot race?
>>A car runs faster than a horse, so, so we stop horse racing?
>>An airplane can...
>>
>>Well, you get the picture, right?
>>
>
>My car can play chess better than your horse, so there!
>Or have I misunderstood?
>JRP
>
My computer can beat me at chess, but it's no match for me at
kick boxing!

Joke (c) Emo Philips.. not me!


--
Andy Duplain, BT Customer Systems, Brighton, UK. dup...@rtf.bt.co.uk
#define DISCLAIMER My views and opinions are my own, and not my company's

David Myers

unread,
Sep 13, 1993, 1:42:22 PM9/13/93
to

PWC> From: pcf...@unity.ncsu.edu (Paul W Celmer)
PWC> Organization: NCSU


PWC> Question: how will chess players feel when their noble game becomes
PWC> dominated by a computer? That is, when a computer can beat the world
PWC> champion, will chess lose its appeal, to become a boring solved game
PWC> like tick-tac-toe??

Chess computers can beat 99% of us now, and I don't think membership
in the USCF is going down. It just adds another flavor to the whole game.

David.

Tim Cuffel

unread,
Sep 10, 1993, 12:54:33 PM9/10/93
to
In article <CD50H...@cbnewsm.cb.att.com> tr...@cbnewsm.cb.att.com (t.roger.kiang) writes:

And in the interest of full coverage, here is my stock response to this
stock response:

Horse have always been faster than humans. So a fast car is no big deal.
Speed is not an inherent human trait, even in the realm of nature.

But thinking is. Until recently, nothing could come close to the power
of the human mind. We are not used to nonhumans beating us in chess.
Getting beat in our own fields of expertise is something different than
fast cars. Computers may not ruin chess, but you are going to need better
reasons than the one you provided.

--
Tim Cuffel "The religious right scares the hell out of me!"

- Barry Goldwater

Benoit St-Jean

unread,
Sep 14, 1993, 9:33:00 PM9/14/93
to
PWC>Question: how will chess players feel when their noble game becomes
PWC>dominated by a computer? That is, when a computer can beat the world
PWC>champion, will chess lose its appeal, to become a boring solved game
PWC>like tick-tac-toe

You'd better expand the game tree MANY plies deeper to see that day!
Also, you'll need LOTS of memory and CPU to do so.

* SLMR 2.1a * Remember to thank your SYSOP on occasion!

----
XON/XOFF Information Service | (514) 683-9345 (voice)
a division of XON/XOFF Computer Solutions | (514) 685-1152 (fax)
Montreal, Canada | (514) 683-6729 (data) HST D/S
------------------------------------------'

Eric J. Olson

unread,
Sep 15, 1993, 3:22:05 PM9/15/93
to

>Horse have always been faster than humans. So a fast car is no big deal.
>Speed is not an inherent human trait, even in the realm of nature.

>But thinking is. Until recently, nothing could come close to the power
>of the human mind. We are not used to nonhumans beating us in chess.

Why do you equate chess with thinking? Do you also equate tic-tac-toe
with thinking? It's just a game. (It's a game I -like-, but
honestly, aren't you reading a little too much into it?) I can write
a tic-tac-toe program which will never lose to a human--including the
World Tic-Tac-Toe Champion, whoever that may be! Are computers
therefore mentally superior?

>Getting beat in our own fields of expertise is something different than
>fast cars. Computers may not ruin chess, but you are going to need better
>reasons than the one you provided.

Why is chess our field of expertise, but speed isn't? Can't humans do
both? Can't machines to both? We're better at one but not the other
right now: does that mean that we're intrinsically better at it? It
doesn't to me...

Eric Olson <e...@kaja.gi.alaska.edu>

Jered M. Moses

unread,
Sep 15, 1993, 3:00:55 PM9/15/93
to

In a previous article, benoit....@xonxoff.com (Benoit St-Jean) says:

>PWC>Question: how will chess players feel when their noble game becomes
>PWC>dominated by a computer? That is, when a computer can beat the world
>PWC>champion, will chess lose its appeal, to become a boring solved game
>PWC>like tick-tac-toe
>
>You'd better expand the game tree MANY plies deeper to see that day!
>Also, you'll need LOTS of memory and CPU to do so.

I dunno; it doesn't really seem all that unreasonable to me.
We already have a computer program (DT, and now DB) which can beat all but
the very top echilon of players. Parallel techniques are developing all
the time; memory is, I think, no issue at all anymore (even a PC can house
64 megs or more). CPU clocks seem to double every few years. It doesn't
seem at all unwarranted to guess that within 10 years, top computers will
routinely crush top humans.

Will this hurt chess? Dunno!

Roy Eassa

unread,
Sep 15, 1993, 5:42:31 PM9/15/93
to
benoit....@xonxoff.com (Benoit St-Jean) writes:

>PWC>Question: how will chess players feel when their noble game becomes
>PWC>dominated by a computer? That is, when a computer can beat the world
>PWC>champion, will chess lose its appeal, to become a boring solved game
>PWC>like tick-tac-toe

>You'd better expand the game tree MANY plies deeper to see that day!
>Also, you'll need LOTS of memory and CPU to do so.


Right. If every sub-atomic particle in the known universe were a
trillion-MIPS computer, all working together to calculate the game
of chess from move 1, and they started this task 100 trillion years ago,
they would still play the openings worse than a Grandmaster!

andrew brian gross

unread,
Sep 15, 1993, 5:56:12 PM9/15/93
to
In article <CDF0A...@world.std.com> m...@world.std.com (Roy Eassa) writes:
>
>Right. If every sub-atomic particle in the known universe were a
>trillion-MIPS computer, all working together to calculate the game
>of chess from move 1, and they started this task 100 trillion years ago,
>they would still play the openings worse than a Grandmaster!
>

This is a joke, right?

If flatly disbelieve this statement.

On reflection, this *has* to be a joke. I need to become more cynical and
less gullible.

--
"The purpose of writing is to | Real Life: Andrew B. Gross
inflate weak ideas, obscure poor | Internet: spc...@cicero.spc.uchicago.edu
reasoning, and inhibit clarity." | ICS: tbdbitl

GREGORY S GRAHAM

unread,
Sep 15, 1993, 6:23:29 PM9/15/93
to
In article <1993Sep15.2...@midway.uchicago.edu> ab...@midway.uchicago.edu writes:
>In article <CDF0A...@world.std.com> m...@world.std.com (Roy Eassa) writes:
>>
>>Right. If every sub-atomic particle in the known universe were a
>>trillion-MIPS computer, all working together to calculate the game
>>of chess from move 1, and they started this task 100 trillion years ago,
>>they would still play the openings worse than a Grandmaster!
>>
>
>This is a joke, right?
>
>If flatly disbelieve this statement.
>
>On reflection, this *has* to be a joke. I need to become more cynical and
>less gullible.

I doubt Roy has exact calculations to back that up. I think it might be
possible someday to have a fast enough, good enough, computer program that
could fairly consistantly beat a Grandmaster. However, this is a long way from
being able to calculate the perfect move among all possible moves. Some of the
discussion in this thread seems to imply that computers may reduce chess to a
trivial problem like tic-tac-toe. We're talking about analyzing every possible
chess position; it would take an eternity to come up with them all, much less
compare them against each other. I think Roy's illustration would be analogous
to reality in this case.

I believe this would take compu
--

Greg Graham ggr...@utdallas.edu

dwe...@uoft02.utoledo.edu

unread,
Sep 16, 1993, 2:08:04 AM9/16/93
to
In article <CDEts...@well.sf.ca.us>, e...@kaja.gi.alaska.edu (Eric J. Olson) writes:
> In article <CD5DM...@cnsnews.Colorado.EDU> cuf...@spot.Colorado.EDU (Tim Cuffel) writes:
>
>>Horse have always been faster than humans. So a fast car is no big deal.
>>Speed is not an inherent human trait, even in the realm of nature.
>
>>But thinking is. Until recently, nothing could come close to the power
>>of the human mind. We are not used to nonhumans beating us in chess.
>
> Why do you equate chess with thinking? Do you also equate tic-tac-toe
> with thinking? It's just a game. (It's a game I -like-, but
> honestly, aren't you reading a little too much into it?) I can write
> a tic-tac-toe program which will never lose to a human--including the
> World Tic-Tac-Toe Champion, whoever that may be! Are computers
> therefore mentally superior?
>

HEY!!!!!

Wait just ONE minute!!!!!

TIC-TAC-TOE is a *SOLVED* game??????

no!!!!!!!

now my whole life is ruined!!!


don wedding


Renato Ghica

unread,
Sep 16, 1993, 11:10:38 AM9/16/93
to

Here's how it goes:

Assume an average of 20 moves available to each side per position.
Assume all rules are in effect, including the 50 move rule and draw by
repetition.

To generate (not analyze) the first ply (one move for each side) it would
take 400 board positions (20 X 20).

To generate the first 5 ply, it would take 20^5 = 3.2 million positions.

To generate the first 10 ply, it would take 20^10 = 10,240,000,000,000
positions, or 10.24 Trillion (!)

To generate the first 20 ply, 20 ^20 = 10.24 Trillion squared =
1,000,000,000,000,000,000,000,000,000 (approx) = 10.24 Trillion Trillion

The first 40 moves would take

10.24 Trillion X 10.24 Trillion X 10.24 Trillion X 10.24 Trillion
= 1 with 52 zeros
= 11,000 Trillion Trillion Trillion Trillion. (!)

Assume you only nedd to look 45 Moves ahead with all the real rules
in progress :

20 ^45 = 35 Billion Trillion Trillion Trillion Trillon
(my head is spinning).

3.5 followed by 58 zeroes!!!

That is how many positions need to be generated to "solve" the game.

To get an idea how large that number is, do the following:


Take all the stars in the known universe : say 100 Billon.

Give each star 9 planets: 100 Billon + 900 Billion = 1 Trillon.

Assume each planet/star is on the average the size of the earth :
volume = 50,265,480 cubic miles with a 4000 mile radius.

Assume one cubic mile of earth has 150,000,000,000 cubic feet.
Assume one cubic foot has Avogrado's number X 1 Million moles
= 1 X 10^26 * 1^6 = 1^32 atoms /cubic foot.

So, how amny atoms in the know universe ?

100 Billion planetary objects X
1^32 atoms/cubic foot X
150 Billon cubic feet/ planetary object =


1E11* 1E32 * 1,5E11 =
(drum roll, please)

1.5E54 !!!
which is 1.5 followed by 54 zeroes.

Assume an error of magnitude of 1000 (3 orders). The answer becomes
1.5E57
-----------------------------------------------------------
Assume every atom in the know universe was a computer able to
generate/evaluate 1 Trillon Trillon positions per second (like a Sparc, say
- ;-))

then it would take 1 E 57 / 1 E 24 seconds to solve the game

which is 1 E 33 seconds.
which is 3 E 25 years.
which is 3 E 19 Million Years
which is 30,000,000,000,000,000 Billion years !
-------------------------------------------------------------


IBM's DEEP BLUE claims to be able to generate 1 Billion positions/second.
I don't know if this assumes analysis also.

So....
"If every atom in the know universe was a supercomputer a Billon Million
times faster than the fastest computer today, it would take
30,000,000 Billion Billion years to solve the game."

I'm sure I might have made some mis-calculations, but don't
forget the 1000 error factor!

good luck to all believers...


--

[the opinions above are my own!]
"die,die, damned thread!"
"delete *this"

Renato Ghica

unread,
Sep 16, 1993, 11:37:39 AM9/16/93
to
this should really be 270,000 Millon cubic miles.
So divide the final answer by 5400 = 5,000 Billon Billon years ;-)

Kenneth Sloan

unread,
Sep 16, 1993, 2:04:25 PM9/16/93
to
In article <CDGCt...@fig.citib.com> gh...@fig.citib.com (Renato Ghica) writes:
>
>That is how many positions need to be generated to "solve" the game.

This is not necessarily correct. Assuming that you calculations are
correct, the number you gave is an *upper bound* on the number of
postiions which need to be generated to solve the game. You haven't
shown anything about the *lower bound*.
--
Kenneth Sloan Computer and Information Sciences
sl...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170

Dr A. N. Walker

unread,
Sep 16, 1993, 2:02:53 PM9/16/93
to
In article <CDGCt...@fig.citib.com> gh...@fig.citib.com (Renato Ghica) writes:
>Assume you only nedd to look 45 Moves ahead with all the real rules
>in progress :
[...]

> 3.5 followed by 58 zeroes!!!
>That is how many positions need to be generated to "solve" the game.

Umm. Alpha-beta pruning and transposition tables help. You
can probably roughly square-root that number. On the other hand, the
longest games go on for *much* longer than 90 ply, and the bushiest bits
of the tree have a branching factor much larger than 20.

[...]


>which is 30,000,000,000,000,000 Billion years !

sqrt (3.5e58) ~ 2e29, which reduces the time to about an hour and
a half. Initialising all those computers might take some time, though.

--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk

Robert Hyatt

unread,
Sep 16, 1993, 2:40:23 PM9/16/93
to
In article <277op7$e...@usenet.INS.CWRU.Edu> jm...@po.CWRU.Edu (Jered M. Moses) writes:
>
>In a previous article, benoit....@xonxoff.com (Benoit St-Jean) says:
>
>>PWC>Question: how will chess players feel when their noble game becomes
>>PWC>dominated by a computer? That is, when a computer can beat the world
>>PWC>champion, will chess lose its appeal, to become a boring solved game
>>PWC>like tick-tac-toe
>>
>>You'd better expand the game tree MANY plies deeper to see that day!
>>Also, you'll need LOTS of memory and CPU to do so.
>
>I dunno; it doesn't really seem all that unreasonable to me.
>We already have a computer program (DT, and now DB) which can beat all but
>the very top echilon of players. Parallel techniques are developing all
>the time; memory is, I think, no issue at all anymore (even a PC can house
>64 megs or more). CPU clocks seem to double every few years. It doesn't
>seem at all unwarranted to guess that within 10 years, top computers will
>routinely crush top humans.
>
>Will this hurt chess? Dunno!
>
>--Kid Kibbitz
>--

There seems to be an inane assumption that before computers can beat Kasparov
et. al., it is necessary to completely *solve* the game by searching the
entire game tree, and this will not happen (at least in our lifetimes.)
However, beating Kasparov does *not* require such a tree and I firmly
suspect that I will live to see the day when no human can beat the best
computers in a match (I am 45 years old, and, based on current U.S. life
expectancies, this gives us 35+/- 10 years. I believe that the day is
already here for 5sec chess (or at least, very close to being here). 35
years is a llloooonnnnnngggggggg time... the field of computer science is
not that old......


--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !

Robert Hyatt

unread,
Sep 16, 1993, 2:44:59 PM9/16/93
to
>In article <CDF0A...@world.std.com> m...@world.std.com (Roy Eassa) writes:
>>
>>Right. If every sub-atomic particle in the known universe were a
>>trillion-MIPS computer, all working together to calculate the game
>>of chess from move 1, and they started this task 100 trillion years ago,
>>they would still play the openings worse than a Grandmaster!
>>
>
>This is a joke, right?
>
>If flatly disbelieve this statement.
>
>On reflection, this *has* to be a joke. I need to become more cynical and
>less gullible.
>
>
>
>--

It is apparently based on the claim that there are approximately 10^120
(10 to 120th power) possible chess positions and only 10^70 atom in the
universe. Have no idea how many sub-atomic particles there are in an atom,
but I doubt that there are anywhere near 10^40 so that 10^10 positions can be
searched by each one. You can play with these numbers all you want, and
still not prove anything. All of these positions don't have to be searched
to win. More importantly, ALL of these don't have to be searched to play
*perfectly* -- alpha/beta will reduce the total number to 10^60, and there
are *still* lots of things that can be eliminated while playing perfectly.
It's about as useful as discussing whether unix or vms is the best system...

Roy Eassa

unread,
Sep 16, 1993, 5:12:44 PM9/16/93
to
sl...@cis.uab.edu (Kenneth Sloan) writes:

>>That is how many positions need to be generated to "solve" the game.

>This is not necessarily correct. Assuming that you calculations are
>correct, the number you gave is an *upper bound* on the number of
>postiions which need to be generated to solve the game. You haven't
>shown anything about the *lower bound*.


You are, of course, correct. I originally quoted all that silly
sub-atomic particle computer stuff to make a point about how absurd
the one post was that stated that chess would soon be solved. Sure,
the best computers might beat the best humans in a match soon, but
that ain't the same as solving the game mathematically, which will
probably never even come close to happening ever, no matter what advances
occur in computer hardware speed or programming.

Zoltan Fekete

unread,
Sep 16, 1993, 7:26:36 PM9/16/93
to
I think you grossly overestimate both the average available moves and
the need for lookahead, even assuming a totally unintelligable program
(you'd of course use the assumption to drive the estimate
hyper-astronomical ;-(). Try taking the lines like
1. e4, e5 2. Bc4, Nc6 3. Qh5, Nf6 4. Qf7 ++ ;-(
(most of the random "available" moves would lead to even less sensible
play with massive loss of pieces and/or quick checkmate or clearly
decided position pretty soon). Throwing in a few orders of magnitude
error estimate cannot correct the fundamentally overblown calculation
when you inflate most every step of the exponential growth ...

-- Zoli
PS this is of course only IMHO - you may convince me otherwise by
showing just a few thousand variation running 45 moves w/ 20 possible
moves per ply (without repeating positions, of course)

Kosmatos Odisseas

unread,
Sep 16, 1993, 11:14:40 PM9/16/93
to
[lost original poster's name]

: >> Question: how will chess players feel when their noble game


: >> becomes dominated by a computer? That is, when a computer can

: >> beat the world champion, will chess lose its appeal (...) ?

I suspect it will take some time before a computer can consistently
beat the best chess players, but when and if it happens, it might
be that beating a chess computer would be a chess player's ultimate
triumph. Whoever beats the 'thinking machine' (and I'd guess surely
someone will come along eventually) would truly be a "grandmaster" :-)

Also, the way I see it, no chess computer could _always_ beat every
player, to always win, because that would imply that it would have to
have the entire tree of possible moves and resulting possible endings
and to be able to search through it in real time as each of the
opponents moves is made... now how many possible games are there? :-)
(very many, and infinite if it were not for the 50 move rule.)

Anyways.. Imagine many years from now, it is an established fact no human
can beat a chess computer in a tournament. People would still try.

The other aspects ("the noble game") have already been posted..
--
|~~~~|_ Odisseas Kosmatos
| O .| | Math, Informatique
|.o |_| kosm...@jsp.umontreal.ca
|_._o| kosm...@iro.umontreal.ca

Kari U Eloranta

unread,
Sep 17, 1993, 2:19:46 AM9/17/93
to

>

>1.5E54 !!!
>which is 1.5 followed by 54 zeroes.
>
>Assume an error of magnitude of 1000 (3 orders). The answer becomes
>1.5E57
>-----------------------------------------------------------
>Assume every atom in the know universe was a computer able to
>generate/evaluate 1 Trillon Trillon positions per second (like a Sparc, say
>- ;-))
>
>then it would take 1 E 57 / 1 E 24 seconds to solve the game
>
>which is 1 E 33 seconds.
>which is 3 E 25 years.
>which is 3 E 19 Million Years
>which is 30,000,000,000,000,000 Billion years !
>-------------------------------------------------------------
>
>
>IBM's DEEP BLUE claims to be able to generate 1 Billion positions/second.
>I don't know if this assumes analysis also.
>
>So....
>"If every atom in the know universe was a supercomputer a Billon Million
>times faster than the fastest computer today, it would take
>30,000,000 Billion Billion years to solve the game."
>
>I'm sure I might have made some mis-calculations, but don't
>forget the 1000 error factor!
>
>good luck to all believers...
>

There are about 10^80 atoms in the universe, if I remember correctly.
Universumi_terveisin
Kari

"


co...@watson.ibm.com

unread,
Sep 17, 1993, 10:42:31 AM9/17/93
to
In <CDGCt...@fig.citib.com>,
Finally! Someone has sat down and drawn up some figures to show how enormous the possibilities of chess are. Well done Renato!

People have this perception that computers are these amazing black boxes which takes in some input and out pops the answer moments later. Yes computer's are getting faster doubling in speed every year (if we are to beleve's Joy's Law - the MIPS rating of a single processor computer in year X is 2^(X-1984) MIPS ); Chips are getting smaller - more millions of transistors per square centimeter. Eventually the atomic barrier will be reached, transistors will not physically be able to get smaller, the electron


can only go so fast - so CPU clocking speeds will reach a finite barrier also. Therefore a single processor CPU will eventually reach a peak in MIPS (millions of instructions per second) and that will be that.

Then there is multiprocessors - but they are generally only feasible if there is an improvement of factor 10 or more ie. more than one CPU can get the job done 10 times faster then just one CPU. It is very important to note that X number of CPU's working in parallel does not get the job done X times faster than one CPU - it is very much less than linear relationship and is very dependent on the parallel software that the computer is using.
Simplified - one node (a CPU) is the master and the others are the slaves. The slaves are each given a job to do by the master - some jobs will be finished quicker by some slaves, not because they are faster nodes but because they way their calculations turned out they justed finished earlier. Now the master can give these, now idle, nodes some more work to do but there comes a time in parallel software that the results of all nodes must be complete before new work can be issued. This means the nodes that


finish early have to wait while the others catch up before more useful work can be done by the slave nodes.
There are techniques in parallel software, such as load balancing where jobs migrate from busy nodes to idle nodes to improve overall performance - but there is generally a high overhead cost in inter-node communication. I hope the above blurb explains why throwing more processor's into a computer won't necessarily make it significantly faster.

So unless there is a subatomic transistor waiting to be discovered, the speed of a computer will have a finite limit which will not be breached according to the laws of physics.

So basicly what I'm saying is, according to the rough estimates of permutations of chess positions, no computer, for the rest of the existence of the human race, will ever
evalutate them all.
I am not familiar with Alpha-Beta pruning of the permutation game tree, but I am almost certain that you CANNOT disregard a line of play BEFORE checking out all the possible positions that line of play leads to. You cannot disregard a pawn move because a pawn is worth so little and attacks so little - it could eventually provide assistance in a mate. In the end game, certainly there are vast majority of moves which can be disregarded eg. K-R v. K
because a win is assured and there are only 3 pieces which are involved in play. The same cannot be said for a board with 25 or so pieces and a win is not evident.

Also a thing people forget about computers is they are just that - a COMPUTEr. They compute, a glorified calculator if you will! They follow a strict algorithm layed down by the programmer. They have no intelligence and they cannot 'think'. Computer Scientists tell us computers can 'learn' from mistakes dropping buzz words like A.I. (artificial intelligence) and Neural Networks - but if a neural network is suppose to be modelled on the brain and the way the brain holds information then looking at todays ef


forts they are a pretty crude and limited representation and certainly have a long long way to go.
The only way a computer can be programmed to play chess is for it to try all or most permutations of a given position - using sensible, but not infalable (sp?), rules to disregard certain avenues of play.
Openings have been developed over hundreds of years by Grand Masters - if you left the best of the best computers to determine an opening move by itself, it would fail miserably on it's own. If you have played computer chess, you will probably have noticed that it's first 8 or 9 moves are made very rapidly when following a standard opening, before reaching the middle game. However if you make some alternative move which is not part of the variations of the particular opening you started with, you will noti


ce the computer will immediately stop to 'think'. This is because the computer program has included with it a standard database of openings which it parrot's off when the human player matches the moves of the opening as well. It has no understanding of openings it just merely plays the moves according to it's database. It would have to look at least 20 moves ahead to come up with an effective opening on it's own - which is just not feasible.
Generally I have found computer chess to be very strong in the middle game (which is probably the most part of the game) - the opening is covered by it's database - but the endgame I have found to be very poor.
I think the reason for this is that being able to check out 5 or moves ahead is easy for a computer and not too time consuming, in the middle game, but for a human there are generally too many pieces and positions to remember that his analysed permutations are more limited.
Openings, as I have said, require more foresight than time permits - so why not use the database - most human players do anyway!
As for the ending - it is very easy for a human to think 20 moves a head when trying to make with a K-R v. K as the operation is so repeditive but I have actually seen a computer on level 4 (which gives a good middle) out of 8 actually draw with a K-Q v. K ending!!!
This of course is the programmers fault for leaving the computer to 4 or 5 moves ahead thinking and not providing simple rules for restricting the opponents king to fewer and fewer ranks of the board until mate is achieved.
Basically, Computer Chess is only as good as the programmer makes it regardless of the fact that it is running on a Cray or a ZX81! (Okay maybe memory problem might be incountered with the ZX81!). A scoring system has to be devised to evaluate how good a position is and if it is better than the current one. Obviously material advantage is an easy way of evaluating a position, board control also (ie. how many squares are controlled by one side and how well are these squares controlled). When you move into s


tuff like pawn structures and the value of open files and diagonals the scoring gets more abstract. You get into the problem of determining when is a material sacrifice merited for positional gain - I have rarely seen a computer sacrifice material except for a short term plan, where it knows it will regain its sacrifice. Also there is the dialema of certain parts of the game changing in importance eg. a knight might be infinitely more useful in an endgame for attacking pawns compared with a bishop of the w


rong coloured square.

I haven't tried to write a computer algorithm for playing chess but I have certainly given it some thought and all I can say is there is certainly no right way of doing - except of course evaluating all permutations which as we have seen, won't be done in our lifetime. I know I may have put down Computer Chess in this article, but that is not to say I don't like them, in fact they are quite challenging sometimes (plus they allow you to take back moves!). But I do realise they limitations but I also underst


and their importance as a teaching aid even for Grand Masters. So don't throw out your ChessMaster computer yet but don't give up faith in the human chess brain - not for a couple of billion years anyway.

Just my $0.02 worth. Regards,
Colm.

Opinions my own and not IBM's. Blah blah blah etc. etc.

andrew brian gross

unread,
Sep 17, 1993, 12:28:26 PM9/17/93
to
As I said to Roy in e-mail, my disbelief of his initial statement sprang from
a differing set of assumptions: Roy assumed that Chess would need to be
completely "solved" in order for a computer to play the openings better than
a grandmaster, while I do not believe that all possible lines of play need to
be explored in order for a computer to play better than a grandmaster.

I will stick by my statement. During my lifetime, computers will soundly
trounce the best human players, and will (if desired) play "out of book"
openings that are improvements on existing lines. Given the absurd
scenario originally presented (every atom in the universe being a supercomputer,
etc.), it is absolutely, completely, utterly absurd to assume that a human
grandmaster would outplay, in any way, in any phase of the game, the computer.

Obsessing about the number of theoretical positions that can result from
a game of chess is a Red Herring. All that matters is how well the computer
can find a *winning* line of play. Chess is not so complex that this cannot
be done, even by existing computers; let alone given the astronomically,
unimaginabally large amount of computing power outlined in the original post.

Robert Hyatt

unread,
Sep 17, 1993, 1:48:29 PM9/17/93
to
In article <CDI66...@yktnews.watson.ibm.com> co...@watson.ibm.com writes:
>
>Finally! Someone has sat down and drawn up some figures to show how enormous the possibilities of chess are. Well done Renato!
>
>People have this perception that computers are these amazing black boxes which takes in some input and out pops the answer moments later. Yes computer's are getting faster doubling in speed every year (if we are to beleve's Joy's Law - the MIPS rating of
>a single processor computer in year X is 2^(X-1984) MIPS ); Chips are getting smaller - more millions of transistors per square centimeter. Eventually the atomic barrier will be reached, transistors will not physically be able to get smaller, the ele
>
>can only go so fast - so CPU clocking speeds will reach a finite barrier also. Therefore a single processor CPU will eventually reach a peak in MIPS (millions of instructions per second) and that will be that.

-------------------------------------------------------------------------------
Lets start here. I doubt that "that will be that" UNLESS you assume that we
are going to be transistor based forever. 30 years ago, we were hearing the
same thing about the vacuum tube. I don't like arguments that "assume" some
unknown boundary exists. 10 years ago we were hearing that the "master"
chess level was a boundary to all computer programs and that significant
research and hardware would be needed to pass it. It is now regularly passed
by $200 machines. Find some other way to pose this argument....
-------------------------------------------------------------------------------


>
>Then there is multiprocessors - but they are generally only feasible if there is an improvement of factor 10 or more ie. more than one CPU can get the job done 10 times faster then just one CPU. It is very important to note that X number of CPU's working
>in parallel does not get the job done X times faster than one CPU - it is very much less than linear relationship and is very dependent on the parallel software that the computer is using.
>Simplified - one node (a CPU) is the master and the others are the slaves. The slaves are each given a job to do by the master - some jobs will be finished quicker by some slaves, not because they are faster nodes but because they way their calculations t
>urned out they justed finished earlier. Now the master can give these, now idle, nodes some more work to do but there comes a time in parallel software that the results of all nodes must be complete before new work can be issued. This means the nodes
>

>finish early have to wait while the others catch up before more useful work can be done by the slave nodes.
>There are techniques in parallel software, such as load balancing where jobs migrate from busy nodes to idle nodes to improve overall performance - but there is generally a high overhead cost in inter-node communication. I hope the above blurb explains wh
>y throwing more processor's into a computer won't necessarily make it significantly faster.

-------------------------------------------------------------------------------
Hsu must really like this argument! :^) Of course, Deep Blue depends on this
very thing. I hope you aren't shattering our dreams of how well it will play?
-------------------------------------------------------------------------------


>
>So unless there is a subatomic transistor waiting to be discovered, the speed of a computer will have a finite limit which will not be breached according to the laws of physics.
>
>So basicly what I'm saying is, according to the rough estimates of permutations of chess positions, no computer, for the rest of the existence of the human race, will ever
>evalutate them all.
>I am not familiar with Alpha-Beta pruning of the permutation game tree, but I am almost certain that you CANNOT disregard a line of play BEFORE checking out all the possible positions that line of play leads to. You cannot disregard a pawn move because a
>pawn is worth so little and attacks so little - it could eventually provide assistance in a mate. In the end game, certainly there are vast majority of moves which can be disregarded eg. K-R v. K
>because a win is assured and there are only 3 pieces which are involved in play. The same cannot be said for a board with 25 or so pieces and a win is not evident.

-------------------------------------------------------------------------------
Again, alpha/beta does not prune ANYTHING before-the-fact. However, after
"trying a move" and completely analyzing the first response, we know a lot
about this move without looking at the other responses. For example, it loses
a pawn (at least). This might be enough to discard the remainder of the choices
since a better move has already been found that doesn't lose a pawn. In any
case it simply takes the 10^120 or 10^62 or whatever bound you want to put on
the number of "real" chess positions and reduces it to the square root of the
original number. This could therefore be either 10^60 or 10^32, either of
which are large enough to defy search with any forseeable machine. However,
in a few years (or centuries or millenia or ...) who knows?
-------------------------------------------------------------------------------

>
>Also a thing people forget about computers is they are just that - a COMPUTEr. They compute, a glorified calculator if you will! They follow a strict algorithm layed down by the programmer. They have no intelligence and they cannot 'think'. Computer Scien
>tists tell us computers can 'learn' from mistakes dropping buzz words like A.I. (artificial intelligence) and Neural Networks - but if a neural network is suppose to be modelled on the brain and the way the brain holds information then looking at tod
>

>forts they are a pretty crude and limited representation and certainly have a long long way to go.
>The only way a computer can be programmed to play chess is for it to try all or most permutations of a given position - using sensible, but not infalable (sp?), rules to disregard certain avenues of play.

-------------------------------------------------------------------------------
So how is this different from humans? I certainly use "fallible" knowledge to
help me play, and I try to improve this knowledge when I get crushed as a
result. I don't buy this argument at all. First, I don't believe that
computers have to emulate a human to play chess. They currently don't (emulate
humans) yet they do (play good chess.) They ARE getting better every year
and there is no reason to suspect that this will stop. Very old technology
(Fidelity Mach III running on a 16mhz 68000) produces master-level play. What
happens when Hsu (and us among others) finally stops working on faster hardware
with corresponding deeper searches and begins to devote time to better utilizing
the hardware currently available. I can't even calculate how much faster our
Cray C90 is than the 68000, but I know that the difference between speeds is
wider than the difference between playing skills. There is still plenty of
"gas" in current technology and I don't believe that we still need orders of
magnitude speedups to become unbeatable. It is certainly the "easiest" way
to get better.... I would love to plug something in my head that would
enable me to search 1 move deeper, but I can't do this. Yet, I can get better
and better. If *I* don't have an asymptote on potential, why do we assume
that current computer hardware does? At least, I suspect that the upper
limit on playing skill for a C90 has NOT been reached yet. Cray keeps
producing faster and faster machines, and we are too often happy to take the
"lazy" way out to get better.... namely, search deeper. We (and others) have
also begun to take a different angle of attack on this problem, improving the
evaluation heuristics and search extension heuristics to make these programs
get better, even in the odd-numbered years where technology "stands still"
for a year.
-------------------------------------------------------------------------------

t


>Openings have been developed over hundreds of years by Grand Masters - if you left the best of the best computers to determine an opening move by itself, it would fail miserably on it's own. If you have played computer chess, you will probably have notice
>d that it's first 8 or 9 moves are made very rapidly when following a standard opening, before reaching the middle game. However if you make some alternative move which is not part of the variations of the particular opening you started with, you wil
>

>ce the computer will immediately stop to 'think'. This is because the computer program has included with it a standard database of openings which it parrot's off when the human player matches the moves of the opening as well. It has no understanding of op
>enings it just merely plays the moves according to it's database. It would have to look at least 20 moves ahead to come up with an effective opening on it's own - which is just not feasible.

-------------------------------------------------------------------------------
Not particularly true. You can play C-B without it's book, and it will play
reasonable chess nonetheless. As white, it plays e4, and if you play e5,
it will follow known analysis Ruy Lopez "on it's on" for many moves. Good
programs HAVE to do this to avoid foolish things that happen after e4,h6 or
whatever. You probably don't give the "good" programs near enough credit
here, and I suspect that that are many of us that would be willing to play
you without the opening book. The only thing we "lose" is the very quick
moves which save up time to be used later in the game.
-------------------------------------------------------------------------------

>Generally I have found computer chess to be very strong in the middle game (which is probably the most part of the game) - the opening is covered by it's database - but the endgame I have found to be very poor.
>I think the reason for this is that being able to check out 5 or moves ahead is easy for a computer and not too time consuming, in the middle game, but for a human there are generally too many pieces and positions to remember that his analysed permutation
>s are more limited.

-------------------------------------------------------------------------------
I suspect that you haven't played any *top* computer program either. Most GM's
will tell you that a deep thought, Cray Blitz, HiTech, and others play excellent
endgames. You simply have to look at recent computer chess and computer/human
chess games to find some truly excellent endgames. Your statement was right
on 10 years ago, where you could lose a pawn or two, but trade into an endgame
where the program would not understand a passed pawn and blunder. Nowadays,
I suspect that programs understand passed pawns better than most humans when
the endgame is reached. I watched Ivanov play Cray Blitz a couple of years
ago and let Cray Blitz force a trade down into an endgame where Ivanov thought
he would win and C-B thought it would win. Turns out that Igor had "miscounted"
by one and C-B was right.
-------------------------------------------------------------------------------

>Openings, as I have said, require more foresight than time permits - so why not use the database - most human players do anyway!

-------------------------------------------------------------------------------
As I said, opening books save us TIME, but don't necessarily make programs
play better. In fact, the programs find so many errors in known book analysis
that we feel MUCH BETTER after we "exit" the book and get a couple of ten
ply searches done to make sure that we haven't fallen for some incorrect
book analysis. If it wasn't for the TIME factor, I would never play C-B
in a meaningful game with the book on.
-------------------------------------------------------------------------------

>As for the ending - it is very easy for a human to think 20 moves a head when trying to make with a K-R v. K as the operation is so repeditive but I have actually seen a computer on level 4 (which gives a good middle) out of 8 actually draw with a K-Q v.
>K ending!!!

-------------------------------------------------------------------------------
Again, not any of the GOOD programs. Most can mate you with B+N vs k in a
heartbeat. Don't lump us in with Saitek and the rest! We've come a long
way baby!
-------------------------------------------------------------------------------

>This of course is the programmers fault for leaving the computer to 4 or 5 moves ahead thinking and not providing simple rules for restricting the opponents king to fewer and fewer ranks of the board until mate is achieved.
>Basically, Computer Chess is only as good as the programmer makes it regardless of the fact that it is running on a Cray or a ZX81! (Okay maybe memory problem might be incountered with the ZX81!). A scoring system has to be devised to evaluate how good a
>position is and if it is better than the current one. Obviously material advantage is an easy way of evaluating a position, board control also (ie. how many squares are controlled by one side and how well are these squares controlled). When you move
>

>tuff like pawn structures and the value of open files and diagonals the scoring gets more abstract. You get into the problem of determining when is a material sacrifice merited for positional gain - I have rarely seen a computer sacrifice material except
>for a short term plan, where it knows it will regain its sacrifice. Also there is the dialema of certain parts of the game changing in importance eg. a knight might be infinitely more useful in an endgame for attacking pawns compared with a bishop of
>

>rong coloured square.

-------------------------------------------------------------------------------
More science fiction. I am the primary author of Cray Blitz. It's rating has
been estimated at around 2600 USCF, while it's speed chess performance rating
over the past 5 years is around 2780. I *am not* a 2600 player. I *am not*
a 2200 player. I *do* understand the game, and can discuss a position
intelligently with a GM and suggest weaknesses in pawn structure and the
like, and I have put as much as I can into Cray Blitz, however, *I cannot*
search 10 plies plus lots of extensions in 3 minutes, so C-B easily crushes
me whenever I get reckless enough to play it. This is why I bought a Mach III
a couple of years ago.... I enjoy watching C-B destroy it as we "test" new
ideas, and don't get angered as I lose my queen to a 16 move trap. There are
lots of examples of poor chess players producing excellent chess programs
and there are lots of excellent chess players working on chess programs as
well (Larry Kaufman comes to mind at once). Just because you play me and win
should not lull you into a sense of security where you play C-B and also expect
to win. Better have a sack handy when it hands you your head! (we used to
keep the heads, but my basement is now full so we return 'em... :^) )
-------------------------------------------------------------------------------

>
>I haven't tried to write a computer algorithm for playing chess but I have certainly given it some thought and all I can say is there is certainly no right way of doing - except of course evaluating all permutations which as we have seen, won't be done in
> our lifetime. I know I may have put down Computer Chess in this article, but that is not to say I don't like them, in fact they are quite challenging sometimes (plus they allow you to take back moves!). But I do realise they limitations but I also u
>

>and their importance as a teaching aid even for Grand Masters. So don't throw out your ChessMaster computer yet but don't give up faith in the human chess brain - not for a couple of billion years anyway.
>
>Just my $0.02 worth. Regards,

Bob Hyatt

Erik Robert Wilson

unread,
Sep 17, 1993, 5:13:38 PM9/17/93
to
For all the big numbers [deleted !] that have been posted here, you folks
have not been thinking big enough. You simply do not have enough faith in
*HUMANS*. That's right, you don't have enough faith in humans, the humans
who design, build and program computers. When you say *NOT EVER*, you are
talking about hundreds, thousands and perhaps millions (if we don't destroy
ourselves) of years of inventive humans building better and better machines
and designing better and better ways of solving problems (such as chess).
I don't think that you can say what they can or can't do! For example, lets
say we took a math-capable caveman and presented him with the problem of
constructing the Hoover Dam. He would calculate that he could carry a basket
of stones weighing a certain amount in a certain amount of time, and that he
would need a total of N baskets of stones and even with a thousand cavemen
it would take a million years to build the dam, therefor it is not possible
(Note I will leave it as an exercise for the reader to work out the actual
numbers!). The caveman simply could not conceive of earth moving machinery
or high explosives. We are still in the caveman era of computers (uh no, I
am not trying to imply that Robert Hyatt is a troglodyte!) and we may not be
able to concieve of what will come in the distant future.
Also, I do believe that "solving chess" (i.e. examining all possible
chess positions or the smaller subset of all legal chess possitions) is
anywhere close to necessary for a machine to play "perfect chess" (i.e. always
best play). People are inventive enough to create better ways of attacking
problems than mere brute force and given that we (not that I am a chess
programmer) have *BARELY BEGUN*, I think that *HUMANS* (and their tools -
computers) are capable of solving the problem (given enough time and the
do ll to do it).
Just so you don't believe that I am a complete computer chauvanist,
I will predict that Kasparov (but not too many others) will be able to hold off
the version of Deep Blue under current developement. The next machine might
just beat him (or whoever is best at the time) though.
All this is IMHO! I really don't mean to claim that any of you are
foolish cavemen scratching your heads! :-) I just think that the universe
and its posibilities are bigger than we all can imagine!

Erik Wilson
--
| \ o IO | "If we do not find | Erik Wilson |
|-----| o GANYMEDE |anything pleasant, at | University of Illinois |
| O | o EUROPA |least we will find | (217) 359-7547 |
|----/ o CALLISTO |something new" -Voltaire| eri...@uiuc.edu |

David James Alexander Hanley

unread,
Sep 17, 1993, 4:48:25 PM9/17/93
to
Of course the *IS* one way that chess could become a solved game in the
concievable future. A forced win could be found for white ~30 ply or so.

Hey, it could happen. I'm betting on e4.

dave

Paul Colley

unread,
Sep 17, 1993, 11:37:12 PM9/17/93
to
In article <93260.154...@uicvm.uic.edu> David James Alexander
Hanley <U34...@uicvm.uic.edu> writes:

> Of course the *IS* one way that chess could become a solved game in the
>concievable future. A forced win could be found for white ~30 ply or so.

Not quite. This, at best, solves one problem: Optimal moves from the
initial position, for white. It doesn't address black's moves.

Suppose there IS a forced win for white on move 30. So you write a
program that understands this. Oops! You draw black against the
human. The poor human, he doesn't have all this information, and
doesn't follow the forced win for white. A program that claims to have
solved chess has to beat white whenever, wherever white makes a move
that no longer leads to a forced mate. If you can't beat white when
white makes a fatal mistake, you haven't solved the game.

And if the shortest forced win for white is 30 moves, what might the
longest forced win be? The amount of information such a program needs
just to identify white's imperfect play is huge. Knowing how to force
a win from each of the possible mistakes makes the problem immesurably
larger still.

This process has a second layer---first, white may make a mistake that
changes a forced win to a draw; the program needs to know how to play
to reach the draw. Later, white may make a second mistake and miss the
draw; the program needs to know how to force a win from this second
layer of mistakes.

It gets worse. More generally, when we say a game is solved, we mean
that given any position, we can declare "player A can force a win" or
"player B can force a win" or "with optimal play on both sides, the
game is drawn." Knowing a forced mate from the initial position for
white doesn't solve the entire game---just one case. Admittedly, it's
a very important and interesting case. THE most important and most
interesting case! But there's still those "white to move and mate
in 3" problems published in the newspaper. Chess isn't a solved game
until the value of all reachable positions is calculatable.

Suppose we found a forced mate in 10 for white, that a good human could
learn? The effect can be predicted by anyone: The initial position of
the board would be changed by FIDE and other organizations. Swap
knights and bishops, and now decide who has the forced win!

> Hey, it could happen. I'm betting on e4.

I personally feel that the game is a draw. This is opinion only, there
is no fact to back up my feeling... and a draw would be the hardest
result to prove (finding a forced draw for white leaves the doubt:
Maybe white could force a win instead?).

-----------

I don't want to overstate my position. When the author said:

> A forced win could be found for white ~30 ply or so.

...he brought up a very good point! This is conceivable, and would
have lasting and irrevocable effect on chess. But it is not the same
thing as solving the *GAME*.

Tic-Tac-Toe is a solved game. Given any position, a modern tic-tac-toe
program (or any 10-year-old) can tell you whether it is a win, loss, or
draw. As a special case of this knowledge, we know that the initially
empty board leads to a draw under perfect play.

Chess the GAME will not be solved in my lifetime. More and more
POSITIONS will be solved (witness the recently discovered 200+ move
forced mate for a particular endgame); perhaps even the initial
position will be solved. But the GAME of chess won't be solved in my
lifetime.

- Paul Colley
University: col...@qucis.queensu.ca
Home: paco...@ember.uucp watmath!ember!pacolley +1 613 545 3807
"Quantum Mechanics: The dreams stuff is made of" - Ken Burnside

Henk Van Wulpen

unread,
Sep 20, 1993, 7:33:48 AM9/20/93
to
In article <CDI66...@YKTNEWS.WATSON.IBM.COM>, co...@watson.ibm.com writes:|> >Take all the stars in the known universe : say 100 Billon.

[stuff deleted]

|> Finally! Someone has sat down and drawn up some figures to show how enormous the possibilities of chess are. Well done Renato!
|>
|> People have this perception that computers are these amazing black boxes which takes in some input and out pops the answer moments later. Yes computer's are getting faster doubling in speed every year

|> can only go so fast - so CPU clocking speeds will reach a finite barrier also. Therefore a single processor CPU will eventually reach a peak in MIPS (millions of instructions per second) and that will
|>

|> Then there is multiprocessors - but they are generally only feasible if there is an improvement of factor 10 or more ie. more than one CPU can get the job done 10 times faster then just one CPU. It is

Hmmm... I strongly disagree here. When using branch-and-bound algorithms for
search problems, which is pretty much the case in most chess programs, it is
possible to get an acceleration that is larger than the number of processors !
This phenomenon is known as the acceleration anomaly. On first sight this seems
impossible. However, when you use several processors to traverse several parts
of the search tree, it is well possible that one processor may halt its search in
a particular part of its subtree due to some information provided by another
processor (e.g. alpha and beta parameters).

As an extremely simple example consider this. Suppose you want a computer to
solve a mate-in-one problem. Say, there are 30 possible moves, and calculating
and evaluating each new position takes 1 second (slow computer :^)). The
algorithm will try out the 30 moves in a particular ordering m1,...,m30. Now
suppose that the correct move is m16. One single processor will need 16 seconds
to find the mate. However, using 2 processors, you can give p1 moves m1 to m15
and the second processor m16 to m30. Your 2 processors will then find the mate
in less more than a second since p2 will notify p1 that it has found the solution
!!! So with only 2 processors you had a speedup of 16 ! Of course I am aware of
the fact that finding the possible moves needs some time as well and is not very
parallelisable. But I think it illustrated the thought.


|> Simplified - one node (a CPU) is the master and the others are the slaves. The slaves are each given a job to do by the master - some jobs will be finished quicker by some slaves, not because they are

|> finish early have to wait while the others catch up before more useful work can be done by the slave nodes.
|> There are techniques in parallel software, such as load balancing where jobs migrate from busy nodes to idle nodes to improve overall performance - but there is generally a high overhead cost in inter-
|>

|> So unless there is a subatomic transistor waiting to be discovered, the speed of a computer will have a finite limit which will not be breached according to the laws of physics.
|>
|> So basicly what I'm saying is, according to the rough estimates of permutations of chess positions, no computer, for the rest of the existence of the human race, will ever
|> evalutate them all.
|> I am not familiar with Alpha-Beta pruning of the permutation game tree, but I am almost certain that you CANNOT disregard a line of play BEFORE checking out all the possible positions that line of play

|> because a win is assured and there are only 3 pieces which are involved in play. The same cannot be said for a board with 25 or so pieces and a win is not evident.

Normally, a line is computed up to a quiescent position. This prevents the
situation that the program would think it is up a piece and would make the move
while it was merely a result of a look-a-head that ended in the middle of
an exchange.

|> Also a thing people forget about computers is they are just that - a COMPUTEr. They compute, a glorified calculator if you will! They follow a strict algorithm layed down by the programmer. They have n

|> forts they are a pretty crude and limited representation and certainly have a long long way to go.
|> The only way a computer can be programmed to play chess is for it to try all or most permutations of a given position - using sensible, but not infalable (sp?), rules to disregard certain avenues of pl

|> Openings have been developed over hundreds of years by Grand Masters - if you left the best of the best computers to determine an opening move by itself, it would fail miserably on it's own. If you hav

|> ce the computer will immediately stop to 'think'. This is because the computer program has included with it a standard database of openings which it parrot's off when the human player matches the moves

|> Generally I have found computer chess to be very strong in the middle game (which is probably the most part of the game) - the opening is covered by it's database - but the endgame I have found to be v

That is the way how a good chess player (not me :^)) can easily beat a chess
computer or program. Play an unusual move in the very beginning to bring the
program out of its opening book. It will usually not know how to punish this and
moreover will not be able to make the best opening moves for itself.

I am also very disappointed in the lack of endgame knowledge in a lot of chess
programs (to be honest, I only have Psion and Gnu Chess - I am not that good a
player that I would buy the most recent and strongest programs available). IMHO
it cannot be too difficult to build in endings like K+p v K which would need a
look-ahead that is that deep that the program will never find that it has to
support the pawn in the front if it has not learned how to do it (e.g. does not
know about opposition).

|> I think the reason for this is that being able to check out 5 or moves ahead is easy for a computer and not too time consuming, in the middle game, but for a human there are generally too many pieces a

|> Openings, as I have said, require more foresight than time permits - so why not use the database - most human players do anyway!

|> As for the ending - it is very easy for a human to think 20 moves a head when trying to make with a K-R v. K as the operation is so repeditive but I have actually seen a computer on level 4 (which give

|> This of course is the programmers fault for leaving the computer to 4 or 5 moves ahead thinking and not providing simple rules for restricting the opponents king to fewer and fewer ranks of the board u

|> Basically, Computer Chess is only as good as the programmer makes it regardless of the fact that it is running on a Cray or a ZX81! (Okay maybe memory problem might be incountered with the ZX81!). A sc

|> tuff like pawn structures and the value of open files and diagonals the scoring gets more abstract. You get into the problem of determining when is a material sacrifice merited for positional gain - I

|> rong coloured square.


|>
|> I haven't tried to write a computer algorithm for playing chess but I have certainly given it some thought and all I can say is there is certainly no right way of doing - except of course evaluating al

|> and their importance as a teaching aid even for Grand Masters. So don't throw out your ChessMaster computer yet but don't give up faith in the human chess brain - not for a couple of billion years anyw
|>

|> Just my $0.02 worth. Regards,

|> Colm.
|>
|> Opinions my own and not IBM's. Blah blah blah etc. etc.

I do support the opinion though that computers never will be able to actually
*solve* the game of chess. I am pretty sure though that it won't take too long
anymore for a computer/program to become World Champion.

Henk.

Renato Ghica

unread,
Sep 20, 1993, 10:59:01 AM9/20/93
to

In article <19930920.133349...@CC1.KULEUVEN.AC.BE>, he...@cs.kuleuven.ac.be (Henk Van Wulpen) writes:
|> In article <CDI66...@YKTNEWS.WATSON.IBM.COM>, co...@watson.ibm.com writes:|> >Take all the stars in the known universe : say 100 Billon.
|>
|> [stuff deleted]
|>
|> |> Finally! Someone has sat down and drawn up some figures to show how enormous the possibilities of chess are. Well done Renato!
|> |>
|> |> People have this perception that computers are these amazing black boxes which takes in some input and out pops the answer moments later. Yes computer's are getting faster doubling in speed every year
|> |> can only go so fast - so CPU clocking speeds will reach a finite barrier also. Therefore a single processor CPU will eventually reach a peak in MIPS (millions of instructions per second) and that will
|> |>
|> |> Then there is multiprocessors - but they are generally only feasible if there is an improvement of factor 10 or more ie. more than one CPU can get the job done 10 times faster then just one CPU. It is
|>
|> Hmmm... I strongly disagree here. When using branch-and-bound algorithms for
|> search problems, which is pretty much the case in most chess programs, it is
|> possible to get an acceleration that is larger than the number of processors !
|> This phenomenon is known as the acceleration anomaly. On first sight this seems
|> impossible. However, when you use several processors to traverse several parts
|> of the search tree, it is well possible that one processor may halt its search in
|> a particular part of its subtree due to some information provided by another
|> processor (e.g. alpha and beta parameters).
|>
|> As an extremely simple example consider this. Suppose you want a computer to
|> solve a mate-in-one problem. Say, there are 30 possible moves, and calculating
|> and evaluating each new position takes 1 second (slow computer :^)). The
|> algorithm will try out the 30 moves in a particular ordering m1,...,m30. Now
|> suppose that the correct move is m16. One single processor will need 16 seconds
|> to find the mate. However, using 2 processors, you can give p1 moves m1 to m15
|> and the second processor m16 to m30. Your 2 processors will then find the mate
|> in less more than a second since p2 will notify p1 that it has found the solution
|> !!! So with only 2 processors you had a speedup of 16 ! Of course I am aware of

^^^^^^^^^^^^^^^^^^^^^^^^^^^


|> the fact that finding the possible moves needs some time as well and is not very
|> parallelisable. But I think it illustrated the thought.
|>
|>


This is where the problem is :

how do you give a processor moves m16 to m30 without generating them first?
You still have to check for legal moves, en passant, and obey all the other
rules (like can't castle out of check, parry double check etc etc.)

With 2 processors it will take you 15 seconds to generate the first 30 moves (assuming
1 sec/move ;-)) and then it will take you one second to find move m16. On the average,
though, you will have to look at move mN/2 or, in this case, m24 (half way between
m16 and m30). Ie if the best move is the last one (m30), it will take you much longer.

Generating chess moves is not as easy as adding numbers. Superficially, all these
variables have to be considered:

- last pawn move
- check of both kings
- rook/king last move
- 50 move rule
- 3 time repetition
- castling rules
- promotion to any piece


You cannot generate legal moves for a position out of thin air.

If the first move is the best move, then having 1000 processors won't make any difference.

;-)

-rg

Israel Silverman

unread,
Sep 18, 1993, 9:14:00 PM9/18/93
to

ME>Right. If every sub-atomic particle in the known universe were a
ME>trillion-MIPS computer, all working together to calculate the game
ME>of chess from move 1, and they started this task 100 trillion years ago,
ME>they would still play the openings worse than a Grandmaster!

[1.e4 d6 2.d4 Nf6 3.Nc3 g6 4.f4 Bg7 5.Nf3 c5 6.e5 Ng4 7.e6 fxe6]

Think again. For DECADES (not years, decades) all the top
players in the world, if they stopped to think about it, KNEW
in the above line that no sane black player could play 7...fxe6??,
because it lost to simply 8.Ng5!, threatening Nxe6 forking the queen
and bishop, as well as Qxg4.

Yet, in 1988, a GM played fxe6, and it turned out to be a DRAW
after 8.Ng5 Bxd4! 9.Nxe6 Bxb5, and if NxQ, then Bf2 is perpetual
check. Then, everyone said it was a draw. Now, everyone says
that it's a game.

ALL the top books on the Pirc said that 7...fxe6 was a terrible
blunder. The excellent 1973 book by Botterill and Keene dismissed it.
A good book by Nunn in 1979 on the Pirc dismissed it with a wave of a
hand. Even the book "200 Modern Chess Traps in the Fianchetto
Openings" published in 1970 has it as one of the 200 traps. Check
page 140. The book dismisses it with "8...PxKP? 9.N-N5! and the threat
of NxKP is unanswerable". Yet Grandmasters now play it all the time.

What is really almost painful is that the fellow who once owned the
used book I bought a few weeks ago even carried the analysis
further! He missed the "drawing" 8...Bxd4! by less than a hair's
width.

He wrote in the margin:
"9...BxB 10 NxKP Q-Q2 11.QxN R-N1 12.NxB! QxN(5) 13.NB7ch wins
Q-B1 11.NxB QxN 12.N-B7ch wins
Q-R4 11.B-Q2 PxP 12. NxB(4) QxN 13.NB7ch wins"

Amazing!

---
ş SLMR 2.1a #1210 ş Are you using Windows, or is that just an XT?

Israel Silverman

unread,
Sep 18, 1993, 9:14:00 PM9/18/93
to
GH>So....
GH>"If every atom in the know universe was a supercomputer a Billon Million
GH>times faster than the fastest computer today, it would take
GH>30,000,000 Billion Billion years to solve the game."

If every atom were a supercomputer, I would still not need every
single one of those positions solved to "solve" chess. I don't
need to solve every future position to know that K+R v. K is a
win, and neither does a computer. The computer has "solved" the
position when it knows to reach K+R v. K. And given enough
computing power, it will form its own millions of shorthand
rules for won positions. We might learn something from them.
---
þ SLMR 2.1a #1210 þ Why be born again, when you can just grow up?

Kenneth Sloan

unread,
Sep 20, 1993, 2:37:38 PM9/20/93
to
In article <49.3660.17...@cdreams.com>
israel.s...@cdreams.com (Israel Silverman) writes:
>...

>
> [1.e4 d6 2.d4 Nf6 3.Nc3 g6 4.f4 Bg7 5.Nf3 c5 6.e5 Ng4 7.e6 fxe6]
>

The analysis you give doesn't seem to match this position. How about a
xxx. Bb5+ Bd7 thrown in somewhere?

Renato Ghica

unread,
Sep 20, 1993, 2:48:43 PM9/20/93
to
|> ş SLMR 2.1a #1210 ş Why be born again, when you can just grow up?


You mean you don't know of any K+R v. K positions that are draws? (hint:
remember all the rules of the game).


I'll give you a K+B+N v. k+q that is draw (the above is too obvious). Give
this to gnuchess and see how it evaluates it ;-)

White: K on b1, B on b2, knight on d4
Black: K any free/legal square, Q any free square
DRAW.


How do you *PROVE* this is a draw without playing on for fifty moves? let
me know and we'll get famous! Store all the positions you say? For
every piece /position combination you say? not good enough. Anyone can do that.
Maybe a Fourier Transform..... ;-)


Now this is ONE position with *FIVE* pieces; How many more do you think there
are?

I'd love to play a computer that would willingly go into this position
because it thought it was up material.

ps, I was more than a couple of orders of magnitude off in my original
posting, but it doesn't matter because I can increase/decrease the
assumed number of stars in the universe! hehehehehehe!

;-)

-rg

Rickard Westman

unread,
Sep 21, 1993, 3:27:10 AM9/21/93
to
co...@watson.ibm.com writes:

>I am not familiar with Alpha-Beta pruning of the permutation game
>tree, but I am almost certain that you CANNOT disregard a line of
>play BEFORE checking out all the possible positions that line of
>play leads to. You cannot disregard a pawn move because a pawn is
>worth so little and attacks so little - it could eventually
>provide assistance in a mate.

Pure alpha-beta pruning does not affect the end result of the tree
search at all. The pruning is done on branches that could not
*possibly* lead to a better position than an already known branch.
This is best understood by looking at an example:

A
/|\
B C D
/ /|\ \
* E F G *
| | |
* * *

Here the capital letters stand for chess positions, and the
asterisks for parts of the game tree that aren't shown in detail
(but contain a possibly huge number of nodes). The tree, rooted
at position A, can of course itself be part of a larger game tree.

The program's task here is to pick the best move out of three
(leading to position B, C or D). Let's say that position B gets
the score 42 (by searching its subtree), where a score is better
for us the higher it is. When we search the C branch we discover
that position E gets the score 17. Since our opponent will chose
the move that results in the *lowest* score, we know that the best
we can ever expect from position C is 17. It doesn't matter if
positions F and G are better for us - if they are, our opponent
will not chose the move leading to them. Thus, we can safely
discard the move leading to C without having to search the
subtrees rooted at F and G - the move leading to B is better.

Note that this kind of pruning can be done on every subtree on
every level of the tree, leading to huge savings. The algorithm
works better if strong moves are investigated before weak ones, but
it will never give incorrect results. If you have N leaves in the
original search tree, you could have as few as 2/sqrt(N) left after
alpha-beta pruning (according to analysis by Knuth in 1975).

In our hypothetical example of trying to "solve" chess we won't
have integer scores like 42 for a position - only a score from the
set { won, lost, draw}. This makes it even easier to understand
why it isn't necessary to search the entire tree. As soon as a
move is found to lead to a won position, it would be unnecessary to
investigate any immediate alternatives.

>In the end game, certainly there are vast majority of moves which
>can be disregarded eg. K-R v. K

A system of rules could be used to cover such positions, with the
appropriate exceptions (not all KRK positions are won for the KR
side!). A more general mechanism, transposition tables, are usually
implemented in chess programs. The idea here is to avoid evaluating
identical positions multiple times, by storing commonly evaluated
positions and their corresponding scores. (Roughly analogous to cache
memory in computers.) This is very useful for end games, and will not
affect the end result in any way, if properly implemented.
--
Rickard Westman <ri...@ida.liu.se> | "I think not."
Programming Environments Laboratory |
University of Linkoping, Sweden | - Cartesius' last words?
------------------------------------+------------------------------------

Roy Eassa

unread,
Sep 21, 1993, 2:50:34 PM9/21/93
to

Regarding alpha-beta pruning:

I agree that it only prunes branches that cannot be better, but this is
only true given that the program is looking only to a fixed depth. I
don't believe this technique has any meaning when a full and complete
search is done (i.e., if you are solving for mate or trying to completely
solve chess -- which is two ways of saying the same thing).

The good news about trying to solve the game completely is that the only
evaluation needed at the end node is a yes/no decision about whether or
not it's mate. The bad thing is that alpha-beta pruning is not available,
and you must search the entire 10^120 lines.

Renato Ghica

unread,
Sep 21, 1993, 3:23:39 PM9/21/93
to

In article <1993Sep21.0...@ida.liu.se>, ri...@ida.liu.se (Rickard Westman) writes:
|> co...@watson.ibm.com writes:
|>
|> >I am not familiar with Alpha-Beta pruning of the permutation game
|> >tree, but I am almost certain that you CANNOT disregard a line of
|> >play BEFORE checking out all the possible positions that line o|> >play leads to. You cannot disregard a pawn move because a pawn is

The problem, of course, is the computer's ability to evaluate a position
correctly. Since is not possible to evaluate a position correctly without
analyzing it, even for one move, brute force will always beat a-b pruning.

Sure, one can count pieces, locate weak squares and so on,
but if the position is a "forced" draw/win/loss, then it doesn't matter.

Example : if F & G lead to a position where mate can be forced in 3 moves
after several piece sacs, but the algorythm says "I have not seen a mate,
there is no compensation", or even more simply, to a liquidation into
a won ending, and something else is chosen because of an (incorrect)
assignment to a position (ie choose the sapce advantage now instead of
F or G), then the computer will have chosen the "wrong" move, and
A-B can be deemed a failure.

Brute force methods (every node every time) do not have to worry about this.

If an algorythm could always correctly evaluate a position, then A-B pruning
would work, but there's no such thing (just like you can't really
use A-B pruning to solve the traveling salesman problem - you have to look
at EVERYTHING to prove the shortest path).


-rg

James Aspnes

unread,
Sep 21, 1993, 3:59:39 PM9/21/93
to
In article <CDpwC...@world.std.com> m...@world.std.com (Roy Eassa) writes:

The good news about trying to solve the game completely is that the only
evaluation needed at the end node is a yes/no decision about whether or
not it's mate. The bad thing is that alpha-beta pruning is not available,
and you must search the entire 10^120 lines.

Suppose I determine that there is a winning strategy for white
starting with 1. e4. Why would I need to search the rest of the tree?
Alpha-beta pruning is just a way of noticing mechanically cases like
this when I can stop searching. It doesn't depend on having a depth
bound, or even on having evaluations other than win/draw/loss.

Roy Eassa

unread,
Sep 21, 1993, 4:12:27 PM9/21/93
to
.9...@world.std.com> <27nmfb...@PINE.THEORY.CS.YALE.EDU>

aspnes...@cs.yale.edu (James Aspnes) writes:


In the context of completely solving chess, the term "strategy" has no
meaning, IMHO.

Renato Ghica

unread,
Sep 21, 1993, 5:04:37 PM9/21/93
to

How do you prove/convince yourself that the strategy is in fact
"winning" without searching the whole tree? My favorite example
is the b/k/n vs. k/q position. Here winning two minor pieces for
a queen does not win the game.

No, the position has to be mate or else it's unclear/unknown
(without further analysis).

(for those who really want to know which position I keep talking about, it's
white: k/b1, b/b2, n/d4, black:k+q anywhere.this is a draw.)

Robert Hyatt

unread,
Sep 21, 1993, 6:04:55 PM9/21/93
to

There are some really WRONG ideas about what alpha/beta is out there in
netland. If you can search to the end of the tree, a mate for white is
usually scored as +infinity, a mate for black as -infinity, and a draw as
zero. These values don't give alpha/beta any problems at all... Don't
know where this rumor came from, but I know where it ought to go...

:^)


--
!Robert Hyatt Computer and Information Sciences !

!hy...@cis.uab.edu University of Alabama at Birmingham !

Robert Hyatt

unread,
Sep 21, 1993, 6:03:00 PM9/21/93
to
In article <CDpwC...@world.std.com> m...@world.std.com (Roy Eassa) writes:
>

Argument doesn't make sense. What is the difference between a score of "n"
and a score of "lose"??? Alpha/beta still works fine for searching for mates.
All current machines have a mate-finder mode and couldn't find anything without
alpha-beta. If you want to know more, email and I can explain further.

Bob Hyatt

James Aspnes

unread,
Sep 21, 1993, 6:51:48 PM9/21/93
to
In article <CDq2J...@fig.citib.com> gh...@fig.citib.com (Renato Ghica) writes:
In article <27nmfb...@PINE.THEORY.CS.YALE.EDU>, aspnes...@cs.yale.edu (James Aspnes) writes:
|> Suppose I determine that there is a winning strategy for white
|> starting with 1. e4. Why would I need to search the rest of the tree?
|> Alpha-beta pruning is just a way of noticing mechanically cases like
|> this when I can stop searching. It doesn't depend on having a depth
|> bound, or even on having evaluations other than win/draw/loss.

How do you prove/convince yourself that the strategy is in fact
"winning" without searching the whole tree? My favorite example
is the b/k/n vs. k/q position. Here winning two minor pieces for
a queen does not win the game.

Easily; I search the entire subtree beginning at 1. e4. If I want to
be even more clever, I search the entire subtree beginning at 1. e4
using alpha-beta pruning. In neither case (assuming I found that
1. e4 wins) do I need to look at any other first moves.

Kenneth Sloan

unread,
Sep 21, 1993, 11:49:04 PM9/21/93
to
In article <CDpwC...@world.std.com> m...@world.std.com (Roy Eassa) writes:
>
>Regarding alpha-beta pruning:
>
>I agree that it only prunes branches that cannot be better, but this is
>only true given that the program is looking only to a fixed depth. I
>don't believe this technique has any meaning when a full and complete
>search is done (i.e., if you are solving for mate or trying to completely
>solve chess -- which is two ways of saying the same thing).

I believe you are incorrect.

>
>The good news about trying to solve the game completely is that the only
>evaluation needed at the end node is a yes/no decision about whether or
>not it's mate. The bad thing is that alpha-beta pruning is not available,
>and you must search the entire 10^120 lines.

Nope. Even when all of the leaf nodes have values of +1, 0, -1,
alpha-beta pruning is still useful. It may even be *more* efficient,
because there will be lots more cutoffs (remember, cutoffs can occur
when the Provisionally Backedup Value is EQUAL to either alpha or beta
(whichever one is relevant at that node).

Consider the case where you happen to stumble on a forced winning line
as the first line you expand. Once you back up the value '1' to the
root node, you will get a cutoff at every node in the rest of the tree
where it is your turn to move. Every possible value backed up to such a
node will be "no better than what you can already achieve by making the
winning first move", and will generate a cutoff.

Of course, if you consider "1" to be "infinity", then you will generate
one Beta-cutoff as soon as you back up the '1' to the root node! This
should be obvious: is you find a forced win from the first move you
consider, there is no need to consider any other move! This is the very
essence of alpha-beta.

If your search algorithm continues to expand the tree, after it has
found a forced win....perhaps it should consider a career in academia.

-Ken Sloan

Kenneth Sloan

unread,
Sep 21, 1993, 11:56:29 PM9/21/93
to
In article <CDpx...@fig.citib.com> gh...@fig.citib.com (Renato Ghica) writes:
>The problem, of course, is the computer's ability to evaluate a position
>correctly. Since is not possible to evaluate a position correctly without
>analyzing it, even for one move, brute force will always beat a-b pruning.

No. The problem is that you do not understand the terms "brute force"
and "alpha-beta pruning". In common usage and practice, "brute force"
is precisely identical with "alpha-beta pruning".

If you are worried about correct evaluation, then you want to search
*all the way to the conclusion of the game*. You can still use
alpha-beta pruning when you do this. Of course, for chess, it is not
possible to search that deeply.

The usual alternative to "brute force" is some sort of heuristic
pruning, which prunes brances of the search tree which appear to be
unpromising, but which cannot be *proven* to be irrelevant. This is
often called "selective search".

Again: "alpha-beta pruning" is guaranteed to give exactly the same
answer as "examine every node" - as long as both searces are to the same
depth. The reason to use alpha-beta pruning is that it gives the same
answer sooner, and as a result you may be able to search more deeply
(thus, getting better evaluations) in the same amount of time. Either
way - it's equivalent (and provably so) to "brute force".

Israel Silverman

unread,
Sep 22, 1993, 12:26:00 AM9/22/93
to
SL>>...
SL>>
SL>> [1.e4 d6 2.d4 Nf6 3.Nc3 g6 4.f4 Bg7 5.Nf3 c5 6.e5 Ng4 7.e6 fxe6]
SL>>

SL>The analysis you give doesn't seem to match this position. How about a
SL>xxx. Bb5+ Bd7 thrown in somewhere?


Whoops. That's what happens when you type without looking. A
variant of moving without looking. You are correct.
---
ş SLMR 2.1a #1210 ş First Hillary, then Gennifer, and now us

Israel Silverman

unread,
Sep 22, 1993, 12:26:00 AM9/22/93
to
GH>I'd love to play a computer that would willingly go into this position
GH>because it thought it was up material.

GH>ps, I was more than a couple of orders of magnitude off in my original
GH>posting, but it doesn't matter because I can increase/decrease the
GH>assumed number of stars in the universe! hehehehehehe!

BTW, when I was an 1100 a long time ago, I found a position
(which I later on learned was known) with K+Q vs. K+Q, and one
side is on the move, and not in check, but the other side wins.
Really neat. Know that position?
---
ş SLMR 2.1a #1210 ş Busier than a one-eyed cat watching 9 mouseholes

Johannes Fuernkranz

unread,
Sep 22, 1993, 4:44:25 AM9/22/93
to
In article <CDpwC...@world.std.com> m...@world.std.com (Roy Eassa) writes:
>

"Iterative Deepening" is what helps here. You search to depth n with alpha-beta
and then increase n by 1 and search again and again and again ...
The costs of the search are dominated by the costs of the search to the biggest n
you use. The information of the previous level can also be used to order the moves
which can buy you a lot of cutoffs.
So altogether the benefits of alpha-beta by far outweigh the trouble of having to
search the lower levels again and again.

Juffi

P.S. Of course this doesn't let you solve the game either.

--
Johannes Fuernkranz ju...@ai.univie.ac.at
Austrian Research Inst. for Artificial Intelligence +43-1-5336112(Tel)
Schottengasse 3, A-1010 Vienna, Austria, Europe +43-1-5320652(Fax)
--------------- "Life's too short for Chess." -- Byron ------------------

Steven Rix

unread,
Sep 22, 1993, 6:49:30 AM9/22/93
to

In article <49.3816.17...@cdreams.com>, israel.s...@cdreams.com (Israel Silverman) writes:
->
-> BTW, when I was an 1100 a long time ago, I found a position
-> (which I later on learned was known) with K+Q vs. K+Q, and one
-> side is on the move, and not in check, but the other side wins.
-> Really neat. Know that position?

I presume you mean Black Kb1, Qa1 v White Kb3, Qd2.

This usually arises from the ending Q v Rook pawn, where the stronger side's
king is close to the queening square. For example, from Black Pa2, Kb1 v
White Kd4, Qg1, play could continue 1... Kb2 2 Qf2+ Kb3 3 Qe1 Kb2 4 Qd2+
Kb1 5 Kc3 a1=Q+ 6 Kb3, etc. In fact, this idea allows you to work out a
region within which White must have his king in order to win against K+Pa2.

--
Steve Rix,
Department of Chemical Engineering, University of Edinburgh.
E-mail: ste...@chemeng.ed.ac.uk, phone: +44 (31) 650 8565.

Feng-Hsiung Hsu

unread,
Sep 22, 1993, 8:05:33 AM9/22/93
to
In article <1993Sep22....@cis.uab.edu> sl...@cis.uab.edu (Kenneth Sloan) writes:
>and "alpha-beta pruning". In common usage and practice, "brute force"
>is precisely identical with "alpha-beta pruning".

No, brute force is NOT identical to "alpha-beta pruning". "Brute force" means
[logically] searching all the moves, while alpha-beta pruning can be applied
to game trees of arbitrary shapes, including brute force search trees.

In my opinion, "alpha-beta" is badly named. The name makes it sound like
something mystic. Any good chess player uses "alpha-beta" implicitly. The
pruning mechanism is nothing more than "A player needs only ONE winning move
against every possible moves by the opponents". (Well, it is a little bit
more than that). It is then trivial to see that only about the square root of
the number of positions need to be searched in the BEST case.

Human players don't use "brute force", but they do use alpha-beta pruning,
or rather glorified branch and bound.

Renato Ghica

unread,
Sep 22, 1993, 8:26:41 AM9/22/93
to

In article <1993Sep22....@cis.uab.edu>, sl...@cis.uab.edu (Kenneth Sloan) writes:
|> In article <CDpx...@fig.citib.com> gh...@fig.citib.com (Renato Ghica) writes:
|> >The problem, of course, is the computer's ability to evaluate a position
|> >correctly. Since is not possible to evaluate a position correctly without
|> >analyzing it, even for one move, brute force will always beat a-b pruning.
|>
|> No. The problem is that you do not understand the terms "brute force"
|> and "alpha-beta pruning". In common usage and practice, "brute force"
|> is precisely identical with "alpha-beta pruning".
|>

Since you can't prove the above statement, I'll dismiss it as more noise.
If you can prove the above, I hope that you don't use "take this position"
as an example.

Brute force means brute force in every application. Look it up in a
computer dictionary if you're unclear about it.

Any algorythm that uses anything that does not traverse all the nodes in any application (chess, traveling salesman, other NP problems) is going to be inferior. IN THE CONTEXT OF SOLVING THE GAME TO CHECKMATE, BRUTE FORCE
****MUST**** BE USED.

Yes, A-B may be faster (it won't be for forced variations), but it cannot be better than brute IF THE FINAL LEAF POSITION IS NOT CHECKMATE. IF THIS IS THE CASE, SINCE MOST PROGRAMS DON'T ANALYZE FROM MOVE 1 TO CHECKMATE, "EVALUATING" A POSITION IS USELESS, BECAUSE EVERYTHING AFTER THAT IS ASSUMPTION.
ie "I ASSUME I'M GOING TO WIN BECAUSE I HAVE A QUEEN FOR TWO PIECES". wrong.

The problem is that you don't understand the game. The purpose is
not to reach a good position, while avoiding others that "look" bad
to a stupid algorythm that couldn't beat 99.9% of chess masters.

The purpose is to checkmate.


ps: I leave the fools to themselves and disavow any knowledge of this
thread. Got to get back to my chessPlan abstract base class ;-)

Jeff Kenton

unread,
Sep 22, 1993, 9:35:50 AM9/22/93
to
gh...@fig.citib.com (Renato Ghica) writes:


>In article <1993Sep22....@cis.uab.edu>, sl...@cis.uab.edu (Kenneth Sloan) writes:
>>

>> [ true and well known comments about alpha-beta pruning from Kenneth Sloan ]
>>

>Since you can't prove the above statement, I'll dismiss it as more noise.
>If you can prove the above, I hope that you don't use "take this position"
>as an example.

. . .

>The problem is that you don't understand the game. The purpose is
>not to reach a good position, while avoiding others that "look" bad
>to a stupid algorythm that couldn't beat 99.9% of chess masters.

There's no need to be rude, especially when you're wrong.


--
-------------------------------------------------------------------------
= Jeff Kenton (617) 894-4508 =
= jke...@world.std.com =
-------------------------------------------------------------------------

Roy Eassa

unread,
Sep 22, 1993, 10:44:19 AM9/22/93
to
sl...@cis.uab.edu (Kenneth Sloan) writes:

>Nope. Even when all of the leaf nodes have values of +1, 0, -1,
>alpha-beta pruning is still useful. It may even be *more* efficient,
>because there will be lots more cutoffs (remember, cutoffs can occur
>when the Provisionally Backedup Value is EQUAL to either alpha or beta
>(whichever one is relevant at that node).

>Consider the case where you happen to stumble on a forced winning line
>as the first line you expand. Once you back up the value '1' to the
>root node, you will get a cutoff at every node in the rest of the tree
>where it is your turn to move. Every possible value backed up to such a
>node will be "no better than what you can already achieve by making the
>winning first move", and will generate a cutoff.

>Of course, if you consider "1" to be "infinity", then you will generate
>one Beta-cutoff as soon as you back up the '1' to the root node! This
>should be obvious: is you find a forced win from the first move you
>consider, there is no need to consider any other move! This is the very
>essence of alpha-beta.

>If your search algorithm continues to expand the tree, after it has
>found a forced win....perhaps it should consider a career in academia.


The following sentences assume we are discussing the value of alpha-beta
pruning used in an all-out attempt to solve the game of chess, and whether
or not it will reduce the tree of possibilities from something like 10^120
to something like 10^60:

Chess is widely believed to be a draw with correct play by both sides.
Thus, the pruning you refer to, in which a force win has been found
already, will not occur.

Second, in normal chess tree searches, pruning is very effective because
every end-node has a "score" and many of these scores will be too high or
too low to continue with a branch. However, the only scores in an all-out
search for mate will be infinity (mate for me), negative infinity (mate for
opponent), or undecided. When searching for mate while trying to solve
chess, there will be very, very few positions reached in the tree that are
mates. The number of such positions is essentially zero compared to the
number of undecideds. Thus, the amount of pruning is negligible compared
to the amount of non-pruning.

Roy Eassa

Roy Eassa

unread,
Sep 22, 1993, 10:47:48 AM9/22/93
to
sl...@cis.uab.edu (Kenneth Sloan) writes:

>Again: "alpha-beta pruning" is guaranteed to give exactly the same
>answer as "examine every node"