ASAbdallah Saffidine

Abdallah Saffidine

*This is an algorithmically generated author record based on publicly available information.

Abdallah Saffidine has a total of 55 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Solving Configuration Problems with Unbounded Cardinalities in COOM

    by Joachim Baumeister, Konstantin Herud, Jan Heuer, Jochen Reutelshöfer, Nicolas Rühling, Abdallah Saffidine, Torsten Schaub

  • Solving Games and All That

    by Abdallah Saffidine

    Résoudre les jeux et le reste: 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.

  • Open Access

    A piecewise approach for the analysis of exact algorithms

    by Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang


  • Open Access

    An Improved Upper Bound on the Threshold Bias of the Oriented-cycle game

    by Anita Liebenau, Abdallah Saffidine, Jeffrey Yang

    We study the $b$-biased Oriented-cycle game where two players, OMaker and OBreaker, take turns directing the edges of $K_n$ (the complete graph on $n$ vertices). In each round, OMaker directs one previously undirected edge followed by OBreaker directing between one and $b$ previously undirected edges. The game ends once all edges have been directed, and OMaker wins if and only if the resulting tournament contains a directed cycle. Bollobás and Szabó asked the following question: what is the largest value of the bias $b$ for which OMaker has a winning strategy? Ben-Eliezer, Krivelevich and Sudakov proved that OMaker has a winning strategy for $b \leq n/2 - 2$. In the other direction, Clemens and Liebenau proved that OBreaker has a winning strategy for $b \geq 5n/6+2$. Inspired by their approach, we propose a significantly stronger strategy for OBreaker which we prove to be winning for $b \geq 0.7845n + O(1)$.

  • A Piecewise Approach for the Analysis of Exact Algorithms

    by Katie Clinch, Serge Gaspers, Zixu He, Abdallah Saffidine, Tiankuang Zhang

  • Open Access

    Enhancing Reinforcement Learning Through Guided Search

    by Jérôme Arjonilla, Abdallah Saffidine, Tristan Cazenave

    With the aim of improving performance in Markov Decision Problem in an Off-Policy setting, we suggest taking inspiration from what is done in Offline Reinforcement Learning (RL). In Offline RL, it is a common practice during policy learning to maintain proximity to a reference policy to mitigate uncertainty, reduce potential policy errors, and help improve performance. We find ourselves in a different setting, yet it raises questions about whether a similar concept can be applied to enhance performance i.e., whether it is possible to find a guiding policy capable of contributing to performance improvement, and how to incorporate it into our RL agent. Our attention is particularly focused on algorithms based on Monte Carlo Tree Search (MCTS) as a guide. MCTS renowned for its state-of-the-art capabilities across various domains, catches our interest due to its ability to converge to equilibrium in single-player and two-player contexts. By harnessing the power of MCTS as a guide for our RL agent, we observed a significant performance improvement, surpassing the outcomes achieved by utilizing each method in isolation. Our experiments were carried out on the Atari 100k benchmark.


  • Open Access

    Fair Railway Network Design

    by Zixu He, Sirin Botan, Jérôme Lang, Abdallah Saffidine, Florian Sikora, Silas Workman

    When designing a public transportation network in a country, one may want to minimise the sum of travel duration of all inhabitants. This corresponds to a purely utilitarian view and does not involve any fairness consideration, as the resulting network will typically benefit the capital city and/or large central cities while leaving some peripheral cities behind. On the other hand, a more egalitarian view will allow some people to travel between peripheral cities without having to go through a central city. We define a model, propose algorithms for computing solution networks, and report on experiments based on real data.

  • Open Access

    Perfect Information Monte Carlo with Postponing Reasoning

    by Jérôme Arjonilla, Abdallah Saffidine, Tristan Cazenave

    Imperfect information games, such as Bridge and Skat, present challenges due to state-space explosion and hidden information, posing formidable obstacles for search algorithms. Determinization-based algorithms offer a resolution by sampling hidden information and solving the game in a perfect information setting, facilitating rapid and effective action estimation. However, transitioning to perfect information introduces challenges, notably one called strategy fusion.This research introduces `Extended Perfect Information Monte Carlo' (EPIMC), an online algorithm inspired by the state-of-the-art determinization-based approach Perfect Information Monte Carlo (PIMC). EPIMC enhances the capabilities of PIMC by postponing the perfect information resolution, reducing alleviating issues related to strategy fusion. However, the decision to postpone the leaf evaluator introduces novel considerations, such as the interplay between prior levels of reasoning and the newly deferred resolution. In our empirical analysis, we investigate the performance of EPIMC across a range of games, with a particular focus on those characterized by varying degrees of strategy fusion. Our results demonstrate notable performance enhancements, particularly in games where strategy fusion significantly impacts gameplay. Furthermore, our research contributes to the theoretical foundation of determinization-based algorithms addressing challenges associated with strategy fusion.%, thereby enhancing our understanding of these algorithms within the context of imperfect information game scenarios.

  • Open Access

    Mixture of Public and Private Distributions in Imperfect Information Games

    by Jérôme Arjonilla, Abdallah Saffidine, Tristan Cazenave

    In imperfect information games (e.g. Bridge, Skat, Poker), one of the fundamental considerations is to infer the missing information while at the same time avoiding the disclosure of private information. Disregarding the issue of protecting private information can lead to a highly exploitable performance. Yet, excessive attention to it leads to hesitations that are no longer consistent with our private information. In our work, we show that to improve performance, one must choose whether to use a player's private information. We extend our work by proposing a new belief distribution depending on the amount of private and public information desired. We empirically demonstrate an increase in performance and, with the aim of further improving performance, the new distribution should be used according to the position in the game. Our experiments have been done on multiple benchmarks and in multiple determinization-based algorithms (PIMC and IS-MCTS).