Excellent Computer-Chess Overview Paper Found!

357 views
Skip to first unread message

Ernst A. Heinz

unread,
Mar 6, 1997, 3:00:00 AM3/6/97
to

Hi all,

yesterday I literally stumbled over an excellent paper named

"Computer Chess and Search," in <Encyclopedia of Artificial Intelligence>,
S. Shapiro (editor), J. Wiley & Sons, 2nd edition, 1992, pages 224-241.

The paper was written by ICCA president Prof. Tony Marsland and seems to be
little known in our community. This is very unfortunate because the paper
constitutes the *best* introductory and overview work on computer chess that
I have seen so far. It contains interesting historical accounts and lots of
detailed descriptions characterizing nearly all sophisticated techniques
relevant for state-of-the-art chess programs.

Excerpts: - minimax search, alpha-beta, minimal tree, horizon effect

- aspiration search, iterative deepening, minimal/zero window
search, null-move and other forward pruning, PVS, selective
search, quiescence search, razoring

- move ordering, transposition tables, refutation tabels,
trans/ref cutoffs, killer heuristic, history heuristic

- Zobrist's hashing scheme, structure of transposition table
entry, hash replacement schemes, pawn and king hash tables

- good Pascal pseudo-code for aspiration window narrowing,
fail-soft alpha-beta, fail-soft PVS, fail-soft minimal
window search with transposition table access and cutoff

The Pascal pseudo-codes are almost directly usable such that I highly
recommend this paper especially for beginners who intend to write their own
chess programs.

Cheers and have an interesting time studying!

=Ernst=

+----------------------------------------------------------------------------+
| Ernst A. Heinz, School of CS (IPD), Univ. of Karlsruhe, P.O. Box 6980, |
| D-76128 Karlsruhe, F.R. Germany. WWW: <http://wwwipd.ira.uka.de/~heinze> |
| Mail: <hei...@ira.uka.de> Tel: +49-(0)721-6084386 Fax: +49-(0)721-694092 |
+----------------------------------------------------------------------------+
"It has recently been found out that research causes cancer in rats!"

Tim Foden

unread,
Mar 7, 1997, 3:00:00 AM3/7/97
to


Ernst A. Heinz <hei...@ira.uka.de> wrote in article <01bc2b08$4cff6530$0100007f@fork>...


| Hi all,
|
| yesterday I literally stumbled over an excellent paper named
|
| "Computer Chess and Search," in <Encyclopedia of Artificial Intelligence>,
| S. Shapiro (editor), J. Wiley & Sons, 2nd edition, 1992, pages 224-241.
|
| The paper was written by ICCA president Prof. Tony Marsland and seems to be
| little known in our community. This is very unfortunate because the paper
| constitutes the *best* introductory and overview work on computer chess that
| I have seen so far. It contains interesting historical accounts and lots of
| detailed descriptions characterizing nearly all sophisticated techniques
| relevant for state-of-the-art chess programs.
|

...snip...

I would be very interested to read this paper. The trouble is that I
don't think my local (Newquay, Cornwall) library will have a copy ;-)
Does anyone know any way of obtaining it online?

Cheers, Tim.

Ernst A. Heinz

unread,
Mar 8, 1997, 3:00:00 AM3/8/97
to

Peter W. Gillgasch <gil...@ilk.de> wrote:

> Ernst A. Heinz <hei...@ira.uka.de> wrote:
>
>> The paper was written by ICCA president Prof. Tony Marsland and seems to be
>> little known in our community.
>

> A revised version of this paper is printed in one of the first ICCAJs.
> *I* have read it in 1993. Sorry, couldn't resist... 8^)
>
> -- Peter

Peter,

while reading so much about about computer chess you seem to have lost your
sense of logic ... :-(

How can a *revised* version of a paper originally published in *1992* be printed in
one of the first ICCA Journals which started as such in *1983*?

Moreover, I checked the cumulative table of contents of the ICCA Journal as
compiled by Jos Uiterwijk and electronically available on the ICCA page at

http://bommel.cs.rulimburg.nl/icca/

*before* I sent my original post. Unfortunately, I did not find any similar
or revised version of this paper in there.

Why don't you name the ICCA Journal reference you talk of in order to enlighten
the dumb rest of us?

=Ernst=

Dr. Christian Renner

unread,
Mar 8, 1997, 3:00:00 AM3/8/97
to

>Seriously, everybody who is interested should join the ICCA and order
>the back issues. Good stuff.

How can the ICCA be joined?

Ciao
Christian Renner
--
Erlangen, Germany ++ V:+9131-207473 ++IRC:Marchal ++ pgp-key on request
"The only way to really learn something is to teach it."
Mike Hess

Peter W. Gillgasch

unread,
Mar 9, 1997, 3:00:00 AM3/9/97
to

Ernst A. Heinz <hei...@ira.uka.de> wrote:

> How can a *revised* version of a paper originally published in *1992* be
> printed in one of the first ICCA Journals which started as such in *1983*?

See below... Key words are: 2nd edition, delay between actually
publishing an encyclepedia and asking for articles for it etc.



> Moreover, I checked the cumulative table of contents of the ICCA Journal as
> compiled by Jos Uiterwijk and electronically available on the ICCA page at
>
> http://bommel.cs.rulimburg.nl/icca/
>
> *before* I sent my original post. Unfortunately, I did not find any similar
> or revised version of this paper in there.

Bad luck indeed. Fortunately I have my own TOC, xref'ed, annotated and
hyperlinked compiled into the back of my brain by actually reading and
trying stuff 8^)

> Why don't you name the ICCA Journal reference you talk of in order to
> enlighten the dumb rest of us?

With pleasure:

Point your nose to ICCAJ Vol. 9, No. 1 (March 1986), page 3. T. A.
Marsland, A Review of game tree pruning.

Quote foot note:

Much of this article is a revsision of material condensed from an entry
entitled "Computer Chess Methods" prepared for the Encyclopedia of
Artificial Intelligence, S. Shapiro (editor), to be published by John
Wiley & Sons in 1987.

End quote foot note.

I agree that it is a __great__ article. Among tons of other things
DarkThought's original hashing code was implemented after reading it in
93, so I just had to giggle, to say the least...

-- Peter

May God grant me the serenity to accept the things I cannot change,
courage to choke the living shit out of those who piss me off,
and wisdom to know where I should hide the bodies...

Ernst A. Heinz

unread,
Mar 9, 1997, 3:00:00 AM3/9/97
to

> Peter W. Gillgasch wrote:
>> Ernst A. Heinz <hei...@ira.uka.de> wrote:
>>
>> Why don't you name the ICCA Journal reference you talk of in order to
>> enlighten the dumb rest of us?
>
> With pleasure:
>
> Point your nose to ICCAJ Vol. 9, No. 1 (March 1986), page 3. T. A.
> Marsland, A Review of game tree pruning.

Oh Peter,

please come on -- the "old" article you refer to above constitutes just an
early version of less than half the material contained in the 1992 contribution
"Computer chess and search". Hint: many bibliographic references of the latter
have publication dates beyond 1986/87.

But you are right in that "A review of game tree pruning" is still worthwhile
reading if you do not have access to copies of the much extended later version!

>> How can a *revised* version of a paper originally published in *1992* be
>> printed in one of the first ICCA Journals which started as such in *1983*?
>
> See below... Key words are: 2nd edition, delay between actually
> publishing an encyclepedia and asking for articles for it etc.
>

> [...]


>
> Quote foot note:
>
> Much of this article is a revsision of material condensed from an entry
> entitled "Computer Chess Methods" prepared for the Encyclopedia of
> Artificial Intelligence, S. Shapiro (editor), to be published by John
> Wiley & Sons in 1987.

Sorry, I still can't follow your logic because I did not refer to the 1987
edition of the "Encyclopedia of Artificial Intelligence" ...

=Ernst=

Chris Whittington

unread,
Mar 9, 1997, 3:00:00 AM3/9/97
to

--
http://www.demon.co.uk/oxford-soft

Dr. Christian Renner <C.Re...@daneel.franken.de> wrote in article
<6SViR...@daneel.franken.de>...


>
> >Seriously, everybody who is interested should join the ICCA and order
> >the back issues. Good stuff.
>
> How can the ICCA be joined?

Send 25 pounds sterling equivalent, or 40 dollars US equivalent to:

ICCA
Don Beal
Dept of Computer Science
Queen Mary and Westfield College
Mile End Road
London E1 4NS
England

Fuller details: ic...@dcs.qmw.ac.uk

Or to pay in Dutch currencyor by direct credit transfer to Netherlands try:
ic...@cs.rulimburg.nl

Chris Whittington

Tom C. Kerrigan

unread,
Mar 9, 1997, 3:00:00 AM3/9/97
to

Peter W. Gillgasch (gil...@ilk.de) wrote:

> Peter W. Gillgasch <gil...@ilk.de> wrote:

> > Ernst A. Heinz <hei...@ira.uka.de> wrote:
> >

> > > The paper was written by ICCA president Prof. Tony Marsland and seems to be
> > > little known in our community.

> Yeah I know that it is pretty lame to follow up your own post... The
> original message reminded me that someone wanted to write a "technical"
> FAQ for this newsgroup... Hi Tom :) Also Bob said something about a book
> he wants to write some time ago... Or should we declare Crafty as "the
> FAQ" ?

Hi Peter :)

Yeah, I started writing something but it turns out there's already some
guy who's maintaining a FAQ that already exists. Seems like a better deal
than what I had. :)

Wiederhoeren,
Tom

Reply all
Reply to author
Forward
0 new messages