Analyses de dépendances et méthodes Monte-Carlo dans les jeux de réflexion

Collection

Informatique

Citation

Helmstetter, Bernard, “Analyses de dépendances et méthodes Monte-Carlo dans les jeux de réflexion,” Bibliothèque numérique Paris 8, accessed October 1, 2020, https://octaviana.fr/document/126279233.

About

Nous explorons deux familles de techniques de programmation des jeux de réflexion : des techniques de Monte-Carlo et des techniques de recherche permettant d'exploiter la faible dépendance entre différentes parties d'un jeu. Ces techniques sont appliquées à des jeux à un ou deux joueurs : un jeu de patience à un joueur appelé Montana, le jeu de Go, et un puzzle à un joueur appelé le Morpion solitaire. Nous présentons un algorithme appelé transpositions incrémentales, que nous appliquons d'abord à Montana ; nous y appliquons aussi un algorithme appelé recherche par blocs. Nous abordons, au Go, la transitivité des connexions, et nous développons l'approche de Monte-Carlo, obtenant un programme particulièrement simple. Au Morpion solitaire, l'application de l'algorithme des transpositions incrémentales combiné à une parallélisation de la recherche mène à un record pour une variante de ce jeu.

We explore two families of game programming methods: Monte-Carlo methods, and methods that exploit the weak dependencies between parts of a game. Those methods are applied to one and two-player games: a solitaire card game called Montana, the game of Go, and a one-player puzzle called Morpion solitaire. We describe an algorithm called incremental transpositions which we first apply to Montana; we also apply an algorithm called block search. We study the transitivity of connections in the game of Go and we develop the Monte-Carlo approach, which make a particularly simple program. On Morpion solitaire, applying the algorithm of incremental transpositions and combining with a parallelized search allows us to find a new record for a variant of the game.

Subject

Jeux intellectuels Monte-Carlo, Méthode de Go (jeu)

Creator

Helmstetter, Bernard

Contributor

Cazenave, Tristan (sous la direction de)

Source

Paris 8, BU - Saint-Denis, Magasin 2, 2430TH

Date

2007

Identifier

126279233

License

Toute reproduction même partielle est interdite sans accord exprès de l'auteur

Index

Informatique

Domain (Dewey)

004 Traitement des données. Informatique. Généralités. Dictionnaires