A dual-tree Monte Carlo search algorithm for sequential synchronous games

Abstract

The invention discloses a dual-tree Monte Carlo search algorithm for solving a large-scale sequential synchronous game problem. Compared with a sequential synchronous Monte Carlo search based on single tree structure, the invention has the advantages that two trees are established to represent the state transition of both sides of the game, which greatly reduces the selection branches of the gametree and reduces the size of the game tree while maintaining the characteristics of synchronous operation, the explosion problem caused by synchronous action is eliminated and the searching depth is increased, the quality of the solution is ensured, and also the efficiency of the solution is improved. Specific technical means include: through the construction of a Nash equilibrium support library,the problem that synchronous Nash equilibrium online calculation time is too long is solved; a deep strategy net and a deep valuation net of a sequential synchronous game are designed, realizing knowledge guidance of sequential synchronous search; research on environment-oriented reinforcement learning solves the decision-making problem under the condition of state transition or lack of benefits.

Description

technical field [0001] The invention relates to the field of machine game search, in particular to a Monte Carlo search algorithm using a double tree structure. Background technique [0002] The Monte Carlo method, also known as the statistical simulation method, is a kind of very important numerical calculation guided by the theory of probability and statistics, which was proposed in the mid-1940s due to the development of science and technology and the invention of electronic computers. method. Refers to the use of random numbers (or more commonly pseudorandom numbers) to solve many computational problems. In the 1970s, the theoretical research on the Monte Carlo method reached its peak. So far, for the research of Monte Carlo theory and method, the theoretical and practical research in the United States is still in a leading position. Many other countries are now involved in Monte Carlo studies. Monte Carlo research has strongly promoted the application and developmen...

AI Technical Summary

Problems solved by technology

[0003] For sequential simultaneous game problems, the existing search methods can only deal with low-complexity game problems. This is because the number of nodes in the game tree is within an acceptable range, so it can effectively solve

However, in the case of a large scale, if the game tree search method is directly used to solve the problem, due to the huge number of action combinations and the exponential increase of the nodes in the tree with the increase of depth, it will inevitably lead to the problem of combination explosion.

Therefore, the existing search methods usually reduce it to a sequential asynchronous problem first, and then use the max-min search algorithm to solve it, but the quality of the solution is degraded due to the serious simplification of the problem

Images