neural network and chess
Yeeming Jih
As I know, the strongest backgammon-playing programs are based on neural
networks; and on the other hand, chess playing programs do not use the
neural network. What are the reasons for this?
--
"Never stop learning."
* I apologize for any inconvenience my disguised email address may cause.
Thank you for your patience.
Komputer Korner
See below for an answer from another poster a long time ago.
--
--
Komputer Korner
The inkompetent komputer
To send email take the 1 out of my address. My email address is
kor...@netcom.ca but take the 1 out before sending the email.
In article <32f73...@news.cranfield.ac.uk>, Simon says...
>In article <32F54...@eecs.umich.edu>, "George says...
For example, why not take every position reached in any recorded
GM level game and use it to train a neural network to do positional
evaluations? [...]
Build a game tree and let the neural network evaluate the leaves.
It seems, at least to this non-expert, that the neural net would then
"posess" any knowledge used by grandmasters to win. I've had quite
some experience with neural networks and I think building an
appropriate
training set of data is certainly feasible.
>I have studied this problem. There are a few issues to address. If
you
assume for now that it's a feed-forward net, so define some inputs and
define some outputs, the following design issues are relevant:
>(1) What is your network going to compute? Here are some choices:
* Probability of winning, given a position
* distance to win, or some function of distance to win, given a
position
* evaluation based on equivalence to material value (most current
> chess programs seem to use this), given a position
* best move: this is a tricky one. You input the position, and the
network outputs the move BUT that means it has to understand
> legal moves and it isn't compatible with the game tree
approach.
It also effectively treats all positions as of equal
complexity,
since they all get one run of the network to produce a move.
* evaluation based on position and proposed move, rather than just
position. A legal move generator supplies the position and a
set of moves; the network computes a score for each proposed
move.
* a score for each piece/square: effectively a piece/square table.
The legal move generator then makes the move which best
matches
this. This means that the network has 64x13 outputs instead
of 1.
2) What part does your network play in the complete chess-player?
>Does it compute legal moves, or does it merely evaluate the goodness
>of a position? With current chess programs, the making-moves part is
separate from the evaluating-positions part.
(3) How much time are you prepared for your network to take to
evaluate
a position? Position evaluators in most chess programs add up some
terms
to get a score. This is a lot simpler than the computations performed
in a neural network. A network performs as many multiplications as
additions (approximately) so it will take quite a lot longer to
produce
an evaluation than a hand-crafted evaluation function. This extra time
may be acceptable if the network's evaluations are of high quality.
Maybe a floating-point co-processor would be useful here.
Graham Douglass:
>I do see a drawback though. The human neural network os estimated to
have
10^11 cells, each connected to an average of 10^4 other cells,
>making a total of 10^14 connections.
:) x 10^15
ops!
`>Graham Douglass:
> but to see if contemporary
>computers can reach grandmaster level, the question we have to ask is
this: is
your neural net able to store 50,000 position patterns in the
foreseeable
future?
One awkward question is: are there really any distinct patterns, or do
they all have overlaps and fuzzy boundaries? You mentioned fuzzy logic
>which may well be part of the answer.
The answer to your question is pretty much "yes", if there are
distinct
patterns, but now we have to calculate the time taken for the network
to
operate, as follows.
You could use a Hopfield net. They are designed for
pattern-recognition.
The auto-associators are presented with an incomplete pattern and
after
a few iterations they converge to the best match. For 50,000 patterns
you would need say about 200,000 neurons in a Hopfield net. For every
connection between a neuron and another neuron you need one multiply
and add step. Let's say this network is connected in a sparse manner
so each neuron has 1000 connections to other neurons. That means
2x10^8
>multiply-accumulate operations for each pattern-recognition
iteration,
and you need a few of those to successfully recognise a pattern, more
if
the pattern you are interested in is very similar to another pattern.
This puts some limit on the speed with which you can recognise
patterns.
Presumably this is equivalent to an upper limit on the number of
position
nodes you can process per second.
Then there are hetero-associators. Given a complete pattern, they
associate that with another pattern. Humans seem to do a lot of that.
Given a queen and knight in a certian position, I think "Philidor's
legacy - smothered mate." That's associating one pattern with another.
The computing time for this is usually one iteration for one
association, but may be more if the pattern in question looks similar
to another. This sort of association may also be used to associate a
suggested move with a position.
Ok, now that the non-expert has spoken, here's my question to the
>>experts: Has the ability of neural networks to "learn" information
>>presented in a training data set ever been used in chess? if so,
>>>what task was the neural network used for? what were the results?
I think Jay Scott's page has a bit on neural learning, but you have to
hunt for it:
Schmidt, Martin - Neural Networks and Chess -
(presentation of the paper is a little rough. The network
doesn't play chess very well. He explores various ways of
representing the input data. Feedforward net, no pattern-
recognition stuff)
and another one from somewhere else:
>Thrun, Sebastian - Learning to Play the game of chess - to appear in
Advances in Neural Information Processing Systems 7
>
Downloadable from the internet - http and ftp site
> http://www.informatik.uni-bonn.de/~thrun/publications.html
this site has many neural network learning papers.
> (a neural network learns to play chess. It sometimes beats
GNUchess.
GNUchess requires about 100 times less CPU time.
Feedforward net, no pattern-recognition stuff.)
Yeeming Jih wrote in message <6hoqmd$4fs$1...@winter.news.erols.com>...
George R. Barrett
Komputer Korner wrote:
>
> See below for an answer from another poster a long time ago.
> --
> --
> Komputer Korner
> The inkompetent komputer
>
> To send email take the 1 out of my address. My email address is
> kor...@netcom.ca but take the 1 out before sending the email.
>
> In article <32f73...@news.cranfield.ac.uk>, Simon says...
>
> >In article <32F54...@eecs.umich.edu>, "George says...
>
> For example, why not take every position reached in any recorded
> GM level game and use it to train a neural network to do positional
> evaluations? [...]
> Build a game tree and let the neural network evaluate the leaves.
> It seems, at least to this non-expert, that the neural net would then
> "posess" any knowledge used by grandmasters to win. I've had quite
> some experience with neural networks and I think building an
> appropriate
> training set of data is certainly feasible.
>
Gee wiz, Korner, you sure do keep old postings... I'm the
"George" from "George says..." above. I'll summarize an answer to
Yeeming Jih's question as follows:
There is no doubt that neural networks can adjust themselves to whatever
function you so desire; however, the time to sweep forward through the
neural network to compute the output of the function is the main
possible drawback to using them in chess software. Consider the
following example based on simply feeding a board position to a network
with 16 hidden nodes. (I chose 16 because one poster said that 50000
positional features may need to be learned and log(50000)/log(2)=15.6
~=16 assuming each hidden neuron had to saturate high or low).
To encode the pieces on the 64 squares we could use 4 bits per piece
because there are (prnbqkPRNBQK) 12 disinct pieces and
log(12)/log(2)=3.6 ~=4. So the total number of weights from the inputs
to the hidden layer is 64*4*16 = 4096. That's 4096 muliplications and
4096 additions.
Whether or not that is prohibitive depends on technology. Most people
who responded to my original question were aggressively anti-neural
network.
--
_____________________________________________________________________
George R. Barrett
Electrical Engineering : Systems `` Without insight, method is
University of Michigan, Ann Arbor largely useless. ''
_____________________________________________________________________
Michael J. White
George R. Barrett wrote in message <3540D141...@eecs.umich.edu>...
>Komputer Korner wrote:
>>
>> See below for an answer from another poster a long time ago.
>> --
>> --
>> Komputer Korner
>> The inkompetent komputer
>>
>> To send email take the 1 out of my address. My email address is
>> kor...@netcom.ca but take the 1 out before sending the email.
>>
>> In article <32f73...@news.cranfield.ac.uk>, Simon says...
>>
>> >In article <32F54...@eecs.umich.edu>, "George says...
>>
>> For example, why not take every position reached in any recorded
>> GM level game and use it to train a neural network to do positional
>> evaluations? [...]
>> Build a game tree and let the neural network evaluate the leaves.
>> It seems, at least to this non-expert, that the neural net would then
>> "posess" any knowledge used by grandmasters to win. I've had quite
>> some experience with neural networks and I think building an
>> appropriate
>> training set of data is certainly feasible.
>>
>
I've tried to use neural networks with chess. I haven't seen a lot of
success, but I'm not through yet, either ;-) Here's my 2 cents.
Sometimes people want to build things out of GM games. OK
mostly, but there are some notoriously *bad* moves in those games.
Then if we check a data set like this by scoring all the nodes
as best we can by computer, and then back up the scores
and eliminate the bad moves, we have a very rigorous opening
book. OK mostly, but now what? How does that make something
useful for training a neural network?
There's a concept that floats around the NG that the goal of the
the neural net should be to predict a "move". To me, that's
an attempt to solve the whole chess problem in one fell swoop.
Noone stops to think how much more complicated the move
prediction problem becomes. A neural net takes forever
to learn a simple truth table, and will fail to learn all the tricky
rules of chess in just the same slow way. A really hopeless project
would be to see if a neural net could distinguish legal/illegal moves.
Asking it to predict a good (and also legal) move would be ... ahhh,
you get the point.
Something less ambitious would be to teach the net to predict a
score for a position. That goal is easier to test, and easily
more useful in application: it could be used to evaluate terminal
nodes, move ordering, improve piece/square tables -- if it works.
A very desirable application of the neural net is to use it to
"see through" and replace a search with a static position
evaluation. Why can't this work? If it really worked, I wouldn't mind
applying it an average 36 times per turn, to find the correct move...
The real challenge is to represent a board position and
permissions (move turn, ep file, castle flags) in a way that
the neural net can use the information. This is necessary to
reduce training time and complexity. These facts usually
stop me, and I hazard the claim that we don't see successful
neural net chess programs because noone solves this.
If you want a neural net to work, you have to have a very
good (comprehensive, diverse, accurate) training set, and present
those positions to the net any times, and grow very old waiting
for convergence. So far my best attempt has come from an old
discussion on this NG about how to store the board in a small but
fixed number of bits.
I have tried some other things and would like to hear from others
about this. In particular, I wonder how many hidden nodes
are really necessary to *represent* the position, and how many
are needed to *assess* the position. Should they be the same?
In building hash codes, I never see a collision at 64 bits, but
saw them frequently (2:100000) at 32 bits. I tried to use the
net to code and decode 64 bit codes to see if it had enough
hidden nodes but never got anywhere (training time is always
huge).
In assessing position scores, chess programs have pretty
simple heuristics and the static exchange algorithms seem
simple, but how much bit-knowledge is that worth in a
neural net? Somehow I can't argue against 50000 position
features being worth 16 bits. Perhaps each feature needs
classifiers, thus more bits? It just seems too small.
Mike