Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old August 21st 05, 12:13 PM
pd42
 
Posts: n/a
Default alpha/beta question

I want to implement different playing levels in my engine.
Is the alpha/beta algortithm suited to set a search window (e.g. alpha=-300,
beta=+300) to get the best move IN that window,
even if the overall best move has a value of, say, +400 (so outside of that
window)?
I tried it without success: if the overall best move falls outside the
search window there is no best move returned....
Any comments appreciated!


  #2   Report Post  
Old August 21st 05, 01:11 PM
Richard Delorme
 
Posts: n/a
Default

pd42 a écrit :
I want to implement different playing levels in my engine.
Is the alpha/beta algortithm suited to set a search window (e.g. alpha=-300,
beta=+300) to get the best move IN that window,
even if the overall best move has a value of, say, +400 (so outside of that
window)?


You must observe one of the following :
* real score = alpha : any legal move, including the worst one, may
be returned.
* alpha real score beta : the best move (or one of them if they
are many) is returned.
* beta = real sco any legal move with a score better than beta may
be returned. The move may be something else than the best one, but it
may be a 'good' move.

I tried it without success: if the overall best move falls outside the
search window there is no best move returned....


Do you mean no move at all or not the best one ? It should always return
a move, although not always the best one.

--
Richard
  #3   Report Post  
Old August 21st 05, 04:30 PM
Hi
 
Posts: n/a
Default

"pd42" wrote in message
...
I want to implement different playing levels in my engine.


Do so by varying the depth of the search, the time searched, quality of the
quiscience search, quality of the evaluator, etc.

Is the alpha/beta algortithm suited to set a search window (e.g.
alpha=-300, beta=+300) to get the best move IN that window,
even if the overall best move has a value of, say, +400 (so outside of
that window)?


The alphabeta is designed to get the move within the window. Trying to get
a move outside of the window doesn't make too much sense, except as a method
to prune away bad moves.

You can use windows in an AB search. (And other types of search
algorithms.) That's called 'aspiration' search and is quite common. If the
move falls outside of the window, you have to research. If it falls inside
the window, then you save time.

If you truely want 'second best' moves, then you'd have to find the best
move and keep track of the second best, and possibly research it if needed.
It'll actually be time consuming.

The nature of alphabeta with minimax (or rather NegaMax, since nobody uses
minimax anymore) is to *maximize* the score. What you are wanting kind of
goes against what the algorithm is designed to do. Therefor you are
fighting it and the AlphaBeta algorithm to try and do something they don't
want to do.

Not really worth the effort, actually.




----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
  #4   Report Post  
Old August 21st 05, 04:46 PM
pd42
 
Posts: n/a
Default

If the move falls outside of the window, you have to research. If it
falls inside the window, then you save time.


But shouldn't you still get the PV for this window?

The nature of alphabeta with minimax (or rather NegaMax, since nobody uses
minimax anymore) is to *maximize* the score. What you are wanting kind of
goes against what the algorithm is designed to do. Therefor you are
fighting it and the AlphaBeta algorithm to try and do something they don't
want to do.


That was what I was thinking, and up to now I didn't succeed in searching
for suboptimal
moves, using a search window (at the root, for instance: alpha =-infinity,
beta=+target_score).
Would be very nice though if it works, because you could start defining the
chess program
playing levels as 'play for a draw', 'win in about 40 moves', 'loose in
about 80 moves', etc
(independent of the opponent's strength, to a certain extend).
Thanks anyhow for your comment, but I still don't fully understand why it
cannot be done with AB.


  #5   Report Post  
Old August 21st 05, 05:13 PM
Hi
 
Posts: n/a
Default

"pd42" wrote in message
...
If the move falls outside of the window, you have to research. If it
falls inside the window, then you save time.


But shouldn't you still get the PV for this window?


No, because the nature of the AB just says that *some* move fell outside the
window, causing a cutoff (which means the rest of the moves weren't
searched.)

That's not the same as it returning the 2nd best move.

The only way it could return the 2nd best move is if it searched all of the
moves and then picked the second best. But that's not the way the AB works.
It only looks for *any* move that causes a cutoff. That implicitly cuts off
anything that isn't 'best'. For the stuff that got cut off, all you can say
is that it was bad enough to cause a cutoff. Beyond that, you just don't
know why.

Because of the essentially random nature of the move generator, you the
moves are searched at random. The second move it tries wont be the 'second
best move', so since it didn't search all the moves, there's no way for it
to say that a move is second best.

(yes yes, move sorting means the moves aren't truely random. They tend to
be 'strongly ordered', with the 'best' move being first about 90%+ of the
time. But that's just for search time improvements. As far as the AB is
converned, the moves it tries are random and one is as good as the next
until proven otherwise.)

The nature of alphabeta with minimax (or rather NegaMax, since nobody
uses minimax anymore) is to *maximize* the score. What you are wanting
kind of goes against what the algorithm is designed to do. Therefor you
are fighting it and the AlphaBeta algorithm to try and do something they
don't want to do.


That was what I was thinking, and up to now I didn't succeed in searching
for suboptimal
moves, using a search window (at the root, for instance: alpha =-infinity,
beta=+target_score).


Another approach would be to generate your moves. Search each of them to a
*short* distance (say 3-4 ply). And then pick the second or third best move
that way.

It wont be accurate, but since you are wanting 'second best' moves anyway,
it might be good enough.

Still, the best way is to just control the search depth & time, simplify the
evaluator, and so on, to give different qualities of play.


Would be very nice though if it works, because you could start defining
the chess program
playing levels as 'play for a draw', 'win in about 40 moves', 'loose in


You can do most of those by setting goals in the evaluator. Give a draw a
very desirable score, and the program will aim for it.

Code the evaluator to give a large bonus for 'winning' (however you want to
define it) at around 40 moves, and it'll try to achive that.

about 80 moves', etc
(independent of the opponent's strength, to a certain extend).
Thanks anyhow for your comment, but I still don't fully understand why it
cannot be done with AB.


Because for you to chose the second best move, you would need to know what
the scores are for *every* move at that particular point. If you don't know
every score, then how can youpossibly pick the second best?

You could do that with the minimax / negamax. It searches every single node
and never does a cutoff.

But the AB, Negascout, etc. etc. are all designed, repeat *designed*, to
find the best move, and do so by skipping anything lest than best.

Since they are designed to cause a cutoff *without* searching all the moves,
you never have any way of saying what the second best move is. The
algorithm just does not know. It (and the minimax / negamax) working
recursively against itself. It's trying to find the best for both sides.

In some cases, it knows (because of the bounds) that a particular move will
cause a cutoff. That it wont be picked. So it can quit searching. Because
of that, at that level and above, you can never know how good it might have
been or what the second best move would have been.

You have incomplete information. All you can say is that the score was high
enough or low enough to cause a cutoff.


It's a lot easier to find the 'best' move than the second best move. To put
it another way, it's easier to prove that every other move is inferior to
this move, than it is to find out how inferior they are. (This is called
the minimax wall, and refers to the amount of search effort involved.)



*IF* you are only searching 2 ply, then there is enough information to pick
the second best.

But at deeper searches, there just isn't enough info.

Try drawing out a tree by hand. Just to keep things simple, do a branching
of 3 to a depth of 4. Give the bottom positions random scores. (Somewhat
related scores, like in a real tree, would be better, but rand should be
good enough for the discussion.)

If you try to search it by hand, using negamax & AB, you'll discover you
simply can't pick the second best move because you are cutting off parts of
the tree (AB cutoffs) that might possibly contain the second best score.




----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----


  #6   Report Post  
Old August 21st 05, 06:10 PM
pd42
 
Posts: n/a
Default


If the move falls outside of the window, you have to research. If it
falls inside the window, then you save time.


But shouldn't you still get the PV for this window?


No, because the nature of the AB just says that *some* move fell outside
the window, causing a cutoff (which means the rest of the moves weren't
searched.)

That's not the same as it returning the 2nd best move.


But I don't want the 2nd best move, just the best move that falls in the
search window that I
provide at the root, I really don't care if it's the 2nd, 3rd or 4th or
worse move...

The only way it could return the 2nd best move is if it searched all of
the moves and then picked the second best. But that's not the way the AB
works. It only looks for *any* move that causes a cutoff. That implicitly
cuts off anything that isn't 'best'. For the stuff that got cut off, all
you can say is that it was bad enough to cause a cutoff. Beyond that, you
just don't know why.


It's OK if some good moves are cut off, because they were too good anyhow
(=outside my root window).


You can do most of those by setting goals in the evaluator. Give a draw a
very desirable score, and the program will aim for it.


Seems a lot of extra work if it chould be done by the existing search
algorithm (alpha-beta).

Because for you to chose the second best move, you would need to know what
the scores are for *every* move at that particular point. If you don't
know every score, then how can youpossibly pick the second best?


Again, I am *not* interested in the 2nd best, nor do I want a score for all
moves.

But the AB, Negascout, etc. etc. are all designed, repeat *designed*, to
find the best move, and do so by skipping anything lest than best.


But they do this with alpha and beta as bounds! The function of these 2
parameters is to
provide the information to the search algorithm where the resulting score/PV
should be,
it should search between alpha and beta.


  #7   Report Post  
Old August 21st 05, 06:49 PM
Hi
 
Posts: n/a
Default

"pd42" wrote in message
...

But I don't want the 2nd best move, just the best move that falls in the
search window that I


That could be the second best move, or whatever. That was why you are doing
a windowed search.

A search window will only return the true score *if* the best score is
within the windows.

Othewise, due to the alpha-beta and the negamax, it'll return the score of
the one that causes *a* cutoff.


Sorry, but what you are wanting, just doesn't work for how the alphabeta
algorithms work. It just is not designed to find that kind of score...

works. It only looks for *any* move that causes a cutoff. That
implicitly cuts off anything that isn't 'best'. For the stuff that got
cut off, all you can say is that it was bad enough to cause a cutoff.
Beyond that, you just don't know why.


It's OK if some good moves are cut off, because they were too good anyhow
(=outside my root window).


But because of the way the alpha-beta works, if *any* score is outside the
window, it'll cause a cutoff. Because of the negamax & AB framework, that's
just how they work.

You can do most of those by setting goals in the evaluator. Give a draw
a very desirable score, and the program will aim for it.


Seems a lot of extra work if it chould be done by the existing search
algorithm (alpha-beta).


Not really!

You obviously don't have much experience with chess / game programming.

Doing the way above (which, admittedly, is simplified somewhat!) will cause
the program to work just like it normally would.

What you are wanting to do will actually cause the program to take even
longer!

Again, that's the nature of the AB. All the AB cares about is that *some*
move causes a cutoff. It tries to find the best move because that's what
the minimax is telling him to do.

As I mentioned before, the 'minimax wall' shows that it takes a heck of a
lot less effort to simply prove that all other moves are inferior, than it
does to find out how good / bad they really are.

Considering there is only one 'best' move, it's a lot easier to find that
one best than it is to find the second best or any move within a particular
score range.

Finding a move within a certain window would mean you'd have to examine all
of the moves. Simplying knowing that one is bad isn't enough.


Because for you to chose the second best move, you would need to know
what the scores are for *every* move at that particular point. If you
don't know every score, then how can youpossibly pick the second best?


Again, I am *not* interested in the 2nd best, nor do I want a score for
all moves.


But what you are wanting to do is equivalent to that.


But the AB, Negascout, etc. etc. are all designed, repeat *designed*, to
find the best move, and do so by skipping anything lest than best.


But they do this with alpha and beta as bounds! The function of these 2
parameters is to
provide the information to the search algorithm where the resulting
score/PV should be,
it should search between alpha and beta.


Not exactly.

The bounds don't *control* the score that gets returned.

They are set based on the scores that get returned.


You've been thinking that those bounds are what controls the scores that get
returned. And that by controlling those bounds, you can control what score
gets returned.

It doesn't work that way. In fact, it's the opposite way. The scores that
get returned control the bounds!

The bounds progressively get set closer and closer to the 'true' score (by
the search process itself) and by doing so, it helps weed out scores that
can't be any better than what has already been found.


(Even with aspiration search and minimal window searches, such as negascout,
you set the bounds to what you expect the score to be. If you are wrong,
you have to research. Those methods are done *only* for performance
reasons. At no time are you actually in control of the bounds.)


Think of this... You are wanting the control the score...

You have a choice a two moves...

1) you checkmate your oponent.

2) you make an insigificant move. This is within your bounds.

In option 2, your oponent has two choices.

a) make an insigificant move. This is within your bounds.

b) check mate you.

You are wanting the score to be within a certain bounds. You want to make
option 2 and for your oponent to make option 'a'

But the reality is that your oponent is going to do the best he can. He'll
go for move 'b'.

This is a bit simplistic, but it shows that you can't bound the search the
way you want. Your oponent is always going to be trying for the best he
can. He's not going to be concerned with moves that fall into a certain
window.

He'll maximize his score, which is what the negamax does.

And because of the way negamax and alphabeta work, you can't really control
that.







----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
  #8   Report Post  
Old August 21st 05, 07:21 PM
pd42
 
Posts: n/a
Default


Normally you start at the root by calling alphabeta with alpha=-infinity and
beta=+infinity (this is the root window).
You can see beta as a *targetscore*, and you set beta=+infinity because
(normally) you are looking for the *best* move.

BUT: if beta is not infinity (at the root) but only +100 (centipawns), I
should get the move that is closest to this score, (but not exceeding 100).


  #9   Report Post  
Old August 21st 05, 08:05 PM
Bo Persson
 
Posts: n/a
Default


"pd42" skrev i meddelandet
...

Normally you start at the root by calling alphabeta with
alpha=-infinity and beta=+infinity (this is the root window).
You can see beta as a *targetscore*, and you set beta=+infinity
because (normally) you are looking for the *best* move.

BUT: if beta is not infinity (at the root) but only +100
(centipawns), I should get the move that is closest to this score,
(but not exceeding 100).


No, you will not.

If there is a best move that is way above +100, that move will easily
reject all other moves, and you will never find out just how bad they
are.

That is the idea of the alpha-beta, you save time because you don't
have to search every move. That also means that you don't know how
good (or bad) these moves are, just that they are all worse than the
top move. There is no second best.

You might just as well do a search to find the best move, and then
chose one of the others at random.


If you want the program to not play at its maximum strength, just
limit its time. The, sometimes, it will not have enough time to find
the real best move, just one that initially looks promising.


Bo Persson





  #10   Report Post  
Old August 21st 05, 08:08 PM
Hi
 
Posts: n/a
Default


"pd42" wrote in message
...

Normally you start at the root by calling alphabeta with alpha=-infinity
and beta=+infinity (this is the root window).
You can see beta as a *targetscore*, and you set beta=+infinity because
(normally) you are looking for the *best* move.


No, beta is not a target score. It is not now nor has it ever been a
"target" score.

They are minimum and maximum bounds to the true score. Not the score that
you want, but the true score that the tree search will return.

At the root, where you pass +- infinity, you are passing the bounds of what
the "true" score is. Because you don't know any more than that.

If you try to force the bounds to a range that the true score doesn't fall
in, it will fail. (As you've discovered.)

The direction of the failure can tell you what direction you need to
research, but it can't say anything about any moves actually in it.

BUT: if beta is not infinity (at the root) but only +100 (centipawns), I
should get the move that is closest to this score, (but not exceeding
100).


Sorry, but no.

There are *two* algorithms at work here.

The alpha-beta method is *only* a pruning method to keep you from having to
search the entire tree in order to find the true score. Not the score that
you want, but the true score.

The mini-max (or nega-max) algorithm will always try to do the best move
based on the score returned by the evaluator. (And you aren't wanting the
best move!)

If you ripped out the AB and used only negamax, it would still return the
exact same score and exact same suggested move. The AB is only a pruning
method, not a search method.

(Both Negamax and Alpha-Beta are fighting you.)

The bounds *you* set in the search will try to pre-prune some moves, for
search efficiency.

The actual bounds collected during the search are what do the real work. If
they fail (because you set your initial bounds wrong), then the search
fails.

It doesn't return 'second best' or 'in the desired rangne'. It simply
fails.


As the example I gave before... Although you may be wanting a search within
the certain bounds, your opponent will be doing their best to win. And
that's what the minimax / negamax tries to do. Your bounds would cause the
search to fail.


You might be able to get the desired results from some other algorithms, but
not from negamax / alpha-beta.

And again, what you are wanting isn't really the best way to do it, anyway.

It's a lot easier to cripple the quality of play by just reducing the search
depth or the time used, modifying the evaluator, etc.

Chosing a certain window to cripple the play isn't really going to help all
that much.




----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
Dear Taylor Kingston Chess One rec.games.chess.misc (Chess General) 74 November 18th 04 01:23 AM
Ratings question; need input Eric Mark rec.games.chess.politics (Chess Politics) 5 July 15th 04 06:48 PM
Drug Testing Poll Parrthenon rec.games.chess.politics (Chess Politics) 60 December 13th 03 08:42 PM
Drug Testing Poll Isidor Gunsberg rec.games.chess.misc (Chess General) 5 December 2nd 03 03:22 AM
TD or not TD? That is the question. Miriling rec.games.chess.politics (Chess Politics) 14 October 8th 03 11:50 PM


All times are GMT +1. The time now is 09:47 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017