BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:5317@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20240910T110000
DTEND;TZID=Europe/Paris:20240910T120000
DTSTAMP:20240902T072632Z
URL:https://www.i2m.univ-amu.fr/evenements/jeux-positionnels-maker-breaker
 /
SUMMARY:Florian Galliot (I2M): Jeux positionnels Maker-Breaker
DESCRIPTION:Florian Galliot: Les jeux positionnels sont une famille de jeux
  à deux joueurs incluant le tic-tac-toe\, Hex ou encore Sim. Le plateau d
 e jeu est un hypergraphe\, i.e. la donnée d'un ensemble de sommets et un 
 ensemble d'(hyper)arêtes qui sont des sous-ensembles de sommets. Tour à 
 tour\, Alice et Bob sélectionnent des sommets un par un\, avec des object
 ifs dépendant de la convention choisie. Cet exposé traite de résultats 
 récents sur la convention "Maker-Breaker" : le but d'Alice ("Maker") est 
 de posséder tous les sommets d'une quelconque arête\, tandis que le but 
 de Bob ("Breaker") est de l'en empêcher. Comme il n'y a pas de partie nul
 le possible\, seules deux issues sont possibles sur un hypergraphe donné 
 : soit Maker a une stratégie gagnante\, soit Breaker a une stratégie gag
 nante. Déterminer l'issue est un problème algorithmique difficile\, qui 
 est PSPACE-complet [Schaefer\, 1978] même restreint aux hypergraphes dont
  toutes les arêtes sont de taille 6 [Rahman & Watson\, 2021]. Nous étudi
 ons ce problème dans les hypergraphes dont toutes les arêtes sont de tai
 lle au plus 3 : nous y obtenons une caractérisation structurelle de l'iss
 ue du jeu\, dont nous déduisons un algorithme de résolution en temps pol
 ynomial. Nous présentons également quelques résultats algorithmiques co
 ncernant une nouvelle version de ce jeu\, où on ajoute sur l'ensemble des
  sommets un ordre partiel limitant les coups légaux\, à la manière du P
 uissance-4.\n
CATEGORIES:Séminaire,Ernest
LOCATION:I2M Luminy - TPR2\, Salle de Séminaire 304-306 (3ème étage)\, 1
 63 Avenue de Luminy\, Marseille\, 13009\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=163 Avenue de Luminy\, Mars
 eille\, 13009\, France;X-APPLE-RADIUS=100;X-TITLE=I2M Luminy - TPR2\, Sall
 e de Séminaire 304-306 (3ème étage):geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20240331T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR