chess:programming:alpha-beta_pruning:example
Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| chess:programming:alpha-beta_pruning:example [2021/10/30 23:19] – created peter | chess:programming:alpha-beta_pruning:example [2021/10/30 23:35] (current) – peter | ||
|---|---|---|---|
| Line 8: | Line 8: | ||
| * At A the maximizer must choose max of B and C, so A calls B first. | * At A the maximizer must choose max of B and C, so A calls B first. | ||
| * At B it the minimizer must choose min of D and E and hence calls D first. | * At B it the minimizer must choose min of D and E and hence calls D first. | ||
| - | * At D, it looks at its left child which is a leaf node. | + | * At D, the maximizer |
| * This node returns a value of 3. | * This node returns a value of 3. | ||
| * Now the value of alpha at D is max(-INF, 3) which is 3. | * Now the value of alpha at D is max(-INF, 3) which is 3. | ||
| Line 15: | Line 15: | ||
| * So it continues the search. | * So it continues the search. | ||
| * D now looks at its right child which returns a value of 5. | * D now looks at its right child which returns a value of 5. | ||
| - | * At D, alpha = max(3, 5) which is 5. Now the value of node D is 5. | + | * At D, alpha = max(3, 5) which is 5. |
| + | * Now the value of node D is 5. | ||
| * D returns a value of 5 to B. | * D returns a value of 5 to B. | ||
| * At B, beta = min(+INF, 5) which is 5. | * At B, beta = min(+INF, 5) which is 5. | ||
| - | * The minimizer is now guaranteed a value of 5 or lesser. | + | * The minimizer is now guaranteed a value of 5 or less. |
| * B now calls E to see if he can get a lower value than 5. | * B now calls E to see if he can get a lower value than 5. | ||
| * At E the values of alpha and beta is not -INF and +INF but instead -INF and 5 respectively, | * At E the values of alpha and beta is not -INF and +INF but instead -INF and 5 respectively, | ||
| Line 27: | Line 28: | ||
| * Hence it breaks and E returns 6 to B. | * Hence it breaks and E returns 6 to B. | ||
| * Note how it did not matter what the value of E's right child is. | * Note how it did not matter what the value of E's right child is. | ||
| - | * It could have been +INF or -INF, it still would not matter, We never even had to look at it because the minimizer was guaranteed a value of 5 or lesser. | + | * It could have been +INF or -INF, it still would not matter. |
| - | * So as soon as the maximizer saw the 6 he knew the minimizer would never come this way because | + | * We never even had to look at it because the minimizer was guaranteed a value of 5 or less. |
| + | * So as soon as the maximizer saw the 6 he knew the minimizer would never come this way because | ||
| + | * The Minimizer would always go for the left side of B as this gives a lesser value. | ||
| * This way we do not have to look at that 9 and hence saved computation time. | * This way we do not have to look at that 9 and hence saved computation time. | ||
| * E returns a value of 6 to B. | * E returns a value of 6 to B. | ||
| * At B, beta = min(5, 6) which is 5. | * At B, beta = min(5, 6) which is 5. | ||
| * The value of node B is also 5. | * The value of node B is also 5. | ||
| + | |||
| + | ---- | ||
| So far this is how our game tree looks. | So far this is how our game tree looks. | ||
| Line 40: | Line 45: | ||
| {{: | {{: | ||
| - | ---- | ||
| * B returns 5 to A. | * B returns 5 to A. | ||
| Line 66: | Line 70: | ||
| * Therefore the best value at A is max(5, 2) which is a 5. | * Therefore the best value at A is max(5, 2) which is a 5. | ||
| * Hence the optimal value that the maximizer can get is 5. | * Hence the optimal value that the maximizer can get is 5. | ||
| + | |||
| + | ---- | ||
| This is how our final game tree looks like. | This is how our final game tree looks like. | ||
chess/programming/alpha-beta_pruning/example.1635635947.txt.gz · Last modified: 2021/10/30 23:19 by peter