Nested Monte Carlo Search (NMCS) has numerous applications, ranging from chemical retrosynthesis to quantum circuit design. We propose a generalization of NMCS that we named Nested Depth Search (NDS), in which a fixed depth search is used during a higher-level playout to generate the states sent to lower-level exploration. We establish the runtime of NDS and provide algorithms to compute the exact probability distribution of sequences generated by NDS. Experiments with the Set Cover problem and the Multiple Sequence Alignment problem show that NDS outperforms NMCS with the same time budget.

Extensive-form games model strategic interaction between players, with an emphasis on the sequential aspect of decision-making: players take turns to move until an ending is reached, and receive a reward according to which ending is reached. We study the complexity of computing the pure maxmin value for such games, i.e. the maximum reward that a player can guarantee by playing a pure strategy, whatever their opponents play. We focus on two-player and two-team games and perform a systematic study depending on the degree of imperfect information of each player or team: perfect information, perfect recall, or perfect recall for each agent in a team (which we call multi-agent perfect recall). For each combination, we settle the complexity of deciding whether the maxmin value is at least as high as a given threshold. We give a complete complexity picture for three orthogonal settings: games represented explicitly by their game tree; games represented compactly by game rules, for which we propose two new formalisms; games in which the set of strategies of the opponents is restricted to a known set of opponent models.

Games with incomplete information are games that model situations where players do not have common knowledge about the game they play, e.g. card games such as poker or bridge. Opponent models can be of crucial importance for decision-making in such games. We propose algorithms for computing optimal and/or robust strategies in games with incomplete information, given various types of knowledge about opponent models. As an application, we describe a framework for reasoning about an opponent's reasoning in such games, where opponent models arise naturally.

We define a new setting related to the evaluation of AND-OR directed acyclic graphs with partially ordered values. Such graphs arise naturally when solving games with incomplete information (e.g. most card games such as Bridge) or games with multiple criteria. In particular, this setting generalises standard AND-OR graph evaluation and computation of optimal strategies in games with complete information. Under this setting, we propose a new algorithm which uses both alpha-beta pruning and cached values. In this paper, we present our algorithm, prove its correctness, and give experimental results on a card game with incomplete information.

αµ is a search algorithm which repairs two defaults of Perfect Information Monte Carlo search: strategy fusion and non locality. In this paper we optimize αµ for the game of Bridge, avoiding useless computations. The proposed optimizations are general and apply to other imperfect information turn-based games. We define multiple optimizations involving Pareto fronts, and show that these optimizations speed up the search. Some of these optimizations are cuts that stop the search at a node, while others keep track of which possible worlds have become redundant, avoiding unnecessary, costly evaluations. We also measure the benefits of parallelizing the double dummy searches at the leaves of the αµ search tree.

Computer Bridge remains a challenging obstacle for Artificial Intelligence. For the last twenty years, the state-of-the-art playing programs have been using a depth-one Monte Carlo (MC) search approach, associated with an open card solver called Double Dummy Solver (DDS). When increasing the computing resources, the MC approach reaches a plateau, and its playing level cannot be improved. In this work, we study Recursive MC (RMC) for Bridge card play. We show that, with more computing resources, this approach performs better than MC. Rather than using DDS or any domain-dependent simulator, a level N + 1 RMC consists in using a level N RMC playing program as simulator, level-zero RMC being MC. This recursion mechanism can be iterated several times at the cost of increasing the computing time, each time a recursion level is added. This work focusses on card play with no trump in duplicate with either 13 cards per player or 5 cards per player. With 13 cards per player, level-one RMC is superior to MC with a margin of 0.5 trick per card distribution on average, which is statistically significant. This is the first time RMC is applied with success to computer Bridge card play.

Bridge is an incomplete information game which is complex both for humans and for Computer-Bridge programs. The purpose of this paper is to present our work related to the adaptation to Bridge of a recent methodology used for boosting game Artificial Intelligence (AI) by seeking a random seed, or a probability distribution on random seeds, better than the others on a particular game. The Bridge AI Wbridge5 developed by Yves Costel has been boosted with the best seed found on the outcome of these experiments and has won the World Computer-Bridge Championship in September 2016.

In many applications there is a need to represent a large number of data by clustering them in a hierarchy of classes. Our basic representation is a Galois lattice, a structure that exhaustively represents the whole set of concepts that are distinguishable given the instance set and the representation language. What we propose here is a method to reduce the size of the lattice, and thus simplify our view of the data, while conserving its formal structure and exhaustivity. For that purpose we use a preliminary partition of the instance set, representing the association of a "type" to each instance. By redefining the notion of extent of a term in order to cope, to a certain degree (denoted as /spl alpha/), with this partition, we define a particular family of Galois lattices denoted as alpha Galois lattices. We also discuss the related implication rules defined as inclusion of such /spl alpha/-extents.

This paper deals with the representation of multi-valued data by clustering them in a small number of classes organized in a hierarchy and described at an appropriate level of abstraction. The contribution of this paper is three fold. First, we investigate a partial order, namely nesting, relating Galois lattices. A nested Galois lattice is obtained by reducing (through projections) the original lattice. As a consequence it makes coarser the equivalence relations defined on extents and intents. Second we investigate the intensional and extensional aspects of the languages used in our system ZooM. In particular we discuss the notion of α-extension of terms of a class language £. We also present our most expressive language £3, close to a description logic, and which expresses optionality or/and multi-valuation of attributes. Finally, the nesting order between the Galois lattices corresponding to various languages and extensions is exploited in the interactive system ZooM. Typically a ZooM session starts from a propositional language £2 and a coarse view of the data (through α-extension). Then the user selects two ordered nodes in the lattice and ZooM constructs a fine-grained lattice between the antecedents of these nodes. So the general purpose of ZooM is to give a general view of concepts addressing a large data set, then focussing on part of this coarse taxonomy.