Transcript Application of Artificial Intelligence to Chess Playing

Application of Artificial
Intelligence to Chess Playing
Jason Cook
Capstone Project
Outline



What this project is/isn't
Goals: Personal and Project
Relevant areas
 Decision


Requirements
Demonstration
 Interface


Trees, Bitboards, Evaluation Functions
and simple game play
Additional ideas/possible continuation
Validation
What it is/is not
Is:
Chess engine
- Logic
Vehicle for investigating AI
Is not:
Full computer game
- GUI, saved games, teaching mode…
- Specialized hardware project e.g. Deep Blue
Personal Goals

Deepen my understanding of Artificial
Intelligence
- No employer/client context


Gain experience from a significant piece of
software engineering and coding, and
demonstrate my skills in those areas
Investigate optimizing the program for
speed
High Priority Project Goals
No illegal moves
- Check user and computer moves
Engine never fails to produce a move
Continually improve the strength of the
engine
Relevant Areas
Bitboards
– 64 bit unsigned integers
– Takes 12 to represent a chess board
– Bitwise operation speed advantage
Relevant Areas
Decision Trees
-
Plies, anytime algorithm, iterative deepening
Evaluation Functions

One score for each board in the Decision Tree
– Calculated independently

NegaMax and recursive descent
– Gets a single score back to the root

Credit for each of your pieces on the board,
negative for your opponent’s pieces
– Weightings per type of piece

Emprise
Evaluation Functions (cont.)

OSTRICH program literature
– “Head in the sand”

Predictability
– Theoretical weakness
– Behavior is affected by how much of the tree is
evaluated, etc.
Constraints

Runs on my personal desktop

Moves in less than one minute

Uses only free development tools
and information

Using C
(trees, bit-wise ops…)
Demonstration
Ideas for Further Work


Evolutionary reasoning for settings
GUI, WinBoard/XBoard compatibility, or
web interface

Beginning and/or endgame databases

Make the program “learn”
Validation


Works within project constraints and
meets high priority goals
Continual progress toward stronger AI
– Playing the engine against other engines
Conclusion



Only valid moves
Engine that balances power with
constraints
Elements of Intelligent Behavior
-
Can’t build the entire decision tree
-
Seek the best “visible” board
-
Tries to predict the human player’s moves
Questions?