57 views

Skip to first unread message

Oct 15, 1996, 3:00:00 AM10/15/96

to

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

Oct 15, 1996, 3:00:00 AM10/15/96

to

Think of alpha-beta as a mini-max with a fail low- fail high move

window.

--

Komputer Korner

Oct 15, 1996, 3:00:00 AM10/15/96

to

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.

Oct 15, 1996, 3:00:00 AM10/15/96

to

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

Oct 15, 1996, 3:00:00 AM10/15/96

to

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

Oct 16, 1996, 3:00:00 AM10/16/96

to

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

Oct 16, 1996, 3:00:00 AM10/16/96

to

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...

Oct 16, 1996, 3:00:00 AM10/16/96

to

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.

Oct 16, 1996, 3:00:00 AM10/16/96

to

[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

Oct 16, 1996, 3:00:00 AM10/16/96

to

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

Oct 16, 1996, 3:00:00 AM10/16/96

to

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

Oct 16, 1996, 3:00:00 AM10/16/96

to

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

Oct 16, 1996, 3:00:00 AM10/16/96

to

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

Oct 16, 1996, 3:00:00 AM10/16/96

to

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".

: 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.

: 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.

Oct 16, 1996, 3:00:00 AM10/16/96

to

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

Oct 17, 1996, 3:00:00 AM10/17/96

to

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

Oct 17, 1996, 3:00:00 AM10/17/96

to

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...

Oct 17, 1996, 3:00:00 AM10/17/96

to

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

Oct 17, 1996, 3:00:00 AM10/17/96

to

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...)

Oct 17, 1996, 3:00:00 AM10/17/96

to

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.)

Oct 17, 1996, 3:00:00 AM10/17/96

to

> <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!!!

> >

> >

> > 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.

>

> --

> Stephen B Streater

> > 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

Oct 17, 1996, 3:00:00 AM10/17/96

to

<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.

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

Oct 17, 1996, 3:00:00 AM10/17/96

to

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

Oct 17, 1996, 3:00:00 AM10/17/96

to

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..

Oct 17, 1996, 3:00:00 AM10/17/96

to

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...

Oct 17, 1996, 3:00:00 AM10/17/96

to

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

Oct 17, 1996, 3:00:00 AM10/17/96

to

> 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)

Oct 17, 1996, 3:00:00 AM10/17/96

to

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.

> >--

> >Komputer Korner

>

> >--

> >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

> 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

Oct 17, 1996, 3:00:00 AM10/17/96

to

Luis A. Dissett wrote:

>

> 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

>

> > 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

> 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

Oct 17, 1996, 3:00:00 AM10/17/96

to

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

>

> Yeah, truly amazing. You are wrong. (Try it on your calculator if the maths to

> hard...)

> hard...)

I apologize and am enrolling now in a course in how to count. I have eaten crow

on this one.

--

Komputer Korner

Oct 17, 1996, 3:00:00 AM10/17/96

to

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

Oct 17, 1996, 3:00:00 AM10/17/96

to

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?

Oct 17, 1996, 3:00:00 AM10/17/96

to

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

Oct 18, 1996, 3:00:00 AM10/18/96

to

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

Oct 18, 1996, 3:00:00 AM10/18/96

to

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?

Oct 18, 1996, 3:00:00 AM10/18/96

to

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

Oct 19, 1996, 3:00:00 AM10/19/96

to

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''

Oct 20, 1996, 3:00:00 AM10/20/96

to

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.

>

Oct 20, 1996, 3:00:00 AM10/20/96

to

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.

Oct 20, 1996, 3:00:00 AM10/20/96

to

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

Oct 21, 1996, 3:00:00 AM10/21/96

to

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.

Oct 21, 1996, 3:00:00 AM10/21/96

to

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]

> >

> > > 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.

> > > 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.

> > > 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

Oct 22, 1996, 3:00:00 AM10/22/96

to

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

Oct 22, 1996, 3:00:00 AM10/22/96

to

DF: >Don Fong (df...@cse.ucsc.edu) wrote:

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: >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:

Oct 23, 1996, 3:00:00 AM10/23/96

to

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...

Oct 23, 1996, 3:00:00 AM10/23/96

to

Oct 24, 1996, 3:00:00 AM10/24/96

to

>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

Oct 24, 1996, 3:00:00 AM10/24/96

to

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

Oct 24, 1996, 3:00:00 AM10/24/96

to

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.

Oct 24, 1996, 3:00:00 AM10/24/96

to

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...

Oct 24, 1996, 3:00:00 AM10/24/96

to

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...

Oct 25, 1996, 3:00:00 AM10/25/96

to

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

Oct 25, 1996, 3:00:00 AM10/25/96

to

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.

: 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

Oct 25, 1996, 3:00:00 AM10/25/96

to

Oct 25, 1996, 3:00:00 AM10/25/96

to

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 |

+----------------------------------------------------------------------+

Oct 25, 1996, 3:00:00 AM10/25/96

to

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.

Oct 25, 1996, 3:00:00 AM10/25/96

to

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

Oct 26, 1996, 3:00:00 AM10/26/96

to

: 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)...

Oct 26, 1996, 3:00:00 AM10/26/96

to

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

Oct 26, 1996, 3:00:00 AM10/26/96

to

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

Oct 26, 1996, 3:00:00 AM10/26/96

to

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

Reply all

Reply to author

Forward

0 new messages