Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!aero-c!gumby.dsd.trw.com!deneva!wiley!jay
From: jay@wiley.uucp (Jay Nelson)
Newsgroups: comp.ai.neural-nets
Subject: Re: Chip vs Chess Master
Message-ID: <27F38BDF.37A3@wilbur.coyote.trw.com>
Date: 29 Mar 91 18:47:59 GMT
References: <13807@ccncsu.ColoState.EDU> <70216@brunix.UUCP>
Sender: news@wilbur.coyote.trw.com (News Software)
Reply-To: jay@wiley.UUCP (Jay Nelson)
Distribution: usa
Organization: TRW Inc., Redondo Beach, CA
Lines: 75

In article <70216@brunix.UUCP> cs196006@cs.brown.edu (Josh Hendrix) writes:
>In article <13807@ccncsu.ColoState.EDU>, gordons@handel.cs.colostate.edu (vahl scott gordon) writes:
>
>|> I am not aware of any neural programs, or even neural programs for
>|> subsets of chess.  I think it would be a great area of research (for
>|> SUBSETS of chess, that is).
>

Check out the approach used by Deep Thought for move generation.  (See
Artificial Intelligence [the journal] about 1-2 years ago.)  They
don't use a neural net, but a parallel implementation which detects
board patterns.  Their approach could easily be cast in a
connectionist architecture.  Rather than studying a board position and
generating all the moves, they analyzed every possible move that could
ever be made by any piece in any board position.  Sounds like a huge
number of possibilities, but it's really just over 4000.

Consider a pawn: it can never legally be on the first rank, on the
second rank it could move forward 2 or 1, on the 3rd through 7th ranks
it can only move forward 1.  So far we have 7 possible moves.  All
pawns have these 7 moves.  Now consider a pawn on the edge of the
board.  It can only capture diagonally in one direction. That's six
more moves.  A pawn not on the edge can capture diagonally in both
directions: 12 moves.  So edge pawns have 13 possible moves and
non-edge pawns have 19 possible moves (We're ignoring en passant as a
special case of a forward move, and the move into the 8th rank has
options for selecting the promoted piece.  For simplification, assume
promotion is determined after the move by a separate mechanism.)  This
gives (2x13) + (6x19) = 140 possible pawn moves that will ever occur
in any game of chess played.

Now, how de we detect and generate these moves?  We want to use the
board as input and the move as output:

        4  p                 =>  White pawn at a4
        3      p             =>  White pawn at b3
        2  P                 =>  Black pawn at a2 (our move)
        1
           a    b


     input layer       connections       output move

      P on a2             +1               a3 if positive
      any piece on a3     -1

      P on a2             +1               a4 if positive
      any piece on a3     -1
      any piece on a4     -1

      P on a2             +1               a2xb3 if >1
      white on b3         +1

There would be 140 output neurons for just the pawn moves.  Each one
corresponds to a specific move.  Notice that only a few squares are
used as input for each of the moves.  So by completing the analysis
for every possible piece we have just over 4000 output neurons, a
clever input layer representation (not that tricky) and integer
weights.  Evaluation is very fast, and all possible moves for the
input board position are calculated in parallel (Deep Thought actually
does this in VLSI using gate logic for each move detector).

Actually this is a connectionist approach and not a neural network.
It's all prewired and uses no learning.  But a similar mechanism might
be used for other parts of the chess game (e.g. evaluation function
for a generated board position where the outputs are continuous values
for features like mobility, king protection, pawn structure, etc.) and
some learning could occur.  The problem as always is choosing an input
representation that expresses all the features necessary for learning
to find a good solution.

Jay Nelson  (TRW)  jay@wilbur.coyote.trw.com


Jay Nelson  (TRW)  jay@wilbur.coyote.trw.com