
Main
Date: 13 Feb 2009 12:54:58
From:
Subject: Game Tree Programming Idea: Selectivity via modified alphabeta

Hello, In single agent branch and bound search, only a single, global, cutoff value is used for pruning. This got me thinking about alphabeta 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 alphabeta 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



Date: 15 Feb 2009 14:28:47
From:
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

On Feb 15, 1:58=A0pm, Andy Walker <[email protected] > wrote: > =A0 =A0 =A0 =A0 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

 
Date: 15 Feb 2009 23:16:34
From: Andy Walker
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

[email protected] 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 alphabeta. "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


Date: 15 Feb 2009 07:21:49
From:
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

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

 
Date: 15 Feb 2009 18:58:30
From: Andy Walker
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

[email protected] 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 alphabeta part of a typical opensource 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

 
Date: 15 Feb 2009 17:52:54
From: Peter Osterlund
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta pruning

[email protected] 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 AB. You could say that alphabeta is what you get if you take brandandbound and generalize so to be able to use if for searching a minimax 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 branchandbound algorithm, it can be modified to compute approximate solutions, ie you can change the cutoff 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 alphabeta 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 alphabeta 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 minimax 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  [email protected] http://web.telia.com/~u89404340

  
Date: 15 Feb 2009 23:34:04
From: Andy Walker
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

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" alphabeta 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 soandso [if better than beta] or at most of value soandso [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 playoff 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

   
Date: 16 Feb 2009 00:04:23
From: Peter Osterlund
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta pruning

Andy Walker <[email protected] > 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" alphabeta 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 soandso [if better than beta] or at most of value soandso [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 alphabeta, and suppose it returns a score of 1.00 up to the root. Using normal alphabeta, 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 minimax 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  [email protected] http://web.telia.com/~u89404340

    
Date: 16 Feb 2009 19:20:17
From: Andy Walker
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

Peter Osterlund wrote: >> If you use the "wrong" alphabeta levels, for whatever reason, >> then one of two things will happen: [...] > I don't think you understood my idea, probably because I didn't > explain it well enough. Ah, OK. I was on the wrong lines, then; however, luckily, most of what I wrote still seems to apply! > Suppose you search the PV using standard alphabeta, and suppose it > returns a score of 1.00 up to the root. Using normal alphabeta, 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. OK. In a "straight" alphabeta search, this does indeed [I guess, though as always the proof lies in experimentation rather than intuition] save some nodes at the expense of accuracy. It's less clear that it saves nodes in some versions of minimal windowing; I'd need to think a little harder to convince myself! > After finishing such a search, you can be sure that the computed score > is at most 0.10 lower than the minimax score. OK. OTOH, if [eg in a tactical situation] your PV turns out to be a lot better than anything else, then you haven't gained anything, whereas if there are [in a positional situation] lots of moves with nearly the same value, then you have thrown away whatever positional acumen your program in fact possesses. On the third hand, I've known positions where the computer seems to be "agonising" between two lines that differ by 0.01, and you want to shake it and say "look, it really, really doesn't matter whether you play A or B, just plump for one", and in those cases it could be a big win. > (It starts to get complicated though, if you do the same thing at > other levels than the root level in the search tree.) In general, it's *harder* to do things only at the root level than everywhere  it means you need special code for that level. If I now understand you correctly, it just means replacing the code that assigns the score to alpha by code that assigns (score + 100) to alpha [if we're measuring in millipawns]. Surely someone has already tried this? If not, go ahead ...!  Andy Walker Nottingham

     
Date: 16 Feb 2009 22:21:35
From: Peter Osterlund
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta pruning

Andy Walker <[email protected] > writes: > Peter Osterlund wrote: > >> Suppose you search the PV using standard alphabeta, and suppose it >> returns a score of 1.00 up to the root. Using normal alphabeta, 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. > > OK. In a "straight" alphabeta search, this does indeed [I > guess, though as always the proof lies in experimentation rather than > intuition] save some nodes at the expense of accuracy. It's less > clear that it saves nodes in some versions of minimal windowing; I'd > need to think a little harder to convince myself! I agree. Tests are needed to find out if there will be any noticeable speedup. I know that the corresponding idea can give a very significant speedup when solving combinatorial optimization problems using branch & bound, but that doesn't automatically mean that the idea will be good for alpha beta too. >> After finishing such a search, you can be sure that the computed score >> is at most 0.10 lower than the minimax score. > > OK. OTOH, if [eg in a tactical situation] your PV turns out to > be a lot better than anything else, then you haven't gained anything, > whereas if there are [in a positional situation] lots of moves with > nearly the same value, then you have thrown away whatever positional > acumen your program in fact possesses. On the third hand, I've known > positions where the computer seems to be "agonising" between two lines > that differ by 0.01, and you want to shake it and say "look, it really, > really doesn't matter whether you play A or B, just plump for one", and > in those cases it could be a big win. A case I had in mind was this: Suppose move A, B, C, D have approximately equal score at a given search depth, but at the next higher search depth, move D reveals a new tactical possiblity, and therefore has a significantly higher score. In that case if your search order is A, B, C, D, you want to quickly dismiss B and C as "not much better than A", so that you have a bigger chance of finding the tactical opportunity in move D before the time runs out. >> (It starts to get complicated though, if you do the same thing at >> other levels than the root level in the search tree.) > > In general, it's *harder* to do things only at the root level > than everywhere  it means you need special code for that level. Sorry, I was unclear again. I meant that analyzing the approximation error is complicated, not that it is complicated to implement the idea. One can quite easily conclude that if you do this approximation (by amount "delta") at K different levels, the approximation error at the root is no more than K * delta. However that quickly becomes too large to be practical if you intend to do it at all levels in the search tree. I was thinking that maybe under some circumstances it would be possible to prove a better bound for the error than "K * delta". However, proving such a bound appeared to be complicated. > If I now understand you correctly, it just means replacing the code > that assigns the score to alpha by code that assigns (score + 100) > to alpha [if we're measuring in millipawns]. Yes, that's correct. > Surely someone has already tried this? If not, go ahead ...! Maybe I will. However, I was initially suggesting this as a way to make the original posters idea work. His idea was in a broad sense "take something good from branch and bound and apply it to alpha beta".  Peter Osterlund  [email protected] http://web.telia.com/~u89404340

      
Date: 18 Feb 2009 00:10:38
From: Andy Walker
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

Peter Osterlund wrote: > One can quite easily conclude that if you do this approximation (by > amount "delta") at K different levels, the approximation error at the > root is no more than K * delta. However that quickly becomes too large > to be practical if you intend to do it at all levels in the search > tree. Actually, half the approximations will be for the other player, so there is a limit of ceiling(K/2)*delta, and even that happens only if there is a sequence of second or later moves being best by no more than delta. So I think the practical performance would be a lot better than the theoretical limit. However, there seem to be problems in the case where alpha+delta >= beta [eg, minimal windowing]  it needs a bit of thought to determine what the best "mend" is, but at least once the alpha and beta levels have become that close, there will be no further approximation errors. >> Surely someone has already tried this? If not, go ahead ...! > Maybe I will. However, I was initially suggesting this as a way to > make the original posters idea work. His idea was in a broad sense > "take something good from branch and bound and apply it to alpha > beta". OK. Just possibly worth noting that ordinary b&b relates to alphabeta in much the same way that helpmates relate to ordinary mates, so there might also be some spinoffs for "fairy" chess.  Andy Walker Nottingham


Date: 14 Feb 2009 16:59:26
From:
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

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


Date: 14 Feb 2009 23:57:08
From: Andy Walker
Subject: Re: Game Tree Programming Idea: Selectivity via modified alphabeta

[email protected] wrote: [...] > This got me thinking about alphabeta 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 sortof can, sortof can't, and it sortof probably doesn't help [at least if I've understood your notion correctly]. (a) It's easy to modify alphabeta 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 prettymuch "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 alphabeta 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 pinheads, 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

