AlphaFold [Jumper et al., 2021, Evans et al., 2022] is a deep learning-based method that can accurately predict the structure of single- and multiple-chain proteins. However, its accuracy decreases with an increasing number of chains, and GPU memory limits the size of protein complexes that can be predicted. Recently, Elofsson’s groupintroduced a Monte Carlo tree search method, MoLPC, that can predict the structure of large complexes from predictions of sub-components [Bryant et al., 2022b]. However, MoLPC cannot adjust for errors in the sub-component predictions and requires knowledge of the correct protein stoichiometry. Large protein complexes are responsible for many essential cellular processes, such as mRNA splicing [Will and Lührmann, 2011], protein degradation [Tanaka, 2009], and protein folding [Ditzel et al., 1998]. However, the lack of structural knowledge of many large protein complexes remains challenging. Only a fraction of the eukaryoticcore complexes in CORUM [Giurgiu et al., 2019] have homologous structures covering all chains in PDB, indicating a significant gap in our structural understanding of protein complexes. AlphaFold-Multimer [Evans et al., 2022] is the only deep learning method that can predict the structure of more than two protein chains, trained on proteins of up to 20 chains, and can predict complexes of up to a few thousand residues, where memory limitations come into play. Another approach, MoLPC, is to predict the structure of sub-components of large complexes and assemble them. It has shown that it is possible to manually assemble large complexes from dimers manually [Burke et al., 2021] or use Monte Carlo tree search [Bryant et al., 2022b]. One limitation of the previous MoLPC approach is its inability to account for errors in sub-component prediction. The addition of small errors in each sub-component can propagate to a significant error when building the entire complex, leading toMoLPC’s failure. To overcome this challenge, the Monte Carlo Tree Search algorithms in MoLPC2 is enhanced to assemble protein complexes while simultaneously predicting their stoichiometry. Using MoLPC2, we accurately predicted the structures of 50 out of 175 non-redundant protein complexes (TM-score >0.8), while MoLPC only predicted 30. It should be noted that improvements introduced in AlphaFold version 2.3 enable the prediction of larger complexes, and if stoichiometry is known, it can accurately predict the structures of 74 complexes. Our findings suggest that assembling symmetrical complexes from sub-components results in higher accuracy while assembling asymmetrical complexes remains challenging.

No description available.

Gomoku, also called Five in a row, is one of the earliest checkerboard games invented by humans. For a long time, it has brought countless pleasures to us. We humans, as players, also created a lot of skills in playing it. Scientists normalize and enter these skills into the computer so that the computer knows how to play Gomoku. However, the computer just plays following the pre-entered skills, it doesn’t know how to develop these skills by itself. Inspired by Google’s AlphaGo Zero, in this thesis, by combining the technologies of Monte Carlo Tree Search, Deep Neural Networks, and Reinforcement Learning, we propose a system that trains machine Gomoku players without prior human skills. These are self-evolving players that no prior knowledge is given. They develop their own skills from scratch by themselves. We have run this system for a month and half, during which time 150 different players were generated. The later these players were generated, the stronger abilities they have. During the training, beginning with zero knowledge, these players developed a row-based bottom-up strategy, followed by a column-based bottom-up strategy, and finally, a more flexible and intelligible strategy with a preference to the surrounding squares. Although even the latest players do not have strong capacities and thus couldn’t be regarded as strong AI agents, they still show the abilities to learn from the previous games. Therefore, this thesis proves that it is possible for the machine Gomoku player to evolve by itself without human knowledge. These players are on the right track, with continuous training, they would become better Gomoku players.

要旨ファイルを差し替え（2023-01-23） / 京都大学 / 新制・課程博士 / 博士(薬学) / 甲第23144号 / 薬博第844号 / 新制||薬||242(附属図書館) / 京都大学大学院薬学研究科薬学専攻 / (主査)教授 高須 清誠, 教授 石濱 泰, 教授 大野 浩章 / 学位規則第4条第1項該当 / Doctor of Pharmaceutical Sciences / Kyoto University / DFAM

In accommodating the growing global demand for wireless, Multi-User Multiple-Input and Multiple-Output (MU-MIMO) systems have been identified as the key technology. In such systems, a transmitting basestation serves several users simultaneously, increasing the network capacity. However, sharing the same time-frequency physical resources can cause interference for the simultaneously scheduled users if not moderated properly. One way to mitigate this interference is by directing radio power through the radio channel in specific directions, a method which is called beamforming. Following the successful implementation of the AlphaZero algorithm in another radio resource management technique, scheduling, this thesis explores the potential of using a similar search-based method for the beamforming problem, striving towards the ultimate objective of making decisions for scheduling and beamforming jointly. However, as AlphaZero only supports discrete action spaces and the action space of the beamforming problem is continuous, a modification of the algorithm is required. The proposed course of action is to extend AlphaZero into Sampled AlphaZero, using sample-based policy improvement to create an algorithm that is both more scalable for large discrete action spaces and able to handle high dimensional continuous action spaces. To evaluate the performance of the models, test environments were simulated and solved using increasingly larger so-called codebooks, containing predefined beamforming solutions. The results of the Sampled AlphaZero model demonstrated promising performance even for very large codebook sizes, indicating the model's suitability for addressing the beamforming problem in a non-codebook-based context. Furthermore, this thesis explores how states in the search can be represented and preprocessed for the neural network to learn efficiently, demonstrating clear benefits of using a singular value decomposition-based state preprocessing over raw states as input to the neural network.

No description available.

No description available.

Depuis son introduction pour le jeu de Go, Monte Carlo Tree Search (MCTS) a été appliqué avec succès à d'autres jeux et a ouvert la voie à une famille de nouvelles méthodes comme Mutilple-MCTS ou Nested Monte Carlo. MCTS évalue un ensemble de situations de jeu à partir de milliers de fins de parties générées aléatoirement. À mesure que les simulations sont produites, le programme oriente dynamiquement sa recherche vers les coups les plus prometteurs. En particulier, MCTS a suscité l'intérêt de la communauté car elle obtient de remarquables performances sans avoir pour autant recours à de nombreuses connaissances expertes a priori. Dans cette thèse, nous avons choisi d'aborder MCTS comme un système apprenant à part entière. Les simulations sont alors autant d'expériences vécues par le système et les résultats sont autant de renforcements. L'apprentissage du système résulte alors de la complexe interaction entre deux composantes : l'acquisition progressive de représentations et la mobilisation de celles-ci lors des futures simulations. Dans cette optique, nous proposons deux approches indépendantes agissant sur chacune de ces composantes. La première approche accumule des représentations complémentaires pour améliorer la vraisemblance des simulations. La deuxième approche concentre la recherche autour d'objectifs intermédiaires afin de renforcer la qualité des représentations acquises. Les méthodes proposées ont été appliquées aux jeu de Go et du Clobber solitaire impartial. La dynamique acquise par le système lors des expérimentations illustre la relation entre ces deux composantes-clés de l'apprentissage / Monte Carlo Tree Search (MCTS) has been initially introduced for the game of Go but has now been applied successfully to other games and opens the way to a range of new methods such as Multiple-MCTS or Nested Monte Carlo. MCTS evaluates game states through thousands of random simulations. As the simulations are carried out, the program guides the search towards the most promising moves. MCTS achieves impressive results by this dynamic, without an extensive need for prior knowledge. In this thesis, we choose to tackle MCTS as a full learning system. As a consequence, each random simulation turns into a simulated experience and its outcome corresponds to the resulting reinforcement observed. Following this perspective, the learning of the system results from the complex interaction of two processes : the incremental acquisition of new representations and their exploitation in the consecutive simulations. From this point of view, we propose two different approaches to enhance both processes. The first approach gathers complementary representations in order to enhance the relevance of the simulations. The second approach focuses the search on local sub-goals in order to improve the quality of the representations acquired. The methods presented in this work have been applied to the games of Go and Impartial Solitaire Clobber. The results obtained in our experiments highlight the significance of these processes in the learning dynamic and draw up new perspectives to enhance further learning systems such as MCTS

Il existe des algorithmes en meilleur d'abord efficace pour la résolution des jeux déterministes à deux joueurs et à deux issues.Nous proposons un cadre formel pour la représentation de tels algorithmes en meilleur d'abord.Le cadre est suffisamment général pour exprimer des algorithmes populaires tels Proof Number Search, Monte Carlo Tree Search, ainsi que l'algorithme Product Propagation.Nous montrons par ailleurs comment adapter ce cadre à deux situations plus générales: les jeux à deux-joueurs à plusieurs issues, et le problème de model checking en logique modale K.Cela donne lieu √† de nouveau algorithmes pour ces situations inspirés des méthodes Proof Number et Monte Carlo.La technique de l'élagage alpha-beta est cruciale dans les jeux à actions séquentielles.Nous proposons une extension de cette techniques aux stacked-matrix games, une généralisation des jeux à deux joueurs, à information parfaite et somme nulle qui permet des actions simultanées. / Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves.

The Physical Uplink Control Channel (PUCCH), which is mainly used to transmit Uplink Control Information (UCI), is a key component to enable the 5G NR system. Compared to LTE, NR specifies a more flexible PUCCH structure to support various applications and use cases. In the literature, however, an optimized solution that exploits those degrees of freedom is missing and fixed-heuristic solutions are just implemented in current 5G networks. Consequently, the predefined PUCCH format configuration is inefficient because it proposes a one-size-fits-all solution. In short, the number of symbols dedicated to PUCCH resources are often pre-determined and fixed without considering the UE’s specific needs and requirements. Failure to exploit the diversity of PUCCH format configurations and sticking to the one-size-fits-all solution, translates into a poor PUCCH resource allocation in the physical grid. To overcome this, a solution is presented by introducing a more efficient PUCCH re-distribution algorithm that exploits the same Physical Resource Block (PRB) domain. This leads into a combinatorial optimization problem with the objective of minimizing the PRBs utilization while maximizing the number of resources allocated and, in essence, the number of UEs “served”. For this purpose, we utilize a Monte Carlo Tree Search (MCTS) method to find the optimal puzzle on the grid, which offers clear advantages in search time benchmarked against an exhaustive search method. A wide variety of cases and scenario-dependent solutions are allowed using this puzzling technique. Overall results indicate that the optimal solutions devised by MCTS in conjunction with the new resource allocation algorithm bring substantial improvement compared to the one-size-fits-all baseline. In particular, this novel implementation, nonexistent to date in the 3GPP standard, reduces the dedicated PUCCH resource region by 1=6 without sacrificing any user’s allocation, while reusing the remaining PRBs (an increase of up to 11:36%) for the UL data channel or PUSCH. As a future work, we expect to observe similar improvements in higher layers metrics and KPIs, once link-level reception details are implemented and simulated for UL control channels based on our resource allocation solution. / PUCCH, som huvudsakligen används för att överföra UCI, är en nyckelkomponent för att möjliggöra 5G NR-systemet. Jämfört med LTE specificerar NR en mer flexibel PUCCH-struktur för att stödja olika tillämpningar och användningsfall. I litteraturen saknas dock en optimerad lösning som utnyttjar dessa frihetsgrader, och fasta heuristiska lösningar har bara implementerats i nuvarande 5G-nät. Följaktligen är den fördefinierade konfigurationen av PUCCH-formatet ineffektiv eftersom den föreslår en lösning som passar alla. Kort sagt, antalet symboler som är avsedda för PUCCH-resurser är ofta förutbestämda och fastställda utan att man tar hänsyn till UE:s specifika behov och krav. Om man inte drar nytta av den mångfald av PUCCH-formatkonfigurationer och håller sig till en lösning som passar alla, kommer det att leda till en dålig PUCCH-resursallokering i det fysiska resursnätet. För att lösa detta presenteras en lösning genom att införa en effektivare algoritm för omfördelning av PUCCH som utnyttjar samma PRB-domän. Detta leder till ett kombinatoriskt optimeringsproblem med målet att minimera PRB-utnyttjandet och samtidigt maximera antalet tilldelade resurser och, i huvudsak, antalet betjänadeänvändare. För detta ändamål använder vi en MCTS-metod för att hitta det optimala pusslet på rutnätet, vilket ger klara fördelar i söktid jämfört med en uttömmande sökmetod. En mängd olika fall och scenarioberoende lösningar tillåts med hjälp av denna pusselteknik. De övergripande resultaten visar att de optimala lösningarna som MCTS har tagit fram tillsammans med den nya resursfördelningsalgoritmen ger avsevärda förbättringar jämfört med den grundläggande lösningen med en enda lösning som passar alla. Denna nya implementering, som hittills inte funnits i 3GPP-standarden, minskar det dedikerade PUCCH-resursområdet med 1=6 utan att offra någon användarallokering, samtidigt som de återstående PRB:erna återanvänds (en ökning med upp till 11:36%) för UL-datakanalen eller PUSCH. Som ett framtida arbete förväntar vi oss att observera liknande förbättringar i mätvärden och KPI:er på högre nivåer, när mottagningsdetaljer på länknivå har genomförts och simulerats för uplink-kontrollkanaler baserade på vår resursallokeringslösning.