Search algorithms in games are artificial intelligence methods for playing such games. Unfortunately, there is no study on these algorithms that evaluates the generality of their performance. We propose to address this gap in the case of two-player zero-sum games with perfect information. Furthermore, we propose a new search algorithm and we show that, for a short search time, it outperforms all studied algorithms on all games in this large experiment and that, for a medium search time, it outperforms all studied algorithms on 17 of the 22 studied games.1. Introduction Games have numerous applications, far beyond the obvious ones (the video game and board game industries) and the slightly less obvious ones (economics, defense, and also education through serious games). In fact, all computational problems can naturally be reformulated in terms of games. Game search algorithms are therefore general-purpose artificial intelligence techniques for problem-solving.

In this paper, we extend the Descent framework, which enables learning and planning in the context of two-player games with perfect information, to the framework of stochastic games. We propose two ways of doing this, the first way generalizes the search algorithm, i.e. Descent, to stochastic games and the second way approximates stochastic games by deterministic games. We then evaluate them on the game EinStein wurfelt nicht! against state-of-the-art algorithms: Expectiminimax and Polygames (i.e. the Alpha Zero algorithm). It is our generalization of Descent which obtains the best results. The approximation by deterministic games nevertheless obtains good results, presaging that it could give better results in particular contexts.

In this paper, we propose a qualitative formalism for representing and reasoning about time at different scales. It extends the algebra of Euzenat and overcomes its major limitations, allowing one to reason about relations between points and intervals. Our approach is more expressive than the other algebras of temporal relations: for instance, some relations are more relaxed than those in Allen's algebra, while others are stricter. In particular, it enables the modeling of imprecise, gradual, or intuitive relations, such as "just before" or "almost meet." In addition, we give several results about how a relation changes when considered at different granularities. Finally, we provide an algorithm to compute the algebraic closure of a temporal constraint network in our formalism, which can be used to check its consistency.