IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v22y2016i6d10.1007_s10732-016-9320-y.html
   My bibliography  Save this article

Can Monte-Carlo Tree Search learn to sacrifice?

Author

Listed:
  • Nathan Companez

    (Monash University)

  • Aldeida Aleti

    (Monash University)

Abstract

One of the most basic activities performed by an intelligent agent is deciding what to do next. The decision is usually about selecting the move with the highest expectation, or exploring new scenarios. Monte-Carlo Tree Search (MCTS), which was developed as a game playing agent, deals with this exploration–exploitation ‘dilemma’ using a multi-armed bandits strategy. The success of MCTS in a wide range of problems, such as combinatorial optimisation, reinforcement learning, and games, is due to its ability to rapidly evaluate problem states without requiring domain-specific knowledge. However, it has been acknowledged that the trade-off between exploration and exploitation is crucial for the performance of the algorithm, and affects the efficiency of the agent in learning deceptive states. One type of deception is states that give immediate rewards, but lead to a suboptimal solution in the long run. These states are known as trap states, and have been thoroughly investigated in previous research. In this work, we study the opposite of trap states, known as sacrifice states, which are deceptive moves that result in a local loss but are globally optimal, and investigate the efficiency of MCTS enhancements in identifying this type of moves.

Suggested Citation

  • Nathan Companez & Aldeida Aleti, 2016. "Can Monte-Carlo Tree Search learn to sacrifice?," Journal of Heuristics, Springer, vol. 22(6), pages 783-813, December.
  • Handle: RePEc:spr:joheur:v:22:y:2016:i:6:d:10.1007_s10732-016-9320-y
    DOI: 10.1007/s10732-016-9320-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-016-9320-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10732-016-9320-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. David Silver & Aja Huang & Chris J. Maddison & Arthur Guez & Laurent Sifre & George van den Driessche & Julian Schrittwieser & Ioannis Antonoglou & Veda Panneershelvam & Marc Lanctot & Sander Dieleman, 2016. "Mastering the game of Go with deep neural networks and tree search," Nature, Nature, vol. 529(7587), pages 484-489, January.
    2. Jean-Yves Potvin & Samy Bengio, 1996. "The Vehicle Routing Problem with Time Windows Part II: Genetic Search," INFORMS Journal on Computing, INFORMS, vol. 8(2), pages 165-172, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jozefowiez, Nicolas & Semet, Frédéric & Talbi, El-Ghazali, 2009. "An evolutionary algorithm for the vehicle routing problem with route balancing," European Journal of Operational Research, Elsevier, vol. 195(3), pages 761-769, June.
    2. Bo Hu & Jiaxi Li & Shuang Li & Jie Yang, 2019. "A Hybrid End-to-End Control Strategy Combining Dueling Deep Q-network and PID for Transient Boost Control of a Diesel Engine with Variable Geometry Turbocharger and Cooled EGR," Energies, MDPI, vol. 12(19), pages 1-15, September.
    3. Tian Zhu & Merry H. Ma, 2022. "Deriving the Optimal Strategy for the Two Dice Pig Game via Reinforcement Learning," Stats, MDPI, vol. 5(3), pages 1-14, August.
    4. Xiaoyue Li & John M. Mulvey, 2023. "Optimal Portfolio Execution in a Regime-switching Market with Non-linear Impact Costs: Combining Dynamic Program and Neural Network," Papers 2306.08809, arXiv.org.
    5. Pedro Afonso Fernandes, 2024. "Forecasting with Neuro-Dynamic Programming," Papers 2404.03737, arXiv.org.
    6. repec:cdl:itsdav:qt2fv5063b is not listed on IDEAS
    7. Guangyuan Li & Baobao Song & Harinder Singh & V. B. Surya Prasath & H. Leighton Grimes & Nathan Salomonis, 2023. "Decision level integration of unimodal and multimodal single cell data with scTriangulate," Nature Communications, Nature, vol. 14(1), pages 1-16, December.
    8. Tambet Matiisen & Aqeel Labash & Daniel Majoral & Jaan Aru & Raul Vicente, 2022. "Do Deep Reinforcement Learning Agents Model Intentions?," Stats, MDPI, vol. 6(1), pages 1-17, December.
    9. Yuchen Zhang & Wei Yang, 2022. "Breakthrough invention and problem complexity: Evidence from a quasi‐experiment," Strategic Management Journal, Wiley Blackwell, vol. 43(12), pages 2510-2544, December.
    10. Ann Melissa Campbell & Martin Savelsbergh, 2004. "Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems," Transportation Science, INFORMS, vol. 38(3), pages 369-378, August.
    11. Benjamin Heinbach & Peter Burggräf & Johannes Wagner, 2024. "gym-flp: A Python Package for Training Reinforcement Learning Algorithms on Facility Layout Problems," SN Operations Research Forum, Springer, vol. 5(1), pages 1-26, March.
    12. Roberto Baldacci & Aristide Mingozzi & Roberto Roberti, 2012. "New State-Space Relaxations for Solving the Traveling Salesman Problem with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 24(3), pages 356-371, August.
    13. Zhang, Yiwen & Ren, Yifan & Liu, Ziyun & Li, Haoqin & Jiang, Huaiguang & Xue, Ying & Ou, Junhui & Hu, Renzong & Zhang, Jun & Gao, David Wenzhong, 2025. "Federated deep reinforcement learning for varying-scale multi-energy microgrids energy management considering comprehensive security," Applied Energy, Elsevier, vol. 380(C).
    14. Elsisi, Mahmoud & Amer, Mohammed & Dababat, Alya’ & Su, Chun-Lien, 2023. "A comprehensive review of machine learning and IoT solutions for demand side energy management, conservation, and resilient operation," Energy, Elsevier, vol. 281(C).
    15. Yassine Chemingui & Adel Gastli & Omar Ellabban, 2020. "Reinforcement Learning-Based School Energy Management System," Energies, MDPI, vol. 13(23), pages 1-21, December.
    16. Biemann, Marco & Scheller, Fabian & Liu, Xiufeng & Huang, Lizhen, 2021. "Experimental evaluation of model-free reinforcement learning algorithms for continuous HVAC control," Applied Energy, Elsevier, vol. 298(C).
    17. Zhewei Zhang & Youngjin Yoo & Kalle Lyytinen & Aron Lindberg, 2021. "The Unknowability of Autonomous Tools and the Liminal Experience of Their Use," Information Systems Research, INFORMS, vol. 32(4), pages 1192-1213, December.
    18. Yuhong Wang & Lei Chen & Hong Zhou & Xu Zhou & Zongsheng Zheng & Qi Zeng & Li Jiang & Liang Lu, 2021. "Flexible Transmission Network Expansion Planning Based on DQN Algorithm," Energies, MDPI, vol. 14(7), pages 1-21, April.
    19. JinHyo Joseph Yun & EuiSeob Jeong & Xiaofei Zhao & Sung Deuk Hahm & KyungHun Kim, 2019. "Collective Intelligence: An Emerging World in Open Innovation," Sustainability, MDPI, vol. 11(16), pages 1-15, August.
    20. Zeqing Jin & Dahyun Daniel Lim & Xueying Zhao & Meenakshi Mamunuru & Sassan Roham & Grace X. Gu, 2024. "Machine learning enabled optimization of showerhead design for semiconductor deposition process," Journal of Intelligent Manufacturing, Springer, vol. 35(2), pages 925-935, February.
    21. repec:osf:osfxxx:tn5rx_v1 is not listed on IDEAS
    22. Jiacheng Zhang & Haolan Zhang, 2025. "Towards Human-like Artificial Intelligence: A Review of Anthropomorphic Computing in AI and Future Trends," Mathematics, MDPI, vol. 13(13), pages 1-49, June.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joheur:v:22:y:2016:i:6:d:10.1007_s10732-016-9320-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.