• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Solving Games and All That

Résoudre les jeux et le reste

Saffidine, Abdallah (2013), Solving Games and All That, doctoral thesis prepared under the supervision of Cazenave, Tristan, Université Paris Dauphine, 165 p.

View/Open
2013PA090069.pdf (766.5Kb)
Type
Thèse
Date
2013-07
Pages
165
Metadata
Show full item record
Author(s)
Saffidine, Abdallah
Under the direction of
Cazenave, Tristan
Abstract (FR)
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
Abstract (EN)
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
Subjects / Keywords
Théorie des jeux; Monte-Carlo, Méthode de; Elagage Alpha-beta; Logique Modale K; Proof Number Search; Monte Carlo Tree Search; Intelligence artificielle
JEL
C7 - Game Theory and Bargaining Theory
C15 - Statistical Simulation Methods: General

Related items

Showing items related by title and author.

  • Thumbnail
    Solving breakthrough with Race Patterns and Job-Level Proof Number Search 
    Cazenave, Tristan; Jouandeau, Nicolas; Saffidine, Abdallah (2012) Communication / Conférence
  • Thumbnail
    General Game Playing and the Game Description Language 
    Saffidine, Abdallah (2012) Communication / Conférence
  • Thumbnail
    On the complexity of trick-taking card games 
    Saffidine, Abdallah; Jamain, Florian; Bonnet, Édouard (2013) Communication / Conférence
  • Thumbnail
    Nested Monte Carlo Search for Two-Player Games 
    Cazenave, Tristan; Saffidine, Abdallah; Schofield, Michael John; Thielscher, Michael (2016) Communication / Conférence
  • Thumbnail
    On the Complexity of Connection Games 
    Bonnet, Edouard; Jamain, Florian; Saffidine, Abdallah (2016) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo