Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old February 13th 09, 08:54 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2008
Posts: 6
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

Hello,

In single agent branch and bound search, only a single, global, cutoff
value is used for pruning.

This got me thinking about alpha-beta in Chess (and other games).
What if these were made global (instead of stack based)? The idea
being that you (and your opponent) wouldn't explore a new path that is
worse than the best path found so far. The benefit being that this
might be a way to perform additional ("unsafe") pruning in a game
independent way. In short, a simple way to do a more selective
search.

I realize that making this change has the effect of eliminating the
fact that alpha-beta pruning is equivalent (in terms of result, not
computational expense) to straight minimax, but once again the idea
here is to perform additional pruning in an intelligent way that
allows deeper searches.

I haven't tried it, but does this idea make sense?

Thanks,
-- Greg
  #2   Report Post  
Old February 14th 09, 11:57 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2008
Posts: 116
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

wrote:
[...]
This got me thinking about alpha-beta in Chess (and other games).
What if these were made global (instead of stack based)? The idea
being that you (and your opponent) wouldn't explore a new path that is
worse than the best path found so far. The benefit being that this
might be a way to perform additional ("unsafe") pruning in a game
independent way. [...]


You sort-of can, sort-of can't, and it sort-of probably doesn't
help [at least if I've understood your notion correctly].

(a) It's easy to modify alpha-beta so as to determine efficiently
whether the current position is better or worse than some fixed value.
In such a case, alpha and beta never change [as any proposed change
would correspond to a beta cutoff], so they may as well be global. But
you don't get the current value, nor a best move. This is pretty-much
"minimal windowing", and it needs to be combined with something else to
become part of a proper search -- after which it's a Good Idea.

(b) Otherwise, you need to be able to "back out" any changes ["Oh,
this looks like a good move -- yes, better and better -- oops, I've now
seen the refutation, back to my previous idea"], so you either can't
change alpha/beta or else you really need to stack them. If you never
change them, then you don't get the benefit from improving alpha, so
your search is less efficient than standard alpha-beta for no improvement
elsewhere in the algorithm.

(c) You have a recursive procedure anyway, and the hard work is not
done when going down or back up the tree [which is where alpha/beta get
stacked and changed], but in the zillions of static evaluations at the
leaves. Almost every intuitive idea about chess programming turns out
to be wrong; despite this, my intuition says that even if you could get
your idea to work efficiently, the improvement would not be measurable.

(d) If you get a result different from straight minimax, then it isn't
merely different, it's wrong -- at least within the "standard model" of
chess programming [by which you're trying to find the best move according
to the static evaluations at whichever leaves your search goes down to].
This is probably Bad News.

(e) Nevertheless, if you have an Idea, chess programming is not like
counting angels on pin-heads, it's an absolutely practical problem. Take
one of the open source programs, change the dynamic search to include the
Idea, run a few hundred games "new vs old", and see which wins. If your
Idea loses, quietly forget it. If it wins, quietly win a tournament or
two using it, then shout it from the rooftops and become famous. If it
draws, then write a paper explaining how your Idea needs development but
shows promise, and how a Large Grant would help with this.

(f) If I've misunderstood your proposal, then (a,b,c) may not apply;
sorry. But (d,e) always apply!

--
Andy Walker
Nottingham
  #3   Report Post  
Old February 15th 09, 12:59 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Feb 2009
Posts: 1
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

a) Good point about "minimal windowing". Perhaps that's a better way
to do what
I have in mind. My idea was inspired by branch and bound search, but
now that I
think about it further, B&B is not a heuristic search so it's
completely safe
to prune based on a global cutoff value. Not so for A-B.

b) Right, you lose the ability to reconsider if you've already
adjusted global bounds. Heuristics can go wrong.

d) Well the idea is to do unsafe pruning anyway as a way of dealing
with bushy search
trees, so I'm willing to depart from the "standard model".

Thanks for your substantial reply.

-- Greg
  #4   Report Post  
Old February 15th 09, 03:21 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2008
Posts: 6
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

a) Good point about "minimal windowing". Perhaps that's a better
way
to do what
I have in mind. My idea was inspired by branch and bound search, but
now that I
think about it further, B&B is not a heuristic search so it's
completely safe
to prune based on a global cutoff value. Not so for A-B.

b) Right, you lose the ability to reconsider if you've already
adjusted global bounds. Heuristics can go wrong.


d) Well the idea is to do unsafe pruning anyway as a way of dealing
with bushy search
trees, so I'm willing to depart from the "standard model".


Thanks for your substantial reply.


-- Greg
  #5   Report Post  
Old February 15th 09, 05:52 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Sep 2007
Posts: 184
Default Game Tree Programming Idea: Selectivity via modified alpha-beta pruning

writes:

a) Good point about "minimal windowing". Perhaps that's a better
way
to do what
I have in mind. My idea was inspired by branch and bound search, but
now that I
think about it further, B&B is not a heuristic search so it's
completely safe
to prune based on a global cutoff value. Not so for A-B.


You could say that alpha-beta is what you get if you take
brand-and-bound and generalize so to be able to use if for searching a
mini-max tree. There are similarities, such as:

* Guaranteed to find the same value as if searching the full tree.
* Cutting away a huge amount of work, but still typically leaving an
exponential amount of work to be done.

Anyway, for the branch-and-bound algorithm, it can be modified to
compute approximate solutions, ie you can change the cut-off condition
so that optimal solutions are allowed to be skipped if they are just a
little better than the best solution found so far. This can
significantly reduce the number of tree nodes that have to be
searched, at the cost of losing the guarantee to find an optimal
solution.

It should be possible to generalize the "approximate B&B" algorithm to
the alpha-beta case too, by modifying the alpha/beta windows
appropriately. I can't tell if this would produce a useful algorithm
for chess though. Some things to consider:

* Can the alpha-beta window be modified at all levels in the search
tree without losing too much precision, or can you only do it at the
root level?

* How big is the speed improvement?

* Will it make the chess program stronger? Increased speed will allow
it to search deeper, but at the same time it will only be able to
compute approximate mini-max values.

Suppose you set the approximation threshold to 0.1 pawns. What will
happen? Will the program slowly lose 0.1 pawns per move until the
position is lost, or will the increased speed make it find a decisive
tactical shot that wins the game?

--
Peter Osterlund -

http://web.telia.com/~u89404340


  #6   Report Post  
Old February 15th 09, 06:58 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2008
Posts: 116
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

wrote:
b) Right, you lose the ability to reconsider if you've already
adjusted global bounds. Heuristics can go wrong.


Yep. But the question is what to do when you find that out!
In chess programming, it usually means starting on a new search with
better bounds, so a heuristic that often goes wrong had better be a
massive improvement when it goes right.

d) Well the idea is to do unsafe pruning anyway as a way of dealing
with bushy search
trees, so I'm willing to depart from the "standard model".


Unsafe pruning is likely to be a disaster. You don't usually
get any measure of *how* unsafe the pruning has been. If you thereby
drop your queen once per game, you will lose every game against a
decent opponent no matter how much deeper you have been able to look.
In general, it seems to be a lot better to stay safe, and instead to
prune to search some things more deeply and some things less.

But, as always, the proof of the pudding is in the eating. If
you have an idea, try it! The alpha-beta part of a typical open-source
engine is only a few lines of code, so it's easy to play with it, and
see whether your program plays better or worse.

--
Andy Walker
Nottingham
  #7   Report Post  
Old February 15th 09, 10:28 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2008
Posts: 6
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

On Feb 15, 1:58*pm, Andy Walker wrote:
* * * * Unsafe pruning is likely to be a disaster.


Would you say that's also true for "selective deepening" as well?
What I'm unclear on is whether you call
it "unsafe pruning" or "selective deepening" (a more accepted term/
technique?), in both cases you're intentionally "pruning" paths. The
only difference I see is that in the latter, you might decide to
search all positions to a fixed depth before pruning. Still, in both
cases pruning based on some heuristic occurs.

I would also like to add that I'm considering a larger set of games
than standard Chess. I'm also considering Chess variants and other
games with bushy trees and where some form of pruning (or selective
deepening, call it what you want) becomes necessary to in order to
search to "useful" depths.

-- Greg
  #8   Report Post  
Old February 15th 09, 11:16 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2008
Posts: 116
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

wrote:
Unsafe pruning is likely to be a disaster.

Would you say that's also true for "selective deepening" as well?


There's a difference [if only psychological] between "those
lines look as though they're not going to be interesting so I'm
going to discard them" and "those lines do look interesting, so I'm
going to analyse them much deeper". ...

What I'm unclear on is whether you call
it "unsafe pruning" or "selective deepening" (a more accepted term/
technique?), in both cases you're intentionally "pruning" paths. The
only difference I see is that in the latter, you might decide to
search all positions to a fixed depth before pruning. Still, in both
cases pruning based on some heuristic occurs.


... It's at least slightly unreasonable to call the "forward"
version "pruning" at all! But in any case, it's the "unsafe" that's
the problem. Any algorithm that discards part of the tree that may
contain the best line is dangerous. For practical games we are
constrained as to the number of nodes we have time to analyse and we
are subject to the vagaries of static evaluations -- after all, if
these were correct, we wouldn't need to analyse past depth 1. But
at least you should [surely?] strive to get a correct evaluation of
whatever part of the tree you have time to analyse -- which means, in
essence, that you must not prune anything that would not be pruned by
alpha-beta. "Shaping" the tree you search is another matter.

I would also like to add that I'm considering a larger set of games
than standard Chess. I'm also considering Chess variants and other
games with bushy trees and where some form of pruning (or selective
deepening, call it what you want) becomes necessary to in order to
search to "useful" depths.


Understood. Games with significantly greater "width" than
chess are a real pain for tree searching .... Some such games break
down into disjunctive [or nearly disjunctive] sums [cf the opening
phase in Go]; some [eg Boxes] have huge transposition possibilities;
but these bring their own problems.

--
Andy Walker
Nottingham
  #9   Report Post  
Old February 15th 09, 11:34 PM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Dec 2008
Posts: 116
Default Game Tree Programming Idea: Selectivity via modified alpha-betapruning

Peter Osterlund wrote:
Suppose you set the approximation threshold to 0.1 pawns. What will
happen? Will the program slowly lose 0.1 pawns per move until the
position is lost, or will the increased speed make it find a decisive
tactical shot that wins the game?


If you use the "wrong" alpha-beta levels, for whatever reason,
then one of two things will happen: (a) by luck, judgement or otherwise,
the "true" value of the position [as determined by the static evaluations]
is within the chosen bounds, or (b) it is outside those bounds. In case
(a), the search will go faster if the "wrong" bounds are "too narrow"
[which is, after all, the basis for "aspiration search" and for "minimal
windowing"] but slower if they are "too wide". In case (b), the *only*
information you get, in general, is that the position is at least of
value so-and-so [if better than beta] or at most of value so-and-so [if
worse than alpha]. There's no "lose 0.1 pawns per move". The evaluation
may return as 0.1 pawns below alpha, but the true value of the move that
gave that evaluation may be a queen lower, and there may be no move that
is better than 0.3 pawns lower. Even in time trouble, a computer can't
afford to use evaluations below alpha.

More generally, it's the play-off between (a) and (b) that makes
chess programming interesting. With care, you can get (a) most of the
time, and consequently search much faster; but you have to be prepared
for case (b) to occur, in which case there is usually little choice but
to search again with wider bounds. If 90% of your searches go twice as
fast, but 10% go twice as slow, you win ....

--
Andy Walker
Nottingham
  #10   Report Post  
Old February 16th 09, 12:04 AM posted to rec.games.chess.computer
external usenet poster
 
First recorded activity by ChessBanter: Sep 2007
Posts: 184
Default Game Tree Programming Idea: Selectivity via modified alpha-beta pruning

Andy Walker writes:

Peter Osterlund wrote:
Suppose you set the approximation threshold to 0.1 pawns. What will
happen? Will the program slowly lose 0.1 pawns per move until the
position is lost, or will the increased speed make it find a decisive
tactical shot that wins the game?


If you use the "wrong" alpha-beta levels, for whatever reason,
then one of two things will happen: (a) by luck, judgement or otherwise,
the "true" value of the position [as determined by the static evaluations]
is within the chosen bounds, or (b) it is outside those bounds. In case
(a), the search will go faster if the "wrong" bounds are "too narrow"
[which is, after all, the basis for "aspiration search" and for "minimal
windowing"] but slower if they are "too wide". In case (b), the *only*
information you get, in general, is that the position is at least of
value so-and-so [if better than beta] or at most of value so-and-so [if
worse than alpha]. There's no "lose 0.1 pawns per move". The evaluation
may return as 0.1 pawns below alpha, but the true value of the move that
gave that evaluation may be a queen lower, and there may be no move that
is better than 0.3 pawns lower. Even in time trouble, a computer can't
afford to use evaluations below alpha.


I don't think you understood my idea, probably because I didn't
explain it well enough.

Suppose you search the PV using standard alpha-beta, and suppose it
returns a score of 1.00 up to the root. Using normal alpha-beta, the
remaining moves for the root position would be searched with a window
such that the search terminates as soon as the score is known to be =
1.00. My idea is to terminate as soon as the score is known to be =
1.10. You can obviously miss the best move in that case, but not if
the best move is a lot better than the best move you found so far.

After finishing such a search, you can be sure that the computed score
is at most 0.10 lower than the mini-max score.

(It starts to get complicated though, if you do the same thing at
other levels than the root level in the search tree.)

--
Peter Osterlund -
http://web.telia.com/~u89404340
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
Is the initial position in chess a mutual Zugswang? [email protected] rec.games.chess.misc (Chess General) 66 April 4th 07 02:14 PM
Interview with CJA Award Winning Historian in The Chess Journalist The Historian rec.games.chess.politics (Chess Politics) 215 November 16th 06 08:34 PM
How to use the rules of the Socratic Method in our search for truth [email protected] rec.games.chess.politics (Chess Politics) 0 March 7th 06 09:20 PM
Tablebases and decidability [email protected] rec.games.chess.analysis (Chess Analysis) 35 February 9th 06 04:12 PM


All times are GMT +1. The time now is 01:34 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