computer chess
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??
t.roger.kiang
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
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
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
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
>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
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
>
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
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
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
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
>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
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
>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
>
>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
>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
> 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
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
So divide the final answer by 5400 = 5,000 Billon Billon years ;-)
Kenneth Sloan
>
>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
>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
>
>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
>>
>>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
>>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
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
: >> 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
>
>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
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
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
>
>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
>
-------------------------------------------------------------------------------
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
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
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
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
[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
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
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
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
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
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
>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
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
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
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
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
aspnes...@cs.yale.edu (James Aspnes) writes:
In the context of completely solving chess, the term "strategy" has no
meaning, IMHO.
Renato Ghica
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
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
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
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
>
>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
>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
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
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
"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
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
>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
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
>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
>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
>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".
You are absolutely correct. However, in the context of searching the
entire tree of the game of chess for a forced mate (especially considering
that the game is believed to be a theoretical draw), the number of branches
that lead to forced mate is negligible compared to the number that do not,
so the amount of pruning that can be done is negligible.
Roy Eassa
> 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?
This occurs commonly in K+Q vs. K+P (bishop-pawn or rook-pawn) endgames
where the attacking King is near enough. One example:
White: K on b6; Q on e7
Black: K on b8; Q on c8
Black to move loses.
Ed Johnson
I don't. I throw out many moves without looking at them in depth so I
can have more time to spend on the ones that are more promising.
Alpha Beta works if you can analyze thousands of positions a second,
but for those of us who work in seconds per position, we would usually
not be able to look 2 ply. So most of us probably use selective
search.
Ed
(ICS edjohn)
Robert Hyatt
Exactly! Well said....
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Robert Hyatt
You are using your "own" definition of brute force, not the widely
accepted (in artificial intelligence) one. Brute force simply
means that from any node in the tree, you try *every* alternative
move available, not "skipping" any. The alternative is called
selective search and here you enumerate the list of possible moves,
throw some of them (many of them for a human, in fact, almost all
of them) out and then only search what is left.
Brute force programs (Cray Blitz, Deep * [don't you just love the
unix syntactical short cuts?], hitech, and almost every other chess
program) do, in fact, use alpha-beta. Alpha-beta is "backward"
pruning where you use knowledge gained from search one sibling branch
to avoid searching other siblings from the same node. This is not
done "before the fact" like a selective search, and, as a result,
brute force/alpha-beta will *not* overlook one single thing that
brute force/no alhpa-beta will find. If you grab any Artificial
Intelligence text you can find, and look up "minimax game trees"
you will find the terms brute-force and selective search applied
to these trees. You will also find that alpha-beta drastically
cuts the work required to do one of these searches, WITHOUT
changing the outcome, move chosen, score, etc. Minimax and
minimax/alpha-beta are equivalent EXCEPT in terms of the work
done. Alpha-beta requires MUCH less. A selective program can
still (and most do) use alpha/beta to further reduce the size
of the tree that is searched. alpha/beta and brute-force are
*not* equivalent terms. They each mean something completely
different from the other.
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Robert Hyatt
Quite the contrary. If you are searching (using the new Cray-99999
machine that is powerful enough to search this tree of 10^60 positions
in reasonable time) then *every* branch in the tree leads to a
win loss or draw. From Ken's previous post, alpha/beta also prunes
quite handily when scores are equal. After all, if e4 is good
enough to win the game (say in 60 moves) do I need to find out that
d4 wins in 50? Who cares? A win is a win and alpha/beta handles
this. Most programs do distinguish between mates in 5 and mates
in 10, but it really isn't necessary as long as your algorithm isn't
stupid enough to continually play a mate-in-5 move instead of
closing in and really mating the king 4 moves later. This has
happened in the early 70's tournaments, but not in the past 20
years.
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Feng-Hsiung Hsu
Using selective search does not preclude alpha-beta pruning. If you
ever think thus, "if (s)he/it plays the stupid move x, then I can just play y
and kill him/her/it badly.", then you used alpha-beta pruning. You are
confusing alpha-beta with brute force. Alpha-beta is nothing special,
just a fancy name for one type of common sense reasoning. The reason it
is giving a special name is that the early programmers do not have
common sense.:-)
Roy Eassa
>>You are absolutely correct. However, in the context of searching the
>>entire tree of the game of chess for a forced mate (especially considering
>>that the game is believed to be a theoretical draw), the number of branches
>>that lead to forced mate is negligible compared to the number that do not,
>>so the amount of pruning that can be done is negligible.
>>
>Quite the contrary. If you are searching (using the new Cray-99999
>machine that is powerful enough to search this tree of 10^60 positions
>in reasonable time) then *every* branch in the tree leads to a
>win loss or draw. From Ken's previous post, alpha/beta also prunes
>quite handily when scores are equal. After all, if e4 is good
>enough to win the game (say in 60 moves) do I need to find out that
>d4 wins in 50? Who cares? A win is a win and alpha/beta handles
>this. Most programs do distinguish between mates in 5 and mates
>in 10, but it really isn't necessary as long as your algorithm isn't
>stupid enough to continually play a mate-in-5 move instead of
>closing in and really mating the king 4 moves later. This has
>happened in the early 70's tournaments, but not in the past 20
>years.
...but:
You have to search to an incredibly deep and wide level before you have
found even one "forced" win, loss, or draw, and it is during that
initial search that alpha-beta has not yet taken place. Sure, *after*
you've found a forced win, you can do pruning, but then it's too late!
Roy
r.c.call
Some people are using it to mean "exhaustive search of the game tree with
no restrictions on depth, with the only leaves being nodes where the game
ends," while others are using it to mean "exhaustive search of the game
tree to a given search depth."
Clearly, an exhaustive search to the end of the game will not yield the
same result as a limited-depth search, whether the limited search uses
pruning or not.
Note, however, that exhaustive search and (alpha-beta) pruned search
are equivalent for a given subset of the tree or for the entire tree.
Whether the tree is being searched to a given depth (and the leaf nodes
evaluated) or searched until a win, loss, or draw is found, alpha-beta
and deep alpha-beta pruning will yield a result equal to that obtained
by an exhaustive search.
Let me put it another way: If exhaustive search (i.e., "brute force")
examines some set S of nodes in the game tree, then alpha-beta or
deep alpha-beta pruning will examine some set P of nodes which is a
subset of S, and yield the same result.
Does that help clear things up?
-- Chris
--
R.C.Call rcc...@blink.att.com
Kenneth Sloan
>
>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.
For the sake of reasoned discussion, I will accept all of your "widely
believed" assumptions. Now, the question is: will alpha-beta pruning
occur. You say no.
You assume that the value of the game is a draw - allow me to assume that
the first line you investigate will back up the value "1/2" (*not*
"undecided"!) to the root node. If you believe that the only values
allowed are +/- infinity and "undecided" - read no further; we have no
hope of ever agreeing on anything.
Now, as you search the second (and successive) moves from the root node,
you will (almost always, according to your assumption) find that the
Provisional Backedup Value of an internal node will also be 1/2. If it
is your opponent's turn to move at that node, alpha-beta pruning will
abandon search below that node. Why? Because the first move (for your
opponent, from that node) has been demonstrated to hold you to a draw.
Since it is your opponent's turn to move here, the value of the game at
that node (for you) is *at most* a draw. If it should happen to turn
out that some other move (for your opponent, from this node) leads to a
win for your opponent....YOU DON'T CARE! In that case, you can always
choose the first move from the root node, and not enter this subtree.
If, on the other hand, another move (at the internal node, by your
opponent) happens to lead to a win for you....YOU DON'T CARE! In that
case, your opponent will choose the first move from that node - which
has just been demonstrated to lead to a draw. And, you might just as
well have made the first move (the draw, remember?) from the root node.
In all cases, the discovery that *one* move for your opponent leads to a
draw from the internal node is enough to convince you that this node is
not worth further investigation.
Thus, there is no possible result which you can discover by further
search below the internal node which will have any effect whatsoever on
the value of the game, or finding a move for you (at the root node)
which maximizes your return. So...you discontinue search (in this case,
it's an alpha-cutoff) - without fear of making a mistake. You have
*proven* that you will get the right answer *whether or not you actually
continue the search below the internal node*
Alpha-beta search is *independent* of the evaluation function.
Alpha-beta search is *independent* of the depth of search.
Alpha-beta search is *trivial* for those who understand it, and *magic*
for those who don't. Trust me...I've moved more than my share of
students from the *magic* to the *trivial* point of view. Usually, it
takes less time than this discussion - but so it goes. I must be losing
my touch.
If you implement Alpha-beta search, and then comment out the
comparisons, and the decisions to discontinue the search, you will get
precisely the same answer - it will just take you longer.
In response to an other post: yes, strictly speaking alpha-beta is not
*identical* to brute force. The Alpha-beta technique can be applied to
other search strategies. But...it is also true that alpha-beta can be
used in a "brute force" tree search - and it's use does not make that
search any less "brute force". And, that was the question at the time.
I apologize for my sloppy phrasing.
In response to the pleasant chap who took it upon himself to point out
the existence of these things called "dictionaries": thanks - but I
prefer to find my definitions of technical terms in the primary
literature. I refuse to argue about whether or not an established
technical term in the context of graph search happens to have another
meaning in other contexts. Sorry to dissapoint.
Kenneth Sloan
>can have more time to spend on the ones that are more promising.
>Alpha Beta works if you can analyze thousands of positions a second,
>but for those of us who work in seconds per position, we would usually
>not be able to look 2 ply. So most of us probably use selective
>search.
Switching sides here...it's possible to use *both* selective search
*and* alpha-beta pruning. My abject apologies for starting this
tangential thread.
Kenneth Sloan
>
>Since you deleted the explanation as to why A-B pruning doesn't always work,
>I'll give you an example using the case you posed above. Given that your
>computer program thinks/proves/determines it has a winning strategy for with
>1. e4 It still must do a complete brute force test of all possible lines
>after 1. e4 to prove this. If it stops at 25 ply or so in any variation,
>there is always the possibility of not evaluating the position correctly
>(space, time, force, etc.).
It depends on *why* it stops. If it stops because of lack of resources,
(a depth bound, say) or because "this variation doesn't look promising"
(selective search), then you are correct.
>... Thus using A-B pruning, your program might
>misjudge a position and discard (prune) it, when in reality it is favorable
>for the opponent.
"Thus"? What "thus"? A-B pruning discards further search from a given
position *only after determining that that position is irrelevant*. If
a full-depth search performs a cutoff, it can be proven that you can
come back and draw *any* subtree you want below that node, and assign
*any* evaluations to the nodes tht you add, and a full-depth search
*without* A-B pruning will return *exactly* the same answer. It will
take longer, though.
The common thread in these objections to A-B search seems to be the
identification of A-B search with the evaluation of non-terminal nodes.
I made a similar mistake when I incorrectly identified A-B with
"brute-force". True - almost all programs which *use* A-B search also
evaluate non-terminals (and also can be characterized as brute force).
But, the three concepts are independent. It's easy to conceive of a
search program which:
*only evaluates terminal nodes
*also does selective search (perhaps only sometimes)
*and uses A-B
Let's do a taxonomy:
Evals non-terminals Selective A-B
0 Y Y Y
1 Y Y N
2 Y N Y
3 Y N N
4 N Y Y
5 N Y N
6 N N Y
7 N N N
I believe that the common case is 2 (YNY). In evaluating "common" I'm
including all homework assignments handed in in AI classes.
Next most common is probably case 0 (YYY). (Bob? would you
characterize Cray Blitz this way?)
I would call any case where "Selective = N" as "brute force", in the
context of the graph search literature. I take it to be a rough antonym
to "selective search". See Shannon. Apparently, some folk here believe
that "brute force" means "case 7 (NNN)". I disagree.
"Evals non-terminals" is almost certainly a practical consideration -
you either have enough poop to expand the graph to the end of the game,
or you don't. When you do - you only evaluate terminal nodes. When you
don't...you do the best you can. Neither decision is dependent on
whether or not you are using A-B (except that A-B will allow you to
search to the end sooner...)
I can't, offhand, think of a reason *not* to use A-B - as long as we
restrict ourselves to backing up evaluations from leaf nodes (either
terminal, or non-terminal). It is, however, true that A-B search makes
it impossible to gather certain types of information about the graph,
which might be used when you are evaluating non-terminal nodes. For
example, an A-B search has a hard time identifying "sharp lines". Sharp
lines can be dangerous when you do imperfect evaluation.
But...if you are only evaluating terminal nodes (win, loss, draw), then
I can't think of any reason *not* to use A-B. In this context, it is
simply a perfectly sound optimization.
So, it's hard to identify a use for cases 5 (NYN) or 7 (NNN). Other
than that, I think all of the other cases have their place...somewhere.
Maybe case 7 (NNN) is what you use when you have a small problem, and can't
program your way out of a paper bag. Certainly, 7 (NNN) is the one to use if
you want to demonstrate parallel speedup! But 5 (NYN)? Can't see it.
Roy Eassa
I have also implemented and taught alpha-beta pruning, and have never
had any trouble understanding it. Yet I do not agree with some of what
you have said.
First, the only "widely believed" "assumption" that I made was that chess
is a theoretical draw. I don't think most grandmasters or theoreticians
would violently argue with this.
Second, you have made an assumption that if it is Black's move, and White
has already found a drawing line, then this branch can be pruned because
it cannot lead to something better than a draw. What about zugzwang?
Just because it's Black's move doesn't mean White cannot win! You must
search to the stalemate or checkmate, i.e., to the very end of the branch
(which can involve quadrillions of quadrillions of nodes).
My belief stands that in an all-out search-to-the-mate chess-solver,
alpha-beta pruning is vastly less useful than in normal games, where you
re-order the move list after each successive ply for better pruning, and
where you have an evaluator that can return a meaningful value at any
point, not just at the checkmate or stalemate.
Roy Eassa
Roy Eassa
>But you miss the point:
>It means I *DON'T* have to try 1 a3, 1 a4, 1 b3, 1 b4, 1 c3, 1 c4, 1 d3, 1
>d4, 1 e3, 1 f3, 1 f4, 1 g3, 1 g4, 1 h3, 1 h4, 1 Na3, 1 Nc3, 1 Nf3, 1 Nh3,
>because none of them can possibly do better than the forced win I found
>with 1. e4.
Right. So, if e4 happens to lead to mate by force (unlikely), then you've
reduce the tree to 1/20 its original size. Hardly the same as reducing it
from 10^120 down to 10^60, which would be a factor of 10^60! And if e4
leads to a draw (or a Black win), then you've reduced even less. The
order of magnitude of the reduction is at most 1, not 160!
My original comment about alpha-beta pruning was to disagree with those
that claimed it would reduce solving chess from a 10^120 order problem down
to a 10^60 order problem. I won't argue that it might reduce it to a
10^119 order problem. :)
Roy Eassa
Jered M. Moses
In a previous article, m...@world.std.com (Roy Eassa) says:
>jm...@po.CWRU.Edu (Jered M. Moses) writes:
>
>
>>But you miss the point:
>>It means I *DON'T* have to try 1 a3, 1 a4, 1 b3, 1 b4, 1 c3, 1 c4, 1 d3, 1
>>d4, 1 e3, 1 f3, 1 f4, 1 g3, 1 g4, 1 h3, 1 h4, 1 Na3, 1 Nc3, 1 Nf3, 1 Nh3,
>>because none of them can possibly do better than the forced win I found
>>with 1. e4.
>
>
>Right. So, if e4 happens to lead to mate by force (unlikely), then you've
>reduce the tree to 1/20 its original size. Hardly the same as reducing it
>from 10^120 down to 10^60, which would be a factor of 10^60! And if e4
>leads to a draw (or a Black win), then you've reduced even less. The
>order of magnitude of the reduction is at most 1, not 160!
You fail to generalize here.
For example, in finding that 1 e4 is a forced win (in this hypothetical), I
have to, e.g., respond to 1. ... e5. Now, if I show that 2. a3 forces a
win for white, then I needn't examine 2 a4, 2 b3, 2 b4, 2 c3, etc., etc.,
ad nauseum, thus pruning roughly 96% of the 1. e4 e5 tree.
The same holds true in general; if any move I examine forces a winning
line, I needn't examine any further (parallel, not serial) lines.
--Jered
--
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
Wlodek Proskurowski
>
>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.
Allow me to quote from my `Fruits':
My first attempt to create an endgame dates back to my late teens while
I was a university student.
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| o | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | K | | | | |
+---+---+---+---+---+---+---+---+
| + | | | | | + | | |
+---+---+---+---+---+---+---+---+
| | k | | | | | | |
+---+---+---+---+---+---+---+---+
White to move and win
1.a3! 1.f4? K:a2 2.f5 Kb1! draws
This move makes it impossible for the bK
to retreat on b1 several moves later
1...Kb2 2.f4 K:a3 3.f5 Kb3
the best; if 3...Kb2 then 7.Qb4+;
if 3...Kb4 then 6.f8Q+, shortening the play
4.f6 a3 5.f7 a2 6.f8Q a1Q 7.Qb8+ Ka3(c1)
7...Ka2 8.Kc2 shortens the fight
8.Qa7(c7)+ Kb2 9.Qb6+ Ka3(c1) 10.Qa5(c5)+ Kb2 11.Qb4+ Ka2
11...Kc1 12.Qd2+ 13.Qc2 mate
12.Kc2! wins.
Later I found that except for the introductory move (1.a3) my position
was anticipated by Maizelis (Averbakh, v.I, Appendix, No.3).
Timothy Loesch
>In-reply-to: m...@world.std.com's message of Tue, 21 Sep 1993 18:50:34 GMT
> 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.
>
>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.
Since you deleted the explanation as to why A-B pruning doesn't always work,
I'll give you an example using the case you posed above. Given that your
computer program thinks/proves/determines it has a winning strategy for with
1. e4 It still must do a complete brute force test of all possible lines
after 1. e4 to prove this. If it stops at 25 ply or so in any variation,
there is always the possibility of not evaluating the position correctly
(space, time, force, etc.). Thus using A-B pruning, your program might
misjudge a position and discard (prune) it, when in reality it is favorable
for the opponent.
*************************************************************************
* Tim Loesch * The more numerous the laws, *
* t...@dsinc.com * the more corrupt the government. *
*************************************************************************
Jered M. Moses
In a previous article, t...@dsinc.com (Timothy Loesch) says:
>>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.
>
>Since you deleted the explanation as to why A-B pruning doesn't always work,
>I'll give you an example using the case you posed above. Given that your
>computer program thinks/proves/determines it has a winning strategy for with
>1. e4 It still must do a complete brute force test of all possible lines
>after 1. e4 to prove this.
Of course.
But you miss the point:
It means I *DON'T* have to try 1 a3, 1 a4, 1 b3, 1 b4, 1 c3, 1 c4, 1 d3, 1
d4, 1 e3, 1 f3, 1 f4, 1 g3, 1 g4, 1 h3, 1 h4, 1 Na3, 1 Nc3, 1 Nf3, 1 Nh3,
because none of them can possibly do better than the forced win I found
with 1. e4.
--Kid Kibbitz
Kenneth Sloan
>Second, you have made an assumption that if it is Black's move, and White
>has already found a drawing line, then this branch can be pruned because
>it cannot lead to something better than a draw. What about zugzwang?
>Just because it's Black's move doesn't mean White cannot win!
No. That's not what I said. I said:
0) White has a draw by playing move 1 (at the root node), based on
a search (exhaustive, if you wish) of the complete subtree starting
with move 1 (at the root node).
1) We are now examining the subtree starting with move 2 (at the root
node). [let's make it simple, by saying we are at the root of this
subtree - call it node X]
2) After searching (exhaustively, if you wish) the leftmost subtree,
beginning with Black's move 1 (at node X), we discover that the
result is also a draw.
3) We can therefore abandon further search below node X.
We have demonstrated that if the play reaches node X, then Black can get
*at least* a draw, by playing move 1 (at node X). I don't see how
zugzwang has anything to do with this. If Black were in zugzwang, then
he could not force a draw by playing move 1 (at node X). We have found
(by exhaustive search) that he *can* get a draw, if the play reaches
node X.
If it turns out that some other move by Black (at node X) gives White a
win, a rational Black will refuse to make that move, and will prefer
Move 1 (at node X) instead. A rational White will not consider move 2
(at the root node) to be *superior* to move 1 (at the root node).
Therefore, node X is irrelevant.
If it turns out that some other move by Black (at node X) gives Black a
win, a rational White will refuse to make move 2 (at the root node) and
will prefer move 1 (at the root node). Therefore, node X is irrelevant.
If it turns out that some other move by Black (at node X) gives Black a
draw, a rational Black will not view this as in any way *superior* to
move 1 (at node X). Similarly, a rational White will not view this as
in any way *superior* to move 1 (at the root node). White will continue
to be perfectly happy with move 1 (at the root node). Therefore, node X
is irrelevant.
OK - that's what I said. Now, please tell me what result you can
possibly find, in the subtree rooted at X (after already proving that
move 1 by Black (at node X) leads to a draw), that will affect White's
choice of move (at the root node). I think I've covered "Black wins",
"White wins", and "draw". Is there some other case that I've missed?
Or can you find an error in the logic for one of these cases?
Remember - I've stipulated that the searches I *did* do above can be
exhaustive, if you wish. The only question is whether or not it is
valid to do an alpha-cutoff at node X, after proving that move 1 by
Black (at node X) is a draw. I claim that it is, and that this will
drastically reduce the amount of work required to search *all* of the
moves (at the root node). Earlier, you claimed (I think) that under
these conditions, there would be *NO* cutoffs, and there would be *NO*
savings is search effort. I think that claim is incorrect.
Now...where are those folks who claim that alpha-beta is "just common
sense"? I don't think Ray lacks "common sense". Really. I don't!
Kenneth Sloan
>jm...@po.CWRU.Edu (Jered M. Moses) writes:
>
>
>>But you miss the point:
>>It means I *DON'T* have to try 1 a3, 1 a4, 1 b3, 1 b4, 1 c3, 1 c4, 1 d3, 1
>>d4, 1 e3, 1 f3, 1 f4, 1 g3, 1 g4, 1 h3, 1 h4, 1 Na3, 1 Nc3, 1 Nf3, 1 Nh3,
>>because none of them can possibly do better than the forced win I found
>>with 1. e4.
>
>
>Right. So, if e4 happens to lead to mate by force (unlikely), then you've
>reduce the tree to 1/20 its original size. Hardly the same as reducing it
>from 10^120 down to 10^60, which would be a factor of 10^60!
True. But...if you've bought the argument about 1 e4 (Huzzah! the
wedge is in! Drive it home!) then we will trot out an argument about 1
e4 <all black moves> 2 <for each black move, the winning White move>.
The same argument will show that Alpha-Beta (and some luck on the move
ordering) will reduce the size of all these subtrees by a large
constant factor (say...20).
And...if you buy that, then we recurse to move 3, and discover that
A-B... reduces all of *those* subtrees by a large constant factor
(say...20).
And so on. See Knuth.
And...I think (but don't have a proof off hand) that the number of
cutoffs will be *larger* if the game turns out to be a draw. The flavor
of my intuition is that if the game is a win for White, then the vast
majority of the cutoffs will be Beta-cutoffs, with very few
Alph-cutoffs. conversely, similarly. But, if the result is a draw, you
will get *both* alpha- and beta-cutoffs.
Looks like a good Qualifying Exam question. Anyone got a proof? or a
disproof? This ought to be "well known" - but I confess that I don't
know it. and no..."WHAT ABOUT ZUGZWANG?" doesn't qualify as a proof,
nor a disproof.
-Ken Sloan
Andrew Koenig
> Alpha-beta search is *trivial* for those who understand it, and *magic*
> for those who don't. Trust me...I've moved more than my share of
> students from the *magic* to the *trivial* point of view. Usually, it
> takes less time than this discussion - but so it goes. I must be losing
> my touch.
I hope you don't mind if I pitch in?
Imagine you're trying to figure out what's the best move in a position.
You see one possibility, analyze it as much as you care to, and
convince yourself that making that move will win a pawn.
Not content with that, you decide to look for a better move.
You try another candidate, but notice that if you make that
second move, your opponent has a back-rank mate.
The point of alpha-beta pruning is that you can stop thinking about your
second candidate move at that point. You don't have to look at your
opponent's other replies, because the fact that your opponent can mate
you is enough to rule out the move.
More generally, you can stop looking at a candidate move as soon as
you find a reply for your opponent that is worse for you than your
winning a pawn, because you can win the pawn with your first candidate
move.
That's the whole idea.
--
--Andrew Koenig
a...@research.att.com
Lloyd Lim
>|> In article <CDpx...@fig.citib.com> gh...@fig.citib.com (Renato Ghica) writes:
>|>
>|> 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.
Well, to me "brute force" means alpha-beta, PVS, and anything else
that is identical to not pruning at all. Forward pruning or selective
search is is the opposite.
My professors use the same terminology, so does my Master's thesis,
so does all the computer chess literature I've read...
+++
Lloyd Lim Internet: l...@cs.ucdavis.edu
Lim Unlimited America Online: LimUnltd
330 W. Iris Ave. AppleLink: LimUnltd
Stockton, CA 95210-3738 CompuServe: 72647,660
Nicolo de Groot
>
> 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.
>
> 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 ;-)
>
>
> -rg
> --
>
> [the opinions above are my own!]
> "die,die, damned thread!"
> "delete *this"
Now stop shouting. It is you who is totaly confused. First of all you are wrong,
secondly even if you were right, there is no need to use a tone like that.
Let me spell it out for you:
alpha-beta pruning is a method for dropping branches of a search tree, when
you know they won't bring you anything new. It gives the same result as
brute-force (see D.Knuth, the art of computer programming, Sedgewick, algorithms)
in a shorter time. In the case of solving the game to checkmate it boils down
to "if you know that white has a forced win with move a there is no point in
looking at move b,c, etc".
Now all back to human chess !
Nicolo
R. J. Pals
aspnes...@cs.yale.edu (James Aspnes) writes:
> gh...@fig.citib.com (Renato Ghica) writes:
> 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.
>
> "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.
Fine. But even if you find that 1.e4 wins, you have only reduced the size
of the problem by a little more than one order of magnitude. A billion
years of computation time is a lot less than 20 billion, granted, but it is
still a rather long time.
And at the end, if 1.e4 doesn't prove to be a win, then you need to still
be around to start the algorithm thinking about 1.d4 (or should we do 1.c4
second?).
--
Randy Pals (pa...@ipact.com) | First Law of Software Projects:
IPACT, Inc. | There is never enough time to do it right,
Automation System Integrators | but there is always enough time to do it over.
Robert Hyatt
Greetings from the "competition", Hsu.... :^)
I don't agree here. Alpha/beta is "backward" pruning and I, as a
human, don't do that. I do use forward pruning (AKA selective
searching) by culling moves that don't look reasonable, but I don't
mentally backup up scores, compare bounds, and discard moves based
on those backed up scores/bounds. I don't believe that humans of
any level use alpha/beta in their searching, I believe that it is
more of a best-first approach, with some sort of "mental bounds"
set (human branch-and-bound search?).
While you might make a case that occasionally what I (we?) do looks
like alpha/beta to a programmer, I believe that that is circumstance
specific and only "appears" to be alpha/beta. We, as humans, might
apply "alpha/beta" at selected points in the tree, but I am sure that
we don't use it throughout the search. In that case, calling it
alpha/beta is somewhat misleading.....
Bob Hyatt
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Robert Hyatt
There isn't much point continuing this argument. Once you study
alpha/beta, you will find that it is equally effective while you
are searching the "first branch". Alpha/beta finds bounds at every
node it reaches. Until you understand the algorithm, it is going to
be hard to explain why you are wrong using reasonable length posts
to this group. I will be happy to continue offline if you want to
email me.....
Bob Hyatt
Robert Hyatt
Sorry to be short, but it is time to R.T.F.M. on alpha/beta. It
DOES NOT have anything to do with search depth! It does not have
anything to do with whether we examine all branches from a node or
only a few. It simply prunes away part of any MINIMAX game tree
that don't have to be analyzed to compute the correct score. Nothing
more, nothing less.
Robert Hyatt
I would classify Cray Blitz as 0 (YYY) as you suspect. The search
has three distinct parts: (1) full-width to a fixed depth, although
this depth limit is somewhat dynamic in that certain types of moves
and/or positions cause the depth to be increased; (2) the selective
search that is applied after this full-width (AKA brute-force to
keep the discussion lively) generates moves at a node, but only
follows a very few of them including captures, certain checks and
pawn pushes, etc. Ie we throw 'em away without looking at them at
all; (3) terminal node evaluations when needed, such as for positions
that are not drawn for whatever reason, nor are mates. We *do* use
alpha/beta to search to a depth of 10 plies on the C90. I doubt we
could reach more than 5 without it (38^5=roughly 79 million nodes,
where we are searching about 1/2 to 1 million nodes per second.) It
is easy (with C-B) to prove that alpha/beta produces exactly the
same move/score as does minimax without alpha/beta, as long as you
equalize the search depth. The 5ply minimax would take us between
80-160 seconds to search. The same search with alpha/beta takes a
fraction of a second.
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Robert Hyatt
>alpha-beta pruning is vastly less useful than in normal games, where you
>re-order the move list after each successive ply for better pruning, and
>where you have an evaluator that can return a meaningful value at any
>point, not just at the checkmate or stalemate.
>
>Roy Eassa
>
I suppose that we will beat this dog till he won't hunt any more
before long. However, your belief is *wrong*. You supply the
position where C-B needs to search for a mate (don't make it a
mate in 20 so that I can do it in reasonable time) and I will
publish the node counts for a full minimax search to find the
mate and then enable alpha/beta and perform the same search. Are
you willing to suggest that the alpha/beta search won't be
significantly smaller (alpha/beta nodes = 2*sqrt(minimax nodes
roughly?) It is an easy thing to answer without all of the
speculating and bickering.....
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Robert Hyatt
See my previous post and send me the position you want to try this
on. Alpha/beta *will* drastically reduce the size of the tree
produced by the first branch, and it *will not* completely choose
to not search the remaining nodes.... Again, you are *not* describing
alpha/beta as it *does not* forward prune and eliminate a4,a3, etc
until it has searched them carefully enough to prove that they can
not possibly be better than the first branch.
Robert Hyatt
Right. C-B has a selective component. Blitz version 4 (circa
1976) was fully selective but used alpha beta, Awit/Wita (marsland
chess program) was/is fully selective and uses alpha/beta on top
of it. Alpha/beta applies to *any* minimax (zero-sum game tree)
search you develop. The only caveat is that if you have an
absolutely abysmal move ordering algorithm, alpha/beta might
actually not eliminate a single node. I ran such a test in my
Ph.D. dissertation just to get parallel performance data on such
trees, and it simply reverts to the same node count as a straight
minimax tree.
--
!Robert Hyatt Computer and Information Sciences !
!hy...@cis.uab.edu University of Alabama at Birmingham !
Timothy Loesch
>But you miss the point:
>It means I *DON'T* have to try 1 a3, 1 a4, 1 b3, 1 b4, 1 c3, 1 c4, 1 d3, 1
>d4, 1 e3, 1 f3, 1 f4, 1 g3, 1 g4, 1 h3, 1 h4, 1 Na3, 1 Nc3, 1 Nf3, 1 Nh3,
>because none of them can possibly do better than the forced win I found
>with 1. e4.
I guess this would be true given your assumption. However, I think that a
much more logical assumption would be that one opening move (1. e4) gives a
much better chances for a win (not a forced win) than any other first move.
In this case, the program would have to completely analyze all of the above
opening moves at least once, to arrive at that conclusion. And THAT would
take an incredible amount of computational power (or time).
Timothy Loesch
>>... Thus using A-B pruning, your program might
>>misjudge a position and discard (prune) it, when in reality it is favorable
>>for the opponent.
>
>"Thus"? What "thus"? A-B pruning discards further search from a given
>position *only after determining that that position is irrelevant*. If
>a full-depth search performs a cutoff, it can be proven that you can
>come back and draw *any* subtree you want below that node, and assign
>*any* evaluations to the nodes tht you add, and a full-depth search
>*without* A-B pruning will return *exactly* the same answer. It will
>take longer, though.
You are, of course, correct. I guess that the problem I had was with the
use of A-B pruning to "solve" chess. That is, to fully analyze all
possible moves in a search for checkmate, stalemate, perpetual check or
insufficent mating material. Unless I've forgotten A-B pruning from my
computer programming days, A-B pruning would not be of any use for that.
It would however be very useful for a working demonstration of the solving
formula, i.e. a chess playing computer that could not be beat. To use your
own words, "only after determining that the position is irrelevant", does
A-B pruning discards a search node. Thus, (I think I'm using thus correctly
this time) every node must be analyzed once for mates, stalemates, etc. and
after doing so, chess would be "solved", so no further use of each node tree
would be needed for the solution.
Note that I am assuming above that you are not using some position analyzer
in the program that calculates a position as a "winning, equal or losing"
at any point, using guess-timation of position, space, material, etc. The
only evaluations for node trees would be (at the end of computations) that
it wins, loses or draws. And again, I'll repeat, that such evaluations
could be greatly pruned be A-B pruning after "solving" chess, but not during
the actual solving (first pass over all nodes) process.
Roy Eassa
>... Until you understand the algorithm, it is going to
>be hard to explain why you are wrong using reasonable length posts
A bit patronizing, no? I can just picture you at the turn of the century
patiently explaining to Einstein why his theory of relatively is wrong.
(No, I'm not likening myself to Einstein, just making a gentle comment on
the attitude displayed above.) I have successfully used alpha-beta
pruning algorithms in the implementation of two different game-playing
programs (admittedly not chess, but the mechanics are the same). I
understand it just fine.
Roy
Timothy Loesch
>In article <CDryp...@world.std.com> m...@world.std.com (Roy Eassa) writes:
>>
>>Right. So, if e4 happens to lead to mate by force (unlikely), then you've
>>reduce the tree to 1/20 its original size. Hardly the same as reducing it
>>from 10^120 down to 10^60, which would be a factor of 10^60!
>
>True. But...if you've bought the argument about 1 e4 (Huzzah! the
>wedge is in! Drive it home!) then we will trot out an argument about 1
>e4 <all black moves> 2 <for each black move, the winning White move>.
>The same argument will show that Alpha-Beta (and some luck on the move
>ordering) will reduce the size of all these subtrees by a large
>constant factor (say...20).
While you are technically correct, I think Roy has a valid point. In
particular, A-B pruning has a very limited practical (not theoritical) value
in speeding up calculations during the opening of a chess game. Because
chess is not a solved game, A-B pruning isn't now used as you describe
above, and is limited to pruning through the opening dictionary for good
continuations. It does however play a big part in the middle game and
endgame, especially for mates and known endings.
Note, this is an aside about practical use of A-B pruning in chess
computers. If you wish to argue "solving" chess with A-B pruning, see my
previous two posts. Actually, this is abuse, arguments are two doors down
the hall, and you'll have to pay <-;
Roy Eassa
>In article <1993Sep22....@cis.uab.edu> sl...@cis.uab.edu (Kenneth Sloan) writes:
>You are, of course, correct. I guess that the problem I had was with the
>use of A-B pruning to "solve" chess. That is, to fully analyze all
>possible moves in a search for checkmate, stalemate, perpetual check or
>insufficent mating material. Unless I've forgotten A-B pruning from my
>computer programming days, A-B pruning would not be of any use for that.
>It would however be very useful for a working demonstration of the solving
>formula, i.e. a chess playing computer that could not be beat. To use your
>own words, "only after determining that the position is irrelevant", does
>A-B pruning discards a search node. Thus, (I think I'm using thus correctly
>this time) every node must be analyzed once for mates, stalemates, etc. and
>after doing so, chess would be "solved", so no further use of each node tree
>would be needed for the solution.
>Note that I am assuming above that you are not using some position analyzer
>in the program that calculates a position as a "winning, equal or losing"
>at any point, using guess-timation of position, space, material, etc. The
>only evaluations for node trees would be (at the end of computations) that
>it wins, loses or draws. And again, I'll repeat, that such evaluations
>could be greatly pruned be A-B pruning after "solving" chess, but not during
>the actual solving (first pass over all nodes) process.
What he said! That's what I've been trying to say! In order to discard a
branch, you must evaluate it, which means going to the very end! Only
*after* you've fininshed solving chess could you discard branches, but
then it's too late -- you're done!
Kenneth Sloan
>...
>What he said! That's what I've been trying to say! In order to discard a
No.
Roy Eassa
Lloyd Lim
>branch, you must evaluate it, which means going to the very end! Only
>*after* you've fininshed solving chess could you discard branches, but
>then it's too late -- you're done!
I know I'm going to reget jumping in...
You never search to the "very end", only to the depth of the forced outcome.
(eg - if chess is a win for White in 80 ply, you'd never have to search
past 80.) The simplest procedure (for solving, mate-finding, etc.) with
minimaxing is as follows: Minimax with a depth of 1 ply. If no forced
outcome, minimax with a depth of 2 ply. And so on.
With alpha-beta pruning, it's the same except that you search roughly
the sqrt of the number of nodes that you would with minimaxing.
Hope this explanation is good enough.
Andrew Koenig
> What he said! That's what I've been trying to say! In order to discard a
> branch, you must evaluate it, which means going to the very end! Only
> *after* you've fininshed solving chess could you discard branches, but
> then it's too late -- you're done!
Not true. Assuming you really had the time to solve chess, you could start
pruning branches the moment you found the first line that led to mate.
You couldn't prune all of them, but I think I recall that in general A-B
searching reduces the number of nodes considered from N to sqrt(N).
--
--Andrew Koenig
a...@research.att.com
Peter Rainer
> And...I think (but don't have a proof off hand) that the number of
> cutoffs will be *larger* if the game turns out to be a draw. The flavor
> of my intuition is that if the game is a win for White, then the vast
> majority of the cutoffs will be Beta-cutoffs, with very few
> Alph-cutoffs. conversely, similarly. But, if the result is a draw, you
> will get *both* alpha- and beta-cutoffs.
>
> Looks like a good Qualifying Exam question. Anyone got a proof? or a
> disproof?
I'm pretty sure that the complexity of calculating the best move
does not only depend on the value of the game alone.
Also the number of cutoffs is not a very good measure.
To my opinion the compexity depends on the destribution of
win/loss/draw nodes in the various levels of the game tree
AND the sorting of successors.
If the game happens to be a win, but the only move in the starting
position that leads to the win is considered last, then lots of
possible cutoffs are missed.
However, if the game tree is well sorted, than it should be easier to calculate
a win, because in this case only one successor of the root has to be examined.
If the result is a draw, all moves have to be examined.
In general a value of 1 (win) is always sufficient to produce a beta cutoff,
if a cutoff is possible.
Peter Mysliwietz
Dr A. N. Walker
>And...I think (but don't have a proof off hand) that the number of
>cutoffs will be *larger* if the game turns out to be a draw.
*If* chess is a forced win for White, then the minimal tree
consists of *one* branch [one which happens to lead to mate] in every
White-to-play node, but is full width in every Black-to-play node.
[This is the tree that is found by alpha-beta, and is why alpha-beta
roughly square-roots the number of nodes to be searched.]
*If* chess is a draw, then the proof of it will contain *two*
trees similar to the above -- a White proof exactly like the above
except that the White-to-play nodes now contain a move that happens
not to lose, and a Black proof that contains similarly moves that
happen not to lose for Black.
Pragmatically, the drawing tree may be easier to find, as the
precise moves are typically less critical, but we see that the pruning
factor is very similar, so the proportion of cutoffs is "the same", to
within a fudge factor. However, my intuition is that the absolute number
of cutoffs will be much, much larger, because the drawing tree will be
much, much larger. If there is a forced mate, then in the end it will
be found by winning material, attacking the king, combinations and
tactics. Forced draws, by contrast, will peter out into meaningless
endings, resolved by the 50-move rule, punctuated by meaningless pawn
moves designed just to keep the game going; they will typically take
many more ply, and so many more nodes, to resolve.
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk
Peter Rainer
> Well, to me "brute force" means alpha-beta, PVS, and anything else
> that is identical to not pruning at all. Forward pruning or selective
> search is is the opposite.
>
> My professors use the same terminology, so does my Master's thesis,
> so does all the computer chess literature I've read...
^^^^^^^^^
Well, I suggest You should start to read some ...
Sorry, I couldn't resist.
How about a citation that says that brute force is the same as alpha-beta?
Would be really interesting to see if you find an article that states that
selective search is the opposite of alpha-beta.
Peter Mysliwietz