Researchers from diverse research areas have been brought together in NSO. Many of their research lines are still actively investigated, while several new lines of research have been started in the past four years. We list the main lines.
Evolutionary Game Theory
The main topic in this area is the study of local population dynamics based on the principals of evolutionary game theory. This topic is addressed for many types of settings (e.g. finite/infinite population, overlapping generations, network related neighborhoods, etc.). Other studies focus on periodically changing fitness functions and on multi-state models. The main spotlight for our line of research in this are is on modeling tumor development in cancer.
Games and Networks
Research is focused on topics related to decision making in models of social networks. Among these are studies on (1) coalition formation; (2) the existence of stable solutions and the development of algorithms to find these; (3) the relation between network characteristics and the possibility of achieving efficient coordination.
Stochastic Game Theory
On this topic there are several lines of research. One study is on the existence of subgame perfect equilibria in specially structured classes of stochastic games. Another study is on the existence of symmetric equilibria in stochastic games with symmetric payoffs and transitions. Future research is planned on the numerical calculation of solutions for stochastic games.
Biological and Biomedical Applications of Game Theory
Several studies are done in the area of biological population models (e.g. on strategic choices in a species of parasitoid wasps and on competing types of mites). Other applications are on the evolutionary development of sex mechanisms in plants and on food distribution in bird broods. Recently started projects are focused on bacterial competition, epidemiology related issues and on the efficiency of preventive actions with respect to the development of obesity.
Monte-Carlo Tree Search
Noteworthy results have been achieved on improving the MCTS search method. The results are in the domains of (1) selection, (2) backpropagation strategies, (3) parallelization of MCTS, (4) opening book, (5) integrating evaluation functions in MCTS, (6) MCTS for scheduling and optimization purposes, and (7) multi-player MCTS.
General Game Playing
In General Game Playing (GGP) the aim is to create intelligent programs that can automatically learn how to play many different abstract games at an expert level without any human intervention. Monte-Carlo based search methods overcome to some extent the knowledge-acquisition bottleneck. Still, all relevant search-control knowledge required for expert-level play must be discovered using machine-learning techniques during online play. The NWO funded project GoGeneral aims to develop new and more effective methods for online learning of search control, which will lead to improved search algorithms.
The Development of Intelligent Search Techniques
In the field of intelligent search techniques (not Monte-Carlo based) the three main topics of interest are (1) Variable-Depth Search, (2) Proof-Number Search and (3) Multi-Player Search. New search variants have been proposed for each topic. For Variable-Depth Search, Enhanced Realization Probability Search and ChanceProbCut have been introduced. Regarding proof-number search, Randomized Parallel Proof-Number Search and Paranoid Proof Number have been developed. Finally, Best Reply Search has been added to the family of Multi-Player Search variants.
Developing Game Solvers
The NSO Group has a reputation in solving games. Recently, Fanorona and Go boards up to 30 intersections were solved and are planning to solve the 6×6 Go board. These games have been mainly solved by “classic” techniques such as αβ, PNS and retrograde analysis. Currently, it is investigated to which extent MCTS integrated with proving capabilities as done in MCTS-Solver can help in solving games.
Combinatorial Game Theory Combinatorial games are two-player perfect-information converging games, that share the characteristic that the first player unable to move loses. For these games a whole mathematical theory has been developed, the Combinatorial Game Theory (CGT). We have solved many instances of Domineering games, among which is 11 x 11 Domineering, currently the largest Domineering board solved. Other games under investigation are Sprouts, Cram, and k-in-a-Row games. The present focus is on combining CGT with alpha-beta search, for which good results are obtained for Domineering and Clobber.
Algorithmic Graph Theory and Phylogenetic Networks
Phylogenetic networks allow us to quantify and explain how “reticulate” evolutionary events such as horizontal gene transfer can lead to multiple, conflicting evolutionary tree hypotheses. The corresponding optimization problems are computationally challenging and closely related to problems in algorithmic graph theory. Another track of this research involves collaboration with biologists to analyse real biological data. Part of these topics are covered in the NWO funded project Reducing complexity in phylogenetic networks.
NSO members are also available for supervision of bachelor and masters graduation projects, a summary of recent thesis projects is available here. A total of at least 30 possible thesis topics to work on can be found here: NSO-thesis-topics-2016, but students are welcome to drop by for a discussion on what topic would suit them best.