Research And Implementation Of Computer Chess-Playing System

Computer Game-Playing is an important branch of artificial intelligence research. Many methods and theories originate from it. It also brings remarkable social and scientific influence. Chess has been regarded as the Drosophila Melanogaster of artificial intelligence, in the sense that the game has spawned a great deal of successful research, including a match victory against the current world champion and arguably the best player of all time, Gary Kasparov, much like many of the discoveries in genetics over the years have been made by scientists studying the tiny fruit fly.In this dissertation, we make basis study on some key technique about Computer Game-playing. Based on that, we design and develop an integrated Computer Chess-playing system. The whole work mainly focuses on the following three aspects:1. Introduce the basic component parts of a computer game-playing system This paper first studies how to represent a chess board in computer, thendiscusses how to generate legal moves. Secondly, this paper studies the minimax searching procedure of Game Tree, and the Alpha-Beta pruning algorithm. After that, according to the character of chess, this paper discusses how to define an evaluation function which is used to compare different positions.2. Make a particular study on the search algorithm and evaluation functionIn this paper, we find out the problem during the Alpha-Beta pruning procedure, and advance that ordering the moves before search is a good way to optimize Alpha-beta pruning algorithm. Then we discuss the implementation of transposition table mechanism, which can eliminate duplicate work during a search, and present some solution to the problem occurred in application. We also do researches on Principal Variation Search which uses a zero-width window to test each successive move against the first move. Only if the zero-width search fails does it do a normal search. PrincipalVariation Search is a means of getting a performance improvement out of the Alpha-Beta algorithm. What's more, we introduce an idea called Iterative Deepening. It provides a simple means of interrupting the search when running out of time, and it makes search more efficient. On the other hand, in the optimization of evaluation function, we advanced that combining piece-square tables with some amount of end-point evaluation is a good way to improve the speed and accuracy of evaluation function. 3. Develop an integrated Computer Chess-playing system EZChessBased on the above work, we design and develop an integrated Computer Chess-playing system EZChess, which is built on the MFC SDI document view architecture by using Visual C++. The implementation of this system adopts improved algorithms of search and evaluation function, and the development is based on the OPP programming idea.