List of bug fixes for Research Re: search & Re-search
version of Wed Apr 15 14:02:34 MET DST 1998
If you find an error, please send me an email at askeplaat at hotmail dot com
- page 14, 5th line from bottom of page
“denotred” should be “denoted” - page 23, figure 2.13 FIXED
The figure shows a version of NegaScout that is not always fail-soft, because of line 7 and 15. The figure should have shown a fail-soft NegaScout. The code, upon failing low or high sometimes returns alpha or beta, instead of the value of the child that caused the fail low/high. Non-fail-soft algorithms are a thing of the past. (And mixtures of the two make no sense at all.) The algorithms in chapter 3 and 4 all need fail-soft versions of Alpha-Beta for their Null-Window searches. More on NegaScout can be found here and in [116] (not [115], which contains an error) and in [81] and [84]. (The rest of the thesis does not use NegaScout, but MT or Alpha-Beta. The code for these algorithms is fail-soft.)
This has been fixed. The web-version of the thesis now has a fail-soft NegaScout.
— Thanks to Dennis Breuker for finding this bug and the one in [115]. - page 26, figure 2.15, and page 94, figure 5.4 FIXED
The result of a search is a fail high, fail low, or accurate value, and, correspondingly, a lower bound, upper bound, or minimax value. These three cases are to be distinguished by comparing the search result against the alpha and beta bounds of the search window. The code in the figure is rather careless in also using alpha and beta to compute the new search window of the children, thus destroying the original search window of the node. The old alpha and beta bounds should be saved since they are used later on to see whether a lower or upper bound should be stored in the transposition table. This can be achieved by adding code to line 9 and 16 (figure 2.15), where g gets set to infinity, to copy the alpha and beta values in extra variables. The correct version can be found here.
This has been fixed in the web-version of the thesis.
— Thanks to Toru Yamazato for pointing out this bug. - page 43, paragraph starting with “Note that while…”
You can save space by not storing both bounds at both node types. Alpha-Beta with a transposition table only has to store upper bounds, f^+, at min nodes, and lower bounds, f^-, at max nodes, and the mechanism still works, give or take a few extra node expansions to retrieve the bounds of the children. - page 133, column “Alpha-Beta” and “NegaScout” position 10 of the table
The number 1869436 is bold, whereas is 1763143 is not. Since the lowest number should be in bold, this is wrong.
— Thanks to Roel van der Goot for finding this bug. - page 147, references [54], [55], [56]
Feng-hsiung Hsu’s first name is usually spelled with a hyphen.
Aske Plaat 