¿Qué juegos populares se han estudiado matemáticamente?

Question

Estoy planeando algunos proyectos de investigación que podría hacer con estudiantes universitarios, y se me ocurrió que los problemas de análisis de juegos podrían ser apropiados. Como teórico de la homotopía abstracta, no tengo experiencia en esto, así que escribo para pedir ayuda. Creo que los estudiantes estarán más interesados en los juegos populares (en los EE.UU., para ser precisos), es decir, cosas a las que podrían haber jugado de pequeños, por ejemplo, Monopoly, Clue, Battleship, Sorry, Settlers of Catan, Dominion, Scrabble, Risk, Uno, Connect Four, Othello, Candyland, Checkers, bridge, war, gin rummy, etc. Supongo que los juegos de móvil también serían interesantes, pero no sé nada de ellos. Escribo para hacerme una idea de la bibliografía, para asegurarme de que no duplico algo que ya se ha hecho, para inspirarme en los tipos de preguntas que podríamos investigar y para ver dónde se publican artículos como éste.

Estoy buscando artículos publicados que lleven a cabo un análisis matemático, por ejemplo, que demuestren qué jugador gana con el juego óptimo, que demuestren que un juego es NP-duro, o que analicen las probabilidades (por ejemplo, la probabilidad de que no haya ningún conjunto en el juego Set, si se muestran 12 cartas).

Ya estoy al tanto de la pregunta " ¿Qué juegos populares son los más matemáticos? ", pero está pidiendo algo diferente. No obstante, en ese enlace ya se habla de algunas matemáticas relacionadas con Ajedrez , Ir a , backgammon , acorazado , póquer , buscaminas , mastermind , conectar cuatro , Mafia , Magic: The Gathering y algunos juegos para teléfonos móviles: "Empujando bloques" , "Pixelated" (en BlackBerry) alias "Flood-It" (en iPhone) . Sin embargo, no da referencias publicadas de todos estos juegos, y no habla de otros juegos populares, por ejemplo, juegos de esta lista . He añadido enlaces arriba a lo más cercano que he podido encontrar a una referencia publicada, para dar una idea de lo que estoy buscando.

Por último, soy consciente de que los deportes se pueden analizar matemáticamente, así que no es necesario escribir una respuesta sobre béisbol, baloncesto, etc. Además, me gustaría evitar respuestas sobre juegos que la gente no juega realmente en el mundo real, como el Nim, el subconjunto para llevar, etc. Hay un montón de ejemplos en la otra pregunta de mathoverflow, pero no creo que capten el interés de los estudiantes de la misma manera.

Answer 1

Hace unos años se examinaron varios juegos clásicos de Nintendo (como Mario, Donkey Kong y Legend of Zelda) desde el punto de vista de la complejidad computacional. Demostraron que las versiones generalizadas de estos juegos son difíciles de NP, y en algunos casos difíciles de PSPACE.

Greg Aloupis, Erik D. Demaine, Alan Guo, y Giovanni Viglietta, "Classic Nintendo games are (computationally) hard," Informática teórica 586 (2015), enlace

Answer 2

Hexágono ( https://en.wikipedia.org/wiki/Hex_(juego_de_tablero) ) es un juego de mesa que fue desarrollado por John Nash (y de forma independiente y anterior, Piet Hein). Es interesante desde el punto de vista matemático por varios motivos. Por ejemplo, a diferencia de algo como el ajedrez, es fácil ver que bajo un juego óptimo el primer jugador ganará una partida de Hex. Pero aunque se sabe que el primer jugador debería ganar, incluso para tamaños de tablero relativamente pequeños no se sabe cuál es esta estrategia óptima. Sin embargo, hace aproximadamente una década, un grupo de probabilistas demostró algo bastante sorprendente: si añadimos un poco de aleatoriedad al juego del Hex, es bastante fácil describir la estrategia óptima. En concreto, Peres-Schramm-Sheffield-Wilson ( https://arxiv.org/abs/math/0508580 ) consideraron el Hex de "turno aleatorio", en el que se lanza una moneda cada turno y el jugador que ganó el lanzamiento de la moneda puede colocar una pieza ese turno. Demostraron que este juego está estrechamente relacionado con la teoría de la percolación y, en particular, que el mejor espacio en el que colocar una pieza es el que tiene más probabilidades de ser "crítico" en una percolación aleatoria de los espacios abiertos del tablero (este movimiento óptimo puede calcularse rápidamente, por ejemplo, mediante métodos de Monte Carlo con cadena de Markov).

Answer 3

El juego de mesa [Monopolio](https://en.wikipedia.org/wiki/Monopoly(game))_ se utiliza a menudo para explicar las cadenas de Markov a los profanos. Ian Stewart tiene un par de Recreaciones matemáticas artículos al respecto en Scientific American .

El primero (en el número de abril de 1996) lleva por título "¿Qué tan justo es el monopolio?" (Se puede encontrar una copia aquí .)

El segundo (en el número de octubre de 1996) se titula "Monopoly Revisited" (se puede encontrar una copia del mismo aquí .)

Answer 4

OMI uno de los trabajos recientes más importantes relacionados con la complejidad computacional de los juegos (de puzzle) es el Modelo de computación de lógica de restricciones no determinista desarrollado por Robert A. Hearn y Erik D. Demaine:

Robert A. Hearn y Erik D. Demaine, "Games, Puzzles, and Computation", 2009

El marco puede utilizarse para demostrar fácilmente la complejidad de la generalización de muchos juegos de rompecabezas de un solo jugador y de dos jugadores (se pueden encontrar muchos ejemplos en el libro).

También puede encontrar otros ejemplos (originales) en mi sitio (debido a la falta de tiempo, muchos de ellos son todavía borradores de resultados no publicados). He escogido algunos de ellos de la Colección de puzzles portátiles de Simon Tatham y probaron su complejidad por diversión. Así que creo que otra buena fuente de "ideas" son los juegos de rompecabezas casuales que están disponibles en línea (en flash/html5); puedes hacer una búsqueda en google para encontrar los más reproducidos.

Tenga en cuenta que también hay muchos " problemas abiertos "; por ejemplo, la complejidad de 1x1 Rush Hour La complejidad de Bloqueo lunar sin bloques fijos, si algunos juegos de bloques caídos que son NP-difíciles están contenidos en NP, y así sucesivamente ... puedes probarlos pero las pruebas probablemente no sean tan fáciles :-D

Answer 5

Formas de ganar sus juegos matemáticos (enlace de Wikipedia) por Berlekamp, Conway y Guy, 1982.

Este es un libro que trata sobre los juegos de información completa para dos jugadores. Es muy bueno. Aunque la mayoría de los juegos del libro no son en absoluto populares, algunos sí lo son. El artículo de Wikipedia ofrece una lista parcial.

El libro se basa en un libro anterior Sobre los números y los juegos (Wikipedia) de Conway, 1976. Este libro anterior es más matemático y menciona muchas menos partidas.

Los métodos de estos libros pueden utilizarse para cualquier juego de este tipo. Berlekamp ha escrito posteriormente varios artículos sobre el Go y el ajedrez.