| |
This function is responsible for all of the rules of the game - how
each type of piece is able to move, when the game ends, checks
(including double checks and discovery check), and special cases
such as castling.
Basic data structures are provided with functions for manipulating
them. These data structures are used in the implementation of the
rules.
| |
2.1.1 Objectives
| |
This section was designed with two primary objectives in mind:
- It should implement all of the basic rules of the game.
- It should execute as quickly as possible. Since these
functions will execute literally thousands of times for each
move the computer makes, small time optimizations can lead to
great performance improvements overall.
|
2.1.2 Design Alternatives
| |
Representation - It was not immediately obvious while
of two reasonable representation schemes for the chess board
would be the most advantageous. The options were an 8x8
two-dimensional array or a list of piece locations.
It was eventually determined that the array implementation
would make it easier to determine the number of available
moves for pieces that move in straight lines (bishops, rooks,
and queens) since it could be quickly determined if a square
was blocked or empty.
Check Detection - In early revisions, a very simple
model was used to determine which potential moves would leaves
the king under attack. (These moves must be eliminated
because the are illegal.) The copy of the board structure was
made and the candidate move was made on this second board.
The the potential move finder was applied for the opposing
side. If any move was found that captured the king, the
original move was rejected.
While this idea was theoretically sound, in practice it proved
too slow to be practical. Instead, an alternate method was
devised which involved tracking which squares were attacks by
opposing pieces (the king cannot move onto these) and piece
pieces are "pinned" to the king along which axes. (These
pieces cannot move along any axis other than the axis along
which they are pinned.)
The only moves that are allowed are those that do not leave
any of these restrictions unsatisfied.
|
2.1.3 Data Description
| |
Most of the data structures are defined using lisp's
defstruct facility.
move - Moves are represented by two pairs of
coordinates and a flag to denote special sorts of moves -
promoting, and castling.
(defstruct move
(from-x -1)
(from-y -1)
(to-x -1)
(to-y -1)
(spec 0)
(value 0)
)
board - This structure represents all aspects of a game
position including where the pieces are, whether the king and rooks
have been moved and whose turn it is. There are also slots for
storing various information about the strength of position; these are
cached here for efficiency, so that they need not be recalculated
whenever they are needed.
(defstruct game
(to-move white)
(sq (make-array '(8 8)))
(state normal)
; The list of squares into which a player can move
; into order to "block" an opponent's check
(check-squares ())
; This list is used to determine if a player is eligible to
; castle
; (<white king moved> <white king's rook moved> <white queen's rook moved>
; <black king moved> <black king's rook moved> <black queen's rook moved>)
(moved-list '())
; These are used to determine the relative strength
; of each position
(material 0) ; material - which pieces are on the board?
(pos 0) ; position - where are they?
(space 0) ; space - how many squares do I control?
(attacks 0) ; attacks - a measure of how much material is under attack
(open-files 0) ; open-files - how many major pieces are on open files
; These are important to alpha-beta pruning of the minimax tree
(alpha nINF)
(beta pINF)
(pcount 0)
(pawn-structure 0)
)
|
2.1.4 Interface
| |
This is an internal component; no user interface is provided. The AI
searching component uses a few high-level interface functions:
new-game - returns a new game structure,
initialized to the standard starting game position.
do-move - Accepts a move and game position.
Modifies the game position to reflect the fact that the given move
has been made.
moves - Accepts as a parameter a game structure
and returns a list of move structures representing valid moves from
that position. As a side effect, also calculates values for
material, position, space, etc.
save-game - Accepts a file name and a game
position. Writes the game position in a Lisp-readable format the
disk with the given filename.
load-game - Accepts a filename. Returns a game
structure that has been loaded from the specified file.
|
2.1.5 Processing
| |
Within the moves function, processing takes four
essential steps:
- Scan the array, taking note of which squares are attacked by
opposing pieces. Also note which pieces are pinned.
- Scan the array again, searching for pieces. For each friendly
piece found, call a special function (based on what type of piece
it is) to generate potential moves.
- Eliminate moves that leave the king in check from the potential
moves list.
- Add castling moves to the list, if appropriate.
|
2.1.6 Verification and Testing
| |
Verification was done through repeated testing. Many games were
played using the rules engine. Each time, the list of acceptable
moves was verified.
In addition, specific test cases were set up to test certain unusual
cases such as pinned pawns, castling eligibility, and allowable moves
while in check. Some of these test cases were generated by manually
editing a saved game file, others happened in the normal course of
play.
|
2.1.7 Constraints and Extensions
| |
One obscure rule was not implemented - that of en passant
capture. In certain situations, a pawn can be captured by another
pawn moving to a square other than the square in which the first pawn
is located. This rule is not implemented because it is an exception
to many of the standard rules and would have required modifications
to code in a number of different places.
|
|
At the heart of the alpha-beta lookahead strategy is the idea of an
evaluation function, a function to determine the relative goodness
or badness of a particular game position. This function is applied to the
leaf node of the game tree and provides the foundation for decision-making.
| |
2.1.1 Objectives
| |
Sevaral factors needed to bew considered:
- It should represent the strength of the player whose turn it is
to move.
- It should implement the general principles used by the author in
his owm games.
- It should execute as quickly as possible, since it will be
called thousands of times for each move the robot makes.
|
2.1.2 Design Alternatives
| |
It was decided early on that since this function would be called so
frequently, it should be able to execute without any loops. To
accomplish this, calculatinos for many of the values needed to
properly evaluate a position were shifted into the moves
function, which would need to be called for every evaluated position
anyway.
This reduced evaluation to a "simple" process of applying weights to
each of the features measured while determining the legal moves.
|
2.1.3 Data Description
| |
The evaluation function accepts as input a game position.
It
accesses these fields:
material - the count of pieces on the board,
weighted by standard piece values (P=1, K=3, B=3, R=5, etc.)
position - a measure of how well pieces are
positioned on the board. Uses look-up tables of optimal positions.
space - the measure of how mobile pieces are.
More mobile is good, especially when that mobility is toward the
center squares.
attacks - the number of opposing pieces that are
under attack minus the number of friendly pieces are being attacked.
open-files - the count of major pieces that are
not blocked by pawns.
In all categories, an even matchup is represented by a value of 0.
|
2.1.4 Interface
| |
The interface here is trivial, just one function:
(defun game-strength (g)
. . .
)
|
2.1.5 Processing
| |
The score returned is a weighted sum of all of the factors:
(* 100 (game-material g))
; Positioning - where your pieces are - up to 300 pts.
(* 2 (game-pos g))
; Space - squares you control - up to 50 pts.
; (more in extreme cases)
(* 50 (/ (game-space g) 48432.0))
; Attacks on opposing pieces - 1.25 pts. each
(* 1.25 (game-attacks g))
; Open files - major pieces not blocked by pawns - 8 pts each
(* 8 (game-open-files g))
; In check - deduct 8 pts.
(if (check-p g) -8 0)
; Connected Pawns - 1.75 pts each
(* 1.75 (game-pawn-structure g))
Material and positioning are, by far, the most important factors. This
mirrors the typical human perception.
|
2.1.6 Verification and Testing
| |
Since the output of this function is not algorithmic but heuristic,
is is impossible to "verify" this it functions "correctly". Instead,
the output of the entire AI (evaluation function + lookahead search)
was repeatedly tested and refined.
|
2.1.7 Constraints and Extensions
| |
The weights for each of the factors were chosen manually. A useful
and effective enchancement would be to use some search algorithm to
optimize these weights. A genetic algorithm approach seems to be the
most appropriate.
|
|
| |
2.1.1 Objectives
| |
The goals here are not terribly complex: We want to choose the best
move possible. To accomplish this, we'd like to search as deeply and
as intelligently as possible.
|
2.1.2 Design Alternatives
| |
There are two common methods for implementing a lookahead search -
one that keeps the entire game tree in memory at once and simulates
recursion, and another that uses true recursion but does not include
keep the entire tree at once.
The second design was chosen because it is easier to implement and
for memory considerations - the game tree that we're evaluating has
literally thousands of nodes.
|
2.1.3 Data Description
| |
The structures defined above in section 2.1.3 are used here.
|
2.1.4 Interface
| |
Again, one function defines the entire interface:
(defun ab-move (g)
. . .
)
This function accepts a game position, performs the search, and returns
the move it chooses.
|
2.1.5 Processing
| |
Since the alpha-beta searching algorithm is fairly standard, this
section will focus on the special extensions made for this particular
problem.
- dynamic lookahead depth - In order to cope with the
horizon effect, searching will not stop until it finds a position
it decides is stable. This is done by watching the changes in the
evaluation function. Changes greater that 100 are considered
interesting.
- hash table caching - Often, a single position will
appear in the search tree more than once. To avoid evaluating this
subtree more than once, the values are cached in a hash table.
Before each subtree is searched, the hash table is consulted to
determine if this possibility has been explored yet.
- end-of-game optimizations - when a checkmate is found,
its value is assigned based on the depth at which it is found in
the tree, such that winning checkmates at the top of the tree are
valued more highly and those found later on. In this way, the
computer player will choose checkmate in a single move over a
longer, more complicated mating sequence.
|
2.1.6 Verification and Testing
| |
This is another difficult function to verify. In early tests, the
search was run in a way the printed out the entire tree. This tree
was verified by hand - it was shown that the max and min branches
were chosen at the appropriate levels.
After this, much like the evaluation function, the search algorithm
was refined throughout the development process, based on the computer
player's quality of play.
|
2.1.7 Constraints and Extensions
| |
The biggest constraint here is execution time. Full lookahead is
only possible to 2 or 3 plys within reasonable time. (Interesting
lines can be explored much more fully.)
One interesting solution to this problem would be to rewrite the
search to run on multiple processors, probably via PVM. Depending on
the number and speed of processors used, this could increase the
search depth by 1-2 plys.
|
|
|