Research Of Key Technologies Of Connection-Pattern Based Computer Connect6

Computer Game is one of the most important issues in the domain of artificial intelligence. It is also considered as the fruit fly and the good test-bed for new theory or method to solve a complex problem of artificial intelligence. The main research content of computer games is closely related to both artificial intelligence and the human intelligence. By the 1960s, a checker program written by Semual defeated the best human player, which has been received a precedence sensation.In 2005, Prof. Wu firstly proposed a new game named Connect6. It is a difficult game to play well than Go-Moku or Renju. Since those two games have been solved successfully, Connect6 becomes a new challenging k-in-a-row game. Based on the earlier research, it should be pointed out that either Go-Moku or Renju overestimates its difficulty, according to which we can say that there must be a great of pitfalls in the research.Taking Connect6 as study issue, and counting the level of existing research, this paper proposed a new method——CPBIM(Connection-Pattern Based Incremental Model). It is expected that this model can help correcting the mistaken ideas in the existing research of Computer Connect6, and improve the level of Computer k-in-a-row games. Based on CPBIM, this paper studied the relevant key technology in detail, such as the representation of data or knowledge, search algorithm, evaluation, move generation and sorting.The main contributions of this dissertation include:(1) Based on incremental model, a new model——Connection-Pattern, which is also suitable for a family of computer k-in-a-row games, is proposed. Firstly, a new pattern——Connection which differs from the traditional model is proposed and it can improve the data representation and the position evaluation. Then, we build a strict and complete Connection classification system to have each Connection with more domain knowledge. After that, to solve the problem of overestimation of the complexity of k-in-a-row, we proposes a system of intersection classification, thus we make the program having the ability to filter unused intersection from all the candidate moves, which is also the key support to sort all moves effectively. At last, considering the representation to a connection with a non-negative integer, a Connection knowledge database is proposed to strengthen the effectiveness of the program and to utilize high level knowledge.(2) By incorporating the idea of Iterative Deepening into Threat Space Search, the DFID-TSS (Depth First Iterative Deepening Threat Space Search) is proposed. The new algorithm will always find out the shortest routine, and the average execution time reduced greatly when keeping the solving ability.(3) In order to use the domain knowledge furnished by CPBIM, based on PN search algorithm, a PN# algorithm is proposed. In addition to favor a thin and slim tree, PN# still prefer to search a good node earlier and deeper than other nodes in the same layer. PN# enhances the search algorithm and reduces the requirement for memory, furthermore, its realization is as the same simple as PN.(4) The combination between Neural Network with TD(λ) algorithm is introduced into the design of evaluation function, and a self-learning algorithm of evaluation function by the prior knowledge is proposed. This method can avoid converging too slow and it is easy to implement. Furthermore, to minimize the side effect caused by useless learning samples, a method using a selective sequence to substitute the whole record is proposed.(5) Aiming at the characteristics of many candidate moves and expensive cost of sorting, a new way of move classification and gradual sorting method is proposed. For the sorting problem of the same type moves, a new sorting mechanism is proposed, i.e., without prejudice to differentiation degrees, the scope of evaluation values is narrowed, so that a fast bucket sort can be used to substitute a normal selective sort algorithm.(6) In the respects of opening book, time controlling, etc., after the balances of performance and cost are considered adequately, some optimal methods are also proposed.The methods and algorithm proposed by this paper are tested in computer Connect6 program NEUConn6 adequately. In a series of native and international competitions, NEUConn6 obtained good places, which also proved that the model and relevant algorithms proposed by this paper are efficient and practicable.