Argument against Alpha-Beta searching
Robert Hyatt
Mike Stoker (sto...@logica.com) wrote:
: In my opinion, it is now time to admit that the search tree
: theory, and in particular improving the evaluation function of Alpha-Beta
: searching can NEVER be a practical way for computers to beat high quality
: players of the GM variety, when playing certain types of position
: requiring long-range planning. The reason for this is that evaluation
: functions simply cannot take into account the "plan" behind a position.
: Let me give an example.
: Supposing white, as a human, can see by looking at the board that the
: black king has little protection, and that if he could get his rooks
: doubled on the seventh rank he would have excellent winning chances.
: However, in order to obtain his rooks in this position, he needs to
: sacrifice a couple of pawns to open files (4 moves), completely
: reposition his rooks (7 moves) and essentially, play moves leading up to
: the doubling of his rooks which appear to make his position worse.
: Now a human can see this plan from the current position after a moments
: thought, and realises that the short-term consequences of a bad position
: are outweighted by the clear cut winning plan which he has formulated,
: which may take as many as 20ply to complete. However, by a tree search
: technique using Alpha-Beta pruning, the tree would be pruned when it came
: to evaluating leaves containing bad positions, as decided by the
: "evaluation function". Consequently, the tree could not be followed to a
: deep enough level to realise that the plan was excellent, and hence play
: the correct moves. Kasparov would see the plan instantly.
: Need I say more?
Don't buy the above. It seems obvious, but it's way too simplistic. Most
likely, by "giving up a couple of pawns, and taking a few moves to relocate
the rooks, you give the opponent several moves to do things as well. Against
deep searchers such a superficial plan will simply return your head in a bucket.
You can certainly develop such plans, but only a very few people can do this
with any regularity because of the extreme tactical difficulties a program
like DB presents. You can't afford *one* imprecise move or it will come
pouring thru that hole. So superficial plans run into practical obstacles
unless you are *very* careful in implementing the plan.
Also, if it takes you N moves to work on getting the rooks to the 7th, you'd
better be sure that there's not some subtle defense that shuts the door at the
last minute, something that has happened to many a IM and GM in tournament
games with computers. Because now you are two pawns down, with your plan in
a plastic bag. All long-range attacks against the king don't work for this
very reason. I've seen crafty survive some truly vicious attacks, because
it was careful, didn't get psyched-out, and played good moves. I've seen
it lose many too, of course.
The problem with beating computers is more difficult than you might imagine.
It's a problem for all of the computers, to be sure, but it's not easy for
a human to do. For example, you play program X and it keeps losing because
it likes to play it's queen over to b3 or b6 or something and get it cut
off from being able to defend on the kingside, and it loses. The programmer
can fix this. And it takes a strong player a few games to figure out that
"hey, this thing won't play the queen to the offside, apparently because it
is afraid of kingside attacks. So I'll feint over there, then start a
queen-side action, and the queen won't come over to help until it's too
late. That's where Kasparov comes in, I believe. The last DB game was
one of these... Attack on the king side, then attack on the queenside,
then back to the kingside, with black always out of sync with what's going
on... But there aren't many Kasparov's however... :)
Mike Stoker
cut: [My argument against tree searching]
I'm afraid this is a completely falacious argument. What you are
essentially saying is that long-term planning is useless becuase of
tactical responses, and that therefore its better to play for short term
tactics. This is completely untrue. Whilst one must at all times be
aware of tactical possibilities, a long-term plan is *essential*,
especially in "quieter" positions where there are fewer tactics around.
Whilst I am by no means saying that *I* could develop a plan to beat Deep
Blue, the idea of a plan would still be correct. The methodology that you
are suggesting, of "woodpushing" pieces into better positions is
something which is erradicated from human players during their first few
games. We are always taught that a bad plan is better than no plan at
all. What is required is a strong tactical search engine, for short term
traps and tactics only, with the main chess engine being based on plans.
As a contributer to this newsgroup rightly pointed out a couple of days
ago, strategy is deep tactics. I would go further, and say that tactics
are simply shallow strategy, in that even the most complex tactics are
really just plans. e.g. plan is to mate the king - to accomplish this
several sub-plans must be achieved such as a) diverting queen from
protection of king b) removing pawn cover of king etc etc
What it all comes down to is that computers *need* a long-term plan!
Robert Hyatt
Mike Stoker (sto...@logica.com) wrote:
: I'm afraid this is a completely falacious argument. What you are
: essentially saying is that long-term planning is useless becuase of
: tactical responses, and that therefore its better to play for short term
: tactics.
I'm not saying that at all. Just that your idea of "4 moves to lose
two pawns to open files, 7-8 moves to relocate rooks, few more moves to
prepare things" makes it look easy. It's not. That's a GM skill level
if we are talking about DB. It's a strong IM skill level if we are talking
about micros...
: This is completely untrue. Whilst one must at all times be
: aware of tactical possibilities, a long-term plan is *essential*,
: especially in "quieter" positions where there are fewer tactics around.
: Whilst I am by no means saying that *I* could develop a plan to beat Deep
: Blue, the idea of a plan would still be correct. The methodology that you
: are suggesting, of "woodpushing" pieces into better positions is
: something which is erradicated from human players during their first few
: games. We are always taught that a bad plan is better than no plan at
: all. What is required is a strong tactical search engine, for short term
: traps and tactics only, with the main chess engine being based on plans.
I don't disagree with your "plan" analogy at all. I'm simply saying that at
the level DB plays at, the "implementation details" are much harder to produce
than the plan itself. Also, to say that computers don't have plans is not
a completely correct analysis. They might not have *one* long-range plan, but
they often have several semi-plans. Such as creating a passed pawn. Then once
it is created, preparing for advancing it is another. Some (WchessX comes to
mind) seem to intentionally prepare king-side attacks, and do it quite well.
Others seem to "plan" on simply playing solid chess and waiting for an opening
to present the basis for a "plan" of sorts to exploit that mistake...
: As a contributer to this newsgroup rightly pointed out a couple of days
: ago, strategy is deep tactics. I would go further, and say that tactics
: are simply shallow strategy, in that even the most complex tactics are
: really just plans. e.g. plan is to mate the king - to accomplish this
: several sub-plans must be achieved such as a) diverting queen from
: protection of king b) removing pawn cover of king etc etc
: What it all comes down to is that computers *need* a long-term plan!
I fully agree here. I'm not opposed to your view at all. As you might notice,
I toss out the example of how often I see the Stonewall attack work against
micros. What I don't often say is how often if fails miserably, even when
carried out by a GM, because one mistake is all it takes. The bottom line
is that a computer presents "an extremely rigorous verification of the
efficacity of your plan"... :) any minor oversight and you might suffer
seriously from it. In human vs human games it is quite different. Once both
sides "see" the plan, one tries to carry it out, the other tries to prevent it
from being carried out. The computer simply "thinks outside that box" and
frequently notices something that was missed by the "planner"...
Mike Stoker
In my opinion, it is now time to admit that the search tree
theory, and in particular improving the evaluation function of Alpha-Beta
Mike Stoker
Robert Hyatt wrote:
>
> I fully agree here. I'm not opposed to your view at all. As you might notice,
> I toss out the example of how often I see the Stonewall attack work against
> micros. What I don't often say is how often if fails miserably, even when
> carried out by a GM, because one mistake is all it takes. The bottom line
> is that a computer presents "an extremely rigorous verification of the
> efficacity of your plan"... :) any minor oversight and you might suffer
> seriously from it. In human vs human games it is quite different. Once both
> sides "see" the plan, one tries to carry it out, the other tries to prevent it
> from being carried out. The computer simply "thinks outside that box" and
> frequently notices something that was missed by the "planner"...
I can't really think of any argument here, as our points of view are so
similar.
All I will say is that there are often cases where it is not necessary
to look at
tactics (and hence perfrom a game tree search) because of the quietness
of the
position. In this case GMs spend 90% of their time looking at possible
plans, and
only around 10% of their time looking for tactics. Maybe my previous
example of
sacrificing a couple of pawns was a bit extreme for the point being
made, as in this
case you have to make damn sure that the plan is going to work.
With respect to tactics/plans, does anyone know if there are currently
any programs which
can work backwards from their analysis of a position. For example if
the computer
"sees" what would be a good plan, which doesn't work due to some tactic,
can it then
play a move to counter that tactic. Does it exist for tactics? For
example during
game tree search if a particular branch would produce a high score
except for a
countering move in the middle of the tactical fire, can it infer a
preparation move?
I believe this type of inference could drastically reduce the size of
tree searches.
Paul Jeremy
In article <1997032000222412764@[194.121.104.138]>,
gil...@ilk.de (Peter W. Gillgasch) wrote:>[ the following stuff is a reply to Bob: ]
>
>> I'm afraid this is a completely falacious argument. What you are
>> essentially saying is that long-term planning is useless becuase of
>> tactical responses, and that therefore its better to play for short term
>
>I think we can agree that you have to survive the tactics, no matter how
>nice your plan is.
>
>> Whilst one must at all times be
>> aware of tactical possibilities, a long-term plan is *essential*,
>> especially in "quieter" positions where there are fewer tactics around.
>> Whilst I am by no means saying that *I* could develop a plan to beat Deep
>> Blue, the idea of a plan would still be correct. The methodology that you
>> are suggesting, of "woodpushing" pieces into better positions is
>> something which is erradicated from human players during their first few
>> games.
>
>make small "atomic" steps into the right direction, those steps are
>called "moves" and those are essentially "woodpushing pieces". So
>essentially chess playing is "woodpushing". The reasons *why* you push
>the wood there can be very complex and deep, though.
>
I totally agree that the plan is made from atomic steps, but these steps
should be suggested by the plan, rather than the plan being suggested by the
steps. It can be compared to any large project (software development?) - you
have to know what your overall goal is to implement the steps to achieve -
implementing ideal programs which are inconsistent with your overall goal will
lead to a failed project.
>> We are always taught that a bad plan is better than no plan at
>> all. What is required is a strong tactical search engine, for short term
>> traps and tactics only, with the main chess engine being based on plans.
>
>Hear hear. There is a solution to this requirement 8^) We could argue
>about which is the "main chess engine" however...
>
>One question. The title of the post implies that you want to do away
>with A-B searching (which I think is a darned stupid idea, like removing
>the engine from a car to avoid accidents). Now you are saying that a
>planning facility coupled with a deep searcher is needed. First, this
>seems like a contradiction to me. Second, are you simply making a point
>for the formerly traditional "high level evaluation and planning"
>component coupled with a full width brute force searcher that execute in
>disjunct time, or are you making a point for a goal directed searcher
>(planning and searching at the same time).
>
>If you make a point for the first scenario, you can have a coffee here
>8^) If you make a point for the second scenario you can drink coffee
>with Botvinnik 8^)
>
OK, OK - I went overboard with the title. The point I was trying to make was
that a deep search is not required, although I'm not specifically against the
alpha-beta algorithm. In almost all situations, we should need to search only
200-300 (roughly!) positions for a move, and far less where tactics are slight
(in some cases I believe we wouldn't need a search at all). This would then
be somewhere approaching human chess players. The vast bulk of the time should
be spent assessing the current position and making plans.
So I'm making the point for a third scenario, "high level evaluation and
planning" coupled with an intellegent search engine, which is used *solely* to
investigate immediate tactics in a position, and to validate each phase of the
plan.
I know I'm not making myself too clear - its getting a bit too late for me
here in London!!
Paul Jeremy
Ooops - I forgot to mention I am using someone elses terminal!
Mike Stoker
Robert Hyatt
Mike Stoker (sto...@logica.com) wrote:
: Robert Hyatt wrote:
: >
: > I fully agree here. I'm not opposed to your view at all. As you might notice,
: > I toss out the example of how often I see the Stonewall attack work against
: > micros. What I don't often say is how often if fails miserably, even when
: > carried out by a GM, because one mistake is all it takes. The bottom line
: > is that a computer presents "an extremely rigorous verification of the
: > efficacity of your plan"... :) any minor oversight and you might suffer
: > seriously from it. In human vs human games it is quite different. Once both
: > sides "see" the plan, one tries to carry it out, the other tries to prevent it
: > from being carried out. The computer simply "thinks outside that box" and
: > frequently notices something that was missed by the "planner"...
: I can't really think of any argument here, as our points of view are so
: similar.
: All I will say is that there are often cases where it is not necessary
: to look at
: tactics (and hence perfrom a game tree search) because of the quietness
: of the
: position. In this case GMs spend 90% of their time looking at possible
: plans, and
: only around 10% of their time looking for tactics. Maybe my previous
: example of
: sacrificing a couple of pawns was a bit extreme for the point being
: made, as in this
: case you have to make damn sure that the plan is going to work.
I agree that some positions are funny to watch, searching zillions of nodes
when there's not a single tactical thread on the entire board. However, and
there's a big *however*... it is very hard to determine there's no tactics
until you search and find that out. Of course, it is then hard to avoid the
search since it's already done. :)
I tend to think you are from what I'll call the "old AI school" that
believed/believes that the computer has to do it like the human does. It's
a good goal, but one unreachable for the forseeable future. Main reason is
we simply don't yet know how the human does it. and until we do, I don't know
how to write the specs for such a program... :)
: With respect to tactics/plans, does anyone know if there are currently
: any programs which
: can work backwards from their analysis of a position. For example if
: the computer
: "sees" what would be a good plan, which doesn't work due to some tactic,
: can it then
: play a move to counter that tactic. Does it exist for tactics? For
: example during
: game tree search if a particular branch would produce a high score
: except for a
: countering move in the middle of the tactical fire, can it infer a
: preparation move?
: I believe this type of inference could drastically reduce the size of
: tree searches.
Yes. Blitz IV uses this sort of trick. I called it a "causality analyzer".
I wrote a bunch of selective search code that was very good at finding
tactical moves against the other side, but it didn't do the inverse very
well. So I (in 1975/6/7) didn't try to write the inverse function. I
simply "passed", let my opponent find the good moves, then I analyzed what
he found to see what I could do to thwart them. Got some great tactical
chess from that program, but some blatant positional blunders because it
was typically searching only 5-6 moves at each ply, max... often much less.
Peter W. Gillgasch
Mike Stoker <sto...@logica.com> wrote:
> cut: [My argument against tree searching]
[ the following stuff is a reply to Bob: ]
> I'm afraid this is a completely falacious argument. What you are
> essentially saying is that long-term planning is useless becuase of
> tactical responses, and that therefore its better to play for short term
> tactics. This is completely untrue.
I think we can agree that you have to survive the tactics, no matter how
nice your plan is.
> Whilst one must at all times be
> aware of tactical possibilities, a long-term plan is *essential*,
> especially in "quieter" positions where there are fewer tactics around.
> Whilst I am by no means saying that *I* could develop a plan to beat Deep
> Blue, the idea of a plan would still be correct. The methodology that you
> are suggesting, of "woodpushing" pieces into better positions is
> something which is erradicated from human players during their first few
> games.
I think you are trivializing the idea. To implement a plan you have to
make small "atomic" steps into the right direction, those steps are
called "moves" and those are essentially "woodpushing pieces". So
essentially chess playing is "woodpushing". The reasons *why* you push
the wood there can be very complex and deep, though.
> We are always taught that a bad plan is better than no plan at
> all. What is required is a strong tactical search engine, for short term
> traps and tactics only, with the main chess engine being based on plans.
Hear hear. There is a solution to this requirement 8^) We could argue
about which is the "main chess engine" however...
One question. The title of the post implies that you want to do away
with A-B searching (which I think is a darned stupid idea, like removing
the engine from a car to avoid accidents). Now you are saying that a
planning facility coupled with a deep searcher is needed. First, this
seems like a contradiction to me. Second, are you simply making a point
for the formerly traditional "high level evaluation and planning"
component coupled with a full width brute force searcher that execute in
disjunct time, or are you making a point for a goal directed searcher
(planning and searching at the same time).
If you make a point for the first scenario, you can have a coffee here
8^) If you make a point for the second scenario you can drink coffee
with Botvinnik 8^)
> As a contributer to this newsgroup rightly pointed out a couple of days
> ago, strategy is deep tactics. I would go further, and say that tactics
> are simply shallow strategy, in that even the most complex tactics are
> really just plans. e.g. plan is to mate the king - to accomplish this
> several sub-plans must be achieved such as a) diverting queen from
> protection of king b) removing pawn cover of king etc etc
I think you go way overboard here. Things like "mating the king",
"winning material" etc are no real plans. Those are the reasons behind
plans. I think such things should be should be left to a hell of a
"device driver" type of program that accidently does a tree search and
looks what is "doable".
> What it all comes down to is that computers *need* a long-term plan!
I agree, but still I am not sure what you are talking about. Please
explain.
-- Peter
May God grant me the serenity to accept the things I cannot change,
courage to choke the living shit out of those who piss me off,
and wisdom to know where I should hide the bodies...
Dan Thies
On Wed, 19 Mar 1997 22:55:34 -0800, Mike Stoker <sto...@logica.com>
wrote:
>All I will say is that there are often cases where it is not necessary
>to look at
>tactics (and hence perfrom a game tree search) because of the quietness
>of the
>position. In this case GMs spend 90% of their time looking at possible
>plans, and
>only around 10% of their time looking for tactics. Maybe my previous
>example of
>sacrificing a couple of pawns was a bit extreme for the point being
>made, as in this
>case you have to make damn sure that the plan is going to work.
Mike:
I have been working on it from "your" angle for a few years now. It
is absolutely necessary to do a game tree search in order to select a
move. It is precisely the type of "quiet" positions you describe
which cause my program to call for searches most often.
Let's take for example your typical "isolated d pawn" middlegame out
of the QGD. White normally has a choice of a couple of plans,
likewise for black. Even if the positions just *screams* for a
minority attack, you can't just start one up without:
(1) verifying that the kingside will last long enough to get it done
(requires some searching and reasoning)
(2) confirming that you're not going to fail due to minor piece
counterplay (requires some searching and reasoning)
(3) deciding which pawn to push, etc.
(requires some searching and reasoning)
Outside of endgames, there are very few positions so quiet that you
couldn't sac a pawn and stir up some kind of trouble. I'm not a big
believer in the future of full-width searching, because you have to
give up something to gain the time needed to reason about the position
and formulate plans. But after almost 3 years, I still have a
production in my expert system that says "Do a full-width alpha-beta
search for n plies." I call this a verification search, but I don't
see the difference, other than that it is just another source of
knowledge about the position instead of the ultimate decision maker.
>With respect to tactics/plans, does anyone know if there are currently
>any programs which
>can work backwards from their analysis of a position. For example if
>the computer
>"sees" what would be a good plan, which doesn't work due to some tactic,
>can it then
>play a move to counter that tactic. Does it exist for tactics? For
>example during
>game tree search if a particular branch would produce a high score
>except for a
>countering move in the middle of the tactical fire, can it infer a
>preparation move?
>I believe this type of inference could drastically reduce the size of
>tree searches.
PARADISE did this, I do this. Hans Berliner has done this, although I
don't think that the HiTech he brought to the last ICCA World Champs
had a "causality facility." It's the only way I know of to get out of
a full-width search. Even if we do a full-width search, we can still
analyze the point in the tree where it failed, and search possible
alternatives to a greater depth. Sometimes the key to a position lies
20-30 plies down a fairly narrow line, and if you don't know *why*
your 8-ply search thinks you're losing a piece, you don't have any
chance to find out if it's right.
Dan
Vincent Diepeveen
In <5gp3a7$n...@romeo.logica.co.uk> Mike Stoker <sto...@logica.com> writes:
[About that alfabeta sucks]
>Need I say more?
We all know the depth limitation problem of brute force iterative
deepening alfabeta.
Alfabeta is knowledge independant. Alfabeta is not the problem,
the iterative deepening brute force search is the problem.
This is however also very knowledge independant.
Humans use a terrible amount of knowledge on which they seem to search.
Humans do use a knowledge based search, where programs use an almost
knowledge independant search (just few extensions require knowledge like
check extensions, and still this remains very little).
For this reason brute force is a fine algorithm, especially if you
if you take into account
the knowledge it requires.
Nullmove is another cheap improvement (although in certain positions
not correctly finding solution), which transforms things into a
giant selective search.
From the viewpoint of trying to beat the strongest humans,
there is no alternative yet. I would love to see an alternative,
but i don't have seen a serious alternative to replace the brute force
principle (searching everything) by some
simplistic selective search.
In my viewpoint the only alternative to prevent a depth limited search
is implementing strategies and knowledge. I will not try this!
All my forward pruning effords failed so far! They considerably cut the
tree size, but so far my effords had huge problems finding difficult
problems.
I'm already trying to put as much
as possible knowledge in the evaluation function. This already hard enough,
and still this evaluation remains an approximation. I think that
as soon as there are programs with very good evaluation functions,
that it will become interesting to implement a selective algorithm like
human uses (still using alfabeta cutoffs).
I think however that these good evaluation functions need something that
can discriminate between factors, and also must not be bound by an
implementation.
If i define in my evaluation program doubled pawns as being weak -0.30,
and open files being a good think: +0.10, then a program has a problem.
Doubled pawns sometimes are NOT bad. The discrimination
is the problem. Humans also have problems with this.
Grandmasters seem usually better in discriminating than expert players.
Perhaps it is just a question of good discriminating code, and better
pattern recognizers, combined with the huge amount of knowledge even
an A-class player also has?
If one can do this, i guess it is time to begin starting program
strategical ideas?
And although i will experiment with forward pruning, Diep will mainly search
brute force until that time.
Vincent
--
+----------------------------------------------------+
| Vincent Diepeveen email: vdie...@cs.ruu.nl |
| http://www.students.cs.ruu.nl/~vdiepeve/ |
+----------------------------------------------------+
Tom C. Kerrigan
Mike Stoker (sto...@logica.com) wrote:
> In my opinion, it is now time to admit that the search tree
> theory, and in particular improving the evaluation function of Alpha-Beta
> searching can NEVER be a practical way for computers to beat high quality
> players of the GM variety, when playing certain types of position
> requiring long-range planning. The reason for this is that evaluation
Ah, but it can still beat them... Yes, I can see how we need to give up a
successful approach...
> which may take as many as 20ply to complete. However, by a tree search
> technique using Alpha-Beta pruning, the tree would be pruned when it came
> to evaluating leaves containing bad positions, as decided by the
> "evaluation function". Consequently, the tree could not be followed to a
Who says? There is no one single fixed evaluation function that programs
use.
Cheers,
Tom
Kevin James Begley
Tom C. Kerrigan (kerr...@merlin.pn.org) wrote:
: Mike Stoker (sto...@logica.com) wrote:
: > In my opinion, it is now time to admit that the search tree
: > theory, and in particular improving the evaluation function of Alpha-Beta
: > searching can NEVER be a practical way for computers to beat high quality
: > players of the GM variety, when playing certain types of position
: > requiring long-range planning. The reason for this is that evaluation
: Ah, but it can still beat them... Yes, I can see how we need to give up a
: successful approach...
I wasn't planning on getting into this, but I think there's something missing
from this debate -- namely that the chief disadvantage to alpha-beta search
is that it only works for relatively easy problems. Chess, I contend, though
infinitely more complex than tic-tac-toe, involves too few decisions at each
node to be considered a good test of intelligence. The so called "old school
of AI" happens to realize that alpha-beta, while certainly a successful
approach in the area of chess (presently), is entirely unacceptable as a
means of producing intelligent machines (particularlly evident when you begin
to consider problems which require more decisions per node).
Now, I will not argue that chess programmers ought to abandon this technique,
clearly it is the most "successful" (if winning at chess is how you
define success). However, if Mike's view of success is to bring us closer
to understanding how we might create an intelligent machine, he certainly
has an excellent point.
True, we may be centuries away from the lofty goals that AI once held, but
it is important to point out that better and better alpha-beta searchers
are doing nothing to motor us toward those goals. I'm not saying that
nothing comes from this effort -- indeed, many applications have come out
of better search algorithms (and, I predict many more will in the future).
The simple truth is, chess may not be the great test of intelligence that
we once believed it would be, and therefore, it is probably too much to
expect a chess-programmer to care much about intelligence (why should he
when it plays no part in his goal to produce the best chess machine?).
Relative to the speed of computers today, chess has too few decisions per
node. So, ultimately, we must rely on brute force and a mixture of greed
algorithm and hard-wired intelligence in the evaluation functions if we
are to solve harder problems.
Ultimately, this is why Fischer's game will fail -- he has too few decisions
per node on average to fascilitate a game that puts more demands upon the
intelligence of its competitors. Capablanca's suggestion of adding a piece
or two is certainly a superior test of intelligence, though Fischer's idea
does reduce the component of memorized pregame analysis (already rampant in
chess).
Bob Hyatt described the mixed feelings he'd have if ever a computer can
clearly demonstrate superiority over a world champion at chess. There is
some debate as to what the future outlook will be if such an event takes
place. Without getting into all that, I think it would be interesting to
hear opinions on where the chess programmers will turn after they've milked
our game dry -- what game will become the next frontier in testing intellect?
: > which may take as many as 20ply to complete. However, by a tree search
: > technique using Alpha-Beta pruning, the tree would be pruned when it came
: > to evaluating leaves containing bad positions, as decided by the
: > "evaluation function". Consequently, the tree could not be followed to a
: Who says? There is no one single fixed evaluation function that programs
: use.
True, you could have full-width (read "no trace of intelligence"), or you
could have a complex evaluation function (read "hard-wired intelligence"),
but either way, somehow you come short of the mark.
Kevin.
Tom C. Kerrigan
Kevin James Begley (kjbe...@chimi.engr.ucdavis.edu) wrote:
> Tom C. Kerrigan (kerr...@merlin.pn.org) wrote:
> : Ah, but it can still beat them... Yes, I can see how we need to give up a
> : successful approach...
> I wasn't planning on getting into this, but I think there's something missing
> from this debate -- namely that the chief disadvantage to alpha-beta search
> is that it only works for relatively easy problems. Chess, I contend, though
> infinitely more complex than tic-tac-toe, involves too few decisions at each
> node to be considered a good test of intelligence. The so called "old school
> of AI" happens to realize that alpha-beta, while certainly a successful
> approach in the area of chess (presently), is entirely unacceptable as a
> means of producing intelligent machines (particularlly evident when you begin
> to consider problems which require more decisions per node).
Eh, that can be argued, seeing as "intelligence" is a really nasty word to
define. Let's say I write an expert system to play chess. Is it
intelligent? Alpha-beta haters will say yes, but I see it as just another
program that I compile and run exactly as I would my traditional program.
It's just some silly algorithm, too. How can it be any more or less
intelligent that what I have now?
Cheers,
Tom
Gerry Quinn
In article <5gsu3o$b8n$1...@mark.ucdavis.edu>, kjbe...@chimi.engr.ucdavis.edu (Kevin James Begley) wrote:
>Tom C. Kerrigan (kerr...@merlin.pn.org) wrote:
>: > In my opinion, it is now time to admit that the search tree
>: > theory, and in particular improving the evaluation function of Alpha-Beta
>: > searching can NEVER be a practical way for computers to beat high quality
>: > players of the GM variety, when playing certain types of position
>: > requiring long-range planning. The reason for this is that evaluation
>
>: successful approach...
>
>
>I wasn't planning on getting into this, but I think there's something missing
>from this debate -- namely that the chief disadvantage to alpha-beta search
>is that it only works for relatively easy problems. Chess, I contend, though
>infinitely more complex than tic-tac-toe, involves too few decisions at each
>node to be considered a good test of intelligence. The so called "old school
>of AI" happens to realize that alpha-beta, while certainly a successful
>approach in the area of chess (presently), is entirely unacceptable as a
>means of producing intelligent machines (particularlly evident when you begin
>to consider problems which require more decisions per node).
[snip]
Alpha-Beta searching has an important place in any strong chess-player's
skills, irrespective of whether the player is machine or human. And since it
is such a vital part of chess, the great superiority of machines in this area
is their biggest advantage.
By playing to that advantage, they have reached the level of the best humans.
There is no doubt that the strongest possible machine player will retain and
expand these abilities, even if other methods are added to its repertoire.
And if other methods lead to better positional evaluation functions, the
better move ordering will make Alpha-Beta all the stronger.
- Gerry
===================================================================
Mailto: ger...@indigo.ie (Gerry Quinn)
Download original Windows puzzles: http://indigo.ie/~gerryq
===================================================================
Simon Read
In article <5gsu3o$b8n$1...@mark.ucdavis.edu>, kjbe...@chimi.engr.ucdavis.edu
(Kevin James Begley) wrote:
>> The so called "old school
>>of AI" happens to realize that alpha-beta, while certainly a successful
>>approach in the area of chess (presently), is entirely unacceptable as a
>>means of producing intelligent machines (particularlly evident when you begin
>>to consider problems which require more decisions per node).
Do you mean more alternatives to choose from (e.g. 36 legal moves) ?
(My semantic quibbling, probably, but I would call this only one decision.)
There are many problem domains in "real life" (who he?) where there are
not a definite number of alternative courses of action and certainly
no way of explicitly counting the alternatives. There may be no
distinct or discrete "moves" to make, but the intelligent agent might
have to make a choice from a continuous range rather than a discrete
set. I can't see how alpha-beta would apply to this.
ger...@indigo.ie (Gerry Quinn) wrote:
> Alpha-Beta searching has an important place in any strong chess-player's
> skills, irrespective of whether the player is machine or human.
I also would choose to keep A-B, but it is only one third of a program.
The other two thirds are evaluation function and choosing which nodes
to search. I don't think that the final third is receiving enough
attention at the moment. Full-width does seem to work better than
selective at the moment, but that's because selectivity is extremely
difficult and no-one's yet demonstrated conclusively a good way to
do it.
Garry Kasparov probably uses A-B, even though he may not know it by
that name. However, Garry uses A-B on a much smaller tree. Not an
exhaustive tree, not a fixed-depth tree and not a full-width tree.
Just the _right_ tree.
I'm reminded of a song which was written by Stevie Nicks (I think)
lead singer of Fleetwood Mac.
Someone said to her, "But it's only got three chords."
She replied, "Yes, but they're the _right_ three chords."
Simon
sreadcranfieldacuk
@ . .
Amir Ban
Mike Stoker wrote:
>
[snip]
> Let me give an example.
>
> Supposing white, as a human, can see by looking at the board that the
> black king has little protection, and that if he could get his rooks
> doubled on the seventh rank he would have excellent winning chances.
> However, in order to obtain his rooks in this position, he needs to
> sacrifice a couple of pawns to open files (4 moves), completely
> reposition his rooks (7 moves) and essentially, play moves leading up to
> the doubling of his rooks which appear to make his position worse.
>
> Now a human can see this plan from the current position after a moments
> thought, and realises that the short-term consequences of a bad position
> are outweighted by the clear cut winning plan which he has formulated,
> which may take as many as 20ply to complete. However, by a tree search
> technique using Alpha-Beta pruning, the tree would be pruned when it came
> to evaluating leaves containing bad positions, as decided by the
> "evaluation function". Consequently, the tree could not be followed to a
> deep enough level to realise that the plan was excellent, and hence play
> the correct moves. Kasparov would see the plan instantly.
>
> Need I say more?
You need to say much more.
The realities of a chess game are usually different. The problem with
such a plan is that practically, to execute it you would need either:
1) Complete control of the game, preferably a rook or two up, and you
may have a superior plan such as mate-in-one.
or:
2) Your opponent fast asleep.
Even if you can play such plans, if that's your only way of winning
against a computer, you will not make more than 2 points in a 10-game
match.
Amir
ChrIsacson
<<Bob Hyatt described the mixed feelings he'd have if ever a computer can
clearly demonstrate superiority over a world champion at chess. There is
some debate as to what the future outlook will be if such an event takes
place. Without getting into all that, I think it would be interesting to
hear opinions on where the chess programmers will turn after they've
milked
our game dry -- what game will become the next frontier in testing
intellect?>>
sorry if this gets off thread, but im especially interested in the game
thoery + its advances + evolution.. chess is a two person deterministic
game w/ realtivly few ( around 40?) "single" moves moves per turn (as
oppessed to being able to make several moves per turn.. dont know the
proper terminalogy).. this doesnt even come close to what "modern" games
can handle.. for instance "Risk" by MB is a 3-6 player non-deterministic
game w/ multiple moves per turn.. while still maitaining simplicity.. each
factor can be explored in greater depth as it applies to game thoery.. >2
players is key as now colitions can be formed.. soething set theory has
helped w/ but not handled very well in games. Non-deterministic as used
here, generally refers to the randomness of the dice so probailty thoery
can help make progress here but wieghing "risk" has alot of "real-life"
applications than just this game.. also multiple moves per turn *may* be
able to be reduced to sigle moves by taking them several at a time.. but
the combinations involved (order matters in many instances) bring the
totals past 40.. also many moves are based if "if this attack is
succesful" type strategey.. again w/ implications of risk management.. so
you see the scope is wide open when it comes to other "tests of intelect"
also good stepping stone canidates are "Monoploy" due to its simplistic
random model, but diffficult valuation model due to colitions.. also "Go"
has been widely worked on because of its much greater width in moves per
turn.. another game not so well known is by Avalon Hill, "Advanced
Civilization". While AH has made good progress in the programming of its
AI its nowhere near strong enough to beat good human players.. this game
is good becuse it has great width + multiple moves per turn w/ colitions
but is completely deterministic (some players shuffle "trading" cards but
as far as i can remeber, once the order is set, it follows determined, not
random rules...) So as i see it, Game AI hasnt even come close to matching
humans in other aspects, while i agree this is a major task as many games
are complex models of life situations (not "simplistic" ones like chess)
it goes to show there are many more "hurdles" to overcome even after
*exhasting* (<- never happen chess has *way* too many combinations even
after pruning) the game of chess..
PS. like people who always wanted to know if black or white would win or
will a computer ever play "perfect" chess, i always wanted to know things
like whats the best starting place in so + so or whats the "perfect"
strategy here or there..