Problems A-F
Problems A-F
Performance of POB and Other Algorithms on Problems A-F
We measure the performance of POB and partial order pruning
by comparing four kinds of search:Plain alpha-beta (abbreviated ab in the table)
uses partial ordering for move
ordering only, and evaluates wins and losses only by capture.
Alpha-beta search with partial order pruning ( abPOP) uses knowledge about partial ordering
to prune moves. Non-pruning POB (POB-) uses partial order
leaf evaluation but no pruning.
Full POB uses both partial order leaf evaluation and
partial order pruning. However, all four types of search
apply the pruning
rule of using only one of several equivalent moves,
such as outside liberties. Without this rule, the non-pruning variants would be much worse.
| BW | POB |
POB- | abPOP | ab |
| | B | 1 | 1 | 20 | 50 |
| A | W | 1 | 1 | 20 | 50 |
| B | B | 1 | 1 | 210 | 441 |
| B | W | 1 | 1 | 250 | 358 |
| C | B | 20 | 26 | 23 | 33 |
| C | W | 6 | 21 | 12 | 21 |
| D | B | 18 | 27 | 433 | 1443 |
| D | W | 18 | 27 | 134 | 284 |
| E | B | 304 | 333 | 1339 | 1523 |
| E | W | 208 | 333 | 993 | 1367 |
| F | B | 18 | 27 | 1066 | 4199 |
| F | W | 18 | 27 | 272 | 662 |
Comparison of POB and alpha-beta
Created: Feb 10, 1999 Last modified: Feb 10, 1999
Martin Müller