The Study And Practice Of Computer Five-Piece Game-playing System

Computer game-playing is an important branch of Artificial Intelligence (AI) which isone of the active research area in recent years. Research results of it contribute to AI notonly in methods but in theories as well as remarkable influence to social and science. Theresearch of Game-Playing is pretty popular, especially in the chess program of IBM "DeepBlue" which has achieved the level of world champion. " Deep Blue", based on themanhunt technique named shearing biggest and smallest tree, provide a well frame ofreference to design other computer chess game-playing systems. But differ in thousandsways of the rule in different chess game bring on the specialty of each chess game-playing.Thus deeply research of chess game in its principle and its inherence law are needed todesign a concrete chess game-playing system.This thesis studies the computer Five-Piece game-playing systems. According to theartificial intelligence and general theory of computer game-playing, a basic models of theFive-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 andhow to store the board position in computer as well as distinguish the sequence in playingand the change \character of situation were discussed.Secondly, the Minimax Searching technology of Game Tree was investigated. Thefurther research of Alpha-Beta Procedure and optimization problem of which based on itwere being done. The candidate sequence nodes were sorted according to there location inorder to optimize the shearing process. Further more, NegeScout algorithm, the improvingalgorithm of Alpha-Beta, was also being studied. At the first, the algorithm adopts alimited Alpha-Beta window to make sure the score of actual evaluation value. Then itsearches an actual evaluation value in the smaller score. Because searching in the smallerscore, efficiency can be improved.Thirdly, according to the character of Five-Piece, some characters of the situationwere being extracted and being endowed with coefficient. By studying the globalattributes of whole board position, the total evaluation value was gotten through a linearfunction. In practice, the first version program with Minimax search and static evaluationfunction achieved a better–than-average level, even some skilled amateur often loss.On the foundation of the above mentioned work, the creative research mainly includesfollowing 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 analyzedcarefully for the simpleness rule, the clarity situation estimation of the Five-Piecegame-playing. A law which is not balance in superiority\inferiority position between twoparts, playing an important effect as a guidance in designing the Five-Piece game-playingsystem, is clarified.Secondly, aiming at overcoming the weakness and shortage in the first versionprocedure, the algorithm was enhanced and optimized. The first version procedure loseours satisfaction for its slow searching speed and bad game exhibition. Two main reasonscontribute to the situation. One is the application of routine Alpha-Beta search andNegaScout 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 lowerintelligence for its unnicety and can not to improve the game power during the gameprocession.There still two methods to solving the problem. One is searching the displacementform to avoid repeating search to the same position nodes before routine Alpha-Betasearch and NegaScout algorithm were performed. The other is applying threaten spacesearch 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 threatensequence to current position, the static function is tranfered. Because the black part has amighty dominance in the game, the threaten sequence can be often found using threatenspace search. The results indicate that the search can increase the program exhibition andgame level greatly.The Five-Piece program carried out by this thesis achieves the initial goal of thedesigner via the optimization and enhance of the algorithm. That is, in general, when thecomputer hold black part in advance, the black part will win the game. The fact provedthat in Five-Piece program design, using threaten space search can solve the man-machinegame of Five-Piece successfully .