From: sje@xylos.ma30.bull.com (Steven J. Edwards)
Subject: GA and chessplaying programs (Was: Simple problems to solve)
Reply-To: sje@xylos.ma30.bull.com
Organization: Bull HN, Worldwide Information Systems, Billerica, Mass., USA
Date: 12 Jan 93 15:59:59
	<1993Jan11.145224@IASTATE.EDU> <7268265448-38850@exaia>
	<1993Jan12.120525@IASTATE.EDU>

In article <1993Jan12.120525@IASTATE.EDU> kv07@IASTATE.EDU (Warren Vonroeschlaub) writes:
# In article <7268265448-38850@exaia>, bruhn@exaia (Peter Bruhn ) writes:
# >In article <1993Jan11.145224@IASTATE.EDU> from [Mon, 11 Jan 1993 20:52:24 GMT]
# you wrote:
# >> In article <1993Jan8.202702.21180@fcom.cc.utah.edu>,
# >> freier@mail.physics.utah.edu (rodney james freier) writes:
# >> >   I'm looking for a few simple games/problems that can be played/solved
# >> > genetically.  I'm just trying to practice with the concept.
# >> 
# >>   Just about any game with an evaluation phase can be done (chess, checkers,
# >> tic-tac-toe).  Just have an alpha-beta search with node rating, and evolve
# >> different ways to rate nodes.  I did this way back with connect-four.
# >> 
# >>   I think some of the top chess programs already do this.
# > 
# >Really? I am highly interested in more information. What chess program does
# >use GAs? Any references?
#
#   I remember hearing that Carnegie Mellon's "Deep Thought" chess player had its
# position evaluater made by a GA (It was #1 in '90 or therabouts).  Can't give
# any references though, sorry.  Try looking in the procedings of the computer
# chess competitions at around that time.  Some others have done this too from
# what I've heard.

As I recall, the Deep Thought team did not use a traditional GA, but
instead employed a hill-climbing approach that provided simultaneous
optimization of several dozen positional evaluation parameter scalars.
The details can be found in past issues of the _ICCA Journal_ (for
subscription details, see the rec.games.chess FAQ or e-mail me).  The
optimization run was made using several thousand master level games
provided by a commercial database service.

I myself am a computer chessplaying program researcher and I am
working on the topic of machine learning in such programs.  My
approach does not use classical GA, but is instead based on "rule
pool" (cf. "gene pool") evolution where rules (pattern templates) are
automatically generated, applied, and scored.  Although I have a
reasonably strong working program, its rule pool subsystem is far from
complete.  However, I feel that this approach is superior to a
classical GA method because of the immense combinatorial numbers
involved in chess search and also because of some previous success
with rule pool evolution as part of an earlier NLP project of mine.

I am hesitent to go into details as much is still yet to be done.  It
may very well be that my particular rule pool approach is insufficient
for the chessplaying domain.  On the other hand, I consider it very
unlikely that any reasonable hardware (ca. US$1000) implementation
using unintelligent brute force has a chance against hardware like
Deep Thought and its multiple MHz node freqencies.  A world class
chessplaying program on a microcomputer must use some sort of
intelligence to hold its own against the special purpose machines.  I
feel that a rule pool method is the best approach; others may prefer
some sort of GA.

 [The above opinions expressed are my own; not necessarily held by others.]
      == Steven J. Edwards           Bull HN Information Systems Inc. ==
      == (508) 294-3484              300 Concord Road         MS 820A ==
      == sje@xylos.ma30.bull.com     Billerica, MA 01821          USA ==
"That Government which Governs the Least, Governs Best." -- Thomas Jefferson