I was going to post this as a comment in Salvador’s thread (https://uncommondescent.com/index.php/archives/1481) but it became too long, so I’m posting it as a new topic.
On the subject of computer checkers I have some observations. I hate to brag (okay, I lied!) but I am one of the world’s leading authorities on this subject.
I know David Fogel. He is a very bright researcher and a really cool, nice guy. (Plus, he is a very talented pianist and musician. We have shared our piano CDs. Is there some correlation between music, mathematics and computer science?)
There are three essential elements in an artificial-intelligence (AI) games-playing computer program:
1) A move generator. The board and pieces must be represented in the computer’s memory, either as arrays or bit-maps. An algorithm must be devised to generate moves based on the rules of the game.
2) A tree-search algorithm. This is even more complex and requires sophisticated software engineering. The game tree explodes exponentially, so an alpha-beta minimax algorithm is employed. Other sophisticated algorithms must be used to curtail the exponential explosion: quickly accessible hash tables that contain previously-seen positions, iterative deepening with best-move prediction accessed from the hash tables, use of killer moves and move sorting based on a history heuristic, and much more.
3) A terminal-node evaluation function which attempts to ascertain the value of a position statically, since the tree search must terminate at some point. These values are backed up through the search tree with the alpha-beta minimax algorithm.
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.
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.
This is not to say that Fogel’s research is meaningless. It is intriguing and worthwhile. What all this means is that a cleverly designed trial-and-error process, combined with a lot of even more clever software engineering and human-devised algorithms, can produce interesting and productive results.
It should be noted that human-crafted (i.e., intelligently-designed terminal-node evaluation functions) totally trounce Blondie’s eval function with ease.
Read More ›