|
||||||
|
Title: Ply vs. Steps Post by IdahoEv on Apr 15th, 2006, 12:12am I see a lot of discussion on the forum about search depth in steps rather than ply ... bots searching 6 or 11 steps deep, etc. While I understand the functional reasons why one would want to do this, it has always seemed crazy to me because you obviously cannot consider all the steps equivalent for evaluation purposes: there are huge numbers of positions that are perfectly fine if they are transitory (like the middle step of walking your phant to the other side of a trap defended by only one other piece) but which are totally unacceptable if you were to end your turn on them. This means you can't statically evaluate these positions the same. How do other developers deal with this? Do you have two evaluators that handle end-turn and mid-turn steps differently? |
||||||
|
Title: Re: Ply vs. Steps Post by 99of9 on Apr 15th, 2006, 12:59am I think this is quite significant. Gnobby does not handle eval at different steps any differently, and I think that is a failing. Some other bots have a static trap search. I presume this takes into account how many steps the player has left to play. |
||||||
|
Title: Re: Ply vs. Steps Post by Fritzlein on Apr 15th, 2006, 9:47am It is intuitively obvious to me that step-by-step searching is not the way to go, and that bots sould search and evaluate on a ply-by-ply basis. It's obvious, I say, but obviously my intuition is wrong, because as far as I can tell, every bot searches step-by-step. That must be the most sensible thing to do if everyone does it. Or does bot_V search ply-by-ply? From the description it sounds like it would have too. It's too bad for my theory if the only bot that does it the "right" way is weaker than any of the five bots that played in the Computer Championship. :P |
||||||
|
Title: Re: Ply vs. Steps Post by IdahoEv on Apr 15th, 2006, 1:25pm I suppose if you are only evaluating material, with no thought at all given to position, then searching by steps is just fine. I wonder if this difference accounts for some of why the overall playing styles of ShallowBlue, Arimaalon, and Arimaazilla are so thoroughly different; Arimaalon searches to a noninteger ply depth. What does the evaluation function look like for these bots? |
||||||
|
Title: Re: Ply vs. Steps Post by 99of9 on Apr 15th, 2006, 6:03pm on 04/15/06 at 09:47:02, Fritzlein wrote:
Gnobot_2004 also searches by move :-). |
||||||
|
Title: Re: Ply vs. Steps Post by rbarreira on Apr 16th, 2010, 1:37pm (is necroing old threads acceptable here? ) I had the same exact concern when reading past threads in this forum. A few of the concerns I have with searching step-by-step instead of ply-by-ply: 1- The repetition rule doesn't work with positions after steps, but after a turn. 2- Goals are not goals if they happen in between steps (admittedly it should be rare that it is useful to push an opposing rabbit to goal in between steps, but it can happen). 3- A player may not have valid 1-step replies but may have valid replies with more steps. (one of the sample bots has this as a documented bug) 4- Inserting evaluations of intermediate steps in a hash table also sounds like trouble. 5- Instead of searching to, say, depth 13, isn't it much better to assume a play of 16 steps? 1-step moves are pretty rare, why not generating a same-sized set of 4-step moves for that ply? It doesn't make the search tree any bigger, but should make it more relevant. In the bot I'm starting, I do generate moves step-by-step (including a "skip" step for terminating a move at less than 4 steps), but evaluation, checking for terminal nodes and everything else which is part of the minimax paradigm happens at the end of a move only. Are there any good reasons to break the minimax paradigm by using steps instead of plies? |
||||||
|
Title: Re: Ply vs. Steps Post by doublep on Apr 16th, 2010, 2:24pm 1, 2, 3: The workaround for this is to not consider a loss a final answer if there are still more steps. Such "imaginable" loss could in principle mess up move ordering badly, but I guess that happens so rarely that only correctness in such cases is important. 4: Because you need to include depth in table key. I.e. the key shouldn't be just the position. 5: Iterational deepening is the killer. In theory what you say would be better, but search results from previous step-depth give so much better move ordering that improved performance trumps all other reasoning. |
||||||
|
Title: Re: Ply vs. Steps Post by rbarreira on Apr 16th, 2010, 2:39pm on 04/16/10 at 14:24:28, doublep wrote:
That makes sense, and is what I meant too. Validity checking, terminal nodes etc. should be done after a full move only, or else they can't prevent the search from progressing (in which case it probably doesn't make sense to check those things in the first place). on 04/16/10 at 14:24:28, doublep wrote:
That sounds good, and together with the previous points means that a step/ply hybrid search is what you are actually doing (taking steps just for the deepening and ordering). So I guess if we agree on the previous points and I end up doing this, we may just be using different terms for the same thing. |
||||||
|
Title: Re: Ply vs. Steps Post by jdb on Apr 16th, 2010, 3:55pm If there is nothing going on in the position, it works well to terminate the search part way through a move. If there is anything going on, then it does not work so well to terminate the search part way through a move. If there are goal threats, capture threats, elephant blockades, frame threats, hostage threats or anything else like that going on, the search should only stop on completed moves. Just my opinion. |
||||||
|
Title: Re: Ply vs. Steps Post by toby1kenobi on May 26th, 2010, 4:02pm I'm not a bot developer yet, but wouldn't a step by step evaluation greatly improve pruning? Imagine you're a pretty simple bot doing a ply by ply evaluation - you take 4 steps and have a look where you are, you see that your elephant has walked into a trap, so discard that option, next you change the last of the four steps and evaluate again. Still the elephant has walked into a trap - you don't realise that it was on the first of the steps that the elephant walked into the trap. If you were evaluating step by step there would be thousands of end of move positions you would not have to evaluate because you evaluated once that the first step of walking an elephant into a trap is not good. |
||||||
|
Title: Re: Ply vs. Steps Post by Fritzlein on May 26th, 2010, 7:16pm Yep, better pruning (specifically better move ordering to make alpha-beta pruning work better) is a large reason to iterate search by steps. Note, however, that there can be no alpha-beta cutoffs until the side to move switches, so Janzert (bot_OpFor) generates whole moves at the root and only switches to step-based searching at 5 steps depth. It would be an interesting investigation to measure the quality of move-ordering produced by step-based search. It could be that evaluating after single steps produces garbage ordering that doesn't actually speed up alpha-beta. But in an exponentially exploding tree, the iterative deepening doesn't have to improve move-ordering by very much to pay for itself, so probably it is worth it even if the move ordering is mediocre. Your post seemed to be talking about a different kind of pruning, namely "forward pruning" where moves that evaluate poorly at a shallow level are thrown away and never examined again at a deeper level. Intuitively forward pruning is a great idea, but it hasn't worked well in practice for Arimaa. Bots that do mild forward pruning don't get much speedup, whereas bots that do heavy forward pruning develop hilarious blind spots. However, forward pruning has been successful in computer shogi, so maybe we just haven't yet figured out how to apply it to Arimaa. |
||||||
|
Title: Re: Ply vs. Steps Post by rednaxela on Aug 25th, 2010, 10:32pm Hmm... so let me see if I'm understanding this right... 1) If I understand correctly, as Fritz states, the alpha-beta pruning can only occur on full ply, not the steps. That makes sense. 2) Since the alpha-beta pruning only happens on the complete-ply step, the move ordering only gives any benefit at the full ply step. Therefore, in terms of: on 04/16/10 at 14:24:28, doublep wrote:
Isn't it the case that: 3) Only the the 3rd step evaluation impacts the order of the 4th step (complete-ply step) 4) Since the complete-ply step's move ordering is only impacted by 3rd step evaluation, there's no point in evaluating the positions of the first and second step. Am I getting this right or am I misunderstanding something? If I am correct about this, I really think the conceptual difference between step-based and ply-based really is not that substantial really. It basically just comes down to a heuristic for move ordering, which could be replaced by other heuristics too (not that it necessarily should be). (Ignoring transposition table interactions, and assuming iterative deepning in both cases for sake of this comparison) |
||||||
|
Title: Re: Ply vs. Steps Post by Fritzlein on Aug 26th, 2010, 3:53am on 08/25/10 at 22:32:00, rednaxela wrote:
Not quite. The alpha-beta pruning can't start occurring until the fifth step, but it can occur on every step thereafter, including the sixth, seventh, eighth, ninth, etc. So there is a genuine move-ordering benefit to doing a step-by-step search rather than ply-by-ply. Quote:
I wouldn't know how to measure the value of move-ordering by iterative deepening relative to move-ordering by other means. Note, however, that a secondary benefit of step-by-step iterative deepening is that it gets closer to being a "stop anytime" algorithm than ply-by-ply iterative deepening. There is some time allocation inefficiency from starting an iteration at a depth that is not completely searched. |
||||||
|
Title: Re: Ply vs. Steps Post by rbarreira on Aug 26th, 2010, 6:39am Cutoffs in the first ply are also possible, if you use aspiration windows. But it's an undesirable event here, as it means that your aspiration heuristic guessed wrong and you have to do a re-search. On the other hand it does mean that the situation is better than expected (i.e. higher score). |
||||||
|
Title: Re: Ply vs. Steps Post by rednaxela on Aug 26th, 2010, 8:13am on 08/26/10 at 03:53:07, Fritzlein wrote:
Well... in that case I'm not sure it's not quite true alpha-beta pruning anymore... I think that for the same reason it would be invalid to alpha-beta prune in the middle of the first ply, it would also be invalid to alpha-beta prune in the middle of any other ply, because that means negative steps that allow an improved move at a whole would be ignored. What I mean is.... it's not to say that what you suggest is a bad way to do things if careful, but I'm pretty sure it breaks the rule that alpha-beta pruned minimax gives the same output as normal minimax. Since the result differs from normal minimax, I would classify anything that "alpha-beta prunes" mid-ply to be more like "an alpha-beta pruning inspired form of forward pruning". All that of course assumes I'm not mistaken in that it causes a deviation in output from normal minimax, but if necessary I think I could come up with an example that shows this to be the case later. |
||||||
|
Title: Re: Ply vs. Steps Post by rbarreira on Aug 26th, 2010, 8:45am on 08/26/10 at 08:13:00, rednaxela wrote:
The only reason why cutoffs wouldn't occur in the first ply is because beta would be equal to plus infinity in that ply (i.e. normal alpha-beta without aspiration windows). A cutoff only happens when score >= beta and score >= + inf is of course impossible. On any other ply, beta is minus the alpha of the previous ply, which is almost always a finite value. So there can be just as many cutoffs at the end of a ply, as in the middle of a ply. In fact this mid-ply, end-of-ply distinction is almost irrelevant for alpha beta, most bots just use it as a way to make it easier to generate moves and do the iterative deepening (doing it step-by-step instead of generating all the moves). In fact, it goes even farther than that. beta will have exactly the same value at the end of a ply as in the middle of that ply, so a cutoff at the end of the ply will immediately propagate upwards and result in an equal cutoff at the previous step, and so on. |
||||||
|
Title: Re: Ply vs. Steps Post by Fritzlein on Aug 26th, 2010, 8:45am on 08/26/10 at 08:13:00, rednaxela wrote:
Alpha-beta pruning relies on the fact that you can stop searching a branch because the move you found is already good enough to refute the move one level higher. You know the move prior won't be played, whether or not the current level has a better move. The reason you can't apply alpha-beta pruning between steps of the the first ply is that all the steps are trying to maximize. (In jargon, the alpha and beta have never been swapped.) A good second step is never a refutation of the first step made by the same player. You are always forced to keep looking for a better move if you want to find the true maximum. This argument doesn't apply between steps of the second ply. If I am searching, say, six steps deep and find a strong step, it can refute the whole first four steps of that line. I can conclude that this branch will not be played because the player on move has a better option that was fully searched earlier. Therefore I can stop looking for a better sixth step in that line. Quote:
I don't see how pruning branches as I mentioned above would change the minimax score from the tree that has been fully searched to a depth of six steps. The pruned branches can only worsen the evaluation of moves at the root which have already been dominated. Obviously the minimax score of a full tree at six steps won't equal the minimax score of a full tree at eight steps, but that isn't the issue. Building the smaller tree helps order moves to make searching the larger tree go faster, and also helps pick a better move than a four-step search even if an eight-step search can't be completed. Quote:
I'm curious to see such an example, because it would show that I'm not understanding how alpha-beta pruning works. Please share if you construct one. |
||||||
|
Title: Re: Ply vs. Steps Post by speek on Aug 26th, 2010, 1:15pm The bot I'm working on is ply-by-ply, and I have no intention of going step-by-step in the future. |
||||||
|
Title: Re: Ply vs. Steps Post by rednaxela on Aug 27th, 2010, 2:20am Alright! I think I finally settled my qualms with step-based alpha-beta pruning tonight! I set up a quick code snippet to compare the output of non-pruned minimax, and alpha-beta pruned. To be a 'good' fuzzing test of the equivalence of output, I made the evaluation function have pseudo-random output that could be repeated such that the same tree nodes get the same results for a given seed. Tested it with some small breadth and moderate depth cases with 2-steps-per-turn, and it seems that despite my unsettled feelings before, it apparently it doesn't break the alpha-beta pruning. I'm convinced now ::) One other interesting thing from my tests: With a variety of settings, I measured how many alpha-beta pruning events happened at each step within a ply. There seemed to be a strong tendency for most of the pruning events to be ply-aligned, however the number of mid-ply pruning events was still very significant. Furthermore, I now see that step-based is a good way to go. I'm still wary of the exact results of some heuristics when not ply-aligned, but I now consider that a minor detail. What I mean by that is.... I can see how step-based would give performance benefits if when the mid-ply evaluations are only kinda-sorta-sane, and one could still ignore non-ply-aligned results for move selection, using them only for iterative deepening purposes. I think I have my head straight with this situation now... |
||||||
|
Title: Re: Ply vs. Steps Post by rbarreira on Aug 27th, 2010, 8:35am on 08/27/10 at 02:20:08, rednaxela wrote:
I don't understand how the number of cutoffs can differ between steps of the same ply, as beta will have the same value in all of them. Therefore, a cutoff at a late step should result in a cutoff at all earlier steps, and a cutoff at an early step can only come from the same cutoff propagated from later steps. What am I missing here? The only thing I can think of is slight distortions from terminal nodes, where a search finishes at the beginning of a ply without continuing to generate the last steps of a ply, but that wouldn't happen at low depth unless you were testing endgame positions (and if it happened, it would make the numbers bigger for the mid-ply cutoffs, not for the ply-aligned cutoffs). |
||||||
|
Title: Re: Ply vs. Steps Post by rednaxela on Aug 27th, 2010, 8:05pm on 08/27/10 at 08:35:16, rbarreira wrote:
Aha, you're right. At one point I had changed my pruning-counting to count total number of branches pruned rather than pruning events. To compare: Depth: 0 Prune events: 0 , 0 , 0 , 0 Depth: 1 Prune events: 0 , 0 , 0 , 0 Depth: 2 Prune events: 0 , 0 , 0 , 0 Depth: 3 Prune events: 0 , 0 , 0 , 0 Depth: 4 Prune events: 0 , 0 , 0 , 0 Depth: 5 Prune events: 809990 , 0 , 0 , 0 Depth: 6 Prune events: 809999 , 798447 , 0 , 0 Depth: 7 Prune events: 809999 , 809999 , 798521 , 0 Depth: 8 Prune events: 809999 , 809999 , 809999 , 798550 vs Depth: 0 Pruned node count: 0 , 0 , 0 , 0 Depth: 1 Pruned node count: 0 , 0 , 0 , 0 Depth: 2 Pruned node count: 0 , 0 , 0 , 0 Depth: 3 Pruned node count: 0 , 0 , 0 , 0 Depth: 4 Pruned node count: 0 , 0 , 0 , 0 Depth: 5 Pruned node count: 22244819 , 0 , 0 , 0 Depth: 6 Pruned node count: 23269668 , 14746159 , 0 , 0 Depth: 7 Pruned node count: 23489971 , 23268493 , 14731938 , 0 Depth: 8 Pruned node count: 23489971 , 23489971 , 23269292 , 14736104 |
||||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |