Searching Optimization Of Connection-Pattern Based Computer Game

Computer Game is considered as fruit fly of Artificial Intelligence, and also recognized as one of the challenging research topic in the field at the same time. The famous scholars of Artificial Intelligence think of that if we can grasp the essence of the game, it also means that we master the core of human intelligence activities at the same time. Because the principles exist in chess game may exist in human intelligence activities. In recent years, Computer Game of domestic and foreign greatly promoted the research of Computer Game and the development of theory and technology of Computer Game. Computer Game involves chesses including Gobang, Connect six, go, chess and so on. A variety of algorithms has been used in the Computer Game.The traditional model of Computer Game designs the data structure based on intersection on the board as the basic units, the situation description is also depended on the of the intersection, the situation of the k-in-a-row can establish one-to-one relationship with a number of Connection-Pattern, the situation of state called Connection-Pattern can be described using a kind of abstract knowledge of pattern library. The abstract knowledge of Connection-Pattern describes the overall effect formed by each piece of Connection-Pattern. The evolution exists between patterns, the efficient Game should promote evolution of patterns on reasonable.In order to improve the searching speed, the searching algorithms of k-in-a-row are designed which are based on the alpha-beta pruning searching. The bigger the depth of Game tree searching, the greater the best method obtained, but with the time constraints of Computer Came, the depth of searching cannot be infinite, only in a limited range, searching technology should be further optimized.With the research object of k-in-a-row, this paper studies the technology of Computer Game, including some basic concepts and searching algorithms; designs Connection-Pattern taking Gobang and Connect6as an example, including relevant chess-shaped, data structure and designing value function; chess-shaped definition, analysis, and design based on chess-shaped scan searching algorithm; this paper analyzes the calculation rules and valuation analysis of the scanning method based on "road". It develops the global scanning method of the game-tree searching algorithm into local scanning method and introduces the calculation rules and valuation analysis. The game-tree searching algorithm based on local scanning method is designed and integrated into the alpha-beta pruning searching in this paper.The experiments with the search efficiency and game level results are that relative to the scanning based on no-chess-shaped, the scanning based on chess-shaped has no significant improvement in search efficiency, but increases significantly in game level; relative to the global scanning, local scanning greatly improves the efficiency of searching and increases significantly the game level. This article only adopts local scan method in opening and mid-game stage, and improves the efficiency of search, how to improve the efficiency and valuations in the needs further research.The innovations are as follows:(1) It improves global scanning method to local scanning method at game tree generation, ignores the useness roads, reduces the numbers of roads and improve the search efficiency; Through the comparison of quantitative analysis between the global scanning and local scanning, it determine local scanning can completely replace global scaning with game tree generation without reducing the accuracy.(2) It designs the game tree generation based on local scanning, and put into alpha-beta pruning search. Comparison of game tree generation based on global scanning, it can significantly improve the game level.(3) It propose a new calculation method of simulation method based on Connect-Pattern, it considers "two steps" as "one step" and calculate the weights of combination points by rules and chess features and applied in k-in-a-row with improve the search precision.The algorithm has been successfully applied to connect-6game software of Dragonworld and obtained good places at computer game competition in the domestic, it proved the work have efficient and practicable and its design methods can be widely used in other Computer Game.