Implementación de números surrealistas para juegos.

11

Hay una muy buena construcción por Conway de números surrealistas. Son "números" que contienen números reales y ordinales, están totalmente ordenados y tienen todas las propiedades de un campo (excepto que no forman un conjunto sino una clase).

Vea, por ejemplo, este pdf o Wikipedia para una introducción.

Se pueden generalizar aún más a los llamados "juegos", que se introdujeron originalmente para estudiar juegos combinatorios. La motivación original de Conway era analizar el juego de Go , en particular el final del juego es especialmente adecuado para ser modelado con "juegos surrealistas".

Mi pregunta es: ¿sabe si alguien ha implementado este enfoque en una IA (es decir, un jugador de computadora) para mejorar su nivel en un juego? Estoy especialmente interesado en el caso de Go, pero también en otros. Si no, ¿hay algún obstáculo o una razón por la cual no sería una buena idea?

reference-request gt.game-theory implementation board-games combinatorial-game-theory Denis
fuente
1
Según el libro "Mathematical Go", parece que solía haber un programa complementario de Raymond Chen para resolver los problemas finales del libro, pero no sé dónde se puede encontrar. También tengo un vago recuerdo de Berlekamp haciendo referencia a "Go explorer", que podría mencionarse en el documento "Smart game board and go explorer: un estudio en software e ingeniería del conocimiento". Sin embargo, no creo que la teoría de juegos combinatorios se use realmente en los mejores programas de Go en este momento.
Mark S.
3
Si recuerdo correctamente (tal vez no como lo fue hace mucho tiempo), según David Wolfe (coautor de Mathematical Go), uno puede inventar posiciones de final de juego de Go donde los mejores jugadores profesionales tienden a jugar de manera no óptima por igual como punto, mientras que el enfoque de la teoría del juego Conway / Berlekamp / Wolfe permite calcular el óptimo con relativa facilidad. Sin embargo, tales posiciones son artificiales. Este fenómeno es raro en los juegos que surgen en el juego real.
Neal Young

Respuestas:

8

No tengo una respuesta a su pregunta sobre si la teoría de los juegos de Conway se ha utilizado para crear programas de juegos, pero aún así podría estar interesado en Combinatorial Game Suite , "un programa de código abierto para ayudar a la investigación en combinatoria teoría del juego "(que aprendí por primera vez aquí ). Incluye una implementación de varias operaciones estándar en juegos de Conway en forma canónica, así como un lenguaje de scripting para describir nuevos juegos.

Noam Zeilberger
fuente
3

En algunas búsquedas, no parece haber muchas implementaciones generales publicadas de números surrealistas. Heres una implementación de números surrealistas en coq .

  • Números surrealistas en coq / Mamane, TYPES'04 Actas de la conferencia internacional de 2004 sobre Tipos de pruebas y programas

    Los números surrealistas forman un campo totalmente ordenado (conmutativo), que contiene copias de los reales y (todos) los ordinales. He codificado la mayor parte de la estructura del anillo de números surrealistas en Coq. Esta codificación se basa en la codificación de Aczel de la teoría de conjuntos en la teoría de tipos.

    Este artículo discute en particular los puntos de definición o prueba en los que tuve que divergir de Conway o de la manera más natural, como la separación de la inducción-recursión simultánea en dos inducciones, transformando la definición del orden en una definición mutuamente inductiva de "a lo sumo" y "al menos" y ajustando los esquemas de inducción / recursión bastante complicados en la teoría de tipos de Coq.

Hay algunas implementaciones parciales de la aritmética surrealista para un juego llamado hackenbush (Davis) popularizado por Conway, Berlekamp y Guy del cual hay algunas referencias.

Go es de hecho una de las áreas de vanguardia de la investigación de IA del juego (considerada significativamente más difícil que el ajedrez que ocupó la IA durante décadas), pero parece que hay poca investigación específicamente sobre el uso de números surrealistas para modelarlo / jugarlo. Go se considera una frontera para los algoritmos de aprendizaje automático / IA porque también tiene un estado / distinción relativamente único en el sentido de que los mejores algoritmos basados ​​en software ("todavía / actualmente") no superan a los jugadores humanos campeones.

vea esta referencia The Mystery of Go, el antiguo juego que las computadoras aún no pueden ganar (Wired mag) para una encuesta aproximada decente de las técnicas / investigadores / líderes actuales de Go AI.

vzn
fuente