Adversarial search method based on backup strategy

A search method and backup strategy technology, applied in the field of adversarial search, to achieve the effects of reducing algorithm complexity, avoiding the risk of evaluation errors, and high decision-making quality

Active Publication Date: 2020-05-19
DALIAN UNIV OF TECH
View PDF4 Cites 1 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0005] In order to solve the local pathological problem existing in the game tree, and avoid the defects of the error minimization algorithm in solving this problem, the present invention proposes a method of assigning different source state values ​​in the process of backtracking and updating backup values Game tree search method with different weights

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Adversarial search method based on backup strategy
  • Adversarial search method based on backup strategy
  • Adversarial search method based on backup strategy

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0028] The present invention will be further described below in conjunction with the accompanying drawings and embodiments.

[0029] Such as figure 1 As shown, the present embodiment provides an adversarial search method based on a backup strategy, comprising the following steps:

[0030] Step S1: Input the parameters situation state s, the player who will act in the current situation state, and the maximum search depth d; initialize the backup value b_val of the current situation state s to +∞; use the static evaluation function to calculate the value of the current situation state s Evaluate the value e_val and record it; judge whether the current search node is a leaf node of the game tree (that is, the depth of the current search node in the game tree reaches the maximum search depth or the corresponding situation state of the node is the end state of the game); if so, the evaluation value of the node e_val is returned as its final backup value b_val; otherwise, go to ste...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention discloses an adversarial search method based on a backup strategy, and belongs to the field of zero-sum game strategy search. An iterative optimal maximum and minimum (IOM) algorithm isprovided by optimizing a backup rule of a classic maximum and minimum algorithm. The method comprises the following steps: firstly, calculating an evaluation value of any given node by utilizing a static evaluation function; and then, updating the final value of each node in a back propagation manner according to a backup rule, i.e., the final backup value of each node is equal to twice of the maximum backup value in child nodes subtracted from the evaluation value of each node. The backup rule used when the final state value of the intermediate node is calculated provides a solution for reducing the influence of ill-conditioned nodes in a game tree on the decision quality. Compared with an error minimization and minimization algorithm and the classic maximum and minimum algorithm, the iterative optimal maximum and minimum algorithm provided by the invention improves the decision quality under the condition of limited search depth.

Description

technical field [0001] The invention belongs to the field of machine game strategy search, and more specifically relates to an adversarial search method for improving the backup method of the max-min algorithm. Background technique [0002] Search algorithm is an important field of machine game research. In the two-person zero-sum game problem, the algorithm based on the minimax theorem is one of the most advanced adversarial search algorithms. When the entire game tree can be searched, the optimal solution of the two-person zero-sum game problem with complete information can be obtained. However, since the state space in many game problems is very large, the game tree cannot be completely searched, so the max-min algorithm proposed by Shannon will choose to expand the game tree to a limited depth during the implementation process, and use the heuristic The function is used as a static evaluation function to evaluate the state value of the leaf node, and the value calculate...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Applications(China)
IPC IPC(8): G06F11/14
CPCG06F11/1448Y02D10/00
Inventor 刘婵娟闫俊名张强魏小鹏
Owner DALIAN UNIV OF TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap