Implémentation de nombres surréalistes pour les jeux

11

Il y a une très belle construction par Conway de nombres surréalistes. Ce sont des "nombres" qui contiennent à la fois des nombres réels et des ordinaux, sont totalement ordonnés et ont toutes les propriétés d'un champ (sauf qu'ils ne forment pas un ensemble mais une classe).

Voir par exemple ce pdf ou Wikipedia pour une introduction.

Ils peuvent être encore plus généralisés aux soi-disant "jeux", qui sont à l'origine introduits pour étudier les jeux combinatoires. La motivation originale de Conway était d'analyser le jeu de Go , en particulier la fin de partie est particulièrement adaptée pour être modélisée avec des "jeux surréalistes".

Ma question est: savez-vous si quelqu'un a implémenté cette approche dans une IA (c'est-à-dire un joueur informatique) pour améliorer son niveau lors d'un jeu? Je suis particulièrement intéressé par le cas de Go, mais aussi par d'autres. Sinon, y a-t-il un obstacle ou une raison pour laquelle ce ne serait pas une bonne idée?

reference-request gt.game-theory implementation board-games combinatorial-game-theory Denis
la source
1
Selon le livre "Mathematical Go", il semble qu'il y ait eu un programme d'accompagnement de Raymond Chen pour résoudre les problèmes de fin de partie du livre, mais je ne sais pas où il peut être trouvé. J'ai aussi un vague souvenir de Berlekamp faisant référence à "Go explorer", qui pourrait être mentionné dans l'article "Smart game board and go explorer: une étude en génie logiciel et en ingénierie des connaissances". Cependant, je ne pense pas que la théorie des jeux combinatoires soit vraiment utilisée dans les meilleurs programmes Go en ce moment.
Mark S.
3
Si je me souviens bien (peut-être pas comme c'était il y a longtemps), selon David Wolfe (co-auteur de Mathematical Go), on peut concocter des positions de fin de jeu Go où les meilleurs joueurs professionnels ont tendance à jouer de manière non optimale par autant comme un point, alors que l'approche de la théorie des jeux Conway / Berlekamp / Wolfe permet de calculer l'optimum relativement facilement. Cependant, ces positions sont artificielles. Ce phénomène est rare dans les jeux qui surviennent en jeu réel.
Neal Young du

Réponses:

8

Je n'ai pas de réponse à votre question de savoir si la théorie des jeux Conway a été utilisée dans la création de programmes de jeu, mais vous pourriez toujours être intéressé par la Combinatorial Game Suite , "un programme open source pour aider la recherche en combinatoire théorie des jeux "(dont j'ai d'abord entendu parler ici ). Il comprend une implémentation de diverses opérations standard sur les jeux Conway sous forme canonique, ainsi qu'un langage de script pour décrire de nouveaux jeux.

Noam Zeilberger
la source
3

sur certaines recherches, il ne semble pas y avoir beaucoup d'implémentations générales publiées de nombres surréalistes. Voici une implémentation de nombres surréalistes en coq .

  • Nombres surréalistes en coq / Mamane, TYPES'04 Actes de la conférence internationale de 2004 sur les types de preuves et de programmes

    Les nombres surréalistes forment un champ totalement ordonné (commutatif), contenant des copies des réels et (tous) des ordinaux. J'ai codé la plupart de la structure en anneau des nombres surréalistes en Coq. Ce codage repose sur le codage d'Aczel de la théorie des ensembles dans la théorie des types.

    Cet article discute en particulier des points de définition ou de preuve où j'ai dû diverger de Conway ou de la manière la plus naturelle, comme la séparation de l'induction-récurrence simultanée en deux inductions, transformant la définition de l'ordre en une définition mutuellement inductive de «au plus» et «au moins» et en adaptant les schémas d'induction / récursivité plutôt compliqués à la théorie des types de Coq.

il existe des implémentations partielles d'arithmétique surréaliste pour un jeu appelé hackenbush (Davis) popularisé par Conway, Berlekamp et Guy dont il y a quelques références.

Go est en effet l'un des domaines de pointe de la recherche sur l'IA de jeu (considéré comme beaucoup plus difficile que les échecs qui ont occupé l'IA pendant des décennies), mais il semble qu'il y ait peu de recherches spécifiquement sur l'utilisation de nombres surréalistes pour le modéliser / jouer. Go est considéré comme une frontière pour les algorithmes d'apprentissage automatique / IA, car il a également un statut / distinction relativement unique en ce sens que les meilleurs algorithmes logiciels ("toujours / actuellement") ne surpassent pas les joueurs humains champions.

voir cette référence The Mystery of Go, le jeu ancien que les ordinateurs ne peuvent toujours pas gagner (Wired mag) pour un aperçu décent des techniques / chercheurs / leads actuels de Go AI.

vzn
la source