Application And Research Based On Searching Algorithm Of AI In Five-Piece Game-Playing

This thesis studies the computer Five-Piece game-playing systems. According to the artificial intelligence and general theory of computer game-playing, a basic models of the Five-Piece game-playing systems is designed. Three aspects were done in the work:Firstly, the question of how to express the Five-Piece in computer was studied and how to store the board position in computer as well as distinguish the sequence in playing and the change \character of situation were discussed. Secondly, the Minimax Searching technology of Game Tree was investigated. The further research of Alpha-Beta Procedure and optimization problem of which based on it were being done. The candidate sequence nodes were sorted according to there location in order to optimize the shearing process.Thirdly, according to the character of Five-Piece, some characters of the situation were being extracted and being endowed with coefficient. By studying the global attributes of whole board position, the total evaluation value was gotten through a linear function.On the foundation of the above mentioned work, the creative research mainly includes following two aspectses:At first ,the professional knowledge of Five-Piece game-playing is sorted carefully. The familiar game beginning, fixed position and the following game play were analyzed carefully for the simpleness rule, the clarity situation estimation of the Five-Piece game-playing. A law which is not balance in superiority\inferiority position between two parts, playing an important effect as a guidance in designing the Five-Piece game-playing system, is clarified.Secondly, aiming at overcoming the weakness and shortage in the first version procedure, the algorithm was enhanced and optimized. The first version procedure lose ours satisfaction for its slow searching speed and bad game exhibition. Two main reasons contribute to the situation. One is the application of routine Alpha- Beta search and NegaScout algorithm which can not avoid repeating search to the same position nodes. The other one is the adoption of fixed estimate method, which will lead to the lower intelligence for its unnicety and can not to improve the game power during the game procession.There still two methods to solving the problem. One is searching the displacement form to avoid repeating search to the same position nodes before routine Alpha- Beta search and NegaScout algorithm were performed. The other is applying threaten space search which can let the computer to find out all the threaten sequence to win the game. This can be aviod tranfer the static function. Only can not the computer find the threaten sequence to current position, the static function is tranfered. Because the black part has a mighty dominance in the game, the threaten sequence can be often found using threaten space search. The results indicate that the search can increase the program exhibition and game level greatly.