Artificial Intelligence and the Game of Checkers

Ok, suppose you have a billion digits of Pi. 2000 digits per page, 1000 pages per book, that's 2 million digits per book. So a billion digits would take 500 books. The fifty millionth digit should be at the end of book 25. You pick book 25 from the shelf, open it up, look at the last digit and there's the fifty millionth digit of pi. Total time - maybe a minute and it's all access time. You don't have to calculate the digits because they're already written down. You already have the information in the first billion digits of pi. Now start with just the algorithm and 500 blank books and start calculating the first fifty million digits of pi. The cows will all be dead of old age before you get there. The reason for the difference in speed is because in the first example you have the information in the digits of Pi. In the second example you have the information in the algorithm that calculates the digits of pi. They are not the same. Similarly, designers who possess knowledge of the strategy of "an interative process of making small variations at random then testing those variations and retaining those that improve our strategy" don't know what the result of the process will be until they actually do it and see what pops out. And, since it uses random variations, they'll get a different answer on their second run and subsequent runs. Houdin

Houdin If I have an algorithm that calculates PI to any desired digit (and I do which is simply to divide 22 by 7) I do have the value of PI to any desired decimal digit of accuracy. The algorithm can be considered a compact method of storing the information, like shorthand. It simply takes longer to access it than you might expect. Just because it takes longer doesn't change the essential nature of it. You know PI to any desired decimal place. Consider that you might have PI written down to a billion decimal places. I ask you for the value of the 50 millionth digit. Manually you'll be counting out digits until the cows have gone and come home several times over. You have the information, you just have to wade through an iterative algorithm (in this case counting digits) to get a specific bit of it. This doesn't compare to a random process. There is nothing random about an algorithm that calculates PI. You get the same result every time. A random process can be expected to give you a different result every time (or at best there's no guarantee of the same result). You're comparing apples to oranges. DaveScot

Gil and Tom, thanks for responding. It looks like evolution does forward pruning. For example, if a fertilized egg is created with a damaged gene that will prevent a heart from developing, that egg does not grow up to have offspring carrying that bad gene and those offspring will never produce eggs that test the combination of a bad heart with a modified liver or a bad heart and a modified ear or a bad heart and a modified lung, etc. Millions and millions of bad combinations will never be tried, making evolution much more efficient. Gil and Dave, if you have an algorithm for calculating PI to a million decimal places, you do not have knowlege of the digits of PI, you only have knowledge of the algorithm. For example, you can stare at the algorithm till the cows come home, but it won't tell you what the millionth digit of PI is. You'll have to follow the instructions in the algorithm over and over again until you finally calculate the millionth digit of PI and then and only then will you know what that digit is. Similarly, you won't know what the iterative process of making small random changes and retaining those that are useful will produce until you run the process over and over and see what it produces. Houdin

Dave, Good point in #41: All this proves is that intelligent agents can use tools of their own design to speed up searches for answers. That was essentially my point in the comment about computing PI to a billion decimal places. Sure, we now know PI to a billion decimal places and didn\'t before, so we have new \"information\" in a sense, but this information was inherent in the algorithm designed by the programmers. It\'s basically the same thing with endgame databases or using evo algorithms with evaluation functions. None of this has any bearing on biological evolution. GilDodgen

"it had been able to derive, by random mutation and selection, more information about how to play the game than the designers themselves possessed" Not really. The designers themselves possessed the information. The information was "our strategy can be improved by an interative process of making small variations at random then testing those variations and retaining those that improve our strategy". The computer only did faster what the designers were always able to do on their own. That's the story of computers in a nutshell. They do exactly what they're instructed to do (which is often not what we want them to do). All this proves is that intelligent agents can use tools of their own design to speed up searches for answers. DaveScot

Gil Sorry to interrupt your thread. I'm banned on all Esley Welsberry's websites and wanted to send a message to him (he and/or his minions clutch at read every word we write here. We started out as igames.com but an early partner who didn't pan out owned the URL and we parted ways he kept it. I changed the name to gamelobby.com and owned that URL for many years. My son didn't care for it and some time ago got cardandboardgames.com instead. But Game Lobby stuck on the website and in the software itself. Anyhow, the cribbabe program is in the download package. All the games I wrote for it (cribbage, hearts, backgammon, spades, gin rummy, pinochle, and euchre) have the ability to stand alone and connect with other players by typing in an IP address. Once the package installs just go to the installation directory and launch the cribbage exe file. It's all written in MS Visual C++. DaveScot

Houdin: "I have a question about alpha-beta minimax algorithms. Are those where you see that a certain move will lead to disaster and don't check out any more moves after that?" Not exactly. What you describe is called forward pruning, but this can be risky business in an AI games-playing program because, for example, it might be that you can make repeated, initially seemingly pointless sacrifices, but engineer a checkmate in doing so. Alpha-beta allows risk-free tree pruning within the horizon of a depth-first search and the knowledge implemented in the evaluation function. On the other hand, my checkers program does include a highly-sophisticated forward-pruning algorithm that is only employed in clearly defined, special circumstances. Its heuristics are 99.9999999% accurate, so I don't worry about its statistical deficiencies because they will realistically never come up in actual play. The concept of the statistical improbability of erroneous collisions in the hash tables is also used to improve search efficiency and memory usage. None of this has any relevance to biological evolution. GilDodgen

"Are those where you see that a certain move will lead to disaster and don’t check out any more moves after that?" When we find that a game state (situation) leads to an inferior score for the player whose move produced the state, we don't waste time evaluating just how bad it is. An "inferior" score is one that is worse than the best score the player is known to be able to obtain through some other line of play. The inferior score may be quite good on an absolute scale. "Is this similar to the alpha-beta minimax algorithm?" Sorry, but I can't discern adversaries in your examples, and I can't see how evolutionary processes recursively searches to a certain depth in the phylogenetic tree and then backs fitness information up the tree. Am I missing something you're trying to say? I do find it interesting, though, that most "hopeless monsters" are culled early in ontogenetic development. Tom English

GilDodgen: "an alpha-beta minimax algorithm is employed" Gil and Tom, I have a question about alpha-beta minimax algorithms. Are those where you see that a certain move will lead to disaster and don't check out any more moves after that? For instance, if you move a pawn and your opponant's next move checkmates you, you don't bother trying to figure out what move to make next because the game is over. This, of course, saves you from having to look at a huge number of moves that will never be made and you can use your computer cycles to figure out moves and counter moves that don't lead to checkmate. I ask because Darwinian evolution has a very similar situation. For instance, suppose you have a fertilized egg with a mutation to part of the DNA that codes for a protein that is essential to heart function. Without that intact protein, the heart never develops, so the embryo dies. That means that evolution never has to check out the countless situations where you have that mutation to the heart protein AND mutations to, say, a protein that is important to liver function or the clarity of the lens of the eye or toenail hardness or countless other mutations. Is this similar to the alpha-beta minimax algorithm? Houdin

j: "Just because you’re not satisfied with one of Dembski’s replies so far doesn’t mean it shouldn’t be considered in the discussion." I discussed the paper. You were notably absent from the discussion. Even now, you offer no counter to my criticism of the "proof bluff." You merely assert that what others have already done should be done. So far? Does your faith that he will do better eventually make the present paper more valuable? j: "Actually, it seems that chance-and-necessity processes generate CSI only if the necessity is as defined by an intelligent agent, rather than being defined by chance. In which case its not really necessity." Say what? Tom English

bFast A strong correlation that I have seen, however, is between an interest in and aptitude for games of intellectual skill, such as chess and checkers and skill as a software developer. Bingo! Give the man a CEE-gar. The best programmers can think very quickly and logically. They can form models of complex logic/decision chains in their minds, test those models in the abstract, and do it much faster than the average bear. These are the same skills needed to excel at games of intellectual skill as well as the math portion of the SAT and IQ tests in general which are just another kind of intellectual game. DaveScot

I'm curious; is it the case that a weak checkers player (e.g. which just makes pseudo-randomly generated moves) has less CSI than a strong player? Does a program which checks if a correct move has been played have the same CSI as a weak or strong player? How do you work this out? Patrick Caldon

Tom English: "It was j who indicated it was relevant." Actually, I said that the paper "probably should be considered in the discussion." Just because you're not satisfied with one of Dembski's replies so far doesn't mean it shouldn't be considered in the discussion. Tom English: "Evolutionary computations are chance-and-necessity processes that seem to generate CSI." Actually, it seems that chance-and-necessity processes generate CSI only if the necessity is as defined by an intelligent agent, rather than being defined by chance. In which case its not really necessity. j

Salvador, Regarding post 28, the preface to the paperback edition of NFL merely points out that "Coevolutionary Free Lunches" does not apply to biological evolution. This does not change the fact that Bill continues to disseminate a claim that the main conclusion of the paper is wrong. And it is irrelevant to my observation that it is inappropriate for Bill to make a counter-assertion rather than provide a counterargument. It was not I who brought up Bill's "rebuttal" of "Coevolutionary Free Lunches." It was j who indicated it was relevant. I responded by arguing strongly that it was not. But let me say this: The claims of ID speak to many things other than living systems. Bill Dembski's law of conservation of information says that no chance-and-necessity process generates complex specified information. Evolutionary computations are chance-and-necessity processes that seem to generate CSI. The fact that they are not biological makes them no less a potential contradiction to the law of conservation of information. Tom English

Tom, I rank myself as a novice based on the standards of the American Checker Federation. In ACF tournaments there are three divisions: Minors, Majors, and Masters. I wouldn't think of embarrassing myself by entering the Minors at the ACF Nationals because I would come in at the bottom of the pack, if not dead last. The Majors division represents the "expert" category (although there is no such formal ACF designation as "expert"). The ACF has a rating system similar to that of the chess world, but you must enter tournaments with other rated players in order to get a rating. By my definition, an expert would be one who could place respectably in the Majors division. The four opening- and mid-game factors I mentioned in post 24 (single-corner development, center control, double-corner and king-row defense) are not esoteric concepts known only to the checkers elite who have spent years studying the game. These are the ABCs of checkers strategy that every student learns immediately after learning the rules of the game. This is equivalent to learning about the benefits of castling in chess. I wish I had time to write about Marion Tinsley, who was the greatest checkerist of all time, in my humble opinion. I fortunately had the opportunity to meet him and have my computer program compete against him at the 1990 ACF Nationals. He scored three draws and then defeated my program in the last round. I once discovered that my computer program, after running overnight and analyzing about a billion positions (in a mail-play tournament in which I was competing with the use of my computer program -- and my competitor knew that I was using my program), had refuted a classic checkers line. I called up Marion. He was watching Nova on PBS and I asked him if I could take a few minutes of his time. He said that he would rather talk to me than watch Nova. I asked him if he needed a checkers board to run up the position. He said no. I verbally rattled off the moves in standard checkers notation but didn't reveal the refutation that my program had found after analyzing a billion positions. Marion thought for less than a minute and replied: "Of course, you have 11-16!" which was the move my computer program found. I talked with Marion just a few weeks before he died in 1995. He was a professor of mathematics and a devout born-again Christian. GilDodgen

I personally find that the growing evidence that insects have evolved very little since the dawn of flowers is significant. The relationship between flowers and insects is significant. One would surely expect that these two kingdoms coevolved, but it seems that they didn't, or not very much at all anyway. In light of this contradictory (to NDE's prediction) evidence, I personally write off the majority of coevolutionary theorizing. With a few possible exceptions here and there, it doesn't seem to happen. bFast

Wolpert is a rabid Darwinian. As such he has no business serving as an Editor of the Journal of Theoretical Biology. Ye Gods, evolution isn't even going on any more. "A past evolution is undeniable, a present evolution undemonstrable." John A. Davison John A. Davison

Tom wrote: Bill has instead disseminated a counterclaim and told the authors of the original proof to prove it. He gives a tiny “hint” to suggest that he knows how to generate the proof, but really can’t be bothered with the details. To reiterate what I said above, even if someone obtained his proof for him, we would have only contention of two parties, not resolution of the matter. I have given the Wolpert and Macready paper close scrutiny, and I believe the proof is correct. The fact that Bill, as a brilliant mathematician who certainly knows that a counterargument is called for, offers a diversion rather than a counterargument leads me to believe that he can’t find anything wrong with the proof either.

In contrast Bill wrote Preface to Paperback Edition of NO FREE LUNCH

… Ironically, the very sketchiness of mathematical details that Wolpert claims prevents one from properly assessing the book does not prevent him from offering just such an assessment. In his review, he writes: “Neo-Darwinian evolution of ecosystems does not involve a set of genomes all searching the same, fixed fitness function, the situation considered by the NFL theorems. Rather it is a co-evolutionary process. Roughly speaking, as each genome changes from one generation to the next, it modifies the surfaces that the other genomes are searching. And recent results indicate that NFL results do not hold in co-evolution.” Since one of my main claims in this book is that NFL results do apply to co-evolution, it would seem that, coming from the inventor of the NFL theorems, this criticism should be devastating. But it is not. In Wolpert’s 2005 paper with William Macready titled “Coevolutionary Free Lunches” (IEEE Transactions on Evolutionary Computation), the authors acknowledge, in both the abstract and the conclusion, that “in the typical coevolutionary scenarios encountered in biology, where there is no champion, the NFL theorems still hold.” I highlight this contradiction not to gloat but simply to point up that the issues raised in this book remain very much alive and under discussion, and that the key players are still quite far from reaching a consensus….

scordova

Gil, Regarding post 24, tread carefully. You say you're a novice, but can beat Blondie. David says Blondie has achieved an expert rating in play against humans. I have been at conferences where he set up his laptop in the hallway and took on all comers. Each time, he announced the outcome of the competition at the meeting. I vaguely recall something like 25 wins and 1 loss in one case. I think your post itself calls the notion that you are a novice into question. If you can spot and name configurations as you do, you understand a lot more than most people do. I have played Blondie, and she trounced me. By the way, have you checked p. xi in David's book? ;) Cheers, Tom Tom English

Gil, trrll: “In other words, the only thing they programmed explicitly was the ‘laws of nature’ for checkers…” Gil: "Wrongo. The alpha-beta minimax algorithm is a human-devised search technique designed to maximize a score at the root node of the search tree. This is not part of the laws of nature for checkers." Trrll is only slightly off the mark. See the section on "The Checkers Engine and the Darwin Engine," starting on page 178 of Fogel's book on the system. Excerpt: "The design for our program decomposed naturally into two separate modules. [...] The evolutionary process was an iterative exchange of information between the Darwin engine and the checkers engine. Having worked on evolving neural networks in many different applications, we already had most of the Darwin engine complete right from the start. Kumar generated the first prototype for the checkers engine in about a week." Unfortunately, the Darwin engine sounds somewhat like a neural-net engine here. Actually, it is trivial to make the Darwin engine generic, so that it evolves individuals without knowing any details about them. (For you programmers out there, the code uses methods of an abstract Individual class. Details of individuals are hidden in subclasses of Individual, e.g. NeuralNet.) The details of the evolutionary process are separate from the details of what is evolved. The checkers engine is essentially the environment. The "laws of nature" in this environment include the rules of checkers and various aspects of how two neural networks are pitted against one another. In essence, there are two identical instances of a checkers program sans static evaluator. Two neural nets are plugged into the programs as static evaluators. The checkers engine gets play underway, and mediates the competition between the two programs. The partial checkers program, with its minimax search and other techniques, does not have a goal of making static evaluators. It is merely part of the environment in which static evaluators are evaluated. The Darwin engine does not have a goal of making static evaluators. Yet the Darwin engine extracts information (in an informal sense) about static evaluation from the environment (checkers engine). Tom English

Since I sensed a degree of interest in the topic of music and ID, and to alleviate Gil's thread, I opened a new thread: Wistar Convention, Salem Hypothesis, and Music Salvador scordova

Tom, That would be an interesting project if I could find the time. By the way, I’ve played Blondie and was able to beat her (with search depths in the range of seven or eight plies, as I recall), despite the distraction of the scantily clad and very voluptuous lady displayed on the monitor. As I mentioned, I’m a novice player. Most players lose because they get caught in “shots,” which are short-range tactics (sacrifice one, take back two, sacrifice two, take back three, etc.) that are detected immediately by the tree search but that can be tricky for a human to spot. I was able to beat Blondie pretty easily by taking advantage of her very basic positional weaknesses. For example, she failed to develop out of the single corner, made moves to the side of the board, allowed me to weaken her double corner, and did not properly defend her king row. At the same search depths I don’t do this well at all against my program (usually lose, sometimes draw, win on a very rare occasion), because all of this knowledge and much, much more has been handcrafted into the evaluation function. Over the course of several years, two of the nation’s top Checkers Masters (Ed Markusic and Leo Levitt) helped me implement and refine WCC’s evaluation function knowledge. GilDodgen

Gil: “It should be noted that human-crafted (i.e., intelligently-designed terminal-node evaluation functions) totally trounce Blondie’s eval function with ease.” CHALLENGE (revised): If your checkers system is written in C / C++, why not get Blondie's static evaluator from David and link it to your own code? The best evolved neural net is hard-coded into the function, so it's easy to use. You would have to translate your board representation into Blondie's before calling the static evaluator, and you might have to map Blondie's return values into the range used by your program. HYPOTHESIS: If you restrict the search depth to 8-ply (of course, selective extensions can go deeper), Blondie's static evaluator will beat the static evaluator in your released system. Assuming my hypothesis is correct, it would be very interesting to see how much the search depth must be increased to compensate for your static evaluator's deficiency in "intelligence." This is a worthwhile study, and the results should be publishable. Tom English

Trrll: “In other words, the only thing they programmed explicitly was the ‘laws of nature’ for checkers...” Wrongo. The alpha-beta minimax algorithm is a human-devised search technique designed to maximize a score at the root node of the search tree. This is not part of the laws of nature for checkers. Tom English: “When the specification of programs goes from ‘sub-novice checkers player’ in the initial generation to ‘expert checkers player’ in the final generation, and the two humans who worked on the system are novice players, the notion that the CSI came from the humans is not all that satisfying.” My program went from a very weak endgame player (both chess and checkers programs have the most trouble in the endgame) to an absolutely perfect endgame player through the generation of the perfect-play databases. (These DBs really are amazing to watch in action.) I gave the computer an algorithm and let it run for two months. When it woke up at the end, it had gone from a novice endgame player to the best player in the history of the game (within the domain of the DBs). I’m not sure that this is essentially much different than the phenomenon you mention in the Blondie project (which I admit is way cool and very interesting). I didn’t give the perfect-play information to the algorithm, it discovered it on its own. I’m not convinced that either of these processes actually represents the generation of CSI. I’d be interested in Dr. Dembski’s take on this. (Bill, care to comment?) By the way, I am a novice player myself. The game is much too difficult for me. GilDodgen

Gil, "These computer programs — and the use of evolutionary algorithms to design evaluation functions, as cool as all this stuff is — shed no light whatsoever on how natural processes could have produced the complex information and functionally integrated machinery found in living systems. What these programs demonstrate is that intelligent designers can do neat stuff with computers." Certainly you are right about "functionally integrated machinery," because the structure of the static evaluator is fixed, as is its function within the overall system. But this does not mean that there cannot be a gain in complex specified information. When the specification of programs goes from "sub-novice checkers player" in the initial generation to "expert checkers player" in the final generation, and the two humans who worked on the system are novice players, the notion that the CSI came from the humans is not all that satisfying. Some careful accounting for CSI is called for, not recitation of doctrine. Nobody has given the accounting. Tom English

j: "'Fitness among Competitive Agents: A Brief Note,' by William A. Dembski, should probably be considered in the discussion" Dembski: "I leave it as an exercise to show that averaged over all possible [values of certain variables], competitive searches based on the game matrix do not outperform blind search (for simplicity assume that the [the values of certain variables] are real numbers between 0 and 1). Accordingly, NFL holds even for competitive agents." Lickety-split, there goes the "Coevolutionary Free Lunches" proof of Wolpert and Macready, just like that. An exercise, indeed! If you see that someone makes an error in a proof and claims that a false proposition is a theorem, how do you deal with the situation? Do you prove that the negation of the false proposition is a theorem? No, because that resolves absolutely nothing. It leads only to two sides saying, "My proof is right. No, my proof is right. NO-O, my proof is right. NO-O-O, MY proof is right." And what is especially depressing about this is that with neither side scrutinizing the proof of the other, both proofs could be wrong. A norm in the cultures of math, science, and engineering is that when you claim a mathematical proof is invalid, you show what is wrong with it. Without a formal counterargument, you are blowing smoke, no matter how lofty an authority you are. Wolpert and Macready give what is known as a constructive existence proof of a coevolutionary free lunch. This means that they contruct a case in which a particular coevolutionary algorithm is generally superior to others. The obvious counterarguments are along the lines that the construction is flawed or the analysis of the construction is wrong. But it does not suffice merely to claim that there must be an error somewhere. You have to find the error. Bill has instead disseminated a counterclaim and told the authors of the original proof to prove it. He gives a tiny "hint" to suggest that he knows how to generate the proof, but really can't be bothered with the details. To reiterate what I said above, even if someone obtained his proof for him, we would have only contention of two parties, not resolution of the matter. I have given the Wolpert and Macready paper close scrutiny, and I believe the proof is correct. The fact that Bill, as a brilliant mathematician who certainly knows that a counterargument is called for, offers a diversion rather than a counterargument leads me to believe that he can't find anything wrong with the proof either. Tom English

Now for the main topic. The challenge I see for AI simulations validating NDE is that AI simulations invariably have the end point in mind. Chess programs have the end of playing better chess. What would be really fun would be to write an AI chess program, then start playing checkers against it. It would intrigue me if the chess program could discover that the primary rules have changed, and if it could adapt to the changed rules and master them. This, even, however, would not show what is needed to demonstrate NDE via AI. I consider the bacterial flagellum. I propose the following simple definition of the flagellum: The flagellum is a motive device. Its job is to cause the bacteria to move. Its method is to rotate a filament. If NDE is true, then a pre-flagellum must at some point existed. By pre-flagellum, I mean a device that did something useful, but that did not cause the bacteria to move. Now, without the bacteria ever "wanting" to move, a single mutational event had to happen which crossed the line between the pre-flagellum and the flagellum. After that mutational event, moving the bacteria must have occurred. If NDE, then in all likelihood this first flagellum also did some other task. However, the fact that the bacteria moved, though it likely had no sense of direction, must have given it some sort of inherent advantage over its siblings. In the context of this discussion, the bacteria stumbled onto "checkers", rather than having any guide pushing it in the direction of checkers. When it stumbled onto "checkers" it had to find advantage in doing so. For this reason, AI has a long way to go in truly simulating an NDE process. As far as Behe's flagellum claim goes, I really believe that Behe's character will be tested when it can be shown that a bacteria can exist with a pre-flagellum. Not just any manufactured pre-flagellum, but a pre-flagellum that is fully sensible, where all of its parts need to be there. Then with a single mutational event the line between pre-flagellum and flagellum needs to be crossed. Not only must the line be crossed, where we now have motion for the bacteria, but the bacteria must experience some sort of advantage in having this uncontrolled motion. (For surely the control of the flagellum must have developed once there was something to control.) The day that the above can be demonstrated, if Behe is of good character he will admit "flagella are reduceable." That day certainly has not come. bFast

I'd like to put my two cents into the discussion about talents that correlate to software development, as I have made it a hobby to observe this equation. I personally have not seen a high correlation between musical talent, musical appreciation and aptitude as a software developer. Scott, what can I say, I have also not seen a high correlation between mathematic aptitude and software developing skill. As a developer who has lightly dabbled in AI, who has developed significant patented software, but who has not developed software specifically intended to "do math" or to do complex engineering calculations, I have found that my math education has been virtually unused beyond algebra. A strong correlation that I have seen, however, is between an interest in and aptitude for games of intellectual skill, such as chess and checkers and skill as a software developer. I find that in designing code, I use farely similar thinking processes to those of playing chess. Software requires envisioning what the "opponent" (user) may do, it requires strategising a few moves ahead, and it requires compartmentalizing your though processes. At least when I play chess, I think in terms of my current offensive -- if I move here, then here, etc., then I will accomplish this. I also think in terms of the presumed strategy of the other -- I think this guy is trying to achieve this, so he's likely to be moving here or here, so I need to fortify my defenses accordingly. In general, good software naturally leads the user to where I want him to go just as good chess play leads the opponent to the same end. Fortunately, hopefully the user is a willing follower where the chess opponent is likely not. Gentlemen, do you also find a correlation between interest and aptitude for games of intellectual skill and aptitude for software development? bFast

Fogel and his team of software engineers programmed elements 1 and 2, without which element 3 (the product of the genetic algorithm) would have been completely useless. The fitness function was the definition of a win at the end of the tree search: no moves left for the opponent. This was a goal defined by the programmers. The leaf-node evaluation function is not essentially strategic; “strategy” is mostly a byproduct of the tree search.

In other words, the only thing they programmed explicitly was the "laws of nature" for checkers: The definition of what is a possible move in checkers (corresponding to the laws of nature, which set the limits of the possible), and the definition of success (winning the game, corresponding in nature to an animal carrying out the activities required for reproduction more successfully than its fellows). The result, after generations of evolution, was a program that was capable of playing a better game of chess than its creators--i.e. it had been able to derive, by random mutation and selection, more information about how to play the game than the designers themselves possessed. trrll

John is right that the fundamentals of music (harmony, the subdivision of the octave into 12 tones, etc.) are based on the physics and mathematics of sound (the nature of vibrating strings and columns of air). Re Scott, Marcos, and bass playing: I guess this just demonstrates that pianists are more highly evolved than bass players. I’m sure Ernst Haeckel would agree. :-) But back to the main topic of this thread. These computer programs -- and the use of evolutionary algorithms to design evaluation functions, as cool as all this stuff is -- shed no light whatsoever on how natural processes could have produced the complex information and functionally integrated machinery found in living systems. What these programs demonstrate is that intelligent designers can do neat stuff with computers. GilDodgen

Music appreciation is most definitely subjective. The under-girding structuring of compositions are not. Scott

Music appreciation is intensely subjective. And since the appreciation is subjective so too must be the composition otherwise everyone could be a wildly successful composer just by following formulaic procedures. I think the mathematical connection pretty much starts and ends with simple relationships between notes on the scale and also the way the notes combine to form harmonic sounds. DaveScot

I am terribly sorry if I strayed ever so little from the subject of the thread. It was the same Pythagoreans that discovered the frequency of the octave is twice that of the lower note as the ones that discovered that A squared plus B squared equals C squared, known among carpenters as the 3,4,5 rule. Mathematics and the rules of music are obviously closely related. They even originated together and neither are subjective. "A past evolution is undeniable, a present evolution undemonstrable." John A. Davison

You are not strange Scott, I fell your pain... I'm a bassist too (currently in a Death Metal band) and I have a bad time when it comes to math. Is there some correlation between bass playing and poor mathematical skills? =P Marcos

I play 4 & 5 string bass and guitar. I have been in a couple of "touring" bands, 2 of which almost signed major label deals (Warner Bros. & Capricorn Records). I can't solve math equations beyond basic polynomials to save my life. Yet, I do computer programming every day. I am strange. Scott

John Davison If you read the part of the article asking about music you'll see a couple of things. First of all the question was asking about a correlation between music, math, and computer science, not just music and math. Second, in context, the music portion of the question regarded talent at playing piano. I have CDs of Gil playing piano. Then Gil, because he is strong in math, computer science, and piano playing and ran into someone else with same set of talents, wondered if the three tended to run in groups. I answered no (based on anecdotal evidence) because I know a lot of people including myself who are strong in math and computer science but play no musical instruments, or at least don't play them well. DaveScot

Tom English: "Along those lines, I should mention that several years ago David and associates evolved new parameter values for the 'intelligently designed' static evaluator of a public-domain chess program." "Fitness among Competitive Agents: A Brief Note," by William A. Dembski, should probably be considered in the discussion: http://www.designinference.com/documents/2005.10.fitness_among_competitive_agents.pdf j

Of course there are many similarities between music and mathematics. My God the Pythagoreans used music as an example when they founded mathematics. You may recall that on another thread I suggested that music, like mathematics had already been composed before the presumed composers "discovered" it. I notice that suggestion did not evoke much response but I was deadly serious. Surely no one is so weak minded as to suggest that mathematics was the invention of the human mind are they? Perhaps some are but I am not one of them. I believe that all of science, which is of course based on mathematics, has always been there just waiting to be discovered. I have simply tentatively extended this notion to include all of man's experiences. What we have dismissed as "subjective" may not be that at all, but just as "prescribed" as every other aspect of the universe. Just as mathematics proceeded through a series of ascending levels of complexity so did music, literature and the arts generally. In my opinion our cultural life has reached what Schindewolf called the evolutionary stage of "typolysis" or degeneration followed by extinction. An interesting question mught be - is that happening to mathematics as well? I can't answer that question except to say that much of recent mathematical and cosmological theory is utterly beyond my comprehension, but then so is most of modern music and art as well. Perhaps we have finally blown out intellectual and cultural wad. Euclid's Elements in several volumes may be lttle different in origin from Beethoven's 9 symphonies. Both may have been simply discovered and, of course, subsequently published. They are now both for eternity for which we should be very grateful. I know this will not sit well with many but doesn't it remain in fundamental agreement with Einstein's unqualified dictum - "Everything is determined... by forces over which we have no control." I say it does. What say others and why? "A past evolution is undeniable, a present evolution undemonstrable." John A. Davison John A. Davison

I think backgammon is a rather more interesting subject of study than e.g. chess and checkers. The latter games are deterministic, and thus a single blunder by the AI can be exploited endlessly by a human. Also, the "branching factor" of these two games is sufficiently low to allow for a systematic tree search. (Which is not to say that these games as a whole were simple!) The remaining problem, then, is simply increasing the search depth by whatever means. In backgammon, the average branching factor is above 200, which makes a tree search infeasible. (There are 21 different rolls, and more than 10 valid moves for each roll, on average.) Because the available moves for each position are limited by the rolled dice, the game is indeterministic. A single mistake usually only *decreases* your chance to win, but does not guarantee a deterministic victory to a perfectly-playing opponent. Also, even if a human opponent detects slightly weak spots in the AI, it will be hard to steer an indeterministic game to a position exploiting a weakness in every game. Thus, it is sufficient for the AI to perform well *on the average*. Most biologists would probably agree that this kind of statistical strength, as opposed to perfection, is typical to a behavior resulting from any genotype. The revolutionary backgammon AIs of the 90s concentrated the bulk of intelligence in the *evalution* function. (A function which in a chess AI might be as simple as a basic "material strength" calculation, e.g. Q=9/R=5/B=3/K=3/P=1.) This evaluation function doesn't just "rate" each position by giving it so-and-so many points. It outputs the direct probability of e.g. black winning the game. (In practice, also winning "gammons" and perhaps even "backgammons" are taken into account, but let's keep it simple here.) I.e. the evaluation function approximates an extremely deep and complicated search. Yes, it's "only" an estimate, but it greatly impressed grand masters initially, and it continues to do so today. The method for creating the evaluation function was neural networks trained with temporal difference learning. A randomly initialized NN learned by playing against itself. Training the network with corpuses containing grand master level games proved less successful than pure self-learning. Including extra "tactical data" in the networks inputs, instead of just the "raw encoding" of the game position, has proved more or less a waste of time. (Increasing hidden nodes often works well!) Thus the "core engine" of a backgammon AI is a neural network which simply takes in a game position, outputs an expert estimate of the winning chance, and learns by simply playing against itself. The current boom in backgammon seems to be GAs. I think the "core engine" remains the same, but instead of reinforcement learning (including the backpropagation method), they are mutating the network randomly. The results are rather good, it seems. But I believe that the training process must take much, much more time than with more traditional NN training. caligula

Gil, The AI community has terribly mixed feelings about two-adversary games of perfect information. Although computer systems are now better than all human players in checkers and chess, they don't succeed by applying any of the principles of AI that have emerged over the past 50 years. And experimentation with the top-flight AI systems for checkers and chess has taught us precious little that we can apply in other domains. Most of cleverness in playing these games derives from two old warhorses, minimax game tree search and alpha-beta pruning. "The game tree explodes exponentially, so an alpha-beta minimax algorithm is employed." Actually, the growth in number of nodes from level to level in the game tree is exponential even with alpha-beta pruning of branches. (In the worst case, there is no pruning at all. In the best case, the exponent is halved.) Heuristics used in conjunction with the basic methods give some speed-up and improvement in quality of play, but selecting moves by minimax game tree evaluation is fundamentally a brute-force proposition. Playing out the endgame according to stored solutions in a massive database is also brute force. Worse yet, it took several decades of fairly intensive work with checkers and chess for all the pieces to come together. Let me put it another way. When you plot the rating of the world computer chess champion as a function of processor speed and get something close to a straight line, it strongly suggests that programs have not so much gotten smarter as computers faster. "Most of the playing strength of these programs comes from the tree search (which is not possible without the move generator), since humans have a hard time keeping track of this much detail." I disagree, and I have an important point to make. What you are trying to say, I think, is that most of the "playing strength" of a program is attributable to how many moves ahead in the game it can look (i.e., how deep the game tree search goes). Researchers have tried to make the static board evaluator (your "terminal-node evaluation function") contribute more to the quality of play. In other words, they have tried to make the program do better at looking a pieces on the board and assessing how good or bad the situation is for the computer. But this is another failure of checkers and chess research. Programs with quick-and-dirty board evaluation have consistently beaten programs with more accurate (slow) evaluation. In other words, adding "intelligence" slows down the evaluator and keeps the program using it from looking as far ahead in the game as it might have. "F*gel and his team of software engineers programmed elements 1 and 2, without which element 3 (the product of the genetic algorithm) would have been completely useless." I think all of the programming was done by one person. The program was an evolutionary algorithm -- the simulation is at level of phenotypes, not genotypes. The population essentially contained strategies (programs) with static board evaluators implemented as artificial neural networks. Only the static board evaluators evolved. "The fitness function was the definition of a win at the end of the tree search: no moves left for the opponent. This was a goal defined by the programmers. The leaf-node evaluation function is not essentially strategic; “strategy” is mostly a byproduct of the tree search." The program has no fitness function. The approach is one of coevolution, in which fitness of strategies is assessed by putting them in direct competition with one another. Each strategy plays games against randomly selected opponents in the population. For each game, both players are awarded points at the end. The payoff is 3 points for a win, -2 points for a loss, and 0 points for a draw (I think). After all of the games are played, the strategies with fewer points are culled from the population, and those with more points engage in reproduction-with-variation. The only goal defined by the programmer is to get points. Everything else is given by the game of checkers. "It should be noted that human-crafted (i.e., intelligently-designed terminal-node evaluation functions) totally trounce Bl*ndie’s eval function with ease." After close to one thousand generations of evolution, David took the best strategy from the population and began using it to play against humans on the Internet. Bl*ndie's opponents did not know they were playing against a computer. Despite very shallow searches of the game tree, Bl*ndie established an expert rating and played better than 99% of human players. In other words, her static evaluator is intelligent. Now we get to the heart of things. You're going to have to prove that to me in a controlled study. See if David will share the Bl*ndie code with you. Create a copy and do nothing to it but plug in a hand-crafted static evaluator you think will beat Bl*ndie. Then immediately test your version against David's. Both versions of the program must search to the same ply in the search tree. And that is why I hypothesize that your version loses. Your intelligently-designed static evaluator will not be as intelligent as the evolved one in Bl*ndie, and your program will be able to beat Bl*ndie only by brute force. Along those lines, I should mention that several years ago David and associates evolved new parameter values for the "intelligently designed" static evaluator of a public-domain chess program. In the beginning, the program was rated a master. After two days of evolution, it was rated a grandmaster. If memory serves, the gain in rating was 389 points. Furthermore, David did not use the asymmetric payoff function that Bill Dembski claimed was a source of CSI in Bl*ndie. Evolving strategies got 1 point for a win, -1 points for a loss, and 0 points for a draw. Tom English

Salvador, "The answer in Debmski’s book is, No." Boldface "no." Inquisitive minds want to know. Why did he say no? Tom English

I wrote a cribbage AI 20 years ago that people swore cheated. It's still on the internet available for download at cardandboardgames.com It doesn't cheat. I simply wrote an expert system that made the same decisions that I would make in any given situation. That alone made it a good competitor. I then improved on mother nature by leveraging what a computer is good at - calculating odds precisely and quickly. As each card was exposed I calculated the odds of where remaining cards would be. This would not be possible for a human unless some kind of savant like Rainman but it's certainly not cheating. Think of it like card counting at blackjack in vegas only more complicated. I didn't take any card into consideration until it had been legally exposed during normal gameplay. This made the program virtually invicible after playing it enough times for luck to average out so skill level can become evident. I could still whip the snot out of it but that's because I knew exactly what it was thinking and that's enough of an advantage to nullify the card counting. DaveScot

The relevance of Computer Checkers is tied to pages 221-223 of Dembski seminal work, No Free Lunch. David Fogel is mentioned:

Perhaps the most subtle example I know of an evolutionary algorith that appears to generate specified complexity for free is the evolutionary checker program of Kuma Chellapilla and David Fogel.... What is remarkable about this program is that it attained such a high level of play without having to be explicitly programmed with expert knowledge like the world champion chess program Deep Blue or the world champion checker program Chinook. But did teh evolutionary checker program of Chellapilla and Fogel find its exper checker-playing neural nets without commensurate input from prior intelligence? William Dembski

The answer in Debmski's book is, No. scordova

"Is there some correlation between music, mathematics and computer science?" No. DaveScot

A brief history of computer checkers

There was Checkers by Gil Dodgen, and Colossus by Martin Bryant. Bryant traded his opening book against Chinook’s endgame database, and in the early 90’s, Colossus was probably the best PC program, but it was never developed further. Gil Dodgen went on to create World Championship Checkers with Ed Trice, …. Murray Cash and the Trice/Dodgen team both computed the 8-piece database by the end of 2001, and after I also finished computing the 8-piece database in early 2002, Schaeffer finally released the 8-piece Chinook database to the public. Nemesis is the current computer world champion. …. On high-end machines, it should be no big problem to compute the 10-piece database, and there are rumours that the Trice/Dodgen team have already done this.

scordova