Title: Solving problems using MCTS Author: Dominik Malý Department: Department of theoretical informatics and mathematical logic Supervisor: RNDr. Jan Hric Supervisor's e-mail address: Jan.Hric@mff.cuni.cz Abstract: MCTS (Monte Carlo Tree Search) methods are a state-of-the-art approach to the computer solution of strategic board game Go. Because of their versatility and successfulness, these techniques show great potential for all kinds of problems. This paper aims to explore the suitability of MCTS for solving different kind of problems, specifically games of one player, like Sudoku or SameGame. I've created a computer player based on MCTS, who can solve not only Sudoku and SameGame, but also other tasks of similar kind. I've experimentally examined many MCTS extensions and their eligibility for solving these games and through extensive testing I've also compared the suitability of various kinds of UCT selection fun- ctions and used heuristics. In case of SameGame I've compared my algorithm to another exi- sting one undertaking the same problem. In the end I've described what kind of problems has a MCTS-based computer player to overcome, if it is to successfully solve games of this type, and what characteristics should these problems posses to be suitable for MCTS solution. Keywords: MCTS, Go, Sudoku,...

Evolutionary and genetic algorithms are problem-solving methods designed according to a nature inspiration. They are used for solving hard problems that we cannot solve by any efficient specialized algorithm. The Monte Carlo method and its derivation the Monte Carlo Tree Search (MCTS) are based on sampling and are also commonly used for too complex problems, where we are dealing with enormous memory consumption and it is impossible to perform a complete searching. The goal of this thesis is to design a general problem solving method that is built from these two completely different approaches. We explain and implement the new method on one example problem: the Traveling salesman problem (TSP). Second part of this thesis contains various tests and experiments. We compare different settings and parametrizations of our method. The best performing variant is then compared with the classical evolutionary TSP solution or, for example, with greedy algorithms. Our method shows competitive results. The best results were achieved with the cooperation of our method and the classical evolutionary TSP solution. This union shows better results than any of its parts separately, which we find as a great success.

Maintenance planning and execution is increasingly important for the modern industrial sector. Maintenance costs can amount to a major part of industrial spending. However, it is not as simple as just reducing maintenance budgets. A balance must be struck between risking unplanned downtime and the costs of maintenance efforts, in order to keep the profit margins needed to compete in the global markets of today. One approach to improve the effectiveness of industries is to apply intelligent maintenance planners. In this thesis, a general-purpose maintenance planner based on Monte-Carlotree search and deep reinforcement learning is presented. This planner was evaluated and compared against two different periodic planners as well as the oracle lower bound on four different maintenance scenarios. These four scenarios are all based on servicing wind turbines. All scenarios include imperfect maintenance actions, as well as uncertainty in terms of the outcomes of maintenance actions. Furthermore, the four scenarios include both single and multi-component variants. The evaluation showed that the proposed method is outperforming both periodic planners in three of the four scenarios, with the forth being inconclusive. These results indicate that the maintenance planner introduced in this paper is a viable method, at least for these types of maintenance problems. However, further research is needed on this topic of maintenance planning under uncertainty. More specifically, the viability of the proposed method on a more diverse set of maintenance problems is needed to draw any clear general conclusions. Finally, possible improvements to the training process that are discussed in this thesis should be investigated.

The purpose of this thesis is to evaluate the possibility of predicting difficulty, measured in average human success rate (AHSR), across game levels of a mobile game using a general AI algorithm. We implemented and tested a simulation based bot using MCTS for Candy. Our results indicate that AHSR can be predicted accurately using MCTS, which in turn suggests that our bot could be used to streamline game level development. Our work is relevant to the field of AI, especially the subfields of MCTS and single-player stochastic games as Candy, with its diverse set of features, proved an excellent new challenge for testing the general capabilities of MCTS. The results will also be valuable to companies interested in using AI for automatic testing of software.

The understanding of the electrical properties of defects introducing deep levels in silicon is of prime technological importance in modern microelectronics. In this thesis, a comprehensive study of the transition metals titanium, cobalt, and nickel in silicon, and of their interaction with hydrogen is presented. The formed defects are detected and characterized by deep level transient spectroscopy (DLTS), Laplace DLTS, and minority carrier transient spectroscopy. A natural starting point for a study of metal-hydrogen reactions in silicon is the analysis of the effect of hydrogen on metal-free silicon. Complexes of hydrogen with carbon, which create deep levels in the band gap of silicon, are observed. Titanium introduces three levels into the band gap. The charge states determined in this thesis are in contradiction to the literature, questioning the assignment of these levels. Upon hydrogenation, TiH complexes with one, two, and three hydrogen atoms are identified. A proposition by theory that two different configurations of TiH with one hydrogen atom exist, can be supported. Cobalt is shown to have only one level in the band gap of silicon, whereas a second level previously attributed to cobalt is assigned to the cobalt-boron pair. Two CoH complexes are determined. Nickel has three levels in the band gap. Upon hydrogenation, complexes with up to three hydrogen atoms are identified. One of the defects can be observed in both n - and p -type silicon. For all three metals investigated, passive hydrogen complexes exist. They are created by further hydrogenation after the appearance of the above mentioned electrically active complexes. The thesis concludes with a comparison of the obtained results with those of neighboring elements to look for similarities and patterns. / Das Verständnis der elektrischen Eigenschaften von Defekten, welche tiefe Niveaus in der Bandlücke von Silizium erzeugen, ist von außerordentlichem Interesse für die moderne Mikroelektronik. In der vorliegenden Dissertation wird eine umfassende Untersuchung der Übergangsmetalle Titan, Kobalt und Nickel in Silizium und ihrer Wechselwirkung mit Wasserstoff vorgestellt. Die entstandenen Defekte werden mit Hilfe von Kapazitätstransientenspektroskopie (DLTS - deep level transient spectroscopy), Laplace DLTS und Minoritätsladungsträgertransientenspektroskopie (MCTS - minority carrier transient spectroscopy) beobachtet und charakterisiert. Für eine fehlerfreie Analyse der Metall-Wasserstoff-Reaktionen ist es sinnvoll, zuerst den Einfluss des Wasserstoffs auf metallfreies Silizium zu prüfen. Dabei wird die Bildung von Kohlenstoff-Wasserstoff-Komplexen, welche Niveaus in der Bandlücke von Silizium erzeugen, beobachtet. Titan besitzt drei Niveaus in der Bandlücke von Silizium. Die in dieser Arbeit bestimmten Ladungszustände stehen im Widerspruch zu den Literaturangaben, daher wird die Zuordnung dieser Niveaus in Frage gestellt. Die Reaktion von Titan mit Wasserstoff führt zu elektrisch aktiven Komplexen mit bis zu drei Wasserstoffatomen. Die Ergebnisse unterstützen einen Vorschlag aus der Theorie, nach dem der Komplex mit einem Wasserstoff zwei verschiedene Konfigurationen besitzen soll. Kobalt erzeugt ein Niveau in der Bandlücke. Ein weiteres Niveau, welches früher ebenfalls dem Kobalt zugewiesen wurde, kann dem Kobalt-Bor-Paar zugeordnet werden. Nach der Reaktion mit Wasserstoff können zwei CoH-Komplexe nachgewiesen werden. Nickel besitzt drei Niveaus in der Bandlücke und erzeugt elektrisch aktive NiH-Komplexe mit bis zu drei Wasserstoffatomen. Einer dieser Defekte kann sowohl im n - als auch im p -Typ Silizium beobachtet werden. Alle drei untersuchten Metalle besitzen elektrisch passive Komplexe, welche nach der weiteren Reaktion von Wasserstoff mit den aktiven Komplexen entstehen. Die Arbeit endet mit einem Vergleich der Ergebnisse mit denen benachbarter Elemente, um mögliche Ähnlichkeiten oder Muster zu erkennen.

The understanding of the electrical properties of defects introducing deep levels in silicon is of prime technological importance in modern microelectronics. In this thesis, a comprehensive study of the transition metals titanium, cobalt, and nickel in silicon, and of their interaction with hydrogen is presented. The formed defects are detected and characterized by deep level transient spectroscopy (DLTS), Laplace DLTS, and minority carrier transient spectroscopy. A natural starting point for a study of metal-hydrogen reactions in silicon is the analysis of the effect of hydrogen on metal-free silicon. Complexes of hydrogen with carbon, which create deep levels in the band gap of silicon, are observed. Titanium introduces three levels into the band gap. The charge states determined in this thesis are in contradiction to the literature, questioning the assignment of these levels. Upon hydrogenation, TiH complexes with one, two, and three hydrogen atoms are identified. A proposition by theory that two different configurations of TiH with one hydrogen atom exist, can be supported. Cobalt is shown to have only one level in the band gap of silicon, whereas a second level previously attributed to cobalt is assigned to the cobalt-boron pair. Two CoH complexes are determined. Nickel has three levels in the band gap. Upon hydrogenation, complexes with up to three hydrogen atoms are identified. One of the defects can be observed in both n - and p -type silicon. For all three metals investigated, passive hydrogen complexes exist. They are created by further hydrogenation after the appearance of the above mentioned electrically active complexes. The thesis concludes with a comparison of the obtained results with those of neighboring elements to look for similarities and patterns. / Das Verständnis der elektrischen Eigenschaften von Defekten, welche tiefe Niveaus in der Bandlücke von Silizium erzeugen, ist von außerordentlichem Interesse für die moderne Mikroelektronik. In der vorliegenden Dissertation wird eine umfassende Untersuchung der Übergangsmetalle Titan, Kobalt und Nickel in Silizium und ihrer Wechselwirkung mit Wasserstoff vorgestellt. Die entstandenen Defekte werden mit Hilfe von Kapazitätstransientenspektroskopie (DLTS - deep level transient spectroscopy), Laplace DLTS und Minoritätsladungsträgertransientenspektroskopie (MCTS - minority carrier transient spectroscopy) beobachtet und charakterisiert. Für eine fehlerfreie Analyse der Metall-Wasserstoff-Reaktionen ist es sinnvoll, zuerst den Einfluss des Wasserstoffs auf metallfreies Silizium zu prüfen. Dabei wird die Bildung von Kohlenstoff-Wasserstoff-Komplexen, welche Niveaus in der Bandlücke von Silizium erzeugen, beobachtet. Titan besitzt drei Niveaus in der Bandlücke von Silizium. Die in dieser Arbeit bestimmten Ladungszustände stehen im Widerspruch zu den Literaturangaben, daher wird die Zuordnung dieser Niveaus in Frage gestellt. Die Reaktion von Titan mit Wasserstoff führt zu elektrisch aktiven Komplexen mit bis zu drei Wasserstoffatomen. Die Ergebnisse unterstützen einen Vorschlag aus der Theorie, nach dem der Komplex mit einem Wasserstoff zwei verschiedene Konfigurationen besitzen soll. Kobalt erzeugt ein Niveau in der Bandlücke. Ein weiteres Niveau, welches früher ebenfalls dem Kobalt zugewiesen wurde, kann dem Kobalt-Bor-Paar zugeordnet werden. Nach der Reaktion mit Wasserstoff können zwei CoH-Komplexe nachgewiesen werden. Nickel besitzt drei Niveaus in der Bandlücke und erzeugt elektrisch aktive NiH-Komplexe mit bis zu drei Wasserstoffatomen. Einer dieser Defekte kann sowohl im n - als auch im p -Typ Silizium beobachtet werden. Alle drei untersuchten Metalle besitzen elektrisch passive Komplexe, welche nach der weiteren Reaktion von Wasserstoff mit den aktiven Komplexen entstehen. Die Arbeit endet mit einem Vergleich der Ergebnisse mit denen benachbarter Elemente, um mögliche Ähnlichkeiten oder Muster zu erkennen.

Within solid tumours, a microenvironment exists that causes resistance to chemotherapy. New drugs that target cells within this microenvironment are required, the first step in this process being the identification of new targets. The aim of this thesis was to characterise changes in the transcriptome and proteome within specific regions of multicell-tumour spheroids (MCTS), an experimental model that mimics many of the features of the tumour microenvironment. HT29 MCTS were separated by sequential trypsinisation into 3 main regions; the outer surface layer (SL) the peri-necroric region (PN) and the necrotic core (NC). Using an iTRAQ quantitative proteomics approach, the proteome of the different MCTS regions was investigated. A 2 dimensional separation approach using Agilent's OffGel system and RP-nano HPLC was incorporated prior to MS analysis. MS analysis was done using both MALDI-TOF-TOF (Bruker Ultraflex II) and ESI-Q-TOF (Agilent 6530 QTOF LC/MS) instruments. Gene expression profiles of the different MCTS were investigated and compared using Agilent's one-color oligonucleotide based microarrays. Transcriptomic and proteomic analysis identified several key differences in the proteins involved in cell metabolism between the SL and PN/NC regions. Similar metabolic changes were also noted between autophagic and normal monolayer cells. Many highlighted proteins represented established cancer associated proteins. Interestingly, a number of proteins were highlighted which have no previous association with cancer and may upon further validation, provide attractive leads for therapeutic intervention.

Ce travail consiste en une tentative de ré-examiner les propriétés électroniques du Fe, Cr et Au au sein de Ge, qui ont déjà été étudiées classiquement par DLTS (Deep Level Transient Spectroscopy). L'image générale qui en découle est que les métaux de transition dans Ge forment de manière prépondérante des centres accepteurs multiples, introduisant plusieurs niveaux profonds dans la bande de gap. A partir d'un modèle de liaison de valence simple, cette conclusion est en accord avec une survenue des impuretés sur des sites de substitution. Cependant, plusieurs questions demeurent ouvertes, comme le rôle de l'hydrogène en tant que contaminant dans l'élargissement des spectres DLTS. Notre contribution se base sur l'utilisation d'une approche plus performante nommée Laplace DLTS, en ce sens qu'elle autorise une meilleure résolution du signal. Nous présentons une analyse extensive par DLTS, MCTS et Laplace DLTS, afin d'étudier les propriétés électroniques des états accepteurs multiples, induits par les 4 métaux de transition sus-nommés. On distingue, parmis les paramètres étudiés, les barrières de capture des porteurs, les vraies sections efficaces de capture de sporteurs majoritaires (déterminées directement par la méthode de variation du pulse de remplissage), L'effet Pool-Frenkel (en lien avec la détermination de l'état de charge du niveau concerné). Ceci permet d'indiquer avec précision la position exacte des niveaux dans la bande interdite. Nous confirmons la plupart des résultats mis en évidence précédemment, tout en ajoutant quelques précisions sir le rôle de l'hydrogène dans la formation de nouveaux complexes. Une mise en parallèle avec le silicium. Dans le cas de Au, de nouveaux niveaux attribués aux complexes Au-Hn et Au-Sb sont observés. De manière générale, l'analyse des porteurs majoritaires et minoritaires par MCYS est toujours sujette à étude. En ce qui concerne le cas du Fe, la faible différence d'énergie entre ses deux niveaux soulève la possibilité d'un caractère de type U-négatif. L'ensemble de ses points devraient faire l'objet d'un travail approfondis dans un avenir proche.

Ce travail consiste en une tentative de ré-examiner les propriétés électroniques du Fe, Cr et Au au sein de Ge, qui ont déjà été étudiées classiquement par DLTS (Deep Level Transient Spectroscopy). L'image générale qui en découle est que les métaux de transition dans Ge forment de manière prépondérante des centres accepteurs multiples, introduisant plusieurs niveaux profonds dans la bande de gap. A partir d'un modèle de liaison de valence simple, cette conclusion est en accord avec une survenue des impuretés sur des sites de substitution. Cependant, plusieurs questions demeurent ouvertes, comme le rôle de l'hydrogène en tant que contaminant dans l'élargissement des spectres DLTS. Notre contribution se base sur l'utilisation d'une approche plus performante nommée Laplace DLTS, en ce sens qu'elle autorise une meilleure résolution du signal. Nous présentons une analyse extensive par DLTS, MCTS et Laplace DLTS, afin d'étudier les propriétés électroniques des états accepteurs multiples, induits par les 4 métaux de transition sus-nommés. On distingue, parmis les paramètres étudiés, les barrières de capture des porteurs, les vraies sections efficaces de capture de sporteurs majoritaires (déterminées directement par la méthode de variation du pulse de remplissage), L'effet Pool-Frenkel (en lien avec la détermination de l'état de charge du niveau concerné). Ceci permet d'indiquer avec précision la position exacte des niveaux dans la bande interdite. Nous confirmons la plupart des résultats mis en évidence précédemment, tout en ajoutant quelques précisions sir le rôle de l'hydrogène dans la formation de nouveaux complexes. Une mise en parallèle avec le silicium. Dans le cas de Au, de nouveaux niveaux attribués aux complexes Au-Hn et Au-Sb sont observés. De manière générale, l'analyse des porteurs majoritaires et minoritaires par MCYS est toujours sujette à étude. En ce qui concerne le cas du Fe, la faible différence d'énergie entre ses deux niveaux soulève la possibilité d'un caractère de type U-négatif. L'ensemble de ses points devraient faire l'objet d'un travail approfondis dans un avenir proche. / The present work is an attempt to re-examine the electronic properties of Fe, Ni Cr and Au in Ge which have been already studied by conventional DLTS (Deep Level Transient Spectroscopy). A general picture, that emerged, is that transition metals in Ge predominantly form multiple-acceptor centres, introducing several deep levels in the band gap, which according to a simple valence bond model is in agreement with a preferential occurrence of the impurities on substitutional sites. However, some questions remained open such as the role of hydrogen as a natural contaminant in the broadening of the DLTS spectra. Our contribution is based on the use of a more powerfull approach called Laplace DLTS in the sense that it allows a better resolution of the signal. We present extensive DLTS, MCTS and Laplace DLTS results to investigate the electronic properties of the multi-acceptor states, induced by mentioned four transition metals. Among the studied parameters we may cite the barrier for carrier capture, the true majority carrier capture cross section directly measured by the variable pulse length method, the Poole-Frenkel effect related to the assignment of the charge states - all these parameters are important to locate the level positions in the band gap. We confirm in the present work most of the results obatained in the past, adding some insight into the role of hydrogen in the formation of new complexes and in this respect a parallel is made with silicon. In case of Au new levels attributed to conjectural Au-Hn and Au-Sb complexes are observed. In addition development of both majority and minority carriers in MCTS analysis still is under consideration. For the Fe case, the small difference in energy of its two levels raises the question as to the possibility of negative-U character. These mentioned points should be treated more thoroughly in a future work.

I arbetet implementerades två algoritmer som utvärderades genom att spela ett matcha-3-spel mot varandra. Den första algoritmen var Minimax som väljer sina drag genom att evaluera de möjliga dragen från ett tillstånd. För att inte sökrymden ska bli för stor begränsas algoritmen med ett sökdjup. Den andra algoritmen var en MCTS som utför flera simuleringar där den utför slumpmässiga drag till ett spelslut för att få en uppskattning över resultatet från de olika dragen. Spelet som de utvärderas på är av typen matcha-3-battle. Flera experiment utfördes sedan på de två algoritmerna, där de spelade flera matcher motvarandra på olika stora bräden, sökdjup och utforskningskonstanter. Testerna visade att i denna implementation var Minimax överlägsen i de fall. När sökrymden blev större presterade MCTS bättre än i mindre rymder, men lyckades aldrig nå en majoritet av vinster.