Author |
Topic: Ply vs. Steps (Read 3894 times) |
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender: 
Posts: 405
|
 |
Ply vs. Steps
« on: Apr 15th, 2006, 12:12am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Ply vs. Steps
« Reply #1 on: Apr 15th, 2006, 12:59am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Ply vs. Steps
« Reply #2 on: Apr 15th, 2006, 9:47am » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Ply vs. Steps
« Reply #3 on: Apr 15th, 2006, 1:25pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Ply vs. Steps
« Reply #4 on: Apr 15th, 2006, 6:03pm » |
Quote Modify
|
on Apr 15th, 2006, 9:47am, Fritzlein wrote: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? 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. |
|
Gnobot_2004 also searches by move  .
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Ply vs. Steps
« Reply #5 on: Apr 16th, 2010, 1:37pm » |
Quote Modify
|
(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?
|
| « Last Edit: Apr 16th, 2010, 2:00pm by rbarreira » |
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Ply vs. Steps
« Reply #6 on: Apr 16th, 2010, 2:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Ply vs. Steps
« Reply #7 on: Apr 16th, 2010, 2:39pm » |
Quote Modify
|
on Apr 16th, 2010, 2:24pm, doublep wrote:| 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. |
|
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 Apr 16th, 2010, 2:24pm, doublep wrote:| 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. |
|
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.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Ply vs. Steps
« Reply #8 on: Apr 16th, 2010, 3:55pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
toby1kenobi
Forum Junior Member
Arimaa player #4714
Gender:
Posts: 8
|
|
Re: Ply vs. Steps
« Reply #9 on: May 26th, 2010, 4:02pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Ply vs. Steps
« Reply #10 on: May 26th, 2010, 7:16pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Ply vs. Steps
« Reply #11 on: Aug 25th, 2010, 10:32pm » |
Quote Modify
|
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 Apr 16th, 2010, 2:24pm, doublep wrote:
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. |
|
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)
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Ply vs. Steps
« Reply #12 on: Aug 26th, 2010, 3:53am » |
Quote Modify
|
on Aug 25th, 2010, 10:32pm, rednaxela wrote:| 1) If I understand correctly, as Fritz states, the alpha-beta pruning can only occur on full ply, not the steps. That makes sense. |
|
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 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). |
|
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.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Ply vs. Steps
« Reply #13 on: Aug 26th, 2010, 6:39am » |
Quote Modify
|
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).
|
| « Last Edit: Aug 26th, 2010, 6:50am by rbarreira » |
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Ply vs. Steps
« Reply #14 on: Aug 26th, 2010, 8:13am » |
Quote Modify
|
on Aug 26th, 2010, 3:53am, Fritzlein 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. |
|
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.
|
| « Last Edit: Aug 26th, 2010, 8:14am by Rednaxela » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print