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,...

The application of Reinforcement Learning (RL) in the field of protein design presents a novel approach to generating protein backbones that fit within an icosahedral structure, while also optimizing five critical structural scores of proteins. Central to this approach are developed two distinct Markov Decision Processes (MDPs), each employing a unique reward mechanism: one operates on a system of thresholds, while the other utilizes sigmoid functions. The study conducts a thorough comparison of these reward mechanisms to determine their effectiveness in guiding RL algorithms for protein design. The findings indicate that the threshold-based reward system outperforms the sigmoid-based system, leading to more desirable protein structures as per the defined scores. Significantly, the thesis examines the performance of AlphaZero agents in this context, comparing them to baseline Monte Carlo Tree Search agents. Results demonstrate that AlphaZero agents consistently achieve at least double the performance of Monte-Carlo Tree Search (MCTS) agents, showcasing their superior capability in top-down protein design task. Moreover, the research extends to evaluate AlphaZero agents optimized for side objectives, revealing promising outcomes. This exploration into multi-objective optimization using AlphaZero agents highlights their potential in more complex and nuanced aspects of protein engineering. This work not only underscores the effectiveness of RL in protein backbone generation but also opens up new possibilities for advanced RL applications in protein engineering, particularly in multi-faceted optimization scenarios. / Tillämpningen av RL inom proteindesignområdet presenterar en ny metod för att generera proteinbackbones som passar in i en ikosaederstruktur, samtidigt som man optimerar fem kritiska strukturella poäng för proteiner. Centralt för denna metod är utvecklingen av två distinkta MDPs, som var och en använder en unik belöningsmekanism: en fungerar på ett system av tröskelvärden, medan den andra använder sigmoidfunktioner. I studien görs en grundlig jämförelse av dessa belöningsmekanismer för att fastställa deras effektivitet när det gäller att vägleda RL-algoritmer för proteindesign. Resultaten visar att det tröskelbaserade belöningssystemet överträffar det sigmoidbaserade systemet, vilket leder till mer önskvärda proteinstrukturer enligt de definierade poängen. Avhandlingen undersöker AlphaZero-agenternas prestanda i detta sammanhang och jämför dem med grundläggande Monte Carlo Tree Search-agenter. Resultaten visar att AlphaZero-agenter konsekvent uppnår minst dubbelt så hög prestanda som MCTS-agenter, vilket visar deras överlägsna förmåga i top-down-proteindesignuppgiften. Dessutom utvidgas forskningen till att utvärdera AlphaZero-agenter optimerade för sidomål, vilket avslöjar lovande resultat. Denna utforskning av flermålsoptimering med hjälp av AlphaZero-agenter belyser deras potential i mer komplexa och nyanserade aspekter av proteinteknik. Detta arbete understryker inte bara effektiviteten hos RL vid generering av proteinbackbones, utan öppnar också upp för nya möjligheter att utveckla

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.