1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
README: Documentation text file for the Chess In Lisp foundation
Revised: 1997.06.08
Comments to the author: sje@mv.mv.com (Steven J. Edwards)
--- Abstract
The CIL (Chess In Lisp) foundation is a Common Lisp implementaion of
all the core functions needed for development of chess applications.
--- Purpose
The main purpose of the CIL project is to get AI researchers
interested in using Lisp to work in the chess domain.
Since the seminal work of Claude Shannon and Alan Turing from nearly a
half century ago, numerous artifical intelligence researchers have
utilized the chess domain as a vehicle for testing their ideas via
program implementations. About a decade after Shannon and Turing,
John McCarthy invented the Lisp language and it has remained to this
day as the programming language of choice for AI applications. Now,
the interesting observation here is that there have been no serious AI
full-domain chess applications in Lisp. While there have been a few
projects in Lisp that worked in restricted subdomains of chess (the
PARADISE project by David Wilkins in 1980 is an example), no one has
developed a full domain chess playing program in Lisp that uses
traditional AI techniques. There have been a few student chess
programs written in Lisp, but none are known to use anything much
beyond the traditional alpha/beta minimax search.
--- The Central Question
Why is it that AI workers haven't used Lisp to attack such an inviting
target as chess?
There are several answers. First, common industrial production
languages like C/C++ and Pascal are easier than Lisp for some and
support for these languages is more common than it is for Lisp.
Second, work in the chess domain has shown that the simple alpha/beta
search technique produces a high standard of performance and this
level has increased through the years as faster hardware has become
available; for those who value performance above generality, it is
difficult to find motivation for alternative approaches. Third, Lisp
has traditionally been implemented as an interpreted language and its
relative slowness is considered by some as a handicap for real time
applications such as tournament chess. Fourth, chess programming
requires a significant amount of low level detail work for move
generation and position operations and this has deterred those with
limited time resources or with limited patience (or skill) with
handling issues not directly related to higher level AI topics.
--- Things Have Changed
There is now a well-recognized and implemented standard for Lisp
(Common Lisp) with support for a variety of platforms. The near
omnipresent alpha/beta search has probably been exploited near to its
limits and so chess performance levels vary not so much on
implementation technique but rather upon how much money one has for
hardware. Public exhibitions of world class levels of chess playing
may impress the masses, but they contribute little (if any) to
artificial intelligence in general. Serious AI workers have, with
justification, criticized chess programmers as claiming AI status only
because of the performace demonstrated and not because of the
methodology employed. The chess programmers have responded mostly by
disclaiming AI status. But a better, or at least a more interesting
response would be to re-examine the tools of AI theory and programming
and start applying them to the chess domain. So, now we have the CIL
project to help stimulate real AI work in the chess domain by making
it easier to utilize well-known Lisp AI techinques (e.g., machine
learning, generalized search techniques, pattern recognition, and
planning).
--- Project status
The current version is a work in progress and is being released so
that other researchers may have an opportunity to see the direction of
the effort and to elicit feedback on future development.
The current version includes a full set of chess definitions, move
generation, move execution/retraction, position status determination,
formatted move I/O using SAN (Standard Algebraic Notation), and
several programming examples. It is not intended as an example of
traditional Lisp programming techniques; instead, it is intended as an
easy to use and portable collection of tools designed to facilitate
the development of applications that do use traditional Lisp
techniques.
--- Data Representation
The program uses the bitboard technique that employs 64 element simple
bit vectors for representing boolean properties of a chessboard. The
various bitboards and arrays of bitboards are documented among the
global constants and global variables within the source. At all
times, the processing core keeps track of:
1) Vacant/occupied squares (bitboard *ammbb*)
2) Occupied by color squares (bitboard vector *c0bbv*; indexed by
color, two elements)
3) Occupied by color-piece type squares (bitboard vector *cpbbv*;
indexed by color-piece type, 12 elements)
4) Attacked by color squares (bitboard vector *acbbv*; indexed by
color, two elements)
5) Attacks to a square by either color (bitboard vector *atbbv*;
indexed by square, 64 elements)
6) Attacks from a square (bitboard vector *afbbv*; indexed by square,
64 elements)
There are also a number of constant bitboards: the null bitboard,
edges, king moves, knight moves, intersquare paths, etc.
Colors are repesented as 0 for white and 1 for black. Pieces are
represented as 0 for a pawn, 1 for a knight, 2 for a bishop, 3 for a
rook, 4 for a queen, and 5 for a king. Color-pieces are represented
as ((color * 6) + piece); a white pawn is 0, a white king is 5, a
black pawn is 6, and a black king is 11. A vacant square color-piece
is a 12.
Ranks are represented with 0 (rank one) to 7 (rank eight) and files
are represented with 0 (file a) to 7 (file h). Each square is
represented as ((file + (rank * 8)), so square a1 is 0, square h1 is
7, square a8 is 56, and square h8 is 63.
The global variable *board* is an array of 64 integers, each with the
value corresponding to the occupying color-piece. The status
environment is composed of the active color (*actc*), the passive
color (*pasc*), the castling availability (*cast*), the en passant
target square (*epsq*), the halfmove clock (*hmvc*), and the fullmove
number (*fmvn*). The board and the status environment (except the
passive color) can be displayed with the "ui-dvfe" user interface
function (display value: Forsyth-Edwards notation).
The current version was developed using Macintosh Common Lisp provided
by Digitool. It should run on any Common Lisp conformant platform.
Unfortunately, the code appears to trigger a garbage collection bug in
GNU Common Lisp running on the Linux operating system. Linux/GCL
workers are invited to diagnose and fix the problem.
--- Roadmap
The CIL Lisp source is entirely contained in the text file cil.lsp and
is organized with global constants appearing first, global variables
appearing second, various core functions appearing third, and some
programming examples appearing last. A number of user interface
functions are provided; each of these have names of the form "ui-XXXX"
where the "XXXX" is a command mnemonic. Note: the function "ui-init"
must be called prior to any other function; it performs general
initialization and this is required before further operations.
The experimenter is invited to work through the source code and
commentary for further details of operation.
--- Future Work
Well, there are a lot of things for future work. Here are some in
progress:
1) Improved external documentation.
2) Improved internal documentation.
3) Lisp packaging.
4) More programming examples.
5) More support for data exchange standards; these include FEN input,
EPD I/O, and PGN I/O.
And here are some to come later, perhaps much later:
1) Development of a general pattern facility that includes a chess
pattern language, pattern primitive recognizers, and a pattern
matching engine.
2) Development of a general search tree facility that includes support
for algorithms like best-first search, beam search, breadth-first, and
even alpha/beta minimax.
3) Development of a general planning facility that includes a planning
language, plan generation, and plan execution.
4) Implementation of various machine learning techniques. Many
opportunities exist for this one.
README: EOF
|
