A Middle Game Search Algorithm Applicable to Low-Cost Personal Computer for Go

Xiali Li, Zhengyu Lv, Song Wang, Zhi Wei, Xiaochuan Zhang, Licheng Wu

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Go Artificial Intellects(AIs) using deep reinforcement learning and neural networks have achieved superhuman performance, but they rely on powerful computing resources. They are not applicable to low-cost personal computer(PC). In our life, most entertainment programs of Go run on the general PC. A human Go master consider different strategies for different stages, especially for the middle stage that has a significant impact on winning or losing. To study arguably a more humanlike approach that is applicable to low-cost PC while not reducing chess power, this paper proposes a new search algorithm based on hypothesis testing and dynamic randomization for the middle stage of the game Go. Firstly, a new method to decide the intervals of different playing stages more reasonable based on hypothesis testing is proposed. Secondly, a new search algorithm including a layered pruning branch method, a comprehensive evaluation function and a new selecting node method is proposed. The pruning method based on domain knowledge and upper confidence bound formula(UCB) are all applied to subtract the branches from the lower evaluation score, which was ranked behind 20%. The comprehensive evaluation function with adjustable parameters is proposed to evaluate the tree nodes after pruning. The new selecting node method based on dynamic randomization is used to expand the tree by selecting a node randomly from the high-quality node interval. Finally, the experimental results show that the designed algorithm outperforms Gnugo3.6 and Gnugo3.8 in chess power while reducing average search time and average RAM cost for one move effectively on a 19×19 board.

Original languageEnglish (US)
Article number8817933
Pages (from-to)121719-121727
Number of pages9
JournalIEEE Access
Volume7
DOIs
StatePublished - 2019

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Materials Science(all)
  • Engineering(all)

Keywords

  • dynamic randomization
  • Go
  • hypothesis test
  • MCTS
  • search algorithm
  • UCT

Fingerprint Dive into the research topics of 'A Middle Game Search Algorithm Applicable to Low-Cost Personal Computer for Go'. Together they form a unique fingerprint.

Cite this