hk.ps

介绍各种经典算法的代码。说明详细

(the)g(cumulati)n(v)o(e)e(number)g(of)i(leaf)g(node)f(e)n(v)n
(aluations)g(for)g(iterati)n(v)o(e)330 2133 y(deepening)16
b(v)o(ersions)i(of)g(AB-SSS*)h(and)f(Alpha-Beta.)28 b(The)18
b Fm(x)p Fs(-axis)h(gi)n(v)o(es)f(the)g(number)f(of)h(entries)g(in)330
2232 y(the)24 b(table)f(in)h(po)n(wers)f(of)g(2.)39 b(As)25
b(will)f(be)g(e)o(xplained)d(in)j(section)f(4.1,)h(these)g(numbers)e
(are)h(a)n(v)o(eraged)330 2332 y(o)o(v)o(er)c(a)h(test-set)h(of)f(20)g
(positions)g(chosen)f(to)h(be)g(representati)n(v)o(e)f(for)g(real)h
(games.)455 2432 y(F)o(or)e(small)h(tables,)g(the)g(solution)f(tree)h
(does)f(not)h(\256t)g(in)g(memory)-5 b(,)17 b(and)h(has)h(to)g(be)g
(re-e)o(xpanded)c(for)330 2531 y(each)24 b(pass)g(of)g(AB-SSS*.)41
b(As)25 b(soon)f(as)h(the)f(storage)f(reaches)h(a)g(critical)g(le)n(v)o
(el)g(and)f(essentially)i(the)330 2631 y(max)d(solution)g(tree)h
(\256ts)g(in)g(memory)-5 b(,)21 b(AB-SSS*')-5 b(s)24
b(tree)e(size)h(stabilizes,)h(and)e(becomes)g(better)g(than)330
2730 y(Alpha-Beta.)31 b(Since)21 b(the)g(line)g(is)h(more)e(or)g(less)j
(straight,)d(it)i(appears)e(that)h(after)f(a)i(certain)e(size,)i(hash)
330 2830 y(k)o(e)o(y)e(collisions)g(play)f(no)h(measurable)f(role.)455
2930 y(Man)o(y)j(reseachers)g(ha)n(v)o(e)h(conjectured)e(that)i
(best-\256rst)g(algorithms)f(such)h(as)h(SSS*)g(w)o(ould)e(need)330
3029 y(too)j(much)f(memory)g(too)h(be)g(practical)g(alternati)n(v)o(es)
f(for)h(depth)f(\256rst)j(algorithms)d(lik)o(e)h(Alpha-Beta)330
3129 y([29)o(,)j(8,)g(12)o(,)g(13)o(,)h(23)o(,)f(26)o(].)53
b(The)28 b(tests)h(with)f(our)f(reformulation)e(of)j(SSS*)h(pro)o(v)o
(e)d(otherwise.)52 b(F)o(or)330 3229 y(present-day)24
b(search)h(depths)g(in)h(applications)e(lik)o(e)i(chess)g(playing)f
(programs,)g(using)g(present-day)330 3328 y(memory)13
b(sizes,)k(and)e(con)m(v)o(entional)d(transposition)i(tables)h(as)h
(storage)f(structure,)g(we)h(see)f(that)h(SSS*')-5 b(s)330
3428 y(search)19 b(trees)i(\256t)f(without)f(problems)g(in)h(the)f(a)n
(v)n(ailable)h(memory)-5 b(.)27 b(F)o(or)19 b(most)h(real-w)o(orld)e
(programs)g(a)330 3527 y(transposition)h(table)h(size)h(of)f(10)f(Me)o
(gabyte)g(will)h(be)h(more)e(than)h(adequate)e(for)i(AB-SSS*.)455
3627 y(The)f(literature)g(cites)h(three)f(main)g(dra)o(wbacks)f(of)i
(SSS*:)29 b(it)21 b(is)f(hard)f(to)h(understand,)d(it)j(performs)330
3727 y(operations)29 b(on)i(a)g(sorted)g(list)h(that)f(are)g(slo)n(w)-5
b(,)34 b(and)c(it)i(uses)f(too)g(much)f(memory)f(to)i(be)g(practical.)
330 3826 y(W)-7 b(e)24 b(think)e(that)h(our)f(reformulation)f(as)i(a)h
(sequence)d(of)i(null)g(windo)n(w)f(Alpha-Beta)g(calls)i(is)f(easy)g
(to)330 3926 y(understand.)29 b(The)21 b(slo)n(w)g(list)h(operations)d
(are)i(traded)f(in)h(for)f(hash)h(table)g(lookups)e(that)i(are)g(as)g
(f)o(ast)h(as)330 4026 y(for)c(Alpha-Beta,)h(and)f(the)h(e)o
(xperiments)f(sho)n(w)g(that)i(AB-SSS*)f(does)g(not)g(need)f(too)h
(much)f(memory)-5 b(.)330 4125 y(W)e(e)21 b(conclude)e(that)h(the)g
(dra)o(wbacks)f(of)h(SSS*)g(are)h(solv)o(ed)e(in)h(the)g(ne)n(w)g
(formulation.)330 4363 y Fo(3.2)99 b(DU)-6 b(AL*)330
4519 y Fs(A)13 b(dual)g(v)o(ersion)g(of)g(SSS*,)g(aptly)g(named)g(DU)m
(AL*,)e(can)i(be)g(created)g(by)g(in)m(v)o(erting)g(SSS*')-5
b(s)13 b(operations:)330 4618 y(use)27 b(an)g(ascendingly)f(sorted)g
(list)i(instead)f(of)g(descending,)g(sw)o(ap)g(max)g(and)f(min)h
(operations,)g(and)330 4718 y(start)21 b(at)f Fn(\000)p
Fr(\245)h Fs(instead)f(of)g(+)p Fr(\245)h Fs([12)n(,)g(23)o(].)455
4817 y(T)-7 b(o)30 b(demonstrate)f(the)i(po)n(wer)f(of)g(the)h(MT)f
(dri)n(v)o(er)g(frame)n(w)o(ork,)g(we)h(sho)n(w)g(the)f(reformulation)
330 4917 y(called)h(AB-DU)m(AL*)f(in)i(\256gure)e(5.)62
b(The)31 b(only)f(dif)n(ference)f(with)i(AB-SSS*)h(is)g(the)f
(initialization)330 5017 y(of)d(the)h(bound)d(to)j Fn(\000)p
Fr(\245)p Fs(,)h(and)e(a)h(change)e(to)h(the)h(w)o(ay)f(Alpha-Beta)g
(is)h(called.)54 b(This)28 b(reformulation)330 5116 y(focusses)23
b(attention)f(on)h(one)g(item)g(only:)35 b(the)23 b(bound)e(starts)j
(at)g(the)f(bottom)f(of)h(the)g(scale,)h(implying)330
5216 y(that)g(the)g(only)g(fundamental)e(dif)n(ference)g(between)h
(SSS*)i(and)e(DU)m(AL*)h(is)h(that)f(upper)f(bounds)g(are)330
5316 y(replaced)e(by)g(lo)n(wer)g(bounds)g(\(which)g(implies)h(that)g
(the)g(max)f(solution)g(tree)h(that)g(is)h(re\256ned)e(by)g(AB-)330
5415 y(SSS*)f(has)g(become)f(a)h(min)f(solution)g(tree)h(in)g(AB-DU)m
(AL*\).)28 b(All)20 b(other)f(dif)n(ferences)f(are)i(apparently)330
5515 y(insubstantial,)d(since)h(Alpha-Beta)e(does)i(not)f(ha)n(v)o(e)f
(to)i(be)f(changed.)27 b(\(That)17 b(Alpha-Beta)f(can)h(be)h(used)330
5614 y(to)c(return)g(both)f(upper)g(and)h(lo)n(wer)f(bounds,)h(can)g
(be)g(seen)h(from)e(case)i(\(2\))e(and)h(\(3\))g(of)g(its)h
(postcondition.)1809 5919 y(6)p eop
%%Page: 7 7
7 6 bop 504 454 a Fv(function)18 b Fw(MTD-f\()p Fe(n)p
Fu(,)12 b Fe(g)p Fw(\))22 b Fu(\256)f(\246)p Fw(;)621
545 y Fu(\246)654 514 y Fc(+)707 545 y Fw(:=)h(+)p Fu(\245)p
Fw(;)d Fu(\246)954 514 y Fq(\000)1027 545 y Fw(:=)j Fb(\000)p
Fu(\245)p Fw(;)621 637 y Fv(r)o(epeat)737 728 y(if)c
Fe(g)k Fw(=)f Fu(\246)956 696 y Fq(\000)1027 728 y Fv(then)d
Fd(g)32 b Fw(:=)21 b Fe(g)d Fw(+)f(1)i Fv(else)g Fd(g)32
b Fw(:=)21 b Fe(g)p Fw(;)737 819 y Fe(g)h Fw(:=)c(Alpha-Beta\()p
Fe(n)p Fu(,)13 b Fd(g)28 b Fb(\000)17 b Fw(1)p Fu(,)c
Fd(g)d Fw(\);)737 911 y Fv(if)18 b Fe(g)k(<)g Fd(g)29
b Fv(then)18 b Fu(\246)1181 879 y Fc(+)1235 911 y Fw(:=)j
Fe(g)e Fv(else)g Fu(\246)1543 879 y Fq(\000)1616 911
y Fw(:=)j Fe(g)p Fw(;)621 1002 y Fv(until)17 b Fu(\246)822
970 y Fq(\000)896 1002 y Fw(=)k Fu(\246)992 970 y Fc(+)1024
1002 y Fw(;)621 1093 y Fv(r)o(etur)o(n)c Fe(g)p Fw(;)926
1359 y Fs(Figure)j(6:)29 b(MTD\()p Fr(\246)p Fs(\),)20
b(a)g(Better)h(Sequence)e(of)h(MT)g(searches.)330 1626
y(That)g(it)h(can)f(be)g(used)g(to)g(re\256ne)g(both)f(max)h(and)g(min)
g(solution)f(trees)i(is)g(sho)n(wn)e(in)h([5,)g(21)o(].\))330
1864 y Fo(3.3)99 b(Other)26 b(Options)e(f)n(or)h(the)h(choice)f(of)g
(Start)h(V)-9 b(alue)330 2020 y Fs(Ha)n(ving)17 b(seen)h(that)g(MT)g
(calls)h(are)f(\257e)o(xible)f(enough)f(to)i(be)g(started)g(of)n(f)f
(with)h(the)g(tw)o(o)g(e)o(xtremes)f(of)h(the)330 2119
y(scale,)e(and)d(ha)n(ving)g(seen)h(that)g(MT)g(can)g(be)g(used)g(to)g
(re\256ne)f(both)h(upper)e(and)i(lo)n(wer)f(bounds,)h(we)g(can)g(try)
330 2219 y(other)j(v)n(alues.)27 b(An)18 b(inuiti)n(v)o(ely)e
(appealing)g(option)g(is)i(to)g(choose)e(a)i(start)g(v)n(alue)f(closer)
g(to)h(the)f(e)o(xpected)330 2318 y(outcome.)30 b(One)21
b(option)e(is)j(to)f(k)o(eep)g(bisecting)f(the)h(interv)n(al)f(between)
g(the)h(upper)f(and)g(lo)n(wer)h(bound,)330 2418 y(to)26
b(reduce)e(the)i(number)e(of)h(MT)h(calls.)46 b(This)26
b(idea)f(has)h(been)f(described)f(in)i([4)o(,)g(20)o(,)g(30)o(].)46
b(Another)330 2518 y(idea)26 b(is)h(to)f(use)g(a)h(heuristic)e(guess)i
(as)f(the)g(start)h(v)n(alue.)46 b(In)26 b(an)g(iterati)n(v)o(e)f
(deepening)f(frame)n(w)o(ork)g(it)330 2617 y(is)g(natural)d(to)i(use)g
(the)g(score)f(from)g(the)h(pre)n(vious)e(iteration)h(for)g(this)h
(purpose,)e(since)i(it)h(is)f(e)o(xpected)330 2717 y(to)28
b(be)f(a)h(close)g(approximation)d(of)i(the)h(score)f(for)g(the)h
(current)e(depth.)51 b(W)-7 b(e)29 b(ha)n(v)o(e)e(called)g(this)h(MT)
330 2817 y(dri)n(v)o(er)21 b(MTD\()p Fr(\246)p Fs(\).)37
b(The)23 b(pseudo)e(code)i(is)g(sho)n(wn)g(in)g(\256gure)f(6.)37
b(The)22 b(\256rst)i(call)f(acts)h(to)f(decide)f(which)330
2916 y(w)o(ay)f(the)g(search)f(will)i(go.)30 b(If)21
b(it)g(is)h(a)f(f)o(ail)g(high,)f(MTD\()p Fr(\246)p Fs(\))h(will)g
(beha)n(v)o(e)f(lik)o(e)h(AB-DU)m(AL*,)f(and)g(k)o(eep)330
3016 y(increasing)26 b(the)h(lo)n(wer)g(bound)f(returned)f(by)i(MT.)g
(If)g(the)h(\256rst)g(call)f(f)o(ails)h(lo)n(w)-5 b(,)29
b(MTD\()p Fr(\246)p Fs(\))e(will,)i(lik)o(e)330 3115
y(AB-SSS*,)16 b(decrease)f(the)g(upper)f(bound)f(until)i(the)h(minimax)
e(v)n(alue)g(is)i(reached.)27 b(AB-SSS*)15 b(starts)h(of)n(f)330
3215 y(optimistic,)h(AB-DU)m(AL*)g(starts)h(of)n(f)e(pessimistic,)i
(and)f(MTD\()p Fr(\246)p Fs(\))g(starts)h(of)n(f)e(in)h(the)g(middle,)g
(possibly)330 3315 y(realistic.)455 3414 y(One)j(of)h(the)g(dra)o
(wbacks)e(of)h(AB-SSS*)i(and)e(AB-DU)m(AL*)g(is)i(the)e(high)g(number)f
(of)i(calls)h(to)e(MT)330 3514 y(that)28 b(it)g(tak)o(es)g(them)f(to)h
(con)m(v)o(er)o(ge)d(on)i(the)h(minimax)e(v)n(alue.)51
b(Most)28 b(of)f(the)h(MT)f(calls)i(mak)o(e)e(small)330
3614 y(impro)o(v)o(ements)e(to)k(the)f(bound,)g(causing)f(the)i
(process)e(to)i(continue)d(in)j(small)f(steps.)54 b(By)29
b(starting)330 3713 y(closer)k(to)g(the)g(minimax)e(v)n(alue,)36
b(man)o(y)31 b(intermediate)h(MT)h(calls)h(are)e(skipped.)67
b(MTD\()p Fr(\246)p Fs(\))32 b(tak)o(es)330 3813 y(one)d(big)g(leap)g
(to)h(come)f(close)g(to)h(the)f(minimax)f(v)n(alue,)j(dramatically)d
(dropping)f(the)i(number)f(of)330 3912 y(intermediate)16
b(MT)i(calls.)29 b(The)18 b(lo)n(wer)f(number)f(of)h(calls)i(has)f(the)
f(adv)n(antage)f(that)i(MTD\()p Fr(\246)p Fs(\))f(performs)330
4012 y(relati)n(v)o(ely)e(better)h(in)h(constrained)e(memory)g(than)h
(SSS*,)h(since)g(there)f(are)g(much)g(less)h(re-e)o(xpansions.)330
4112 y(Measurements)22 b(con\256rm)f(that)i(MT)g(typically)f(gets)i
(called)e(3)h(to)g(6)g(times)h(in)f(MTD\()p Fr(\246)p
Fs(\).)37 b(In)22 b(contrast,)330 4211 y(the)k(AB-SSS*)g(and)f(AB-DU)m
(AL*)g(results)h(are)g(poor)e(compared)g(to)i(Aspiration)e(Ne)o
(gaScout)g(when)330 4311 y(all)f(nodes)e(in)h(the)g(search)f(tree)h
(are)g(considered.)33 b(Each)21 b(of)h(these)g(algorithms)f(performs)f
(dozens)h(and)330 4411 y(often)j(e)n(v)o(en)g(hundreds)f(of)h(MT)h
(searches.)43 b(The)24 b(wider)h(the)f(range)g(of)h(leaf)g(v)n(alues,)g
(the)g(smaller)g(the)330 4510 y(steps)c(with)f(which)g(the)o(y)f(con)m
(v)o(er)o(ge,)e(and)j(the)g(more)f(re-searches)g(the)o(y)h(need.)330
4790 y Ft(4)119 b(P)n(erf)m(ormance)330 4976 y Fs(T)-7
b(o)17 b(assess)i(the)f(feasibility)e(of)h(the)h(proposed)d
(algorithms,)h(a)i(series)g(of)f(e)o(xperiments)e(w)o(as)j(performed.)
330 5076 y(W)-7 b(e)22 b(present)e(data)h(for)f(the)g(comparison)f(of)h
(Alpha-Beta,)g(Aspiration)g(Ne)o(gaScout,)f(AB-SSS*,)i(AB-)330
5175 y(DU)m(AL*,)e(and)h(MTD\()p Fr(\246)p Fs(\).)330
5413 y Fo(4.1)99 b(Experiment)27 b(Design)330 5569 y
Fs(W)-7 b(e)15 b(will)f(assess)h(the)e(performance)e(of)i(the)h
(algorithms)e(by)h(counting)f(leaf)h(nodes)g(and)g(total)h(nodes.)26
b(F)o(or)330 5668 y(tw)o(o)17 b(algorithms)f(we)i(also)f(pro)o(vide)f
(data)h(for)f(e)o(x)o(ecution)f(time.)29 b(This)17 b(metric)g(may)g(v)n
(ary)f(considerably)1809 5919 y(7)p eop
%%Page: 8 8
8 7 bop 330 390 a Fs(for)30 b(dif)n(ferent)f(programs.)58
b(It)31 b(is)h(ne)n(v)o(ertheless)d(included,)i(to)g(gi)n(v)o(e)f(e)n
(vidence)f(of)h(the)h(potential)f(of)330 490 y(MTD\()p
Fr(\246)p Fs(\).)455 589 y(W)-7 b(e)20 b(ha)n(v)o(e)f(tried)f(to)i
(come)e(as)i(close)g(to)f(real)g(life)h(applications)e(of)h(our)f
(algorithms)g(as)i(possible)f(by)330 689 y(conducting)f(the)i(e)o
(xperiments)e(with)j(a)f(tournament-quality)c(game)k(playing)e
(program.)455 789 y(All)24 b(algorithms)e(used)h(iterati)n(v)o(e)g
(deepening.)37 b(The)o(y)23 b(are)g(repeatedly)f(called)i(with)f
(successi)n(v)o(ely)330 888 y(deeper)f(search)h(depths.)39
b(All)24 b(three)f(algorithms)f(use)h(a)h(standard)f(transposition)f
(table)h(with)h(a)f(max-)330 988 y(imum)36 b(of)g(2)709
958 y Fk(21)808 988 y Fs(entries;)44 b(the)36 b(tests)i(from)d(section)
h(3.1)g(sho)n(wing)f(that)i(the)f(solution)g(trees)h(could)330
1088 y(comfortably)23 b(\256t)j(in)g(tables)g(of)f(this)h(size,)h
(without)e(an)o(y)g(risk)g(of)g(noise)h(due)f(to)g(collisions.)45
b(F)o(or)25 b(our)330 1187 y(e)o(xperiments)d(we)i(used)f(the)h
(original)e(program)g(author')-5 b(s)23 b(transposition)f(table)i(data)
f(structures)g(and)330 1287 y(code)g(without)f(modi\256cation.)1231
1257 y Fk(1)1302 1287 y Fs(At)h(an)h(interior)e(node,)h(the)g(mo)o(v)o
(e)f(suggested)h(by)g(the)g(transposition)330 1386 y(table)18
b(is)h(al)o(w)o(ays)f(searched)f(\256rst)i(\(if)f(kno)n(wn\),)e(and)i
(the)g(remaining)e(mo)o(v)o(es)h(are)h(ordered)e(before)h(being)330
1486 y(searched.)28 b(Phoenix)19 b(uses)i(dynamic)d(ordering)g(based)i
(on)g(the)g(history)g(heuristic)f([28)o(].)455 1586 y(Con)m(v)o
(entional)d(test)j(sets)h(in)f(the)f(literature)g(pro)o(v)o(ed)e(to)j
(be)g(inadequate)d(to)j(model)f(real-life)g(condi-)330
1685 y(tions.)29 b(Positions)18 b(in)g(test)h(sets)g(are)f(usually)g
(selected)g(to)g(test)h(a)g(particular)e(characteristic)g(or)h
(property)330 1785 y(of)24 b(the)h(game)f(\(such)f(as)j(tactical)f
(combinations)d(in)j(chess\))g(and)f(are)g(not)h(necessarily)f
(indicati)n(v)o(e)f(of)330 1885 y(typical)k(game)f(conditions.)49
b(F)o(or)27 b(our)g(e)o(xperiments,)g(the)g(algorithms)f(were)i(tested)
f(using)g(a)h(set)g(of)330 1984 y(20)c(positions)h(that)g(corresponded)
c(to)k(mo)o(v)o(e)f(sequences)g(from)g(tournament)e(games.)43
b(By)25 b(selecting)330 2084 y(mo)o(v)o(e)g(sequences)h(rather)f(than)i
(isolated)f(positions,)h(we)g(are)g(attempting)e(to)i(create)f(a)h
(test)g(set)g(that)330 2183 y(is)f(representati)n(v)o(e)d(of)h(real)h
(game)f(search)g(properties)g(\(including)f(positions)h(with)h(ob)o
(vious)e(mo)o(v)o(es,)330 2283 y(hard)h(mo)o(v)o(es,)g(positional)g(mo)
o(v)o(es,)g(tactical)i(mo)o(v)o(es,)e(dif)n(ferent)f(game)h(phases,)h
(etc.\).)43 b(A)25 b(number)e(of)330 2383 y(test)g(runs)f(w)o(as)i
(performed)19 b(on)j(a)h(bigger)e(test)j(set)f(and)f(to)g(a)h(higher)e
(search)h(depth)g(to)g(check)g(that)h(the)330 2482 y(20)d(positions)f
(did)h(not)g(contain)f(anomalies.)455 2582 y(Man)o(y)25
b(papers)h(in)g(the)h(literature)f(use)g(Alpha-Beta)g(as)h(the)g
(base-line)f(for)f(comparing)g(the)h(per)n(-)330 2682
y(formance)i(of)h(other)g(algorithms)f(\(for)h(e)o(xample,)h([3)o(,)g
(11)o(]\).)58 b(The)29 b(implication)f(is)j(that)f(this)g(is)h(the)330
2781 y(standard)c(data)h(point)f(which)h(e)n(v)o(eryone)e(is)j(trying)e
(to)h(beat.)53 b(Ho)n(we)n(v)o(er)m(,)28 b(game-playing)c(programs)330
2881 y(ha)n(v)o(e)e(e)n(v)n(olv)o(ed)e(be)o(yond)g(simple)i(Alpha-Beta)
f(algorithms.)34 b(Most)22 b(use)h(Alpha-Beta)e(enhanced)f(with)330
2980 y(minimal)27 b(windo)n(w)f(search)h(\(Ne)o(gaScout\),)f(iterati)n
(v)o(e)h(deepening,)f(transposition)g(tables,)j(mo)o(v)o(e)d(or)n(-)330
3080 y(dering)c(and)h(an)g(initial)g(aspiration)g(windo)n(w)-5
b(.)37 b(Since)23 b(this)h(is)g(the)f(typical)g(search)g(algorithm)e
(used)i(in)330 3180 y(high-performance)16 b(programs)i(\(such)i(as)h
(Phoenix\),)e(it)i(seems)g(more)e(reasonable)g(to)i(use)f(this)h(as)g
(our)330 3279 y(base-line.)455 3379 y(The)35 b(w)o(orse)h(the)g
(base-line)g(comparison)e(algorithm)g(chosen,)39 b(the)d(better)g
(other)f(algorithms)330 3479 y(appear)22 b(to)h(be.)38
b(By)23 b(choosing)e(Ne)o(gaScout)h(enhanced)f(with)i(aspiration)f
(searching)f([2])i(\(Aspiration)330 3578 y(Ne)o(gaScout\))i(as)i(our)g
(performance)d(metric,)k(and)e(gi)n(ving)g(it)h(a)h(transposition)d
(table)i(big)g(enough)d(to)330 3678 y(contain)g(all)i(re-search)d
(information,)h(we)i(are)f(emphasizing)e(that)i(it)h(is)g(possible)f
(to)g(do)f(better)h(than)330 3778 y(the)h(\252best\272)f(methods)g
(currently)e(practiced)i(and)g(that,)h(contrary)e(to)i(published)e
(simulation)g(results,)330 3877 y(some)c(methods\320notably)d
(SSS*\320will)k(turn)f(out)g(to)g(be)g(inferior)-5 b(.)455
3977 y(Because)21 b(we)g(implemented)e(the)i(MTD)f(algorithms)g(\(lik)o
(e)h(AB-SSS*)g(and)f(AB-DU)m(AL*\))g(using)330 4076 y(MT)j
(\(null-windo)n(w)d(Alpha-Beta)i(calls)i(with)f(a)g(transposition)f
(table\))g(we)h(were)g(able)g(to)g(compare)e(a)330 4176
y(number)f(of)h(algorithms)f(that)i(were)f(pre)n(viously)e(seen)j(as)g
(v)o(ery)f(dif)n(ferent.)31 b(By)22 b(using)f(MT)g(as)h(a)g(com-)330
4276 y(mon)g(proof-procedur