Approach to nondeterministic games programming (Part II: Special heuristics and examples)

Background. Creation of intellectual computer games is one of the main directions of artificial intelligence. Besides, computer games provide a wide range of various means used in education. The classical method for programming nondeterministic games for 2 users with full information is a minimax algorithm. In programming of nondeterministic games it is impossible to apply standard methods developed for deterministic games. The article is aimed at developing algorithms for nondeterministic games based on processing of a modified search tree of a game. Materials and methods. The authors developed heuristics to order the top points in a nondeterministic search tree, that reduce the time of tree nodes processing and, consequently, allow to obtain an estimate of the investigated game position with greater probability, close to optimal. The authors also considered a possibility of simultaneous application of the nondeterministic search tree and the neural networks. The article adduces the performance examples of the suggested algorithms for constructing concrete estimates of top points (game positions) of various levels in the nondeterministic search tree. For practical application of the onsidered heuristics in game programs it is necessary to use the position estimator. The article describes the methods of formation and self-learning thereof. In algorithm performance examples the estimates' values are chosen in such a way that the examples, regardless of their small size, would be interesting. Results. The algorithms, developed by the authors, are realized in computer game programs; they also find application not just in nondeterministic games, but in other problems of discrete optimization as well. Conclusions. Application of the heuristics, developed by the authors, allows to increase effectiveness of the algorithms for nondeterministic games programming - reduce the running time and capacity of used memory, improve game quality.