A Case-Based Reasoning Approach to A Chess AI Using Shallow Similarity
Abstract
Chess is a game that is often used to examine different techniques in AI. In this thesis, the following question is asked: "Is it possible to develop an AI-agent whose decision making is based on the technique Case-based Reasoning (CBR) that uses shallow similarity, and plays better using case bases based on the better players?". An AI-agent has been developed that has played a number of games against itself using different case bases based on different players. After examining the results, it turned out that the AI-agent plays so bad that it almost never manages to win regardless of case base, which meant that it was not possible to grade them based on skill. It's could still be useful to examine if a CBR-based chess playing AI-agent could play chess with great skill.
The whole thesis report is available for download.
Programming Experience
This project was very interesting to work with because it gave me a chance to program in a more functional style than I've previously been used to. Immutable Classes were written, and their public interfaces were severely restricted to the bare minimum, which made it harder to write bug ridden code. Almost everything chess related was unit tested, and I never even ran the program before all the tests passed.
While this may have been working great in the beginning, I was soon faced with a performance problem, mostly related to unnecessary and expensive allocations of lists and boards. In order to fix the problem, I changed the representation and implementation of some classes without changing their public interfaces. This allowed me to test any changes I made, to make sure that I didn't introduce a bug.
So, in the end I introduced mutability in order to solve the problem. However, that doesn't mean that it was a waste of time to program functionally at the start.
- The immutability caused the class interfaces to shrink, which sped up the initial testing process.
- Even if the initial implementation and representations where replaced, they were quick to develop, and led to clearer code.
- Due to the non-existence of mutable state-sharing, it was easy to scale the program to simulate multiple chess games in parallel using PLINQ.
This experience has lead me to develop in a more functional style, and writing more unit tests. Unfortunately, sometimes the pros aren't worth it on short projects with rapidly changing requirements. It's important to be pragmatic, and use the right tool for the right job.