Genetic Algorithms and Programming

Today I was reading an article on GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players by Ami Hauptman and Moshe Sipper. The article discusses how the authors used Genetic Programming to develop chess strategies in various type chess endgames (KQRKQR, KRRKRR, and KRKR). The authors consulted with chess masters, then tested their work against CRAFTY. Because of the promising results of the research, the authors aimed three paths for future activity:

• improve the evolved programs’ performance against the above and other endgames,
• branch out beyond endgames,
• analyze the evolved cognition as to its resemblance and difference from human cognition.

The loftiest goal is using this effort to branch out beyond endgames. Since I am starting new I would start with Quinlan’s work, then perhaps look at Ken Thompson’s chess endgame effort, and finally attempt to duplicate this articles effort.

Also, I was exploring John Koza’s web site on Genetic Programming. There is some very interesting information; for example, I downloaded and read the power point presentation on Genetic Programming and Genetic Algorithms.

My biggest complaint is the cost of obtaining scientific articles. Although I understand that publishers need a return on their investment in publishing, I find it excessive to download a PDF document for $25. Publishers should make resonable to obtain such articles. For now, I will be using my local University to access and obtains articles of interest.

For references, see the reference page.

Recent Explorations

In the past few days I explored the AAAI Topics website and was researching the agent page. I stumbled into the MIT OpenCourseWare and various courses in AI. From the agent section, I found a website article on GameDev.Net that describes how build a chess program. Also, from the comp.ai new group I found the book A Field Guide to Genetic Programming by Poli, Langdon, and McPhee, which available for downloading. Finally, I was exploring how to operate the AIMA game agents. Just a brief update on is happening.

Representations for Knowledge-Based Systems

As my AI journey continues, I began reading part IV, which is titled Representations for Knowledge-Based Systems, from Luger’s book Artificial Intelligence: Structures and Strategies for Complex Problem Solving. After the introduction, I dove into the chapter on Rule-Based Expert Systems, followed by the Chapter on Knowledge Representation. My progress this month was limited because of time, other distractions, and reviewing other books and programs.

What is a rule-based expert system? A expert system consists of a user interface, an inference engine, an explanation subsystem, a knowledge-base editor, case specific data, and a general knowledge base. Typically separate from the general knowlege base, the case specific data contains facts, conclusions, and other relevant information under consideration such as the data in a problem instance, partial conclusions, confidence measures of the conclusions, and dead ends in the search process. The explanation subsystem allows the program to explain its reasoning to the user by explaining its justifications of the system’s conclusions, requests for a particular piece of data, and possibly presents tutorial or deeper theoretical justifications for the program’s actions. The knowlege base editor is used to correct errors or to add new knowledge. The heart of the export system, the general knowledge base contains the problem solving knowledge of a particular problem, which is represented in the form of if-then rules. Finally, the inference engine applies the knowledge to the solution of actual problems and is the interperter for the knowledge base.

There is plenty of information in the Internet regarding the topic of Expert Systems. A good start is the Expert Systems webpage from the AAAI website. In addition Luger supplies references for additional reading.

Decision Trees

I have been reading about decision trees, which induces concepts from examples. According to Luger (1993), the earliest is the ID3 tree induction algorithm, which was developed and experimented by Ross Quinlan back in the late 1970s and early 1980s. After the development of ID3 algorithm, Paul Utgoff (1989) developed the ID5 algorithm.

Ross Quinlan (1983) describes how the ID3 algorithm was used to identify positions, using the white king and white rook versus the black king and knight endgame as the domain set, that lead to a loss for black in n-ply moves after processing a training set. Therefore, by using a tree structure, the idea is to classify the training set and induce a rule set. In the experiments, the larger the training set, the more accurate the induction rules became in classifying and identifying a position more accurately. The problem was back then was computing resources were limited compared to today’s PCs. So, if the training set was modified, then entire training set was processed in a batch and the new tree induction was created.

Ross Quinlan (1992) continued his work with tree induction algorithms and developed the RC4.5 algorithm. His work continued until he developed RC5.0 algorithm, a closed propriety algorithm used for commercial data mining applications.

Utgoff (1989) developed the ID5 tree induction algorithm. The purpose of the ID5 tree induction algorithm was to modify the induction tree if a second training set was added to the existing training set. Instead of batching the entire training set, ID5 algorithm modified the existing tree because the cost of rebuilding tree was expensive. In addition, the ID5 algorithm had yield the same tree as the ID3 algorithm. Utgoff (1997) continue his work in this field and developed the Incremental Tree Induction algorithm.

Much of the above research was found in the Internet by using Goole to search various topics as the references below. The idea for decision trees is to take a training set from a domain set, develop a decision tree, generate a rule set, and validate against a test set. I forsee this effort in the development knowledge bases for expert systems and other rule based systems.

The above is not a theoretical discussion about the ID3, RC4.5, RC5, ID5, and ITI algorithms. For specifics and details, read the references in the reference page.  The authors may have sample code available – typically in LISP (Luger and Mitchell). Quinlan and Utgoff have restrictions for the use of their code base.