Top

Published in:

2021 | OriginalPaper | Chapter

Stabilized Nested Rollout Policy Adaptation

Authors : Tristan Cazenave, Jean-Baptiste Sevestre, Matthieu Toulemont

Published in: Monte Carlo Search

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Nested Rollout Policy Adaptation (NRPA) is a Monte Carlo search algorithm for single player games. In this paper we propose to modify NRPA in order to improve the stability of the algorithm. Experiments show it improves the algorithm for different application domains: SameGame, Traveling Salesman with Time Windows and Expression Discovery.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter The Search Algorithm for the Game of Bridge

next chapter zoNNscan: A Boundary-Entropy Index for Zone Inspection of Neural Models

Bouzy, B.: Monte-Carlo fork search for cooperative path-finding. In: Computer Games - Workshop on Computer Games, CGW 2013, Held in Conjunction with the 23rd International Conference on Artificial Intelligence, IJCAI 2013, Beijing, China, 3 August 2013, Revised Selected Papers, pp. 1–15 (2013)

Bouzy, B.: Burnt pancake problem: new lower bounds on the diameter and new experimental optimality ratios. In: Proceedings of the Ninth Annual Symposium on Combinatorial Search, SOCS 2016, Tarrytown, NY, USA, 6–8 July 2016, pp. 119–120 (2016)

Browne, C., et al.: A survey of Monte Carlo tree search methods. IEEE Trans. Comput. Intell. AI Games 4(1), 1–43 (2012). https://doi.org/10.1109/TCIAIG.2012.2186810CrossRef

Cazenave, T.: Nested Monte-Carlo search. In: Boutilier, C. (ed.) IJCAI, pp. 456–461 (2009)

Cazenave, T.: Nested Monte-carlo expression discovery. In: ECAI 2010–19th European Conference on Artificial Intelligence, Lisbon, Portugal, 16–20 August 2010, Proceedings, pp. 1057–1058 (2010). https://doi.org/10.3233/978-1-60750-606-5-1057

Cazenave, T.: Monte-carlo expression discovery. Int. J. Artif. Intell. Tools 22(1) (2013). https://doi.org/10.1142/S0218213012500352

Cazenave, T.: Nested rollout policy adaptation with selective policies. In: CGW at IJCAI 2016 (2016)

Cazenave, T., Hamida, S.B.: Forecasting financial volatility using nested Monte Carlo expression discovery. In: IEEE Symposium Series on Computational Intelligence, SSCI 2015, Cape Town, South Africa, 7–10 December 2015, pp. 726–733 (2015). https://doi.org/10.1109/SSCI.2015.110

Cazenave, T., Jouandeau, N.: Parallel nested monte-carlo search. In: 23rd IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2009, Rome, Italy, 23–29 May 2009, pp. 1–6 (2009). https://doi.org/10.1109/IPDPS.2009.5161122

10.

Cazenave, T., Saffidine, A., Schofield, M.J., Thielscher, M.: Nested Monte Carlo search for two-player games. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 12–17 February 2016, Phoenix, Arizona, USA, pp. 687–693 (2016). http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12134

11.

Cazenave, T., Teytaud, F.: Application of the nested rollout policy adaptation algorithm to the traveling salesman problem with time windows. In: Hamadi, Y., Schoenauer, M. (eds.) LION 2012. LNCS, pp. 42–54. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34413-8_4CrossRef

12.

Edelkamp, S., Gath, M., Cazenave, T., Teytaud, F.: Algorithm and knowledge engineering for the TSPTW problem. In: 2013 IEEE Symposium on Computational Intelligence in Scheduling (SCIS), pp. 44–51. IEEE (2013)

13.

Edelkamp, S., Gath, M., Greulich, C., Humann, M., Herzog, O., Lawo, M.: Monte-Carlo tree search for logistics. In: Clausen, U., Friedrich, H., Thaller, C., Geiger, C. (eds.) Commercial Transport. LNL, pp. 427–440. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-21266-1_28CrossRef

14.

Edelkamp, S., Gath, M., Rohde, M.: Monte-Carlo tree search for 3D packing with object orientation. In: Lutz, C., Thielscher, M. (eds.) KI 2014. LNCS (LNAI), vol. 8736, pp. 285–296. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11206-0_28CrossRef

15.

Edelkamp, S., Greulich, C.: Solving physical traveling salesman problems with policy adaptation. In: 2014 IEEE Conference on Computational Intelligence and Games (CIG), pp. 1–8. IEEE (2014)

16.

Edelkamp, S., Tang, Z.: Monte-Carlo tree search for the multiple sequence alignment problem. In: Eighth Annual Symposium on Combinatorial Search (2015)

17.

Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: Fürnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol. 4212, pp. 282–293. Springer, Heidelberg (2006). https://doi.org/10.1007/11871842_29CrossRef

18.

Koza, J.R., et al.: Genetic programming II, vol. 17. MIT Press, Cambridge (1994)

19.

Langdon, W.B., Poli, R., et al.: An analysis of the max problem in genetic programming. Genet. Program. 1(997), 222–230 (1997)

20.

Méhat, J., Cazenave, T.: Combining UCT and nested Monte Carlo search for single-player general game playing. IEEE Trans. Comput. Intell. AI Games 2(4), 271–277 (2010)CrossRef

21.

Nagorko, A.: Parallel nested rollout policy adaptation. In: IEEE Conference on Games (2019)

22.

Négrevergne, B., Cazenave, T.: Distributed nested rollout policy for samegame. In: Computer Games - 6th Workshop, CGW 2017, Held in Conjunction with the 26th International Conference on Artificial Intelligence, IJCAI 2017, Melbourne, VIC, Australia, 20 August 2017, Revised Selected Papers, pp. 108–120 (2017). https://doi.org/10.1007/978-3-319-75931-9_8

23.

Portela, F.: An unexpectedly effective Monte Carlo technique for the RNA inverse folding problem. bioRxiv, p. 345587 (2018)

24.

Potvin, J.Y., Bengio, S.: The vehicle routing problem with time windows part II: genetic search. INFORMS J. Comput. 8(2), 165–172 (1996)CrossRef

25.

Poulding, S.M., Feldt, R.: Generating structured test data with specific properties using nested Monte-Carlo search. In: Genetic and Evolutionary Computation Conference, GECCO 2014, Vancouver, BC, Canada, 12–16 July 2014, pp. 1279–1286 (2014)

26.

Poulding, S.M., Feldt, R.: Heuristic model checking using a Monte-Carlo tree search algorithm. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, 11–15 July 2015, pp. 1359–1366 (2015)

27.

Rimmel, A., Teytaud, F., Cazenave, T.: Optimization of the nested Monte-Carlo algorithm on the traveling salesman problem with time windows. In: Di Chio, C., et al. (eds.) EvoApplications 2011, Part II. LNCS, vol. 6625, pp. 501–510. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20520-0_51CrossRef

28.

Rosin, C.D.: Nested rollout policy adaptation for Monte Carlo tree search. In: IJCAI, pp. 649–654 (2011)

Title: Stabilized Nested Rollout Policy Adaptation
Authors: Tristan Cazenave
Jean-Baptiste Sevestre
Matthieu Toulemont
Publisher: Springer International Publishing
Book: Monte Carlo Search
Print ISBN: 978-3-030-89452-8

Electronic ISBN: 978-3-030-89453-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-89453-5_2

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner