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.
|