A Chess forum. ChessBanter

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below.

Go Back   Home » ChessBanter forum » Chess Newsgroups » rec.games.chess.misc (Chess General)
Site Map Home Register Authors List Search Today's Posts Mark Forums Read Web Partners

Chess and Cellular Automata



 
 
Thread Tools Display Modes
  #1  
Old July 23rd 03, 07:34 AM
Nick
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata

"Doug Wedel" wrote in message ...
I noticed in a recent post that people were surprised that anyone could
imagine that there might conceivably be a mathematical approach to chess,


Hamlet: 'There are more things in heaven and earth, Horatio,
Than are dreamt of in your philosophy.'
--Shakespeare (Hamlet)

Dear Mr. Wedel,

What you actually wrote in your cited post was not quite the same as
what you now imply to have written.

In your post (19 June 2003) in the thread, "The Formula for the Best
Move?", you wrote: "It is my (rather vague) understanding that some
mathematician at the early part of the last century 'proved' that
chess play is susceptible to mathematical certainty if only we could
elucidate the formula (I am not talking about brute-force look-ahead
which if (sic) the typical software approach to playing chess). Does
anyone know any more about this? Is it theoretically possible to
develop a 'formula' that would spit out the best move in any chess
situation based on all the relevant variables?"

Evidently, knowledgeable readers here should not have been "surprised
that anyone could imagine that there might conceivably be a
mathematical approach to chess"--that's hardly an original concept.
Actually, going back at least as far as Alan Turing's time, some
chess-playing mathematicians probably have hypothesized about an
ideal mathematical algorithm for deciding chess moves. My impression
was that most readers here were more surprised by the apparent claim
that "some mathematician at the early part of the last century"
already had "proved" that such an optimal approach exists.

so I thought I would (very briefly) elaborate on the kind of mathematical
structure I see chess as. Specifically I see chess as a special kind of
cellular automaton.

Cellular automata have become famous recently as a result of Stephen
Wolfram's "A New Kind of Science," which is all about them. An early famous
example of a cellular automaton was the game of "Life" by the English
mathematician Conway.


John Horton Conway has invented many mathematical games.

Cellular automata are two dimensional grids of cells, like a chess board.
Each site on the lattice, or cell, can, like a square on a chess board, be in
any of a number of different "states". These states, in the game of chess,
correspond to the different pieces, as well as empty squares. Just as in
cellular automata, the moves of the game are determined by rules--but here is
where an intriguing difference arises between chess and the standard finite
cellular automata. In your ordinary CA the state transtions are
deterministic--the rules are all you need to know what state each site or
cell will hold at the next tick of the clock. In chess, by contrast, the
rules only give you the set of legal moves. There has to be something else,
some other mathematical component of the model, that can choose between
alternative existing legal moves--and this would be the magical "formula" for
the best move that I was alluding to an earlier post, a notion which drew
considerable albeit highly literate derision.


In your earlier post, your implied "magical formula" for determining
the best move in any given chess position seemed too prescriptive
and non-empirical to be taken quite seriously by some readers.

How could the cellular automata "choose" between alternative legal moves?
The model that I am working with uses a genetic algorithm with "genes".
Genetic algorithms were originally developed by John Holland at the
University of Michigan, and later at the Santa Fe Institute. Since their
introduction, genetic algorithms have been used to "evolve" highly
sophisticated mathematical models to optimize solutions to highly nonlinear
problems such as the flow of natural gas or the design of jet engines.
In teh genetic algorithms I am developing for chess, the genes have
"weightings" for different geometic and combinatorial aspects of the
gameboard. The geometric aspects of the of the model involve things like
corners, edges, center, rows, columns, diagonals. The combinatorial aspects
refer to the different combinations of, say, possible centers. The genetic
algorithm which "decides" on the best move has "genes" for evaluating
alternative transitions based on pawn structures, minor pieces, doubled
pawns, position, mobility, et cetera. Of course saying this is rather easier
than doing it. But what I envision is that the genetic algorithms (GAs)
would be paired in endless Swiss pairs tournaments. After each tournament,
the winners would exchange genetic material with other winners (using
the kinds of "crossover" techniques that have become familiar
in the mathematics of genetic algorithms).

So my idea is to create a model in which a genetic algorithm sits
on top of a cellular automata, and humans are able to introduce
hypothetical genes into the genetic algorithms and test them to see if they
increase the ability of the GAs to play chess. It seems to me that
after maybe 10-20 years of hard work you could begin to tease out rules,
variables, if-then statements, and a system of weightings which could in
fact determine the best move at a high level of play but in a highly
mathematical way without multi-ply look-ahead. Hope that is not too Star
Trekky--it seems to like real mathematics to me, but then maybe I'm crazy ;-)


I doubt that you are 'crazy'. You are hopeful and idealistic,
however, which some people tend to conflate unfairly with being
deranged. Perhaps your approach might succeed in theory. But have
you been able to make any realistic estimates about the computing
time that would be needed to put it into practice? Also, might there
not be a possibility that your genetic algorithm model could run into
an evolutionary dead end? Complex mathematical models may sometimes
exhibit some unexpected and apparently inexplicable behaviour.

Actually, what you have proposed doing in chess with genetic
algorithms reminds me somewhat of an artificial intelligence
researcher who was contemplating approaching chess in terms of a
vast neutral network (which would have been implemented on a
'massively parallel' network of computer processors). As far as
I know, his research project never really got off the ground.

In my view, computer go presents a more interesting challenge now
than computer chess. If you should become disenchanted in your
pursuit of Caissa, then go could become an alternative research
subject. Good luck--you probably will need it.

"Du sublime au ridicule il n'y a qu'un pas."
--Napoleon (1812)

--Nick
  #2  
Old July 23rd 03, 05:47 PM
Doug Wedel
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata


"Nick"

Actually, going back at least as far as Alan Turing's time, some
chess-playing mathematicians probably have hypothesized about an
ideal mathematical algorithm for deciding chess moves. My impression
was that most readers here were more surprised by the apparent claim
that "some mathematician at the early part of the last century"
already had "proved" that such an optimal approach exists.


Alan Turing and the early chess software developers focused, so far
as I know, on the basic idea of coupling a relatively "dumb" evaluation
engine with a multi-ply look-ahead--a paradigm which has remained
at the center of chess software ever since, albeit with numerous
substantial improvements in terms of searching through the tree of
all possible moves. In the mid-'80s, I believe, developers attempted
to improve the evaluation engines by employing chess grandmasters
to help them develop more sophisticated algorithms, but they found
that the time conisumed in doing more sophisticated evaluations at
every node in the expanding tree of possibilities consumed more time
than the brute-force-plus-simple-evaluation-scheme approach. There
have also been attempts to "fine tune" the evaluation engine by a kind
of reverse engineering--seeing what weightings and so forth would produce
the moves in well-established masterpiece games.

My point was somewhat different than this. I believed at the time of the
post,
and still believe, that some French mathematician (I could be wrong about
the
French part ;-) "proved" to the satisfaction of other mathematicians that
since
chess was "decidable" by brute force look-ahead that therefore there
existed,
if only in theory, a formula that could in fact "decide" what the best move
was
in any given board position. I read about this in an old verison of
Encylopedia
Britannica, and am trying to find the mathematicians' name ;-)

In my view, computer go presents a more interesting challenge now
than computer chess. If you should become disenchanted in your
pursuit of Caissa, then go could become an alternative research
subject.


Go is certainly a fascinating challenge, worth a million bucks to the
first software developed whose program can beat a master (so I heard).
One tantalizing challenge in Go is to develop the "mathematics of
enclosure",
which no doubt would be primarily an exercise in geometry. In fact, the
cellular-automaton-plus-genetic-algorithm model that I have
developed for chess works for almost all board games, including tic tac toe,
checkers and go. My main interest is in the evolution of intelligence, and
I
take as a "working definition" of intelligence the ability to increase one's
ability to play a board game well.

By the way, what is "Caissa"?


  #3  
Old July 23rd 03, 09:54 PM
Adam Augusta
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata

This is from the hip, but I think it's valid.

How to always win or force a draw for White:

There are a finite number of states of the game. Every possible piece
combination * 2, depending on whose turn it is.

1) Mark all states where it's white's turn white.
2) Mark all states where it's white's turn black.
3) If a state is at Checkmate for black, mark it red.

Checkmate only happens on Black's turn, so all states pointing to them are
forcable black decisions.

4) Mark all states pointing to previously marked states blue.

All arrows leading to blue states are White's decision. Mark them as bad.

5) If an arrow points to a blue state, mark it red.

All states that only lead to blue states are bad.

6) If a state only has red arrows leading from it, mark it red.
7) Go to 4.

If white avoids all blue moves, he will always have a move that leads to
draw or victory.

If this algorithm found that the game start state is red, then white is
categorically screwed.

The problem with this is that there's something like 10^60 states.
Retaining marking info for states and arrows would require more memory
than is possible. So screw cellular automata.

-Adam
  #4  
Old July 24th 03, 02:33 AM
Nick
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata

"Doug Wedel" wrote in message ...
"Nick" wrote:
...
Actually, going back at least as far as Alan Turing's time, some
chess-playing mathematicians probably have hypothesized about an
ideal mathematical algorithm for deciding chess moves....


Alan Turing and the early chess software developers focused, so far as I
know, on the basic idea of coupling a relatively "dumb" evaluation engine
with a multi-ply look-ahead--a paradigm which has remained at the center
of chess software ever since, albeit with numerous substantial improvements
in terms of searching through the tree of all possible moves.


Dear Mr. Wedel,

As I recall, Alan Turing began thinking of how to play chess according to
mathematical algorithms before he had a computer available to implement them.
My point was only that there's been a tradition of thinking about mathematical
approaches toward chess. I did not claim that Alan Turing's concept was
the same as yours.

In the mid-'80s, I believe, developers attempted to improve the evaluation
engines by employing chess grandmasters to help them develop more
sophisticated algorithms, but they found that the time conisumed in doing
more sophisticated evaluations at every node in the expanding tree of
possibilities consumed more time than the brute-force-plus-simple-evaluation-
scheme approach. There have also been attempts to "fine tune" the evaluation
engine by a kind of reverse engineering--seeing what weightings and so forth
would produce the moves in well-established masterpiece games.
...
In my view, computer go presents a more interesting challenge now than
computer chess. If you should become disenchanted in your pursuit of
Caissa, then go could become an alternative research subject.


Go is certainly a fascinating challenge, worth a million bucks to the
first software developed whose program can beat a master (so I heard).
One tantalizing challenge in Go is to develop the "mathematics of
enclosure", which no doubt would be primarily an exercise in geometry.


With respect to computer Go, the combinatorial space (a 19 x 19 board) is
far too vast for a 'brute force lookahead' approach to succeed.

In fact, the cellular-automaton-plus-genetic-algorithm model that I have
developed for chess works for almost all board games, including tic tac toe,
checkers and go. My main interest is in the evolution of intelligence, and
I take as a "working definition" of intelligence the ability to increase
one's ability to play a board game well.
By the way, what is "Caissa"?


Caissa is the muse (patron goddess) of chess. Here's how she was created:

"...fram'd a tablet of celestial mould
Inlay'd with squares of silver and gold;
Then of two metals form'd the warlike band,
That here compact in show of battle stand;
He taught the rules that guide the pensive game,
And call'd it Caissa from the dryad's name.
Whence Albion's sons, who most its praise confess,
Approved the play and named it thoughtful Chess."
--William Jones (1763, 'Caissa')

--Nick
  #5  
Old July 24th 03, 06:31 PM
Adam Augusta
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata

On Thu, 24 Jul 2003, Doug Wedel wrote:

He talks about how, as with the
current approach to chess software, for example, you can iterate
all possible transitions and thereby find those paths which lead to
victory, but how, as another poster pointed out, there are
combinatorial spaces such as the game of go where this approach
cannot work in finite time. To make good decisions in these
more complex problem spaces you need a formula instead of a
brute force lookahead. My post was about finding such a formula
as a *substitute* for the kind of brute force lookahead you're
talking about.


Gotcha. I got the impression that you were lending credibility to the
idea of there being a deciding formula by saying that a given chess move
is /decidable/. I merely intendid to show that decidability lended no
credence to such a theory at all.

My intuition indicates that you need some kind of state-based answer.
Defining things /positionally/ is probably a satisfying way of compressing
these states to a much, much smaller solution set.

I get the sense that this is ultimately the kind of information a genetic
algorithm would store. As it tested swiss rounds against itself, it would
acquire more and more knowledge about useful states. Eliminating less
common and less useful states is also another form of compression.

I fear that if you are trying to capture the essence of a human's
intuition of positional understanding, while a genetic algorithm may
succeed and make you reputed theoretical software engineer, you will not
have acquired a chess /solution/.

That said, there are far better men than I to discuss this topic with.

-Adam
  #6  
Old July 24th 03, 06:36 PM
Doug Wedel
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata


"Adam Augusta" wrote

I fear that if you are trying to capture the essence of a human's
intuition of positional understanding, while a genetic algorithm may
succeed and make you reputed theoretical software engineer, you will not
have acquired a chess /solution/.


Hm, interesting. We already know that human beings do not think
like the current chess-playing software--i.e. humans do not examine
billions of board positions in their imagination. Perhaps humans do
have some kind of algorithm for evaluating the limited number of
alternatives they do examine--after all, what other kind of decision-
making process could there possibly be other than brute force
iteration? Human beings may perform complex mathematics all
the time without being aware of it ;-)


  #7  
Old July 24th 03, 09:42 PM
Adam Augusta
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata

On Thu, 24 Jul 2003, Doug Wedel wrote:

"Adam Augusta" wrote

I fear that if you are trying to capture the essence of a human's
intuition of positional understanding, while a genetic algorithm may
succeed and make you reputed theoretical software engineer, you will not
have acquired a chess /solution/.


Hm, interesting. We already know that human beings do not think
like the current chess-playing software--i.e. humans do not examine
billions of board positions in their imagination. Perhaps humans do
have some kind of algorithm for evaluating the limited number of
alternatives they do examine--after all, what other kind of decision-
making process could there possibly be other than brute force
iteration? Human beings may perform complex mathematics all
the time without being aware of it ;-)


I get the impression that the human mind goes, "How many ways could this
wind up?" I gets tons of impressions, some legally incorrect, some
disinteresting, some interesting, and the interesting ones surface to an
upper level of consciousness where they're evaluated more rationally. The
neural mechanisms used to produce the valid, conscious choices are
rewarded, causing the brain to perform better through training.

Examine your consciousness next time you play. Your mind is probably
racing through noise, with a few possibilities popping into thought. In a
novice player, there are probably as many bad and even illegal moves as
good moves. The bright novice will quickly make a legality check then
ponder the move's ramifications in a somewhat brute force, deterministic
pattern.

Of course, this is all entirely speculation. Perhaps a genetic algorithm
could assist in the first part of the supposed first process.

-Adam
  #8  
Old July 25th 03, 12:59 AM
Larry Tapper
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata

"Doug Wedel" wrote in message ...


My point was somewhat different than this. I believed at the time of

the
post, and still believe, that some French mathematician (I could be

wrong about
the French part ;-) "proved" to the satisfaction of other

mathematicians that
since chess was "decidable" by brute force look-ahead that therefore

there
existed, if only in theory, a formula that could in fact "decide"

what the
best move was in any given board position. I read about this in an

old version of Encylopedia
Britannica, and am trying to find the mathematicians' name ;-)


Doug,

You may be thinking of Zermelo's Theorem (1913) which was later
elaborated by von Neumann in the context of developing formal game
theory. There is a mathematical overview at:

http://www.econ.keio.ac.jp/staff/nak...pdf/minmax.pdf

In your earlier post, you mentioned the idea of "mating" the winners
of large Swisses in the hope of developing ever-better genetic
algorithms. I thought this was a delightful, if Utopian idea.

I think the main problem with this magic formula (which exists in
principle) is that Zermelo and von Neumann make no promises about its
length! That is, there is nothing in game theory that formally blocks
the dismaying possibility that there is no useful way to describe the
perfect maximin strategy shorter than spelling out all the moves.

Still, this is no reason to abandon your research, because you still
have some hope of hitting upon the best algorithm invented so far,
even though it may not be THE algorithm that solves the mystery of
chess once and for all.

Regards, Larry
  #9  
Old July 25th 03, 02:15 AM
Wlodzimierz Holsztynski
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata

"Doug Wedel"
wrote about things he knows very little
in message ...

[...]

I believed at the time of the post,
and still believe, that some French mathematician
(I could be wrong about the French part ;-) "proved"
to the satisfaction of other mathematicians that since
chess was "decidable" by brute force look-ahead that
therefore there existed, if only in theory, a formula
that could in fact "decide" what the best move was
in any given board position. I read about this in
an old verison of Encylopedia Britannica, and am trying
to find the mathematicians' name ;-)


Yes and no. Yes, there was a famous, great ("French" :-)
German mathematician:

Ernst Friedrich Ferdinand Zermelo

who showed that chess (and similar open information
finite games) is determined. here is a quote from

http://william-king.www.drexel.edu/top/class/histf.html

1913

The first theorem of game theory asserts that
chess is strictly determined, ie: chess has
only one individually rational payoff profile
in pure strategies. This theorem was published
by E. Zermelo in his paper Uber eine Anwendung
der Mengenlehre auf die Theorie des Schachspiels
and hence is referred to as Zermelo's Theorem

No, (real) mathematicians never claimed to have
an approach to an efficien analytic move producing
function. Any true mathematician would be seriously
enough dobtful about the existence of such as thingy
-- there is no reason for it.

In my view, computer go presents a more interesting challenge now
than computer chess. If you should become disenchanted in your
pursuit of Caissa, then go could become an alternative research
subject.


In fact, the cellular-automaton-plus-genetic-algorithm
model that I have developed for chess works for almost
all board games, including tic tac toe, checkers and go.


I grant you 3 by 3 tic tac toe.

My main interest is in the evolution of intelligence,


It's an excellent interest for you. Good luck.

Wlod
  #10  
Old July 25th 03, 03:55 AM
Ed Seedhouse
external usenet poster
 
Posts: n/a
Default Chess and Cellular Automata


Hm, interesting. We already know that human beings do not think
like the current chess-playing software--i.e. humans do not examine
billions of board positions in their imagination.


We do not, actually know this. We only know that they do not do so at a
conscious level. What the brain may be doing below the level of
conscience is a matter of conjecture and, while it is unlikely that a
brute force tree examination is going on at that level, I don't think it
has been directly proved that it isn't.

Human beings may perform complex mathematics all
the time without being aware of it ;-)


Every time you catch something thrown your way for example.
Mathematically it requires massively complex integration, but we do it
without conscious effort, virtually instantaneously.

 




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Forum Jump


All times are GMT +1. The time now is 02:44 AM.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.Content Relevant URLs by vBSEO 2.4.0
Copyright 2004-2017 ChessBanter.
The comments are property of their posters.