Home 
Search 
Today's Posts 
#1




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 bruteforce lookahead 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 chessplaying 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 rulesbut here is where an intriguing difference arises between chess and the standard finite cellular automata. In your ordinary CA the state transtions are deterministicthe 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 movesand 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 nonempirical 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 1020 years of hard work you could begin to tease out rules, variables, ifthen 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 multiply lookahead. Hope that is not too Star Trekkyit 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 luckyou probably will need it. "Du sublime au ridicule il n'y a qu'un pas." Napoleon (1812) Nick 
#2




Chess and Cellular Automata
"Nick" Actually, going back at least as far as Alan Turing's time, some chessplaying 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 multiply lookaheada 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 bruteforceplussimpleevaluationscheme approach. There have also been attempts to "fine tune" the evaluation engine by a kind of reverse engineeringseeing what weightings and so forth would produce the moves in wellestablished 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 lookahead 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 cellularautomatonplusgeneticalgorithm 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




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




Chess and Cellular Automata
"Doug Wedel" wrote in message ...
"Nick" wrote: ... Actually, going back at least as far as Alan Turing's time, some chessplaying 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 multiply lookaheada 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 bruteforceplussimpleevaluation scheme approach. There have also been attempts to "fine tune" the evaluation engine by a kind of reverse engineeringseeing what weightings and so forth would produce the moves in wellestablished 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 cellularautomatonplusgeneticalgorithm 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




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 statebased 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




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 chessplaying softwarei.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 examineafter 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




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 chessplaying softwarei.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 examineafter 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




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 lookahead 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 everbetter 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




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 lookahead 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://williamking.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 cellularautomatonplusgeneticalgorithm 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




Chess and Cellular Automata
Hm, interesting. We already know that human beings do not think like the current chessplaying softwarei.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. 