Transcript Application of Artificial intelligence to Chess Playing Capstone

Application of Artificial intelligence to Chess Playing
Capstone Design Project 2004
Jason Cook
Abstract:
Chess presents challenges that are not present in other games, because of its complexity and the number of possible
moves to evaluate. A common strategy for chess programs is to develop a tree data structure with all of the possible
moves from a given starting board up to a certain depth, and then traverse the tree and evaluate it to find a good
move.
I have implemented a simple "chess engine", which is the logic behind a full chess computer game. The program attempts
to balance as much chess playing power as possible with the constraints of running on a desktop computer.
The number of moves evaluated is of great importance in determining the strength of a chess engine of this type. For that
reason I have implemented the engine in C to minimize the time of execution for the many tree manipulations and
bitwise operations involved. The validation of this project was done by testing the engine against multiple freely
available chess engines of varying power. The results of these games were then documented and analyzed.
Bitboards




Decision Trees
Bitboards are 64 bit unsigned integers, with the bits
mapped to the 64 squares on the chess board.
It takes 12 bitboards to represent a chess board,
one per combination of piece and color.
Bitwise operations have a large speed advantage
over 2 dimensional array manipulations, especially
on 64 bit hardware where they become a single
operation.
Bitwise operations are powerful: left shift by 8 gives
the effect of advancing all pawns 1 square, bitwise
AND tests for check or capture.


The decision tree is built out of states of the chess board, with the root
node being the current state. A decision tree for chess expanded to
checkmate on every branch has 10120 nodes, so we can never hope to
build or evaluate the entire tree.
Evaluation of the decision tree in this project is implemented as an
anytime algorithm, which builds part of the tree, then generates and
stores a next move based on that tree. If time remains the tree is
extended and reevaluated, and the new move replaces the old one.
Root (current board)
Bitboards
Evaluation score
Board after white pawn move
Bitboards
Evaluation score
Evaluation Functions





There is one score for each chess board in
the decision tree. These are calculated
independently of the preceding boards, using
criteria borrowed from OSTRICH, a well
documented chess engine.
NegaMax (a MiniMax variation) is
implemented with recursive descent to bring
the score of one terminal node to the root of
the decision tree.
Credit for each of your pieces on the board,
negative points for your opponent’s pieces,
with weightings per type of piece
Emprise: On which squares could you make
a capture in one move, if there we an enemy
piece there. This is reduced to a integer
value for evaluation purposes.
The engine is predictable. This is a
theoretical weakness, but in reality the
behavior changes along with the current look
ahead allowed by the anytime algorithm.
Board after black knight move
Bitboards
Evaluation Score
Board after white rook move
Bitboards
Evaluation score
...
Decision tree implementation



Equal depth breadth first (no pruning of
the tree)
Typically built to ~4 ply
Uses dynamic memory allocation,
allowed to use up to 90% of physical
memory
Ideas for further work
Results





Moderately weak performance
against an online chess engine
Elements of intelligence
Indecisive/repeated moves
Opponent appeared to have a begin
game database, which allowed it to
develop its pieces more effectively.
Visible potential for tuning the AI





Tree pruning algorithm
Evolutionary reasoning
experiment to refine settings
GUI, WinBoard/XBoard
compatibility, or web interface
Deterministic beginning and/or
endgame databases
Make the program “learn” via
case based reasoning