An Adversarial Search Method Based on an Iterative Optimal Strategy

Chanjuan Liu, Junming Yan, Yuanye Ma, Tianhao Zhao, Qiang Zhang and Xiaopeng Wei
Additional contact information
Chanjuan Liu: School of Computer Science and Technology, Dalian University of Technology; Dalian 116024, China
Junming Yan: CNGC North Automatic Control Technology Institute, Taiyuan 030000, China
Yuanye Ma: School of Computer Science and Technology, Dalian University of Technology; Dalian 116024, China
Tianhao Zhao: School of Computer Science and Technology, Dalian University of Technology; Dalian 116024, China
Qiang Zhang: School of Computer Science and Technology, Dalian University of Technology; Dalian 116024, China
Xiaopeng Wei: School of Computer Science and Technology, Dalian University of Technology; Dalian 116024, China

Mathematics, 2020, vol. 8, issue 9, 1-16

Abstract: A deeper game-tree search can yield a higher decision quality in a heuristic minimax algorithm. However, exceptions can occur as a result of pathological nodes, which are considered to exist in all game trees and can cause a deeper game-tree search, resulting in worse play. To reduce the impact of pathological nodes on the search quality, we propose an iterative optimal minimax (IOM) algorithm by optimizing the backup rule of the classic minimax algorithm. The main idea is that calculating the state values of the intermediate nodes involves not only the static evaluation function involved but also a search into the future, where the latter is given a higher weight. We experimentally demonstrated that the proposed IOM algorithm improved game-playing performance compared to the existing algorithms.

Keywords: minimax; zero-sum games; game tree pathology (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/9/1623/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/9/1623/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:9:p:1623-:d:416078

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().