Selective Searching
Bob Durrett
the last ten years, how to do selective searching in the best way.
I was not around [in the computer chess world] ten years ago and have not
followed the progress in the development of this technology.
If there are any "computer chess historians" looking at this, would you mind
summarizing this here, to bring everybody up-to-speed on this?
Thanks in advance.
Anders Thulin
> On CCC, it was noted that chess-playing programmers have known, for at least
> the last ten years, how to do selective searching in the best way.
'chess-playing programmers'? I suspect you mean 'computer chess programmers'.
Searching is a very complex area. As far as I understand, chess programmers
may possibly lay claim to to do *internal* selective searching in the best way --
although I sort of doubt that as there's no obvious interpretation of 'best'.
Whether they are any good at external searches, such as database searches, is
a different question.
One area closely related to searching is IP routing -- the faster the search for
a network / netmask can be done, the quicker the IP packet can be sent on its
way, and the faster the router and hence the network will operate.
No, I don't think the programmers of these algorithms do any chess programming.
--
Anders Thulin Anders....@telia.se 040-10 50 63
Telia Prosoft AB, Box 85, S-201 20 Malmö, Sweden
Steve Maughan
~1940 Turing hypothesised about how a computer could play chess
1950s First games playing machines including Samuels Checkers program
~1956 First use of Alpha Beta algorithm allowing machines to search 'much'
deeper
1978 Arrival of the chess challenger series by the Spracklens. Mainly brute
force i.e. looks at all of the possible moves
1982 Mephisto 2 launched. Tries to be selective - looking at ~3 positions
per second. Doesn't work too well. Mark V does a better job but brute
force rules!
1985 Amsterdam by Lang win the WCCC. First successful selective search
machine.
~1987 Mach III does well to hold it's own against Lang's more selective
programs. MM3 starts to be selective.
1990 The PC programs emerge. Until now _ALL_ successful programs were
written in assembler. At about this time the 'c' programs start to emerge
e.g. The King in the ChessMachine. In addition the 'null' move' algorithm
is discovered / becomes popular. This gives selectivity to brute force
programs.
1991 Fritz 1 / KnightStalker emerges as a fast 'null mover'. MChess
dominates the PC market with some highly selective searching.
1992 Genius 1 by Richard Lang. This marks the move from dedicated to PC
programs. Genius uses a selective search algorithm and dominates the
market.
1995 Fritz 3 reaches 100,000 nodes / second on a Pentium 90. The power of
the PC now means that programmers can have the luxury of trying and testing
much more elaborate search techniques. HIARCS also starts to do well as
does Junior, both written in 'C'
~1996 Crafty launched by Bob Hyatt as a open source project. This marks the
starts of the strong amateur programs. The internet becomes prevalent and
it becomes relatively easy to find all necessary info on computer chess
programming. Bob also introduces the World to bitboard as a way of
generating chess moves. From this stage selective search rules - a pure
brute force wouldn't stand a chance.
1997 Due to ICC and FICS (online chess) the programs are thoroughly tested
against computer chess savvy opponents. King safety emerges as a major
weakness. Programmers beef up king safety aspects of the evaluation.
Shredder comes from nowhere to win the WCCC.
1998 Parallel PC programs emerge Crafty and Deep Junior (1999). On the
fastest hardware this gives 1,000,000 nodes per second. CSTal by Chris
Whittington is launched. This aims to know how to attack and has a
sophisticated evaluation function and slow search (5k node/sec)
1999 Plethora of Winboard programs become freeware. This has definitely
changed the market. Commercial apps no longer look so attractive. Anyone
can have >50 engines on their PC without spending a penny.
2000 Shredder is clearly strong. Gambit Tiger may have a more successful
CSTal type approach and Rebel is still making progress with Century 3.0
Hope it's useful
Regards,
Steve Maughan
------------------------------------------------------------
Chess, Othello and European Union
http://www.maughan.clara.net
"Bob Durrett" <rhd...@bellsouth.net> wrote in message
news:VaTR5.720$u62....@news4.atl...
> On CCC, it was noted that chess-playing programmers have known, for at
least
> the last ten years, how to do selective searching in the best way.
>
Bob Durrett
"Anders Thulin" <Anders....@telia.se> wrote in message
news:3A18CE3E...@telia.se...
> Bob Durrett wrote:
>
> > On CCC, it was noted that chess-playing programmers have known, for at
least
> > the last ten years, how to do selective searching in the best way.
>
> 'chess-playing programmers'? I suspect you mean 'computer chess
programmers'.
Yes. "Haste makes waste." I got in too big of a hurry to write my
question.
> Searching is a very complex area. As far as I understand, chess
programmers
> may possibly lay claim to to do *internal* selective searching in the best
way --
> although I sort of doubt that as there's no obvious interpretation of
'best'.
> Whether they are any good at external searches, such as database searches,
is
> a different question.
Please forgive my ignorance. I do not know the distinction between
*internal* selective searching and other kinds. Could you please elaborate?
> One area closely related to searching is IP routing -- the faster the
search for
> a network / netmask can be done, the quicker the IP packet can be sent on
its
> way, and the faster the router and hence the network will operate.
Again, please forgive my ignorance. What are "IP routing" and
"network/netmask"? By "router," are you referring to a computer on the
internet?
I suspect that I am not the only uninformed person here. Maybe others could
benefit from any additional explainations you may care to offer.
Are there websites which explain these things? Perhaps they are elementary
concepts which any computer chess programmer should know about?
Ed Schroder
Very nice overview Steve!
Like to add that Rebel since day one (1981) has been selective. I dumped
the brute force method immediately.
Kind regards,
Ed Schroder
__________________________________________________________________________
_____ _ _
| _ \ | | | | WWW: http://www.rebel.nl
| |_| / ____| |__ ____| | Email: in...@rebel.nl
| _ \/ _ ) _ \ / _ ) |
| | | | (/ (| |_| ( (/ (| |__ Results: http://www.rebel.nl/results.htm
|_| |_|\____)____/ \____)____| Features: http://www.rebel.nl/features.htm
__________________________________________________________________________
Anders Thulin
> Please forgive my ignorance. I do not know the distinction between
> *internal* selective searching and other kinds.
I don't know what to say ... I thought I gave an example.
> Are there websites which explain these things? Perhaps they are elementary
> concepts which any computer chess programmer should know about?
I doubt it.
In one sense I'm only questioning the use of the term 'best'.
Carlos Linares
Regarding selective search and what other people have answered yet, I'd like
to add some (useful?) bibliographical references regarding selective search.
First of all, selective search is a completely different method for
performing search.
Whereas old search algorithms (namely, alpha-beta and all of its related
algorithms
like falpha-beta, lalpha-beta [Campbell, 83] and even SSS* [Roizen, 93;
Pearl, 84]
and, more recently, MTD [Plaat, ?]) exhaustively explore the whole state
space tryin'
to cut off as many nodes as they can (in order to achive higher
performance), selective
search tries to imitate the human searching method, i.e., instead of
searching through the
whole state space, they just explore a few lines. Just those ones they
consider of interest.
And this is what selective search tries to do.
There are many ways for achieving this goal and many researchers have
proposed new ideas.
One I like a lot is Recursive-Best-First-Search [Korf, 94] which can be
equally applied to
one-agent or two-player search algorithms. One of the first selective search
algorithms
is conspiracy-numbers [McAllester, 88] which was re-considered and enhanced
by
Jonathan Schaeffer [Schaeffer, 90] who has been devoted to the study of this
search
algorithm for a long. Another algorithm which is quite well-known is
Quiescence Search
[Beal, 90]. This algorithm tries to identify quiescence positions and
explore them in
order to get a stable game value. Another excellent (really!) approach is
the one
devised by Ingo Althofer who proposed the Incremental Negamax Algorithm
[Althofer, 90]
mainly devoted to reduce the propagation errors through the game search
(but, ok, this
is not selective search but could be succesfully applied, of course! I
couldn't avoid
mention this great work! :). Anoher selective search is Singular Extensions
[Anantharaman, 90] which consist of a mathematical treatment of the scores
in order
to perform selective search. Recently, Louis Victor Allis has proposed
proof-number
search [Allis, 94] which works very well in some domains as Awari and, of
course,
chess. This researcher is still working on his idea and you can find other
papers regarding
proof-number search in [Maastricht]. And, at last, but not least, the last
selective search
algorithm I've ever heard is ProbCut [Buro, 95] which is developed upon some
very
useful statistical ideas and was firstly tested on Logistello, the best
othello player in the
world (even human players fail to beat Logistello and my program that was
called
Monyca was terribly crashed by Logistello with an unforgetable 63-0 :)
Finally another method for selective searching can be achieved handling
knowledge
within the tree search [Wilkins, 82]
Ah! Yes, somebody has mentioned Null-move, ... That's a good idea as well.
It
simply consists of considering it is your opponent's turn and to look for
"killer"
moves. If it can checkmate you in 1, your choices has been dramatically
reduced
and you know have to look only for those moves that can evitate the great
disaster.
Nevertheless, I cannot find the reference I have about Null-move. Sorry! :(
I hope this helps,
Bibliography:
[Allis, 94] Louis Victor Allis, Maarten van der Meulen, H. Jaap van den
Herik.
Proof-number search. Artificial Intelligence, 66:91-124, 1994
[Anantharaman, 90] Singular Extensions: Adding Selectivity to Brute-Force
Searching.
Artificial Intelligence, 43: 99-109, 1990.
[Beal, 90] Don F. Beal. A Generalised Quiescence Search. Artificial
Intelligence,
43: 85-98, 1990.
[Buro, 95] Michael Buro. ProbCut: A powerful selective extension of the
alpha-beta
algorithm. Journal of the International Computer Chess Association,
18(2):71-81, 1995
[Campbell, 83] Murray S. Campbell, T. Anthony Marsland. A comparison of
Minimax tree search Algorithms. Artificial Intelligence, 20:347-367, 1983
[Korf, 94] Richard E. Korf and David Maxwell Chickering. Best-first minimax:
othello-results. In Proceedings of the National Conference on Artificial
Intelligence
(AAAI-94), August, 94. I think they published another paper in "Artificial
Intelligence"
but I'm not sure, ... maybe you should have a look there as well.
[Maastricht] http://www.cs.rulimburg.nl/~uiterwyk/cg.htm
[McAllester, 88] Conspiracy Numbers for Min-Max Search. Artificial
Intelligence,
35:287-310, 1988
[Pearl, 84] Judea Pearl. Heuristics: Intelligent Search Strategies for
Computer Problem
Solving.Addison-Wesley, 1984. Reading, Massachusets. ISBN 0-201-05594-5
[Plaat, ?] Ok, I have this reference elsewhere but know I don't know exactly
where.
Anyway, check Maastricht and you'll find it. Here I'm referring his PhD
named something
like: Re-search: searching and re-searching or something like that.
[Roizen, 83] Igor Roizen and Judea Pearl. A Minimax Algorithm Better than
Alpha-Beta? Yes and No, 21:199-220, 1983. There is an article older than
this
presenting the SSS* for the very first time, but [Pearl, 83] is even more
complete.
[Schaeffer] http://games.cs.ualberta.ca/~jonathan/
From here you can access all his papers where you will find many dedicated
to
conspiracy numbers and other search algorithms as well.
[Schaeffer, 90] Conspiracy Numbers. Jonathan Schaeffer. Artificial
Intelligence: 43:
67-84, 1990. If you are quite interested in Conspiracy Numbers you can find
quite a lot papers regarding this search algorithm in the Schaeffer's home
page:
http://games.cs.ualberta.ca/~jonathan/
[Wilkins, 82] David E. Wilkins. Using Knowledge to Control Tree Searching.
Artificial Intelligence, 18: 1-51, 1982
PS - In http://liinwww.ira.uka.de/bibliography/Ai/minimax.html you can find
a great collection of minimax bibliographical references collected by
Diderich.
Thanks Diderich!! Excellent job!!!
Bob Durrett <rhd...@bellsouth.net> escribió en el mensaje de noticias
VaTR5.720$u62....@news4.atl...
> On CCC, it was noted that chess-playing programmers have known, for at
least
> the last ten years, how to do selective searching in the best way.
>
Carlos Linares
Regarding selective search and what other people have answered yet, I'd like
to add some (useful?) bibliographical references regarding selective search.
First of all, selective search is a completely different method for
performing search.
Whereas old search algorithms (namely, alpha-beta and all of its related
algorithms
like falpha-beta, lalpha-beta [Campbell, 83] and even SSS* [Roizen, 93;
Pearl, 84]
and, more recently, MTD [Plaat, 96]) exhaustively explore the whole state
Ah! Yes, somebody has mentioned Null-move, ... [Beal, 90] That's a good idea
as well.
It
simply consists of considering it is your opponent's turn and to look for
"killer"
moves. If it can checkmate you in 1, your choices has been dramatically
reduced
and you know have to look only for those moves that can evitate the great
disaster.
I hope this helps,
Bibliography:
[Allis, 94] Louis Victor Allis, Maarten van der Meulen, H. Jaap van den
Herik.
Proof-number search. Artificial Intelligence, 66:91-124, 1994
[Anantharaman, 90] Singular Extensions: Adding Selectivity to Brute-Force
Searching.
Artificial Intelligence, 43: 99-109, 1990.
[Beal, 89] Don F. Beal. Experiments with the {N}ull Move.
Advances in Computer Chess, 5: 65-79, 1989.
[Beal, 90] Don F. Beal. A Generalised Quiescence Search. Artificial
Intelligence,
43: 85-98, 1990.
[Buro, 95] Michael Buro. ProbCut: A powerful selective extension of the
alpha-beta
algorithm. Journal of the International Computer Chess Association,
18(2):71-81, 1995
[Campbell, 83] Murray S. Campbell, T. Anthony Marsland. A comparison of
Minimax tree search Algorithms. Artificial Intelligence, 20:347-367, 1983
[Korf, 94] Richard E. Korf and David Maxwell Chickering. Best-first minimax:
othello-results. In Proceedings of the National Conference on Artificial
Intelligence
(AAAI-94), August, 94. I think they published another paper in "Artificial
Intelligence"
but I'm not sure, ... maybe you should have a look there as well.
[Maastricht] http://www.cs.rulimburg.nl/~uiterwyk/cg.htm
[McAllester, 88] Conspiracy Numbers for Min-Max Search. Artificial
Intelligence,
35:287-310, 1988
[Pearl, 84] Judea Pearl. Heuristics: Intelligent Search Strategies for
Computer Problem
Solving.Addison-Wesley, 1984. Reading, Massachusets. ISBN 0-201-05594-5
[Plaat, 96] Aske Plaat. Research Re: Search {\&} Re-Search. PhD Thesis,
Rotterdam, 1996.
Ernst A. Heinz
> the last ten years, how to do selective searching in the best way.
>
> I was not around [in the computer chess world] ten years ago and have not
> followed the progress in the development of this technology.
>
> If there are any "computer chess historians" looking at this, would you mind
> summarizing this here, to bring everybody up-to-speed on this?
>
> Thanks in advance.
My book on "Scalable Search in Computer Chess" discusses various flavours
of selective search and its history in computer chess. The first part of
the book exclusively focusses on selective search techniques (see
http://supertech.lcs.mit.edu/~heinz/node1.html for details).
Please enjoy,
=Ernst=
+--------------------------------------------------------------------------+
| Ernst A. Heinz, M.I.T. Lab for CS, NE 43-228, 545 Technology Square, |
| Cambridge, MA 02139, USA. WWW: <http://supertech.lcs.mit.edu/~heinz/> |
| Tel. / Fax: +1-617-253 8853 / 253 0415 E-Mail: <he...@mit.edu> |
+--------------------------------------------------------------------------+
"It has recently been found out that research causes cancer in rats!"
Steve Maughan
> Very nice overview Steve!
Thanks!
> Like to add that Rebel since day one (1981) has been selective. I dumped
> the brute force method immediately.
Interesting. What were the nodes / sec and seach depths back in 1981?
Regards,
Steve maughan