Author |
Topic: Ply vs. Steps (Read 3723 times) |
|
rbarreira
Forum Guru
Arimaa player #1621
Gender: 
Posts: 605
|
 |
Re: Ply vs. Steps
« Reply #15 on: Aug 26th, 2010, 8:45am » |
 Quote  Modify
|
on Aug 26th, 2010, 8:13am, rednaxela wrote:
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 |
|
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.
|
| « Last Edit: Aug 26th, 2010, 8:52am by rbarreira » |
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Ply vs. Steps
« Reply #16 on: Aug 26th, 2010, 8:45am » |
Quote Modify
|
on Aug 26th, 2010, 8:13am, rednaxela wrote:| 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 |
|
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'm pretty sure it breaks the rule that alpha-beta pruned minimax gives the same output as normal minimax. |
|
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:| 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. |
|
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.
|
|
IP Logged |
|
|
|
speek
Forum Guru
Arimaa player #5441
Gender:
Posts: 75
|
|
Re: Ply vs. Steps
« Reply #17 on: Aug 26th, 2010, 1:15pm » |
Quote Modify
|
The bot I'm working on is ply-by-ply, and I have no intention of going step-by-step in the future.
|
|
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Ply vs. Steps
« Reply #18 on: Aug 27th, 2010, 2:20am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Ply vs. Steps
« Reply #19 on: Aug 27th, 2010, 8:35am » |
Quote Modify
|
on Aug 27th, 2010, 2:20am, rednaxela wrote:
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. |
|
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).
|
| « Last Edit: Aug 27th, 2010, 8:40am by rbarreira » |
IP Logged |
|
|
|
Rednaxela
Forum Senior Member
Arimaa player #4674
Gender:
Posts: 34
|
|
Re: Ply vs. Steps
« Reply #20 on: Aug 27th, 2010, 8:05pm » |
Quote Modify
|
on Aug 27th, 2010, 8:35am, rbarreira 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.
|
|
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
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print