Approach to programming of nondeterministic games (Part I: Description of general heuristics)

Background. The article considers several approaches used in programming intelligent nondeterministic games - the approaches that have not been described in authors' previous publications. The methods of algorithmization, developed and realized by the authors, deal with the search tree, modified specially for the nondeterministic games, and represent an addition (sometimes an alternative) to the neural network methods. It is important to note that the developed algorithms may be applied not only directly in the nondeterministic games, but in other problems of discrete optimization. Materials and methods. After realization of the algorithms of statistical evaluation of the position (carried out either by standard approaches to intelligent games programming, or by neural network methods) the final (dynamic) evaluation of the position is calculated by all deterministic values obtained for all possible realizations of a random event. These values are averaged by a special method, and the results of the said averaging are considered as a dynamic value. From the physical point of view the applied averaging gives the center of gravity position of one-dimensional system of bodies, the mass of which is set by a special function - the so-called risk function. The coordinates of bodies correspond to the deterministic values depending, similarly to the regular method of minimax, only on the deterministic factors of the game. To determine the sequence of nondeterministic searching tree tops' processing the authors build special heuristic functions (preference functions), on the basis of which the researchers apply sorting in each of two sets of tops. The said preference functions depend on the following parameters: depth of the current top of the game tree; previous evaluation of the position; value of the reached depth of searching. Simultaneously with the building of the evaluation function with the help of the expert the authors considered several problems relating to the algorithms of automated building of such functions. The three-layer neural network with reverse error distribution was used as the approximation of the static evaluation of the position. Results. The results of the study are not just the developed programs for intelligent nondeterministic games, but also the application description of the considered “game” approaches in various problems of discrete optimization. Conclusions. Practical results of the programs, created on the basis of the considered algorithms, show the advantages of the authors' approach to the sequence of nondeterministic searching tree tops' processing in comparrison with the approaches similar to the exhaustive search.