Algo Scout

An Improvement to the Scout Tree SearchAlgorithm

by Alexander Reinefeld

Tsan-sheng Hsu

[email protected]

http://www.iis.sinica.edu.tw/~tshsu

1

Introduction

It looks like alpha-beta pruning is the best we can do for ageneric searching procedure.

• What else can be done generically?• Alpha-beta pruning follows basically the “intelligent” searching behav-

iors used by human when domain knowledge is not involved.• Can we find some other “knowledge” behaviors used by human in

searching?

Intuition: One a MAX node• Suppose we know currently we have a way to gain at least 300 points

at the first branch.• If there is an efficient way to know the second branch is at most

gaining 300 points, then there is no need to search the second branchin detail.

. Is there a way to search a tree approximately?

. Is searching approximately faster than searching exactly?

The same intuition holds for a MIN node.

TCG: NegaScout, 20071126, Tsan-sheng Hsu 2

Scout procedure

Invented by Judea Pearl in 1980.It is possible to verify whether the value of a branch is greatthan a value v or not in a way that is faster than knowing itsexact value.procedure TEST(J : position, v: value, >: condition)

• determine the successor positions p1, . . . , pd• if d = 0, then

. return TRUE if value(J) > v

. return FALSE otherwise

• for i := 1 to d do. if J is a MAX node and TEST(pi, v, >) is TRUE then return TRUE. if J is a MIN node and TEST(pi, v, >) is FALSE then return FALSE

• if J is a MAX node then return FALSE• if J is a MIN node then return TRUE

Condition can be stated as ≥ by properly revising the algorithm.

• For the condition to be < or ≤, we need to switch conditions for theMAX and MIN nodes.


EVAL for Scout

Algorithm SCOUT(J : position)• determine the successor positions p1, . . . , pd• if b = 0, then return value(J) else• v = SCOUT (p1)• for i := 2 to d do

. if J is a MAX node and TEST(pi, v, >) is TRUE thenv = SCOUT (pi)

. if J is a MIN node and TEST(pi, v, ≥) is FALSE thenv = SCOUT (pi)

• return v


Performance of Scout

Show great improvements on depth > 3 for games with smallbranching factors.

• It traverses most of the nodes without evaluating them preciously.• Few subtrees remained to be revisited to compute their exact mini-max

values.

Experimental data shows• Scout favors “skinny” games, that is games with high depth-to-width

ratios.• One depth = 5, it saves over 40% of time.• Maybe bad for games with high branching factors.• Move ordering is very important.

. The first branch, if is good, offers a great chance of pruning furtherbranches.

A node may be visited more than once.• First visit is to test.• Second visit is to find its exact value.• Q: Can information in the first search be used in the second search?


Discussions for SCOUT I

EVAL and TEST may visit less nodes than alpha-beta.

max

min

max

min

5

8

15

10

0

5

8

15

10

0

J J

KK

SCOUT ALPHA−BETA

• Assume TEST (J, 5, >) is called by the root after the first branch isevaluated.

. It calls TEST (K, 5, >) which skips K’s second branch.

• TEST (J, 5, >) fails after returning from the 3rd branch.• No need to do Scout for the branch J .


Discussions for SCOUT II

EVAL and TEST is not always better than alpha-beta.

max

min

max

min

max

ALPHA−BETA

5

10

0

25

20

8

[10, infinity]

[10,25]

[10,25]

[10,25]

TEST[10,A,>]: true

TEST[25,B,>]: false

TEST[0,C,>]: true

SCOUT

5

10

0

25

20

8

A

B

C

DTEST[8,D,>]: false


Discussions for SCOUT III

When the first branch of a node has the best value, then TESTscans the tree fast.

• For TEST to return TRUE for a subtree T , it needs to evaluate atleast

. one child for a MAX node in T , and

. and all of the children for a MIN node in T .

. If T has a fixed branching factor b and uniform depth d, the number ofnodes evaluated is Ω(bd/2).

Compared to alpha-beta pruning whose cut off comes frombounds of search windows.

• It is possible to have some cut-off for alpha-beta as long as there aresome move ordering are “good”.

• For SCOUT to run well, it requires that the first branch needs to bethe best branch.


Alpha-beta revisited

Definitions:• An alpha-beta search failed-high means it returns a value that is larger

than its upper bound β.• An alpha-beta search failed-low means it returns a value that is smaller

than its lower bound α.

Null window search:• Using alpha-beta search with the window (m,m + 1).• The result can be either failed-high or failed-low.• Fail high means the return value is at least m + 1.

. Equivalent to TEST (J, m, >) is true.

• Fail low means the return value is at most m.. Equivalent to TEST (J, m, >) is false.

Versions:• Fail hard alpha-beta Nega-Max version: F2• Fail soft alpha-beta Nega-Max version: F3• Brute force Mini-Max version: F

. Always finds the correct answer according to the Mini-Max formula.


Fail hard version

Original version.Algorithm F2(position p, integer alpha, integer beta)

• determine the successor positions p1, . . . , pd• if d = 0, then return f(p) else• begin

. m := alpha

. for i := 1 to d do

. t := −F2(pi,−beta,−m)

. if t > m then m := t

. if m ≥ beta then return(m)

• end• return m

Properties:• alpha < beta• F2(p, alpha, beta) ≤ alpha if F (p) ≤ alpha• F2(p, alpha, beta) = F (p) if alpha < F (p) < beta• F2(p, alpha, beta) ≥ beta if F (p) ≥ beta• F2(p,−∞,+∞) = F (p)


Fail soft version

Algorithm F3(position p, integer alpha, integer beta)• determine the successor positions p1, . . . , pd• if d = 0, then return f(p) else• begin

. m := −∞


. t := −F3(pi,−beta,−m)

. if t > m then m := t

. if m ≥ beta then return(m)

• end• return m

Properties:• alpha < beta• F3(p, alpha, beta) ≤ alpha if F (p) ≤ F3(p, alpha, beta) ≤ alpha• F3(p, alpha, beta) = F (p) if alpha < F (p) < beta• F3(p, alpha, beta) ≥ beta if F (p) ≥ F3(p, alpha, beta) ≥ beta• F3(p,−∞,+∞) = F (p)


Comparisons between F2 and F3

Both versions find the corrected value v if v is within thewindow (α, β).Both versions scan the same set of nodes during searching.F3 finds a “better” value when the value is out of the searchwindow.

• Better means a tighter bound.• When it fails high, F3 normally returns a value that is higher than that

of F2.. Never higher than that of F !

• When it fails low, F3 normally returns a value that is lower than thatof F2.

. Never lower than that of F !

F3 saves about 7% of time when transposition table is used tostore searched results.


NegaScout

Intuition:• Try to incooperate SCOUT and alpha-beta together.• The searching window of alpha-beta if properly set can be used as

TEST in SCOUT.• Using a searching window is better than using a single bound as in

SCOUT.

Modifications to the Scout algorithm:• Use Nega-Max approach instead of mini-max.• Traverses the tree with two bounds as alpha-beta does.

. A searching window.

• Using a fail soft version to get a better result when the returned valueis out of the window,


The NegaScout Algorithm

Algorithm F4(position p, integer alpha, integer beta, integerdepth)

• if depth = cut off depth then return f(p)• determine the successor positions p1, . . . , pd• if d = 0, then return f(p) else• begin

. m := −∞ /* the best value so far */

. n := beta


. 9: t := −F4(pi,−n,−maxalpha, m, depth + 1)

. 10: if t > m then11: if (n = beta or depth ≥ cut off depth− 2)12: then m := t13: else m := −F4(pi,−beta,−t, depth + 1)

. 14: if m ≥ beta then return(m)

. 15: n := maxalpha, m+ 1

• end• return m


Search behaviors I

If the depth is enough or it is a terminal position, then stopsearching further.

• Return f(p) as the value computed by an evaluation function.

Fail soft version.For the first child p1, a normal alpha beta searching window isused.

• line 9: normal alpha-beta search for the first child• the initial value of m is −∞, hence −maxalpha, m = −alpha

. m is current best value

• that is, searching with the normal window (α, β)


Search behaviors II

For the second child and beyond pi, i > 1, first perform a nullwindow search for testing whether m is the answer.

• line 9: a null-window of (m,m + 1) search for the second child andbeyond.

. m is best value obtained so far

. m’s value will be first set at line 12 because n = beta

. The null window is set at line 15.

• line 11: on a smaller depth subtree, i.e., depth at least 2, NegaScoutalways returns the best value.

. Normally, no need to do alpha-beta or any enhancement on very smallsubtrees.

. The overhead is too large on small subtrees.

• line 13: re-search when the null window search fails high.. The value of this subtree is at least t.. This means the best value in this subtree is more than m, the current

best value.. This subtree must be re-searched with the the window (t, beta).

• line 14: the normal pruning from alpha beta.


Example for NegaScout

−5 −4 −6 −7 −4 −4

null window[−6,−5]

[4,5]


Refinements

When a subtree is re-searched, it is best to use information onthe previous search to speed up the current search.

• Restart from the position that the value t is returned.

Maybe want to re-search using the normal alpha-beta procedure.F4 runs much better with a good move ordering andtransposition tables.

• Orders the moves in a best-first list.• Reduces the number of re-searches.


Performances

On a uniform random game tree.Normally superior to alpha-beta when searching game tree withbranching factors from 20 to 60.Shows about 10 to 20% improvements.


Comments

Incooperating both Scout and alpha-beta.Used in state-of-the-art game search engines.The first search, though maybe unsuccessful, can provide usefulinformation in the second search.

• Information can be stored.


References and further readings

* A. Reinefeld. An improvement of the scout tree searchalgorithm. ICCA Journal, 6(4):4–14, 1983.J. Pearl. Asymptotic properties of minimax trees and game-searching procedures. Artificial Intelligence, 14(2):113–138,1980.John P. Fishburn. Another optimization of alpha-beta search.SIGART Bull., (84):37–38, 1983.


Documents

Algo Scout