Representing Chess

Over the years chess positions have been represented by bit maps and coordinates.  Bit maps are the most efficient representation of a chess board, and it is used by many programs to save storage.  A coordinate system uses an array or a list to store information about a chess position.  These two approaches have been applied to various chess applications.  In this text chess positions will be described in logic programming framework, a similar approach to McCarthy’s frame problem (McCarthy 1969).

First, the domain knowledge begins with the square(X,Y) relation.  The board starts with square(1,1) to square(8,8).  Thus, there are definitions for all 64 squares.  The next piece of domain knowledge is color relation with two facts – color(white) and color(black).  The piece relation has the following facts – piece(pawn), piece(knight), piece(bishop), piece(rook), piece(queen), and piece(king).  That is the basic knowledge in the domain.

The current state of each piece on the board will be defined as four tuple relation called state.  The state fact has four elements – color, piece, square, and position.  Upon close study, one can easily derive the state relation with the first three elements easily.  The state relation was first defined in Learning Chess Patterns (Morales 1992).  The color is an element of the set of {white, black}.  The piece is an element of the set of { pawn, knight, bishop, rook, queen, king }.  The square is the piece current location from the set of { square(1,1), square(1,2), …., square(8,7), square(8,8) }.  The last element state relation is the position number.  The position is an integer in the positive integer number set and allows a history of the positions.  Without this position information, the history of the previous position is lost after the move transition.

Example 1: Describe the state of the white king located at 4,4 and the black king located at 6,6.

state(color(white), piece(king), square(4,4), position(1)).
state(color(black), piece(king), square(6,6), position(1)).

Example 2: Using the position above, update the state after the white king moves to 4,5.

state(color(white), piece(king), square(4,5), position(2)).
state(color(black), piece(king), square(6,6), position(2)).

The state will have more state relations as their more pieces in the board.

Year In Review 2011

Unfortunately, I have stepped away from this blog.  However, I have made some interesting conclusions.  First, the production language CLIPS is taking longer than expected to learn compared to other languages.  The implementation of the blackboard architecture may be complex in LISP, but adding new facts to the blackboard is simply asserting new facts into temporary database.  The PAL system has been used for simple endgame of king and rook versus king, where the PARADISE system computed combinations based on examples from Fred Reinfeld’s book.  Finally, in the logic programming, chess positions can be described by the state(Color, Piece, square(File, Row)) term.

Next CLIPS Project

My next CLIPS projects are to develop a program for the three blocks world puzzle and the King and Rook versus King (KRK) chess endgame.  The CLIPS documentation comes with many examples, which some take advantage of the CLIPS Object Oriented Language (COOL).  The approach to the blocks world puzzle will be based on [Luger, Stubblefield 1993].  Because the KRK chess endgame is the most used test platform in Artificial Intelligence research, I have not found an CLIPS implementation and look at the Bratko AL0 for its implementation.  All these activities will aid in learning the CLIPS language because the goal is to implement PARADISE into CLIPS.

CLIPS Part Deux

As I continue to learn on how to use CLIPS, I found an improvement to the terminating condition for the knights tour from the previous post by using the halt statement. Replace the terminating condition with the code as follows:

;; Terminating condition
(defrule goal-rule
?init <- (square-is 2)
=>
(printout t “Reached the goal square.” crlf)
(halt))

CLIPS

For the past few days I have been experimenting with C Language Integrated Production System (CLIPS). It is an interesting platform to experiment with Expert Systems. The users guide is a good introduction into rule based systems. The software is the topics of multiple books in Amazon. All the books on LISP and Prolog that are in my personal collection have a common theme – building expert systems at some point in the book.

Why an interest in expert systems? Well, IBM Watson, the Jepoardy playing computer, is a high end expert system using statistical inference (possibly bayes net) to find questions to Jepoardy topics. I was also interest in Watson’s capabilities. Also, AL3 is an expert system as well as PARADISE. My interest is in designing a knowledge based chess playing program with the capability of playing like a human chess player using rule based knowledge to solve positions as well as adding new knowledge based on relational learning.

Depth-First Search II

In the previous discussion regarding the depth-first search, I provided prolog code for the program.  In my research, I asked the following:

Because the current maze puzzle has only one solution, can the maze puzzle be modified to contain additional exit nodes so that the depth-first-search program can test for additional solutions?

Search Algorithms

While reading Artificial Intelligence Techniques in Prolog (Shoham 1994), in the Search chapter, the author writes generic search algorithms.  For example, the depth first search algorithm passes the name of the function connecting the nodes in the graph.  That is very interesting since in other Prolog books, the authors customizes the search algorithm to the problem.  As a result of this information, I simply modify a puzzle from book and incorporated the generic depth first search algorithm.  I took and modified the maze problem in Chapter 8 from Covington’s book.

Progress Report – October 2010

Sorry about the lack of recent progress reports; however, I took a vacation from the subject.   Recently towards the end of October, I upgraded my AI environment to Fedora 13, which was released last year.  Interesting the distribution comes with CMUCL and SBCL as well as an older version of SWI-Prolog.  However, I downloaded the lasted SWI-Prolog v5.10.2 and compiled it.  An interesting that SWI-Prolog binary is now called swipl, which was in previous editions simply just pl.  Because of this, I added an alias to my bash run control file to start swipl as pl.

Also, I am continuing studying and working problems using the Poisson process and Bayes Theorem.  After taking the break, I had not lost any concepts that I had learned earlier.  The book does have a table of Poisson probabilities, which does save time.

My current goals to finish what I have started in terms of Prolog, LISP, and Bayes Theorem as well continue to read interesting AI articles.

I want to thank my readers for supporting this blog.

Progress Report – June 2010

This month’s focus is RRL Code, Model based RL Video, and Incomplete data structures.  The RRL Code is my Prolog implementation.  The Model based RL Video is Michael Littman’s video lectures from NIPS  2009, which available from video lectures dot net.  Finally, I read Chapter 15 on Incomplete Data Structures of the Sterling and Shapiro (1994) book.  Each of these topics have their own blog entry.

From video lectures I have started watching an An Introduction to Statistical Relational Learning by Dr. Lise Getoor and Policy Gradient Reinforcement Learning by Dr. Douglass Aberdeen.  From the NIPS 2009 conference, I watched Bootstrapping from Game Tree Search, and consequently the article.

Incomplete Data Structures

Another interesting concept from 1994.  The chapter has four sections covering difference lists, difference structures, dictionaries, and queues.  The power behind this concept is unification.  The append operation against difference lists is completed in linear time.  Difference structures is similar to difference lists.  Queues are very self explanatory.  I will analyze existing Prolog programs to verify if incomplete data structures will improve the execution.