From: 33plato@sol.cs.wmich.edu (Larry Plato)
Subject: Re: NNs in chess or other games
Organization: Western Michigan Univ. Comp. Sci. Dept.
Date: Sat, 12 Sep 1992 02:03:09 GMT

bruhn@uxe.wu-wien.ac.at (Peter Bruhn) writes:

>Does anyone of you know something about an application of neural nets
>in strategic games (esp. chess). What I think about is that a NN could
>be trained to evaluate a position or some aspects of a position (e.g.
>the structure of your pawns, how safe is the position of your king,...).

>The idea behind is that evaluating a position is (as I see it) closely
>related to pattern-recognition. An experienced human chess player is
>able to identify a position as weak, even though there are no tactical
>dangers to perceive and he/she has not seen the position before. So how
>does he/she know? I think it is due to pattern recognition: He/She has
>seen similiar positions before or has made the experience that a certain
>pawn structure is a weak point. Once a chess master (I don't remember his
>name) was asked how many moves he prefigures in advance and he answered
>"normally: none". Even though this is an exageration, of course, his
>answer shows that it is more important to be able to evaluate a position
>than to prefigure a lot of moves! Interestingly todays chess programs
>take the other way: the use brute force! And this is the reason why
>computers are good in chess, but not in games like Go. In Go there are
>more possibilities and brute force will not work so well. So what I
>think is that we should put more emphasis on the evaluation of positions
>(of a game) rather than on brute force. And maybe NNs could help !?

>Any comments are appreciated!

>Peter (bruhn@uxe.wu-wien.ac.at)

    I wholeheartedly agree.  I am an undergrad at Western Michigan U and
a senior in the CS program taking Neural Nets.  I think a three tiered approach
would be best.  As you mentioned, a complete search of the game space tree
in prohibitive.  So what we do is this...

a) a neural net analyses the board and produces a list of 'insightful moves'
   that are worthy of consideration.
b) an expert system could analyse the board based on more traditional
   factors, such as fiancetti, pawn location, freedom of movement of the
   major pieces and territory controlled.
c) a brutre force approach could be applied to the promising moves.

to further analyse my ramblings imagine this . . .

A traditional program does b) quite well, and a certain amount of a.
this is referred to as pruning, because you 'prune' the game space tree.
The only thing we are doing by adding the neural net is allowing the
'rouge' element to come to the fore.  The net might see a promising
pattern that a more traditional view would miss.  This is sort of like
a local minima problem.  If you start pruning the tree by some objective
function, then you will find a local minima (eg a good solution) but you may
or may not find the 'global minima' which is to say the best solution.

A couple of old jokes here, the first is have you heard about the US Army
chess manual? chapter 1 is white kings pawn to kings pawn 1 chapter 2 are the choices for white kings pawn to king pawn 2 etc ad nauseum.
The other is the chess master who draws black and is so good the game goes
white queens pawn to queen's pawn 2 and black resigns.

The 2 problems I see immediately are 

1) how to choose a network configuration?

2) how to run backprop on a net with no immediately obvious objective function

I am working on a idea to represent nets so I can run GA's on them but if it
goes like most of my projects I would not expect results this decade.
as for 2) I would use famous games as a data set.  Start with the move before
checkmate, train the net on the 2nd to last move of a hundred famous games,
when it can extend the game some of the time then go to n-2 moves etc.  I would
avoid porting in the expert system, brute force crap until the net got pretty
good, we want a 'rouge' element not a random one.
  best of luck
    Larry Plato

-- 
--------------------------------------------------------------------------------
There are many ways to die, some are less pleasant than others.
  33plato@sol.cs.wmich.edu
--------------------------------------------------------------------------------
Newsgroups: comp.ai.neural-nets