CS297 Proposal

Improving Chess Program Encoding Schemes

Supriya Basani (sbasani@yahoo.com)

Advisor: Dr. Chris Pollett

Description:

Computer chess is a classic AI problem. In psychology chess has also been used to study human thinking. Many successful chess programs can beat chess experts, yet their style of play is incomparable to chess grandmasters. Unlike the computer logic that examines every possible position for a fixed number of moves, the grandmasters get their right moves from constructing the whole board based upon few pieces of information on the board and from recollections of salient aspects of past games. In this project my goal is to try to modify an existing computer chess program, GNU chess, so that it plays more like a human player. To do this I am going to experiment with modifying how GNU chess keeps encodings of chess games so that it is more human-like. I will also modify the boards considered in GNU chess' minimax algorithm to only those boards close to boards seen in some historical chess game. The measure of closeness will be based on my notion of human-like encoding.

Schedule:

Week 1: 08/29/2006	Read article "The Expert Mind" and submit the Project Proposal
Week 2: 09/05/2006	Research on clustering algorithm to cluster board positions and GNU chess program.
Week 3: 09/12/2006	Read article "Recent advances in computer chess" and do a presentation on Clustering algorithm and the article.
Week 4: 09/19/2006	Come up with a distance algorithm to form clusters of board positions.
Week 5: 09/26/2006	Download GNU chess program and make a non-trivial modification to its minimax algorithm.
Week 6: 10/03/2006	Demo the modified GNU chess program.
Week 7: 10/10/2006	Download chess game databases and convert to a format usable by GNU chess program. Read the article "Learning long-term chess strategies from databases."
Week 8: 10/17/2006	Read the article "Chess playing machines from natural towards artificial intelligence?" and demo the integrated databases.
Week 9: 10/24/2006	Implement a clustering algorithm on board positions.
Week 10: 10/31/2006	Demo the clustering algorithm.
Week 11: 11/07/2006	Read the article "Mechanisms for comparing chess programs" and research on different encoding schemes.
Week 12: 11/14/2006	Experiment with Hidden Markov Model.
Week 13: 11/21/2006	Demo the new encoding scheme.
Week 14: 11/28/2006	Work on the report
Week 15: 12/05/2006	Presentation on the project report.
Week 16: 12/12/2006	Submit final report.

Deliverables:

The full project will be done when CS298 is completed. The following will be done by the end of CS297:

1. Install GNU chess program and make a non-trivial modification to its minimax algorithm.

2. Download chess game databases for example from chessgames.com and convert to a format usable by GNU chess program.

3. Implement a clustering algorithm on board positions that have appeared in a historical chess game database.

4. Experiment with Hidden Markov Model to come up with more human-like choices of next board positions based upon human-like cluster of similar board positions.

5. Final Report.

References:

[1973] Mechanisms for comparing chess programs. T. A. Marsland. P. G. Rushton. ACM Press. 1973.

[1996] Recent advances in computer chess. M. Newborn. T. Marsland. ACM Press. 1996.

[2004] Chess playing machines from natural towards artificial intelligence?. F. Paul. Technical University of Wroclaw. 2004.

[2006] The Expert Mind. P. Ross. Scientific American. 2006.

[2006] Learning long-term chess strategies from databases. Sadikov. Aleksander. Bratko. Ivan. Kluwer Academic Publishers. 2006.

http://www.chessgames.com/ Online historical chess games databases.

http://www.gnu.org/software/chess/ GNU chess program web site.