Programming

Forum Archive : Programming

 
Board encoding for neural network

From:   Brian Sheppard
Address:   brians@mstone.com
Date:   26 February 1997
Subject:   Re: Ideas on computer players
Forum:   rec.games.backgammon
Google:   01bc23ed$e5165a80$3ac032cf@polaris.mstone.com

Gargle Zndflxtzyh wrote:
> any ideas of what a good layout of neurons should be?
>
> my initial thought is:
> for each slot on the board have
> 1 neuron to represent empty,
> 1 neuron to represent 1 piece and
> 1 neuron to represent 2-3 and perhaps 1 neuron to represent 4+ pieces
>
> (the last one might not be necessary).
>
> is this way off?

Something about your answer makes me think there might be some
confusion as to what a neuron is, so I figured I should write
a note to define the terms. If you knew this all along, then
I figure that maybe someone else will benefit.

A neural network consists of 3 types of elements:

    1) Inputs, which describe the state of a system (like the
    board configuration in a backgammon application),

    2) Outputs, which are trained to approximate some important
    measure of the system (like winning and gammon chances in
    a backgammon application), and

    3) Neurons, which are computational elements. These transform
    the inputs into the outputs by a form of magic that is rarely
    humanly understandable.

I have one paragraph for the computationally inclined:
A neuron typically takes the form Logistic(Summation(Constant * Input)),
where Logistic is the function 1 / (1 + exp(-x)). In words: a neuron
is a linear sum of inputs "squashed" by a function whose output is
bounded. If you want to generalize this concept, you can change the
squashing function to something else (tanh is equivalent to logistic,
but an interesting choice is erf(), the Gaussian error function), or
you can allow the linear sum to include the results of other neurons.

Now, the reason that I figure you misunderstand the term "neuron"
is that you are describing how to encode the board position, which
means that you are talking about Inputs, rather than Neurons.

To respond to your actual question about whether this is a good
encoding: Yes, it is. Gerald Tesauro published a paper quite a while
ago (I think it was in the journal "Artificial Intelligence" around
1989) about the precursor to TD-Gammon, named Neurogammon. The
Neurogammon feature set allocated inputs as follows:

    1 boolean input, set if Black has a blot on this point,
    1 boolean input, set if Black has a block (2 or more men),
    1 boolean input, set if Black has exactly 3 men on this point,
    1 boolean input, set if Black has exactly 4 men on this point,
    1 integer input, set to the number of men beyond 4 on this point.

There are 5 inputs per side per point. There are 24 points, plus the
bar (one bar for each color). I don't remember how Tesauro handled
men borne off, nor how he handled the side to move.

Tesauro supported his method by comparing it to another system of
inputs. He also argued that this system contains a lot of semantic
content (the concepts Blot, Block, Builder, and Overloaded are
inherent in the inputs), and so neural network capacity does not
need to be devoted to identifying those features.

Note that this input set, by itself, is not sufficient to play a
strong game. Tesauro's best program using this feature set played at
a "strong intermediate" level. This basically means that the program
would clobber a novice, but it still makes lots of errors.

Tesauro's feature set for TD-Gammon has never been published, since
IBM regards it to be a trade secret. But you have to figure it
contains a few strategic concepts (e.g. the safe-play-versus-bold play
criteria from Magriel) and tactical factors (like counts of shots
or point-making rolls). There is a lot of scope for creativity here.

Best Wishes,
Brian
 
Did you find the information in this article useful?          

Do you have any comments you'd like to add?     

 

Programming

Adjusting to a weaker opponent  (Brian Sheppard, July 1997) 
Anticomputer positions  (Bill Taylor+, June 1998) 
BKG 9.8 vs. Villa  (Raccoon+, Aug 2006) 
BKG 9.8 vs. Villa  (Andreas Schneider, June 1992) 
BKG beats world champion  (Marty Storer, Sept 1991) 
Backgames  (David Montgomery+, June 1998)  [Long message]
Blockading feature  (Sam Pottle+, Feb 1999)  [Long message]
Board encoding for neural network  (Brian Sheppard, Feb 1997) 
Bot weaknesses  (Douglas Zare, Mar 2003) 
Building and training a neural-net player  (Brian Sheppard, Aug 1998) 
How to count plies?  (Chuck Bower+, Jan 2004)  [GammOnLine forum]
How to count plies?  (tanglebear+, Mar 2003) 
Ideas for improving computer play  (David Montgomery, Feb 1994) 
Ideas on computer players  (Brian Sheppard, Feb 1997) 
Introduction  (Gareth McCaughan, Oct 1994) 
Measuring Difficulty  (John Robson+, Feb 2005)  [GammOnLine forum]
Methods of encoding positions  (Gary Wong, Jan 2001) 
N-ply algorithm  (eXtreme Gammon, Jan 2011) 
Neural net questions  (Brian Sheppard, Mar 1999) 
Pruning the list of moves  (David Montgomery+, Feb 1994) 
Search in Trees with Chance Nodes  (Thomas Hauk, Feb 2004) 
Source code  (Gary Wong, Dec 1999) 
TD-Gammon vs. Robertie  (David Escoffery, June 1992) 
Training for different gammon values  (Gerry Tesauro, Feb 1996) 
Training neural nets  (Walter Trice, Nov 2000) 
Variance reduction in races  (David Montgomery+, Dec 1998)  [Long message]
Variance reduction of rollouts  (Michael J. Zehr+, Aug 1998)  [Long message]
Variance reduction of rollouts  (Jim Williams, June 1997) 
What is a "neural net"?  (Gary Wong, Oct 1998) 
Writing a backgammon program  (Gary Wong, Jan 1999) 

[GammOnLine forum]  From GammOnLine       [Long message]  Long message       [Recommended reading]  Recommended reading       [Recent addition]  Recent addition
 

  Book Suggestions
Books
Cheating
Chouettes
Computer Dice
Cube Handling
Cube Handling in Races
Equipment
Etiquette
Extreme Gammon
Fun and frustration
GNU Backgammon
History
Jellyfish
Learning
Luck versus Skill
Magazines & E-zines
Match Archives
Match Equities
Match Play
Match Play at 2-away/2-away
Miscellaneous
Opening Rolls
Pip Counting
Play Sites
Probability and Statistics
Programming
Propositions
Puzzles
Ratings
Rollouts
Rules
Rulings
Snowie
Software
Source Code
Strategy--Backgames
Strategy--Bearing Off
Strategy--Checker play
Terminology
Theory
Tournaments
Uncategorized
Variations

 

Return to:  Backgammon Galore : Forum Archive Main Page