Alpha-Beta explained???
Bryan
Is anyone aware of any material on the WWW which explains the Alpha-Beta
search algorithm? (I have uncovered copious amounts of very informative
publications concerned with improvements to Alpha-Beta, however it is
difficult to really apply these without first understanding the original
algorithm.)
Any and all information would be greatly appreciated.
Regards,
Bryan
Komputer Korner
Think of alpha-beta as a mini-max with a fail low- fail high move
window.
--
Komputer Korner
graham_laight
In article <3263F2...@bit.net.au>, Bryan says...
>
>Is anyone aware of any material on the WWW which explains the Alpha-Beta
>search algorithm? (I have uncovered copious amounts of very informative
>publications concerned with improvements to Alpha-Beta, however it is
>difficult to really apply these without first understanding the original
>algorithm.)
>Any and all information would be greatly appreciated.
>
>Regards,
>Bryan
I agree with Bryan. For some reason, when people try to explain alpha-beta, they
insist on making it sound more complicated than it really is.
This is my understanding - correct me if I'm wrong:
Most computer chess programs generate a game tree. That is, they make a list
of all the legal moves. For all the legal moves, they generate a list of all
the legal replies, and then all the replies to these and so on.
The trouble is, the game tree becomes unmanagebly large. If there are an average
of 36 legal replies per position, the number of leaves on the tree will be
36^n - where n is the number of plies to look ahead. A minute with your
calculator will show you how quickly the tree grows.
Alpha-beta is one way of pruning the tree (there are others).
Under alpha-beta, you choose a depth (say 3 ply) and generate a search to that
depth on a depth first basis (a breadth first search would entail looking at
all the moves at ply 1, then all the moves at ply 2 etc). As you look at
subsequent moves at depth 2, if any of them produce an evaluation that is lower
than your best depth 3 evaluation, you refuse to generate the depth 3 moves
for that position, on the grounds that you've already got a better move than
that. Hence, you've pruned off a chunk of the game tree.
Alpha-beta has the advantage of allowing you to search twice as deeply in the
same processor time, but introduces the risk of occasionaly missing good moves
whose strength does not become apparent until deeper in the search. It is
generally regarded as an algorithm that improves most chess programs
significantly.
Simon Read
GL: Graham Laight
GL> Alpha-beta has the advantage of allowing you to search twice as
GL> deeply in the same processor time, but introduces the risk of
GL> occasionaly missing good moves whose strength does not become
GL> apparent until deeper in the search.
-->
No, there is no risk with alpha-beta. It has no drawbacks!!!
It can be proved, (fairly easily) that
alpha-beta will find the same move which simple minimax will find,
but with much less processor time. (This assumes that the better
moves are usually examined first.) Alpha-beta is a way of proving
that certain subsets of the tree are irrelevant, because either:
(a) the score is too good for white, in which case black will steer
away from that part of the tree, or:
(b) the score is too good for black, in which case white will steer
away from that part of the tree one ply earlier or later.
In either case, one player is simply denying the other the option of
reaching a certain position, because he knows that the other player
has a good move available in that position.
Proving that one of the above two holds just requires comparing the
current "best-play" score with upper and lower limits, and throwing
away a whole sub-tree if even one node is outside those limits.
There are other tree search speed-up proceedures which do carry some
risk, but alpha-beta doesn't have any risk.
Simon
Robert Hyatt
Simon Read (s.r...@cranfield.ac.uk) wrote:
: GL: Graham Laight
Shoot, this was proven in the original paper. :) Alpha/Beta result ==
minimax result, just with far fewer nodes visited.
Bob
Marcel van Kervinck
GrahamLaight wrote:
: Alpha-beta has the advantage of allowing you to search twice as deeply in the
: same processor time, but introduces the risk of occasionaly missing good moves
: whose strength does not become apparent until deeper in the search. It is
: generally regarded as an algorithm that improves most chess programs
: significantly.
This is completely new to me. Could you point out the error
in Knuths 1975 proof of correctness?
Marcel
-- _ _
_| |_|_|
|_ |_ Marcel van Kervinck
|_| bue...@urc.tue.nl
Robert Hyatt
Marcel van Kervinck (bue...@asterix.urc.tue.nl) wrote:
: GrahamLaight wrote:
: : Alpha-beta has the advantage of allowing you to search twice as deeply in the
: : same processor time, but introduces the risk of occasionaly missing good moves
: : whose strength does not become apparent until deeper in the search. It is
: : generally regarded as an algorithm that improves most chess programs
: : significantly.
:
: This is completely new to me. Could you point out the error
: in Knuths 1975 proof of correctness?
The two statements are both incorrect. Alpha/beta reduces the size
of the minimax tree by approximately alpha_beta=sqrt(minimax). That
does not translate into anywhere near "twice the search depth." It
helps a whole lot of course.
It has also been proven in several papers (knuth/moore maybe?) that
alpha/beta returns exactly the same move and score as minimax, only
after visiting far fewer nodes. There is *no* error associated with
alpha/beta, only horizon effects that disturb both minimax and alpha
beta searches...
Jesper Antonsson
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>The two statements are both incorrect. Alpha/beta reduces the size
>of the minimax tree by approximately alpha_beta=sqrt(minimax). That
>does not translate into anywhere near "twice the search depth." It
>helps a whole lot of course.
Aren't you a bit self-contradictory here, Bob? What you said should
translate into something *very* near "twice the search depth".
If you can search to depth n with pure mini-max, and the number of
nodes you have to visit is approximately 36^n, then it would require
approx. sqrt(36^n) = 6^n nodes with alpa/beta, right? Now, if you did
search 36^n = 6^(2n) nodes with alpa/beta you would reach depth 2n.
Dr A. N. Walker
[Much deleted.]
I find these descriptions very hard to understand. For a
chess-player, there is a much simpler explanation of what alpha-
beta *is* [though not why it's called that, nor how to program it
in detail]. It's the simple fact that "a bad move needs only one
refutation".
For example, let us play 1 e4 Nf6; we contemplate White's
second move. There are some good moves [2 e5, 2 Nc3, even 2 d3],
some not very good moves [2 Qf3], some quite poor moves [2 h3] and
some downright blunders [2 Ba6, 2 Qg4, 2 Qh5]. The computer will
look at *all* of them, assuming it isn't using its book. And it
doesn't matter whether it is thinking about 1 e4 and wondering how
the game will go, or is playing Black and thinking about 1 ... Nf6,
or is White and actually looking for a second move; in all cases
it will eventually look at 2 Ba6. Now there may be lots of things
that Black can now do. 2 ... d5 may be quite good, or 2 ... Nxe4;
for all we know, 2 ... g6 may lead to a forced mate in 37. All
irrelevant. As soon as we look at 2 ... Nxa6, we discover that
2 Ba6 was a bad move, and 2 ... Nxa6 is its refutation. It doesn't
matter that 2 ... bxa6 is also a refutation, and may even be better
[we can't tell without analysis]. As soon as you've found that
2 ... Nxa6 wins a piece, you can stop looking at 2 Ba6. If, as it
should be, 2 ... Nxa6 is just about the first reply you look at,
then you can dispose of 2 Ba6 in roughly 5% of the time it would
take to look at all possible Black responses.
OK, a reasonably frequent speed-up by a factor of 20 is not
to be sneezed at, but it's not that startling either. But it's much
better than that. In principle, a full search looks at *every*
possible continuation, no matter how stupid, to some chosen depth.
Alpha-beta means that you gain a considerable factor in speed at
[almost] *every* depth after *every* silly move; and since in most
positions most moves are silly, it's a *huge*, *huge* win. And
although it may not always find the *best* move, it only misses
out *after* a blunder, so it *always* finds *the* best play for both
sides. [Best here is relative, of course, to what the computer
thinks is good, not to what Kasparov might like.]
There is a nice story, which I tell my students when I'm
lecturing on this stuff. Tal once, being Tal, found a beautiful
complicated sacrifice which won his opponent's Queen. The opponent
resigned. The spectators then pointed out an even better line which
forced mate. Tal was mortified -- "How could I have missed such a
move, I should have been more careful", etc. But I prefer to think
that he was using alpha-beta pruning, however imperfectly. He only
needed to find one way to win.
--
Andy Walker, Maths Dept., Nott'm Univ., UK.
a...@maths.nott.ac.uk
cma...@ix.netcom.com
hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>It has also been proven in several papers (knuth/moore maybe?) that
>alpha/beta returns exactly the same move and score as minimax, only
>after visiting far fewer nodes.
Does anyone know of any modifications to alpha-beta that returns the
same move, but sacrifices exact knowledge of the score to further
reduce the number of nodes?
I came up with a way to do this a while ago that can reduce the nodes
of the last sibling of the search tree. Basically, if you find a
better move you need the quantitative solution unless you are at the
last sibling, in which case you can stop the search knowing the move
is better, but not by how much.
This goes against A-B in that you now want to search the second best
move first for the best A-B pruning, and the best move last to
maximize the "last sibling" pruning. (Unless someone has already
thought of this and given it a name, I call it Alpha-Beta-Omega
pruning.) It can reduce the branching factor by up to 1/2.
Chris Mayer
Stephen B Streater
In article <5436ec$e...@newsy.ifm.liu.se>, Jesper Antonsson
This is what happens - the search depth can be up to double. However,
it depends on the best moves for each player being searched first.
If you sort all moves in exactly the wrong order, then you have to
search the same number of positions as minimax.
As I seem to have been suddenly sucked into this thread, I'll point
out that the optimal branch factors of the search tree change from
n x n x n x n x ... (minimax)
to
n x 1 x n x 1 x ... (alpha beta)
So only even ply depths can give you square root.
An example of this is a 1 ply search, where all n moves are needed
to give the optimal move, not sqrt(n).
--
Stephen B Streater
Stephen B Streater
In article <3263e...@news.cranfield.ac.uk>, Simon Read> GL> Alpha-beta has the advantage of allowing you to search twice as
> GL> deeply in the same processor time, but introduces the risk of
> GL> occasionaly missing good moves whose strength does not become
> GL> apparent until deeper in the search.
> -->
> No, there is no risk with alpha-beta. It has no drawbacks!!!
>
> It can be proved, (fairly easily) that
> alpha-beta will find the same move which simple minimax will find,
> but with much less processor time.
Not true necessarily - it _will_ find a move with same score as
the best move the minimax algorithm will find though.
--
Stephen B Streater
Komputer Korner
Robert Hyatt wrote:
>
> Jesper Antonsson (d93j...@und.ida.liu.se) wrote:
> :
> : If you can search to depth n with pure mini-max, and the number of
> : nodes you have to visit is approximately 36^n, then it would require
> : approx. sqrt(36^n) = 6^n nodes with alpa/beta, right? Now, if you did
> : search 36^n = 6^(2n) nodes with alpa/beta you would reach depth 2n.
> Amazing how easy it is to forget just how efficient alpha/beta is, of
> course. :)
>
> And then there's null-move...
>
> Bob
It is amazing how many people can't add,subtract, divide and multiply
on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
So Bob, you were right in the first place.
--
Komputer Korner
Robert Hyatt
Jesper Antonsson (d93j...@und.ida.liu.se) wrote:
: hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
:
: >The two statements are both incorrect. Alpha/beta reduces the size
: >of the minimax tree by approximately alpha_beta=sqrt(minimax). That
: >does not translate into anywhere near "twice the search depth." It
: >helps a whole lot of course.
:
: Aren't you a bit self-contradictory here, Bob? What you said should
: translate into something *very* near "twice the search depth".
: nodes you have to visit is approximately 36^n, then it would require
: approx. sqrt(36^n) = 6^n nodes with alpa/beta, right? Now, if you did
: search 36^n = 6^(2n) nodes with alpa/beta you would reach depth 2n.
my error. however the real formula is:
nodes= W^(floor(d/2)) + W^(ceil(d/2))
for d even, this is 2*W^(d/2)
for d odd, this is W^(d/2) + W^(d/2+1) with exponents being integer numbers.
So, maybe "close" to double is accurate. but not *real close* because of that
2x multiplier for d even, and something even bigger for d odd. However, alpha/
beta and minimax are guaranteed to return the same value, path, and move that
leads to that path. The only risk is inherent in any tree searching paradigm,
not something caused by using alpha/beta, which is a depth-first pruning
strategy, rather than some sort of best-first pruning strategy.
Joseph McCaughan contra
Simon Read (s.r...@cranfield.ac.uk) wrote:
: GL: Graham Laight
: GL> Alpha-beta has the advantage of allowing you to search twice as
: GL> deeply in the same processor time, but introduces the risk of
: GL> occasionaly missing good moves whose strength does not become
: GL> apparent until deeper in the search.
: -->
: No, there is no risk with alpha-beta. It has no drawbacks!!!
=== 8< ============== snip ============== 8< ===
I was under the impression that *any* time pruning is used there
is some risk of missing good moves. Even DB has to prune some
stuff. An earlier post said that alpha-beta is a method of
pruning - therefore there must be a certain amount of risk
with alpha-beta.
-- Joe McCaughan
jmc...@xsvr1.cup.hp.com
: Simon
Joe Stella
Komputer Korner <kor...@netcom.ca> wrote:
>It is amazing how many people can't add,subtract, divide and multiply
>on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
>So Bob, you were right in the first place.
>--
>Komputer Korner
Yes, it's amazing. The square root of 36^n is (36^n)^(1/2). Multiply
exponents, you get 36^(n/2). This is the same as (36^(1/2))^n,
or 6^n as the original poster said.
So Bob, please come again? It seems to me that alpha-beta really
should get you to about twice the depth. If you assume that the
number of nodes searched is a^d (where d is the depth and a is any
number) and also that alpha-beta node number = square root of minimax
node number, the conclusion seems unavoidable...
Joe Stella
Robert Hyatt
Joe Stella (jo...@ultranet.com) wrote:
:
:
I responded later that this is right. Here's a simple analysis:
lets assume that we have a magic position with 16 legal moves for both
sides, for several moves.
The number of terminal nodes is:
N=W^D for minimax, where N=terminal nodes, W=branching factor and D=
depth. For this case, lets try D=2 for minimax and compute the nodes
searched:
N=16^2=256
Now lets assume our search space is fixed (because of speed) so that
we can't search more than 256 nodes. How deep can we go with alpha
beta?
N=2*W^(D/2) assuming D is even.
This gives
256=2*16^(D/2) and we want to solve for D to see how deeply Alpha/Beta
can reach given the same number of nodes searched.
first square both sides:
65536=4*16^D
Divide by 4 gives
16384=16^D
So, what power do we raise 16 to to get 16384?
16^1=16
16^2=256
16^3=4096
16^4=65536
so we get just over 3 plies now, but obviously not anywhere near 4 plies
because we can only search 1/4 of the nodes the 4 ply search will take
using alpha/beta...
So, in this case, we don't get 2x the depth, we get 1.5x the depth, which
is signficantly less.
the answer would be different for 5 plies since it is odd, but the effect is
similar...
Robert Hyatt
Joseph McCaughan contra (jmc...@cup.hp.com) wrote:
No. Forward pruning causes problems, but backward pruning does not.
Here's an example: there are three holes in the wall. I assign you the
task of sticking your hand into each hole for one minute, and then you have
to tell me which was the least unpleasant experience.
You go to hole #1 and for 1 minute, your hand is treated to a steady stream
of warm water.
you go to hole #2, you are stuck by a pin. You can instantly take your
hand out without waiting any further. Why? Because the pin was unpleasant,
much more so than the warm water, and there's no need to stick around to see
if something even worse is going to happen. That'd be stupid.
you go to hole #3. you are greeted by cool water, but it starts getting
warmer, and warmer until it gets uncomfortable. Do you wait until you
get 3rd degree burns or do you pull your hand out now? *now*... :)
notice you give me an exact answer, hole number 1 is best. You give me this
answer in less than 3 minutes because you don't take the whole minute to
reject #2 or #3. That is alpha/beta. All I need to reject a move is to know
it's worse than another move, not *exactly* how much worse, just that it's
worse.
Rearrange the holes... if you do #2 first, you have to stick it out for
the whole minute, because you have nothing to compare it to. You don't get
that savings. If good moves are searched first, you get good efficiency in
alpha/beta. If not, you get minimax efficiency. But you get the same answer
regardless...
Bob
Jesper Antonsson
In article <32654D...@netcom.ca>, Komputer Korner <kor...@netcom.ca> wrote:
>It is amazing how many people can't add,subtract, divide and multiply
>on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
>So Bob, you were right in the first place.
>--
>Komputer Korner
Yeah, truly amazing. You are wrong. (Try it on your calculator if the maths to
hard...)
Jesper Antonsson
In article <544907$i...@juniper.cis.uab.edu>, hy...@crafty.cis.uab.edu (Robert Hyatt) wrote:
>The number of terminal nodes is:
>
>N=W^D for minimax, where N=terminal nodes, W=branching factor and D=
>depth. For this case, lets try D=2 for minimax and compute the nodes
>searched:
>
>N=16^2=256
>
>Now lets assume our search space is fixed (because of speed) so that
>we can't search more than 256 nodes. How deep can we go with alpha
>beta?
>
>N=2*W^(D/2) assuming D is even.
Sorry Bob, this last formula I don't understand. How did you come to it?
Shouldn't it be:
N=(W/2)^E Where E is the new search depth (from alpha/beta).
It's the branching factor you cut in half, not search depth, and where the
factor 2 in your formula comes from I don't understand either. Have I
missed something?
(With my formula E always equals 2D if N,W are fixed.)
brucemo
> >
> > GL: Graham Laight
> > GL> Alpha-beta has the advantage of allowing you to search twice as
> > GL> deeply in the same processor time, but introduces the risk of
> > GL> occasionaly missing good moves whose strength does not become
> > GL> apparent until deeper in the search.
> > -->
> > No, there is no risk with alpha-beta. It has no drawbacks!!!
> >
> > alpha-beta will find the same move which simple minimax will find,
> > but with much less processor time.
>
> Not true necessarily - it _will_ find a move with same score as
> the best move the minimax algorithm will find though.
>
> --
> Stephen B Streater
If you traverse nodes in the same order in each case, and have a
deterministic search (no hash tables, etc.) you will find the SAME move
with alpha-beta as you do with min-max.
bruce
Stephen B Streater
> It is amazing how many people can't add,subtract, divide and multiply
> on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> So Bob, you were right in the first place.
So in the case where n=1 you are saying that sqrt(36^1) = 6^(0.5).
Personally, I had thought it was 6^1.
--
Stephen B Streater
Stephen B Streater
In article <32660D...@nwlink.com>, brucemo
<URL:mailto:bru...@nwlink.com> wrote:
>
> Stephen B Streater wrote:
> >
> > In article <3263e...@news.cranfield.ac.uk>, Simon Read
> > <URL:mailto:s.r...@cranfield.ac.uk> wrote:
> > >
> > > GL: Graham Laight
> > > GL> Alpha-beta has the advantage of allowing you to search twice as
> > > GL> deeply in the same processor time, but introduces the risk of
> > > GL> occasionaly missing good moves whose strength does not become
> > > GL> apparent until deeper in the search.
> > > -->
> > > No, there is no risk with alpha-beta. It has no drawbacks!!!
> > >
> > > It can be proved, (fairly easily) that
> > > alpha-beta will find the same move which simple minimax will find,
> > > but with much less processor time.
> >
> > Not true necessarily - it _will_ find a move with same score as
> > the best move the minimax algorithm will find though.
> If you traverse nodes in the same order in each case, and have a
> deterministic search (no hash tables, etc.) you will find the SAME move
> with alpha-beta as you do with min-max.
OK - what I meant to say was that alpha-beta isn't very useful without
sorting, which is a waste of time for mini-max. So in practice, you will
get a different answer, but only as an indirect result of alpha beta.
I use alpha-beta windowing and hash tables, so get different moves
(same score) for these reasons as well.
--
Stephen B Streater
Jesper Antonsson
In article <ant162109572%2...@surprise.demon.co.uk>, Stephen B Streater <ste...@surprise.demon.co.uk> wrote:
>As I seem to have been suddenly sucked into this thread, I'll point
>out that the optimal branch factors of the search tree change from
>
> n x n x n x n x ... (minimax)
>to
> n x 1 x n x 1 x ... (alpha beta)
>
>So only even ply depths can give you square root.
>
>An example of this is a 1 ply search, where all n moves are needed
>to give the optimal move, not sqrt(n).
Yes, that's about correct. I did a study on "best case" alpha/beta and
it seems that even search depths (d), given a "mini-max" branching
factor n, require about (d/2+1) * n^(d/2) terminal nodes to be
evaluated.
If the search depth is odd, it's required approximately n^((d+1)/2)
terminal nodes. But here there is a term k*n^((d-1)/2) where k
get larger with increased depth.
Numerically, with a branching factor 36, we have exactly: (best case)
d nodes nodes div by 36^(d/2) nodes div by 36^((d+1)/2)
1: 36 1.0
2: 71 2.0
3: 1331 1.0
4: 3,816 2.9
5: 50,401 1.1
6: 183,961 3.9
7: 1,947,996 1.2
8: 8,386,631 5.0
9: 76,566,491 1.3
10: 370,098,576 6.1
I hope the table is readable..
Robert Hyatt
Stephen B Streater (ste...@surprise.demon.co.uk) wrote:
: In article <32660D...@nwlink.com>, brucemo
No. You get the *same* answer, with only one exception: if two moves at
any node produce the exact same score, then reordering the moves may choose
one over the other. But *only* if the score is equal...
Luis A. Dissett
In article <32654D...@netcom.ca> Komputer Korner <kor...@netcom.ca> writes:
[snip]
> It is amazing how many people can't add,subtract, divide and multiply
> on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> So Bob, you were right in the first place.
> --
> Komputer Korner
What I find amazing is that some people who know how to add,
substract, divide and multiply but DO NOT know how to manipulate
powers, get awarded a major in statistics ... sheeesh ...
Luis
Ernst A. Heinz
> It is amazing how many people can't add,subtract, divide and multiply
> on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
Nope, it is 36^(n/2) == 6^n.
=Ernst=
P.S.
36^n == (6^2)^n == 6^(2n) == (6^n) * (6^n)
Komputer Korner
Joe Stella wrote:
>
> Komputer Korner <kor...@netcom.ca> wrote:
>
> >It is amazing how many people can't add,subtract, divide and multiply
> >on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> >--
> >Komputer Korner
>
> exponents, you get 36^(n/2). This is the same as (36^(1/2))^n,
> or 6^n as the original poster said.
>
> So Bob, please come again? It seems to me that alpha-beta really
> should get you to about twice the depth. If you assume that the
> number of nodes searched is a^d (where d is the depth and a is any
> number) and also that alpha-beta node number = square root of minimax
> node number, the conclusion seems unavoidable...
>
> Joe Stella
I guess I will have to go back to basic math class. Sorry!!!!!
--
Komputer Korner
Komputer Korner
Luis A. Dissett wrote:
>
> In article <32654D...@netcom.ca> Komputer Korner <kor...@netcom.ca> writes:
> [snip]
>
> > on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> > So Bob, you were right in the first place.
> > --
> > Komputer Korner
>
> substract, divide and multiply but DO NOT know how to manipulate
> powers, get awarded a major in statistics ... sheeesh ...
>
> Luis
Okay I apologize, quit picking on me. It was late at night and the 36 looked
too inviting not to divide it up. I have sent a memo to the originator
apologizing for the mistake.
--
Komputer Korner
Komputer Korner
Jesper Antonsson wrote:
>
> In article <32654D...@netcom.ca>, Komputer Korner <kor...@netcom.ca> wrote:
> >It is amazing how many people can't add,subtract, divide and multiply
> >on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> >So Bob, you were right in the first place.
> >--
> >Komputer Korner
>
> hard...)
I apologize and am enrolling now in a course in how to count. I have eaten crow
on this one.
--
Komputer Korner
Kelly Harrelson
The real risk in alpha-beta (and min-max) is in the evaluation
function. How good it is it? Ideally, if it were perfect,
you wouldn't have to look very deep (if at all) in the game tree.
- Shane
Urban Koistinen
Komputer Korner (kor...@netcom.ca) wrote:
KK> Robert Hyatt wrote:
KK> >
KK> > Jesper Antonsson (d93j...@und.ida.liu.se) wrote:
KK> > :
KK> > : If you can search to depth n with pure mini-max, and the number of
KK> > : nodes you have to visit is approximately 36^n, then it would require
KK> > : approx. sqrt(36^n) = 6^n nodes with alpa/beta, right? Now, if you did
KK> > : search 36^n = 6^(2n) nodes with alpa/beta you would reach depth 2n.
KK> > Bo Hyatt wrote
KK> > Amazing how easy it is to forget just how efficient alpha/beta is, of
KK> > course. :)
KK> >
KK> > And then there's null-move...
KK> >
KK> > Bob
KK> It is amazing how many people can't add,subtract, divide and multiply
KK> on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
I think you meant to write 36 instead of the last 6.
Or did you mean to include the effect of null moves?
Null moves ain't quite as reliable as alpha-beta is.
KK> So Bob, you were right in the first place.
No, The Square root of 36^n IS always 6^n BUT IS NOT
36^(n/2) except for even nand so you are very wrong.
I don't think negative depths work very well at all.
KK> Komputer Korner
Integers Integrity Intelligence Ignorance Iterative,
:-) Urban.K...@abc.se - e...@algonet.se a flame?
Stephen B Streater
In article <5458vg$u...@juniper.cis.uab.edu>, Robert Hyatt
<URL:mailto:hy...@crafty.cis.uab.edu> wrote:
>
> Stephen B Streater (ste...@surprise.demon.co.uk) wrote:
> : OK - what I meant to say was that alpha-beta isn't very useful without
> : sorting, which is a waste of time for mini-max. So in practice, you will
> : get a different answer, but only as an indirect result of alpha beta.
> :
> : I use alpha-beta windowing and hash tables, so get different moves
> : (same score) for these reasons as well.
> No. You get the *same* answer, with only one exception: if two moves at
> any node produce the exact same score, then reordering the moves may choose
> one over the other. But *only* if the score is equal...
This is what I have a lot, as my scores are quite quantised.
--
Stephen B Streater
Simon Read
No, alpha-beta is legitimate pruning with no mistakes. Here's a
simple example:
If I make move A, my opponent will checkmate me. I don't care what
other moves he can make, because I know that he can checkmate me,
so I'm not going to give him/her that choice.
Therefore, once I've discovered the checkmate, I prune the
alternatives to checkmate.
Less extreme examples of this occur all the time, and are
incorporated into the alpha-beta algorithm.
Simon
john quill taylor
Simon Read <s.r...@cranfield.ac.uk> wrote:
>...
>hahahaha ha ha ha hahaha ha hahaha haha
>..but KK does a good chess column, so I'll forgive him.
You'll forgive HIM? HIM!? Why, you've ruined my weekend... ;)
__
john quill taylor / /\
writer at large / / \
Hewlett-Packard, Storage Systems Division __ /_/ /\ \
Boise, Idaho U.S.A. /_/\ __\ \ \_\ \
e-mail: jqta...@hpdmd48.boi.hp.com \ \ \/ /\\ \ \/ /
Telephone: (208) 396-2328 (MDT = GMT - 6) \ \ \/ \\ \ /
Snail Mail: Hewlett-Packard \ \ /\ \\ \ \
11413 Chinden Blvd \ \ \ \ \\ \ \
Boise, Idaho 83714 \ \ \_\/ \ \ \
Mailstop 852 \ \ \ \_\/
\_\/
"When in doubt, do as doubters do." - jqt -
haiti, rwanda, cuba, bosnia, ... we have a list,
where is our schindler?
Simon Read
KK: Komputer Korner <kor...@netcom.ca>
KK> It is amazing how many people can't add,subtract, divide and multiply
KK> on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
hahaha ha ha ha hahaha ha ha haha
YOU CAN NOT BE SERIOUS.
Substitute n=1 and you get (from above)
KK> The Square root of 36 IS NOT 6 BUT IS 6^(1/2)
hahaha ha ha hah Komputer Korner, did you do basic maths?
The square root of 36^n is 36^(n/2) which is 6^n
Go and check a few examples on a calculator.
It is amazing how many people who say "It is amazing how many people
can't add, subtract, divide and multiply" can't add, subtract, divide
or multiply.
hahahaha ha ha ha hahaha ha hahaha haha
..but KK does a good chess column, so I'll forgive him.
Simon
Don Fong
In article <5453r3$m...@oden.abc.se>, Urban Koistinen <m10...@abc.se> wrote:
>No, The Square root of 36^n IS always 6^n BUT IS NOT
>36^(n/2) except for even nand so you are very wrong.
oh come on. the formula -is- true for all real n,
given the usual real number definitions of these operations.
remember that b^a=exp(a*ln(b)) .
sqrt(36^n) = (36^n)^(1/2) = 36^(n/2)
it doesn't matter whether n is even, odd, positive, negative,
irrational, or whatever. just to make this clear, by sqrt(x)
i mean a number y such that x=y^2 .
>I don't think negative depths work very well at all.
negative n works just fine in the formula. (:-)
that is not to say that the formula has anything to
do with chess programming.
--
don fong ``i still want the peace dividend''
John Luebs
No, the sqrt of 36^n is 36^(n/2) !
Stephen B Streater <ste...@surprise.demon.co.uk> wrote in article
<ant171127b49%2...@surprise.demon.co.uk>...
> In article <32654D...@netcom.ca>, Komputer Korner
> <URL:mailto:kor...@netcom.ca> wrote:
>
> > It is amazing how many people can't add,subtract, divide and multiply
> > on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> > So Bob, you were right in the first place.
>
Urban Koistinen
Don Fong (df...@cse.ucsc.edu) wrote:
DF: Urban Koistinen <m10...@abc.se> wrote:
DF: >No, The Square root of 36^n IS always 6^n BUT IS NOT
DF: >36^(n/2) except for even nand so you are very wrong.
DF: oh come on. the formula -is- true for all real n,
DF: given the usual real number definitions of these operations.
DF: remember that b^a=exp(a*ln(b)) .
DF: sqrt(36^n) = (36^n)^(1/2) = 36^(n/2)
I don't believe in real numbers in general.
As in computer chess, computations are made
almost exclusively with integer values, odd
numbers behave different from what we would
expect.
DF: it doesn't matter whether n is even, odd, positive, negative,
DF: irrational, or whatever. just to make this clear, by sqrt(x)
DF: i mean a number y such that x=y^2 .
No, you mean a non-negative number y.
Peter Osterlund
On Thu, 17 Oct 1996, Komputer Korner wrote:
> Joe Stella wrote:
> >
> > Komputer Korner <kor...@netcom.ca> wrote:
> >
> > >It is amazing how many people can't add,subtract, divide and multiply
> > >on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> > >So Bob, you were right in the first place.
> >
> > Yes, it's amazing. The square root of 36^n is (36^n)^(1/2). Multiply
> > exponents, you get 36^(n/2). This is the same as (36^(1/2))^n,
> > or 6^n as the original poster said.
>
> I guess I will have to go back to basic math class. Sorry!!!!!
Maybe you'll have to go back to basic logic class too. :) Even if your
square root calculation had been correct, your conclusion that "Bob was
correct in the first place" would still be invalid. With your square root
formula alpha-beta would let you search almost 4x the depth of minimax,
while Bob claimed you wouldn't even reach 2x the depth of minimax.
--
Peter Österlund Email: peter.o...@mailbox.swipnet.se
Sköndalsvägen 35 f90...@nada.kth.se
S-128 66 Sköndal Homepage: http://home1.swipnet.se/~w-15919
Sweden Phone: +46 8 942647
Don Fong
In article <54dq6s$e...@oden.abc.se>, Urban Koistinen <m10...@abc.se> wrote:
>Don Fong (df...@cse.ucsc.edu) wrote:
>DF: Urban Koistinen <m10...@abc.se> wrote:
>DF: >No, The Square root of 36^n IS always 6^n BUT IS NOT
>DF: >36^(n/2) except for even nand so you are very wrong.
>
>DF: oh come on. the formula -is- true for all real n,
>DF: given the usual real number definitions of these operations.
>DF: remember that b^a=exp(a*ln(b)) .
>
>DF: sqrt(36^n) = (36^n)^(1/2) = 36^(n/2)
>
>I don't believe in real numbers in general.
>As in computer chess, computations are made
>almost exclusively with integer values, odd
>numbers behave different from what we would
>expect.
look, you made a pedantic claim that the formula was -very wrong-.
if you want to issue pedantic corrections to others, then it behooves
you to explicitly state your underlying assumptions. if you want
your claim to apply only to the natural numbers (eg), then you should
have said so explicitly. you don't believe in real numbers, but you
believe people are somehow able to psychically understand your peculiar
beliefs without your having to state them? (:-)
>DF: it doesn't matter whether n is even, odd, positive, negative,
>DF: irrational, or whatever. just to make this clear, by sqrt(x)
>DF: i mean a number y such that x=y^2 .
>
>No, you mean a non-negative number y.
yes, the formula is still true, even allowing y to be negative,
as long as you are consistent in your interpretation of sqrt and ln.
sqrt(36^n) = 36^(n/2)
you are right that it would have been better to specify the positive
branch, for concreteness.
again, i am not claiming the formula has any valid bearing on
chess programming. but the formula itself is still valid.
Luis A. Dissett
In article <32669D...@netcom.ca> Komputer Korner <kor...@netcom.ca> writes:
> Luis A. Dissett wrote:
> >
> > In article <32654D...@netcom.ca> Komputer Korner <kor...@netcom.ca> writes:
> > [snip]
> >
> > > on this newsgroup. The Square root of 36^n IS NOT 6^n BUT IS 6^(n/2).
> > > So Bob, you were right in the first place.
> > > Komputer Korner
> >
> > What I find amazing is that some people who know how to add,
> > substract, divide and multiply but DO NOT know how to manipulate
> > powers, get awarded a major in statistics ... sheeesh ...
> >
> > Luis
>
>
> Okay I apologize, quit picking on me. It was late at night and the 36 looked
> too inviting not to divide it up. I have sent a memo to the originator
> apologizing for the mistake.
OK, ok, apologies accepted! Peace?
> --
> Komputer Korner
Luis
cma...@ix.netcom.com
m10...@abc.se (Urban Koistinen) wrote:
>No, The Square root of 36^n IS always 6^n BUT IS NOT
>36^(n/2) except for even nand so you are very wrong.
>I don't think negative depths work very well at all.
Excuse me, but n can be any integer fraction or decimal, even or odd,
positive or negtive. It even works with 0!
Chris Mayer
Urban Koistinen
DF: >DF: Urban Koistinen <m10...@abc.se> wrote:
DF: >DF: >No, The Square root of 36^n IS always 6^n BUT IS NOT
DF: >DF: >36^(n/2) except for even nand so you are very wrong.
DF: >
DF: >DF: oh come on. the formula -is- true for all real n,
DF: >DF: given the usual real number definitions of these operations.
DF: >DF: remember that b^a=exp(a*ln(b)) .
DF: >
DF: >DF: sqrt(36^n) = (36^n)^(1/2) = 36^(n/2)
DF: >
DF: >I don't believe in real numbers in general.
DF: >As in computer chess, computations are made
DF: >almost exclusively with integer values, odd
DF: >numbers behave different from what we would
DF: >expect.
DF: look, you made a pedantic claim that the formula was -very wrong-.
Sorry, I meant to be silly, not pedantic.
The formula was also very wrong for other reasons than my silly one.
DF: if you want to issue pedantic corrections to others, then it behooves
DF: you to explicitly state your underlying assumptions. if you want
DF: your claim to apply only to the natural numbers (eg), then you should
DF: have said so explicitly. you don't believe in real numbers, but you
DF: believe people are somehow able to psychically understand your peculiar
DF: beliefs without your having to state them? (:-)
By reading my signature you might have gotten a clue.
Reason I don't believe in real numbers is I don't understand them.
I hope this may change some day, so I know them to be or not.
DF: >DF: it doesn't matter whether n is even, odd, positive, negative,
DF: >DF: irrational, or whatever. just to make this clear, by sqrt(x)
DF: >DF: i mean a number y such that x=y^2 .
DF: >
DF: >No, you mean a non-negative number y.
DF: yes, the formula is still true, even allowing y to be negative,
DF: as long as you are consistent in your interpretation of sqrt and ln.
DF: sqrt(36^n) = 36^(n/2)
DF: you are right that it would have been better to specify the positive
DF: branch, for concreteness.
DF: again, i am not claiming the formula has any valid bearing on
DF: chess programming. but the formula itself is still valid.
In rgcc I always assume context is computer chess.
Negative node counts always mean the program is buggy.
Rerun of signature:
Robert Hyatt
Tom Johnson (kom...@netcom.com) wrote:
: Robert Hyatt (hy...@crafty.cis.uab.edu) wrote:
:
: : No. Forward pruning causes problems, but backward pruning does not.
:
: : Here's an example: there are three holes in the wall. I assign you the
: : task of sticking your hand into each hole for one minute, and then you have
: : to tell me which was the least unpleasant experience.
:
: : You go to hole #1 and for 1 minute, your hand is treated to a steady stream
: : of warm water.
:
: : you go to hole #2, you are stuck by a pin. You can instantly take your
: : hand out without waiting any further. Why? Because the pin was unpleasant,
: : much more so than the warm water, and there's no need to stick around to see
: : if something even worse is going to happen. That'd be stupid.
:
: : you go to hole #3. you are greeted by cool water, but it starts getting
: : warmer, and warmer until it gets uncomfortable. Do you wait until you
: : get 3rd degree burns or do you pull your hand out now? *now*... :)
:
: : notice you give me an exact answer, hole number 1 is best. You give me this
: : answer in less than 3 minutes because you don't take the whole minute to
: : reject #2 or #3. That is alpha/beta. All I need to reject a move is to know
: : it's worse than another move, not *exactly* how much worse, just that it's
: : worse.
:
: : Rearrange the holes... if you do #2 first, you have to stick it out for
: : the whole minute, because you have nothing to compare it to. You don't get
: : that savings. If good moves are searched first, you get good efficiency in
: : alpha/beta. If not, you get minimax efficiency. But you get the same answer
: : regardless...
:
: : Bob
:
: Hello Bob,
:
: I am new to this newsgroup and trying to follow this thread. Your analogy
: is interesting, but how does this pertain to chess where you go thru
: 'pain' to get the 'reward'. Let's say you you have to sacrifice a rook to
: open a line for your bishop that will not pay off for several moves.
: Wouldn't a program using this method say, "Hey, I lost a rook with no
: equivalent material exchange." and simply end this search line?
:
: As a programmer interested in possibly exploring this arena, it is
: imperative that I understand this from the beginning. Thanks in advance.
:
: Regards,
:
: Tom
Exactly correct. The *only* way this can happen is for either (a) the
search actually sees that giving up the rook results in gaining a rook
(or more) later in the search; or (b) the evaluation (positional) can
produce scores large enough to outweigh the material value of a rook
(or a pawn, or whatever.)
The search (alpha/beta) has nothing to do with speculative sacrifices,
it is simply a graph (tree) traversal algorithm that finds the best
path from the root to the most promising looking endpoint that it can.
Period. It avoids looking at branches that are unnecessary to determine
what is best, but it doesn't speculatively throw anything out unless it is
sure the result is not needed...
Tom Johnson
Jesper Antonsson
>Hello Bob,
>
>I am new to this newsgroup and trying to follow this thread. Your analogy
>is interesting, but how does this pertain to chess where you go thru
>'pain' to get the 'reward'. Let's say you you have to sacrifice a rook to
>open a line for your bishop that will not pay off for several moves.
>Wouldn't a program using this method say, "Hey, I lost a rook with no
>equivalent material exchange." and simply end this search line?
>
>As a programmer interested in possibly exploring this arena, it is
>imperative that I understand this from the beginning. Thanks in advance.
>
>Regards,
>
>Tom
Hi Tom!
You don't "end the search line". You always search to a specific depth.
(ok, ok, search extensions, I know)
This is an attempt to explain it. Use a pen and paper and draw a tree while
following this...
Assume that we decide to search to depth 3, and have two replies to every
move. We name the
moves A and B. If we first do A, then the first reply (also A), and call the
arising position AA.
First, AAA gets a value 1 from the position-evaluator.
AAB gets 2. White, who does half-move 1 and 3 want large values, so he would
prefer AAB. So AA get 2. If ABA gets 4, black would rather choose AA, since AB
at best results in 4.
This means A get the value 2.
BAA gets 0, BAB gets -1 => BA gets 0.
This means that B will be 0 at best, right? White would rather choose A in
this case, and position
BB and it's children don't need to be generated.
It's obvious that these cutoffs won't affect the result.
I hope you could follow my muddy explanation. Next time I'm going to draw a
gif-pic with an alpha/beta-tree and send it instead of trying to explain it
textually. :)
Regards,
Jesper
Roy Mongiovi
In article <54435j$g...@juniper.cis.uab.edu>,
Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
>If good moves are searched first, you get good efficiency in
>alpha/beta. If not, you get minimax efficiency. But you get the same answer
>regardless...
Not to be too much of a stickler, but alpha-beta does not guarantee
that you get the same answer. It guarantees that you get an answer
with the same *score* as the full minimax search. Exactly which of
equivalently scored moves you get depends on your code and the move
ordering....
--
Roy J. Mongiovi System Support Specialist IV Information Technology
Georgia Institute of Technology
Tough are the souls that tread the knife's edge Atlanta, Georgia 30332-0715
Jethro Tull - "Passion Play" r...@prism.gatech.edu
Komputer Korner
Robert Hyatt wrote:
> snipped
>
> Exactly correct. The *only* way this can happen is for either (a) the
> search actually sees that giving up the rook results in gaining a rook
> (or more) later in the search; or (b) the evaluation (positional) can
> produce scores large enough to outweigh the material value of a rook
> (or a pawn, or whatever.)
>
> The search (alpha/beta) has nothing to do with speculative sacrifices,
> it is simply a graph (tree) traversal algorithm that finds the best
> path from the root to the most promising looking endpoint that it can.
> Period. It avoids looking at branches that are unnecessary to determine
> what is best, but it doesn't speculatively throw anything out unless it is
> sure the result is not needed...
The example of a rook is not the best. He should have used a minor
piece sacrifice. The reason is, is that I have investigated all the
piece sacrifices in opening chess history that are still unclear and
I have never found one where a whole rook deficit was stable. In other
words, there is never enough positional compensation for the rook and
either the rook sacrifice was in reality just a combination or the
sac was not successful against best play. In the few sacrifices with a
rook that are stable, there is at least 1 pawn in exchange for the rook.
I found over 150 positions from opening theory that are still playable
for both sides and that involve at least the sacrifice of a minor piece
for one or more pawns and in rare cases other sac situations like 2
minors for a queen. Of the total of approx. 150 sacs, I found only 3
that had a materiel difference of 3 points or 4 points. I have also
found 3 positions in chess opening theory that are still unclear and
that involve a 3 pawn sacrifice. So this tends to put a limit on
how much positional compensation can actually be.
were 3 pawn sacrifices.
--
Komputer Korner
The komputer that couldn't kompute the square root of
36^n.
Robert Hyatt
Komputer Korner (kor...@netcom.ca) wrote:
I was thinking, in the case of a rook, he was talking about a simple
exchange, RxN for example. That's much more common than Bxh7 since
the exchange (while the same material points) is not so bad if your
bishop is good, and there are no open files for the opposing rook...
Robert Hyatt
Roy Mongiovi (r...@prism.gatech.edu) wrote:
: In article <54435j$g...@juniper.cis.uab.edu>,
: Robert Hyatt <hy...@crafty.cis.uab.edu> wrote:
: >If good moves are searched first, you get good efficiency in
: >alpha/beta. If not, you get minimax efficiency. But you get the same answer
: >regardless...
:
: Not to be too much of a stickler, but alpha-beta does not guarantee
: that you get the same answer. It guarantees that you get an answer
: with the same *score* as the full minimax search. Exactly which of
: equivalently scored moves you get depends on your code and the move
: ordering....
: --
Depends. Logically if you search the nodes in the same order with
both minimax and alpha / beta, you get the same score, the same
move, the same PV, exactly. If you fritz around with move ordering,
that won't happen, however. Of course, minimax can also return a
different move/PV with the same score if you change the move ordering
so this is not a bug or disadvantage...
Tom Johnson
Nice analysis. Apparently my choice of the word sacrifice was
innappropriate for what i was thinking. Seems i should have chosen the
word combination as in the game I was reviewing, the loss of the rook led to
a forcing of mate or greater material gain 3 or 4 moves ahead.
I still don't see why a search engine would find this unless searching
all possible combinations. Seems as if any pruning at all could overlook
the 'right' play. What am I missing?
Thanks for your patience.
Tom
Robert Hyatt
Komputer Korner (kor...@netcom.ca) wrote:
: Tom Johnson wrote:
: > snipped
: >
: > I still don't see why a search engine would find this unless searching
: > all possible combinations. Seems as if any pruning at all could overlook
: > the 'right' play. What am I missing?
: >
: > Thanks for your patience.
: >
: > Tom
: Bob replied to you telling you that basically computers have to see the
: gains down the road or they won't sac. It is possible to write
: computers to sac for large positional compensation, but it is rare
: and difficult. The problem is that the evaluation function that
: decides on positional compensation is not as good as a GM's. It is
: the positional evaluation that allows GM's to sac a piece.
: Komputer Korner
: The komputer that couldn't kompute the square root of
: 36^n.
Or, if you take the "wild attacking Crafty" scenario from several months
back as an option, what will happen is occasionally you will play Bxg6
hxg6 Qxg6 and it will result in a crushing loss and your program looks
brilliant. The next game you play this (WchessX is quite eager to sac a
piece for two pawns around the king) and lose without incident. I can't
think of a case in recent months when WchessX pulled this off with Crafty
and won, yet I've seen many humans crumble apart, panic, and die by making
an inexact move. Sacrificing at the right moment is easy to do, but not
sacrificing at the wrong minute is really difficult... :)
Bob
Komputer Korner
Tim Mirabile
kom...@netcom.com (Tom Johnson) wrote:
>I still don't see why a search engine would find this unless searching
>all possible combinations. Seems as if any pruning at all could overlook
>the 'right' play. What am I missing?
>
>Thanks for your patience.
Ok, maybe this will help. Lets consider a three ply search, where each side has
three legal moves in each position. In the initial position "*", white can
choose between moves which lead to positions A, B, or C. If white chooses A,
then black can choose between positions A1, A2, or A3. Etc. In our static
positive evals are good for white, negative ones are good for black.
*
/ | \
/ | \
A B C
/ | \ / | \ / | \
/ | \ / | \ / | \
1 2 3 1 2 3 1 2 3
/|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\ /|\
/ | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \ / | \
A B C A B C A B C A B C A B C A B C A B C A B C A B C
Now a simple minimax search will apply the static evaluator to each of the 27
nodes at the bottom of the tree. It will apply the highest of the evaluations
of A1A, A1B, and A1C to position A1, the highest of A2A, A2B, and A2C to A2, and
so on. Then it will apply the lowest of the evaluations of A1, A2, and A3 to
position A, etc. Then it will pick the move that leads to the position A, B, or
C with highest evaluation.
Our Alpha-Beta search will be a little different. It will apply the static
evaluator to A1A, A1B, and A1C, and apply the highest evaluation to A1. Then it
will go to A2A. Now lets say A2A has a higher evaluation then A1. Node A2 will
be pruned, since regardless of what A2B and A2C evaluate to, position A2 will
have a higher evaluation than A1, and black wants to choose the lower one. Now
the search goes on to A3A. Let's assume it evaluates lower than A1. The search
goes on to A3B, which let's say is higher than A1. Then A3C will be skipped,
and the evaluation of A1 will be applied to position A, and the search will go
on to node B1A, B1B, and B1C. The highest of these are applied to B1, and if
this is _lower_ than A, then the entire node B will be pruned, and the search
will go on to C1A, etc.
All the alpha-beta search is really doing is applying some mathematical
reasoning to the search, so that if W > Z, then max(W,X,Y,...) > Z without
having to know what X,Y, etc are. Similarly, if W < Z, then min(W,X,Y,...) < Z.
Now, and I think this is what you may be missing, if you want to go on to depth
four, you have to look at the entire tree again, including the nodes you pruned
at depth three, because all those evaluations could be different.
+----------------------------------------------------------------------+
| Tim Mirabile <t...@mail.htp.com> http://www.webcom.com/timm/ |
| TimM on FICS - telnet://fics.onenet.net:5000/ PGP Key ID: B7CE30D1 |
+----------------------------------------------------------------------+
Komputer Korner
Robert Hyatt wrote:
snipped
> I was thinking, in the case of a rook, he was talking about a simple
> exchange, RxN for example. That's much more common than Bxh7 since
> the exchange (while the same material points) is not so bad if your
> bishop is good, and there are no open files for the opposing rook...
Yes, if he meant exchange sac, then of course, it is appropriate. I
would estimate there must be as many exchange sacs as there are piece
sacs in the opening. The only problem is getting the rook into position
to sac, but with the length of the opening increasing these days, more
and more exchange sacs are showing up. An interesting field for
further study.
Peter W. Gillgasch
Roy Mongiovi <r...@prism.gatech.edu> wrote:
> Not to be too much of a stickler, but alpha-beta does not guarantee
> that you get the same answer. It guarantees that you get an answer
> with the same *score* as the full minimax search. Exactly which of
> equivalently scored moves you get depends on your code and the move
> ordering....
This is partially true but it holds for simple minimaxing as well, if
the scores are the same it depends on your move generator 8^)
So there is really no difference.
-- Peter
Robert Hyatt
: kom...@netcom.com (Tom Johnson) wrote:
:
: >I still don't see why a search engine would find this unless searching
: >all possible combinations. Seems as if any pruning at all could overlook
: >the 'right' play. What am I missing?
: >
: >Thanks for your patience.
Here's the simple version. Suppose you look at the first move at
the root of the tree, and discover that you can play that move and
win a pawn, no matter what your opponent does. So the evaluation is
+1.000 for that move.
Now you try the second move at the root, and when you try the first
move for your opponent, you discover *he* can win a pawn no matter
what you do by playing that move. You don't need to search any more
moves for the opponent because you already know that you are going to
lose a pawn if you play the second move at the root, and if you search
more moves by the opponent, it can only get *worse*. Why bother? You
can win a pawn with (1), you lost *at least* a pawn with (2), why bother
to see how much worse (2) really is? It's already bad enough that you
won't play it. That's all you really need to know, and that's *exactly*
what alpha/beta is all about. Notice you don't discard things until you
know it is safe... which is how alpha/beta is different from "forward
pruning" (AKA selective search)...
Simon Read
TJ: kom...@netcom.com (Tom Johnson)
TJ> I still don't see why a search engine would find this unless
TJ> searching all possible combinations. Seems as if any pruning
TJ> at all could overlook the 'right' play. What am I missing?
-->
Let's be clear about what's being pruned. You're not going down
to a certain depth and deciding not to go any deeper.
You _are_ going down to a certain depth and deciding not to
go sideways. You can decide not to go sideways because you
know you have just found something which refutes a move which
was made higher up in the tree. The idea is that if a move is
bad, there are several bad consequences. You only have to
find _one_ of those bad consequences to reject the move.
Simon
Tom Johnson
Tim Mirabile (t...@mail.htp.com) wrote:
<snip fine explanation and graphics>
Thanks Tim. This makes sense. I guess what I was taking issue was a
statement made that the best move couldn't be overlooked. Apparently the
poster meant the best move as determined by the static position evaluator
and not the empirically best move.
Regards,
Tom
Robert Hyatt
Tom Johnson (kom...@netcom.com) wrote:
We were talking about the best move returned by a minimax search to
depth=N will be the same best move that's returned by an alpha-beta
search to depth=N as well, although the alpha-beta search will search
roughly 2*sqrt(nodes) where nodes= the nodes searched by the pure minimax
search... and you'll get this "same" move way faster as a result of the
tree being much smaller...
Bob