# Fileset

[MDTS_automatic_complex_materials_design_using_Monte_Carlo_tree_search.pdf](https://mdr.nims.go.jp/filesets/dfd8bfb8-7424-4857-99df-7dc022395af5/download)

## Creator

[Tsuda, Koji](https://orcid.org/0000-0002-4288-1606), Shiomi, Junichiro, Ju, Shenghong, [Hou, Zhufeng](https://orcid.org/0000-0002-0069-5573), [Dieb, Thaer M.](https://orcid.org/0000-0002-8111-2009), Yoshizoe, Kazuki

## Rights



## Other metadata

[MDTS: automatic complex materials design using Monte Carlo tree search](https://mdr.nims.go.jp/datasets/4b694172-54b7-4596-965e-78062d2e3bf1)

## Fulltext

MDTS: automatic complex materials design using Monte Carlo tree searchFull Terms & Conditions of access and use can be found athttps://www.tandfonline.com/action/journalInformation?journalCode=tsta20Science and Technology of Advanced MaterialsISSN: 1468-6996 (Print) 1878-5514 (Online) Journal homepage: https://www.tandfonline.com/loi/tsta20MDTS: automatic complex materials design usingMonte Carlo tree searchThaer M. Dieb, Shenghong Ju, Kazuki Yoshizoe, Zhufeng Hou, JunichiroShiomi & Koji TsudaTo cite this article: Thaer M. Dieb, Shenghong Ju, Kazuki Yoshizoe, Zhufeng Hou, JunichiroShiomi & Koji Tsuda (2017) MDTS: automatic complex materials design using MonteCarlo tree search, Science and Technology of Advanced Materials, 18:1, 498-503, DOI:10.1080/14686996.2017.1344083To link to this article:  https://doi.org/10.1080/14686996.2017.1344083© 2017 The Author(s). Published by InformaUK Limited, trading as Taylor & FrancisGroupView supplementary material Published online: 20 Jul 2017. Submit your article to this journal Article views: 3441 View related articles View Crossmark data Citing articles: 17 View citing articles https://www.tandfonline.com/action/journalInformation?journalCode=tsta20https://www.tandfonline.com/loi/tsta20https://www.tandfonline.com/action/showCitFormats?doi=10.1080/14686996.2017.1344083https://doi.org/10.1080/14686996.2017.1344083https://www.tandfonline.com/doi/suppl/10.1080/14686996.2017.1344083https://www.tandfonline.com/doi/suppl/10.1080/14686996.2017.1344083https://www.tandfonline.com/action/authorSubmission?journalCode=tsta20&show=instructionshttps://www.tandfonline.com/action/authorSubmission?journalCode=tsta20&show=instructionshttps://www.tandfonline.com/doi/mlt/10.1080/14686996.2017.1344083https://www.tandfonline.com/doi/mlt/10.1080/14686996.2017.1344083http://crossmark.crossref.org/dialog/?doi=10.1080/14686996.2017.1344083&domain=pdf&date_stamp=2017-07-20http://crossmark.crossref.org/dialog/?doi=10.1080/14686996.2017.1344083&domain=pdf&date_stamp=2017-07-20https://www.tandfonline.com/doi/citedby/10.1080/14686996.2017.1344083#tabModulehttps://www.tandfonline.com/doi/citedby/10.1080/14686996.2017.1344083#tabModuleSCIENCE AND TECHNOLOGY OF ADVANCED MATERIALS, 2017VOL. 18, NO. 1, 498–503https://doi.org/10.1080/14686996.2017.1344083 OPEN ACCESSMDTS: automatic complex materials design using Monte Carlo tree searchThaer M. Dieba,b, Shenghong Juc, Kazuki Yoshizoed, Zhufeng Houa, Junichiro Shiomia,c and Koji Tsudaa,b,daNational Institute for Materials Science, Tsukuba, Japan;bGraduate School of Frontier Sciences, The University of Tokyo, Kashiwa, Japan;cDepartment of Mechanical Engineering, The University of Tokyo, Tokyo, Japan;dRIKEN, Center for Advanced Intelligence Project, Tokyo, JapanABSTRACTComplex materials design is often represented as a black-box combinatorial optimizationproblem. In this paper, we present a novel python library called MDTS (Materials Design using TreeSearch).Our algorithm employs a MonteCarlo tree search approach, which has shown exceptionalperformance in computer Go game. Unlike evolutionary algorithms that require user interventionto set parameters appropriately, MDTS has no tuning parameters and works autonomously invarious problems. In comparison to a Bayesian optimization package, our algorithm showedcompetitive search efficiency and superior scalability. We succeeded in designing large Silicon-Germanium (Si-Ge) alloy structures that Bayesian optimization could not deal with due toexcessive computational cost. MDTS is available at https://github.com/tsudalab/MDTS.ARTICLE HISTORYReceived 25 April 2017Revised 29 May 2017Accepted 15 June 2017KEYWORDSMaterials informatics;Materials design; MonteCarlo tree search; Si-Gealloy interfacial structure;Python libraryCLASSIFICATION60 New topics/Others; 600Others: Materialsinformatics1. IntroductionComplex materials design is a key topic in materi-als science and engineering. The design of a complexmaterials’ structure that meets certain criteria is oftenformulated as the problem of finding the optimal so-lution from a space of candidates [1,2]. A commonproblem in solid-state materials design is the structuredetermination of a substitutional alloys problem [3,4],where atoms or vacancies are assigned to positions ina crystal structure. For example, Ju et al. [4] recentlysolved the optimal assignments of Silicon (Si) andGermanium (Ge) to a certain crystal structure that achi-eves minimum and maximum thermal conductance.To accelerate the materials design process, severalexperimental design algorithms have been used to findthe optimal structure with as few experiments as possi-ble (Figure 1). Experimental design is an iterative pro-cess for selecting the next candidates for experiments,where the outcome of the experiments are exploitedCONTACT Koji Tsuda tsuda@k.u-tokyo.ac.jpSupplemental data for this article can be accessed https://doi.org/10.1080/14686996.2017.1344083.for making further choices. In many cases, simula-tors are substituted to experiments, e.g. first-principlecalculations. In earlier studies, quantitative structure-property relationship (QSAR)modelsweremainly used[5]. Recently, Bayesian optimization [6], a technique toselect promising candidates using Bayesian learning,has been proven as an effective tool in materials design[1,2,4,7–9]. The difference between Bayesian optimiza-tion methods and traditional QSAR models is that theuncertainty of prediction is quantified as predictivevariance: the candidates are scored by an acquisitionfunction that takes into account both predicted meritand uncertainty. Bayesian optimization is very effectivein finding optimal structures but has problems withscalability, as the acquisition function has to be ap-plied to all candidates. Evolutionary algorithms suchas genetic algorithms [10,11] are more scalable, buthavemany parameters, such as crossover andmutationrates, that must be tuned properly to obtain the best© 2017 The Author(s). Published by National Institute for Materials Science in partnership with Taylor & Francis.This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricteduse, distribution, and reproduction in any medium, provided the original work is properly cited.http://www.tandfonline.comhttp://crossmark.crossref.org/dialog/?doi=10.1080/14686996.2017.1344083&domain=pdfhttps://github.com/tsudalab/MDTShttps://doi.org/10.1080/14686996.2017.1344083http://creativecommons.org/licenses/by/4.0/Sci. Technol. Adv. Mater. 18 (2017) 499 T. M. DIEB et al.Figure 1.Materials design by an experimental design algorithm.The process starts with an initial random design. The algorithmselects the next candidates for experiments, where the outcomeof the experiments are exploited by the algorithm to makefurther selection.performance. In most cases, in materials design, theamount of data available a priori is very limited, sotuning parameters using data may not be possible.In this paper, we propose a novel python librarycalled Materials Design using Tree Search (MDTS).MDTS solves structure determination of substitutionalalloys with composition constraints using a MonteCarlo tree search [12], a guided-randombest-first searchmethod that showed significant success in computerGo[12,13]. Our library is highly scalable and does not haveany tuning parameter.In experiments, we applied MDTS and an efficientBayesian optimization implementation [7] to a Si-Gealloy interface design between two Si leads [4]. The localforce field (bonding characteristics) in the structure canchange due to substitution. However, in this demon-stration case, we did not consider structure relaxationbecause the force constants of Si and Ge are known tobe transferable [14]. On the other hand, there are waysto include the change in the local force constants andthe current method can be simply used to incorporatesuch an effect [15]. The total computational time isdecomposed into design time and simulation time. Theformer represents the selection of the next candidatesand the latter simulator time. In terms of the number ofcalculations to find the optimal solution, Bayesian op-timization was better due to its high prediction ability.However, MDTS was comparable or better in terms oftotal computational time, because Bayesian optimiza-tion takes exponential design time with respect to thenumber of atoms.MDTS is a practical tool thatmaterialscientists can easily deploy in their own problems andhas the potential to become a standard choice.2. MethodConsider a black-box function, f (x), where x is a vectorof discrete variables x ∈ {0, 1, k − 1}N . We aim to findthe optimal solution x∗ that maximizes f (x) subject tocomposition constraintsN∑�=1I(x� = j) = nj, j = 0, . . . , k − 1 (1)where I is the indicator function that returns one ifthe given condition is satisfied and zero otherwise. Theconstant ni indicates the number of variables with valuei. Notice that∑k−1j=0 nj = N . In an atom assignmentproblem, x corresponds to atom types and f (x) is atarget property evaluated, for example, through first-principles calculations.Monte Carlo tree search (MCTS) employs a searchtree, where nodes at the �th level correspond to valueassignment to x� (Figure 2). A path from the root to anode at level � corresponds to a partial solution withrespect to x1, . . . , x�. In the first round of MCTS, onlythe root node exists and then the search tree is graduallyconstructed. To obtain a full solution x, a completepath to a leaf node at the Nth level is necessary. Oneinteresting feature of MCTS is that only a shallow treeis built and the complete paths are obtained via ran-dom playouts [12]. A ‘playout’ creates a solution bystarting from a node and determining the remainingvariables randomly. The random playout allows us toexplore a large candidates space without learning fromdata. Once a solution has been obtained by a playout,the black-box function f (x) is evaluated and recorded.By combining tree expansion, backtracking and play-outs, a large candidate space can be searched systemati-cally. When a predetermined number of calculations isreached, the best solution so far is returned as the finalresult.Each node i contains three variables: the visit countvi represents the number of visits in the search process;fi denotes the immediate merit of node i evaluated byplayout; and the cumulative merit wi is defined as thesum of all direct merit for all descendant nodes includ-ing itself. The Upper Confidence Bound (UCB) score[12] of a node is an index indicating how promising itis to explore the subtree under the node. It is definedbased on the cumulative merit and the number of visitsas follows:ui = wivi+ C√2 ln vparentvi(2)where C is the constant to balance exploration andexploitation and vparent is the visit count of the parentnode. Whenever a new node is added, the variables areinitialized asvi = wi = fi = 0, ui = ∞ (3)Each round of MCTS consists of: selection, expan-sion, simulation and back propagation (Figure 2). Inthe selection step, the tree is traversed from the root toa leaf by choosing the child with the maximum UCBscore at each branch. If there is a tie, the winning childis chosen randomly. Let i denotes the identified leaf, �the level of the node i, x1, . . . , x� the partial solutioncorresponding to the path from the root to i. In theexpansion step, children nodes are added under thenode i. If the number of atoms j reaches the limitSci. Technol. Adv. Mater. 18 (2017) 500 T. M. DIEB et al.Figure 2.Monte Carlo tree search (MCTS) for a binary atom assignment problem. The candidate space is represented as a tree whereeach node represents a possible atom assignment. One round of MCTS consists of four steps, Selection, Expansion, Simulation andBackpropagation. In the selection step, a promising leaf node is chosen by following the node with the best UCB score in eachbranch. The expansion step adds a number of children nodes to the selected one. In simulation, solutions are created by randomplayouts from the expanded nodes. The backpropagation step updates nodes’ information along the path back to the root.already, i.e.∑�l=1 I(xl = j) = nj the jth child is notadded. In the simulation step, a playout is performedfrom each of the added children. Notice that the ran-dom assignments are made such that the compositionconstraints are satisfied. With the solutions obtained, asimulator is applied to evaluate f (x) and store the valueas the immediate merit of the corresponding nodes.Finally, in the back propagation step, the visit count ofeach ancestor node of i is incremented by one and thecumulative value is also updated to keep consistency.The value of C crucially affects the performanceof MDTS. According to the analysis by Kocsis andSzepesvári [16], to guarantee the convergence to theoptimal solution,C should be proportional to the rangebetween zmax and zmin, i.e. themaximumandminimumimmediate merit observed in downstream nodes. Ad-justing C, either statically or dynamically, is a standardtechnique for applying MCTS (as shown in [12]). Fol-lowing a similar idea, MDTS controls C adaptively ateach node as follows:C =√2J4(zmax − zmin) (4)where J is a meta-parameter initially set to one andincreased whenever the algorithm encounters a ‘dead-end’ leaf, to allowmore exploration. At a dead-end leaf,the number of possible structures narrows to one. Thishappens when the numbers of k − 1 atoms reaches thelimit. J is updated as J ← J +max{T−tT , 0.1}, where Tis the total number of candidates to be evaluated andt is the number of candidates for which the black-boxfunction is evaluated. See supplemental material for thealgorithm.3. Experiments and resultsIn this section, we compare MDTS to a Bayesian opti-mization package called COMBO [7] in a binary atomassignment problem (notice that MDTS is able to han-dle multiple atom types assignment problems). Theperformance of MDTS depends on the variable order-ing in x. The following three options were tried: direct(left-to-right), reversed (right-to-left) and random.MDTS and COMBOwere applied to design optimalSi-Ge alloy (Si:Ge=1:1) interfacial structures (Figure 3)with both minimum and maximum thermal conduc-tance [4]. Materials with both minimum (e.g. thermo-electric materials) and maximum (e.g. CPU cooling)interfacial thermal conductance have potential appli-cations. As shown in Figure 3, the system consists ofan interface region between two Si leads with infinitethickness. In the interface, there are N positions filledeither by Si or Ge. The number of atoms of each type isconstrained to N/2. The number of possible structuresgrows rapidly as the number of atoms N increases.For example, at 14, 20 and 26 atoms, the number ofpossible structures is 3432, 184,756 and 10,400,600,Figure 3. Si-Ge interfacial structure between two Si leads. In this case, the interface region is made up of 16 atoms.Sci. Technol. Adv. Mater. 18 (2017) 501 T. M. DIEB et al.(a)(b)(c)Figure 4. Comparison betweenMDTS and Bayesian optimization (BO) in finding the structure with minimum andmaximum thermalconductance. (a) Design time for choosing a candidate structure against the number of atoms in the interfacial structure N. Thetime for BO grows exponentially as N increases. Results averaged over 10 runs, each for 30 solutions. (b) The fraction of optimalstructure discovery (i.e. success rate) for both minimum and maximum thermal conductance in 100 runs against the number ofthermal conductance calculations. The number of atoms is 16 (N = 16). BO takes fewer calculations to find the optimal structure.(c) Optimal observed thermal conductance (minimum and maximum) against total computational time including both design andsimulation time (N = 22). The result is averaged over 10 runs. Here, the efficiency of the twomethods is comparable. For N < 22, BOwas more efficient and MDTS was more efficient for N > 22.respectively. The thermal conductance was computedusing the atomistic Green’s function implemented intheATK-Classical Simulator ofAtomistixToolKit (ATK)[17,18]. SiGe Tersoff [19,20] potential was used to de-scribe the atom interactions. The size of the supercell inthe transverse direction (perpendicular to the directionof heat conduction) is 1 unit cell, i.e. 5.43 Å × 5.43 Å,and periodic boundary conditions were used. See Ref.[4] for further details.Since the process of simulation-based structure op-timization involves an experimental design algorithmand a simulation algorithm, the total computationaltime is divided into two parts: design time and simula-tion time. The design time per structure against theSci. Technol. Adv. Mater. 18 (2017) 502 T. M. DIEB et al.number of atoms is shown in Figure 4(a). Bayesianoptimization shows an exponential increase in designtime, because it needs to compute a score for everycandidate structure. On the other hand, the design inMDTS takes only a tree traversal, whose computationalcost is scarcely affected by the number of atoms. Figure4(b) shows the fraction of optimal structure discoveryover 100 runs (i.e. success rate) for both minimum andmaximum thermal conductance against the number ofthermal conductance calculations at N = 16. Bayesianoptimization required a smaller number of calculationsto achieve the same level of success rate due to itssophisticated prediction algorithm. Nevertheless, theperformance of MDTS was better than random search,indicating its substantial capability of learning fromdata. Among the three variable orderings ofMDTS, thereversed order was best. Random order performancewas lowest in this particular case, likely because theexistence of neighbourhood relations may be crucialfor the optimal thermal conductance. Despite betterlearning capability, the advantage ofBayesianoptimiza-tion in total computational time is rapidly wiped out,as N increases, because of the exponentially increasingdesign time. At N = 22, the speed of thermal conduc-tance minimization and maximization of MDTS andBayesian optimization is comparable as shown in Fig-ure 4(c). At N = 26, however, Bayesian optimizationbecomes significantly slower: it takes about 15 timesmore time than theN = 22 case. This result shows thatMDTS should be chosen over Bayesian optimizationunless the problem size is sufficiently small.4. ConclusionIn this paper, we presented MDTS: a materials designlibrary based on Monte Carlo tree search. MDTS is anopen source project and interested researchers can joinin the development of MDTS. The balance betweendesign time and simulation time is an important factorin automaticmaterials design. Efficient designmethodsincluding MDTS are most useful when the simulationtime is short. The long design time of a more inef-ficient machine-learning based approach can appearless problematic when the simulation time is longer. Infuturework, itwould benecessary to pursue an adaptiveapproach that can balance optimality and design timein a variable manner. Additionally, we plan to makeMDTS more customizable for diverse materials designproblems with possibly different kinds of constraints.AcknowledgementsWe would like to thank David A. duVerle for fruitful discus-sions. We also would like to thank anonymous referees fortheir comments and suggestions to improve the manuscript.Disclosure statementAuthors declare no conflict of interest.FundingThis work was supported by the ‘Materials research by In-formation Integration’ Initiative (MI2I) project and CREST[grant number JPMJCR16Q5] from Japan Science and Tech-nology Agency (JST). It was also supported by Grant-in-Aidfor Scientific Research on Innovative Areas ‘Nano Informat-ics’ [grant number 25106005] from the Japan Society for thePromotion of Science (JSPS).References[1] Seko A, Togo A, Hayashi H, et al. Prediction of low-thermal-conductivity compounds with first-principlesanharmonic lattice-dynamics calculations and bayesianoptimization. Phys Rev Lett. 2015;115:205901.[2] Balachandran PV, Xue D, Theiler J, et al. Adaptivestrategies for materials design using uncertainties. SciRep. 2016;6:19660.[3] Okhotnikov K, Charpentier T, Cadars S. Supercell pro-gram: a combinatorial structure-generation approachfor the local-level modeling of atomic substitutions andpartial occupancies in crystals. J Cheminf. 2016;8(1):17.DOI: 10.1186/s13321-016-0129-3[4] Ju S, Shiga T, Feng L, et al. Designing nanostructuresfor phonon transport via Bayesian optimization. PhysRev X. 2017;7:021024.[5] Coulinga D, Bernotb R, Dochertyb KM, et al. Assessingthe factors responsible for ionic liquid toxicity toaquatic organisms via quantitative structure-propertyrelationship modeling. Green Chem. 2006;8:82–90.[6] Snoek J, Larochelle H, Adams R. Practical Bayesianoptimization of machine learning algorithms. AdvNeural Inf Process Syst. 2012;2951–2959.[7] Ueno T, Rhone T, Hou Z, et al. COMBO: an efficientBayesian optimization library for materials science.Mater Discov. 2016;4:18–21.[8] Seko A, Maekawa T, Tsuda K, et al. Machine learningwith systematic density-functional theory calculations:application to melting temperatures of single-andbinary-component solids. Phys Rev B. 2014;89:054303.[9] Kiyohara S, OdaH, TsudaK, et al. Acceleration of stableinterfacestructure searching using a kriging approach.Jpn J Appl Phys. 2016;55:045502.[10] Patra TK,MeenakshisundaramV,Hung J, et al. Neural-network-biased genetic algorithms formaterials design:Evolutionary algorithms that learn. ACS Comb Sci.2017;19(2):96–107.[11] Paszkowicz W, Harris KD, Johnston RL. Geneticalgorithms: a universal tool for solving computationaltasks in materials science. Comput Mater Sci.2009;45(1):ix–x.[12] Browne C, Powley E, Whitehouse D, et al. A survey ofMonte Carlo tree search methods. IEEE Trans ComputIntell AI in Games. 2012;4(1):1–43.[13] Silver D, Huang A, Maddison C, et al. Mastering thegame of Go with deep neural networks and tree search.Nature. 2016;529:484–489.[14] Murakami T, Hori T, Shiga T, et al. Probing and tuninginelastic phonon conductance across finite-thicknessinterface. Appl Phys Express. 2014;7:121801.[15] Murakami T, Shiga T, Hori T, et al. Importance of localforce fields on lattice thermal conductivity reduction inPbTe1−xSex alloys. EPL. 2013;102:46002.[16] Kocsis L, Szepesvári C. Bandit based monte-carloplanning. European conference on machine learning.Berlin: Springer; 2006. p. 282–293.https://doi.org/10.1186/s13321-016-0129-3Sci. Technol. Adv. Mater. 18 (2017) 503 T. M. DIEB et al.[17] Griebel M, Hamaekers J. Molecular dynamicssimulations of the elastic moduli of polymer-carbonnanotube composites. Comput Meth Appl Mech Eng.2004;193:1773–1788.[18] Griebel M, Knapek S, Zumbusch G. Numericalsimulation in molecular dynamics. Vol. 5, Textsin computational science and engineering. Springer-Verlag, Berlin Heidelberg; 2007.[19] Tersoff J. Modeling solid-state chemistry: interatomicpotentials for multicomponent systems. Phys Rev B.1989;39:5566(R).[20] Tersoff J. Erratum: Modeling solid-state chemistry:interatomic potentials for multicomponent systems.Phys Rev B. 1990;41:3248. 1. Introduction 2. Method 3. Experiments and results 4. Conclusion Acknowledgements Disclosure statement Funding References