Juego generalizado

Juego generalizado para que pueda jugarse en un tablero o cuadrícula de cualquier tamaño.

Sudoku generalizado incluye rompecabezas de diferentes tamaños.

En la teoría de la complejidad computacional , un juego generalizado es un juego o rompecabezas que se ha generalizado para que pueda jugarse en un tablero o cuadrícula de cualquier tamaño. Por ejemplo, el ajedrez generalizado es el juego de ajedrez que se juega sobre un tablero, con piezas a cada lado. El Sudoku generalizado incluye Sudokus construidos sobre una cuadrícula. ${\displaystyle n\times n}$ ${\displaystyle 2n}$ ${\displaystyle n\times n}$

La teoría de la complejidad estudia la dificultad asintótica de los problemas, por lo que se necesitan generalizaciones de los juegos, ya que los juegos en un tamaño fijo de tablero son problemas finitos.

Para muchos juegos generalizados que duran un número polinómico de movimientos en el tamaño del tablero, el problema de determinar si hay una victoria para el primer jugador en una posición determinada es PSPACE-completo . El hexadecimal generalizado y el reversi son completos en PSPACE. ^{[1] [2]}

Para muchos juegos generalizados que pueden durar un número de movimientos exponencial en el tamaño del tablero, el problema de determinar si hay una victoria para el primer jugador en una posición determinada es EXPTIME-completo . El ajedrez generalizado , el go (con reglas ko japonesas), Quixo, ^[3] y las damas son EXPTIME-completos. ^{[4] [5] [6]}

Ver también

• Complejidad del juego
• Teoría de juegos combinatoria

Referencias

1. Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica , 15 (2): 167–191, doi :10.1007/bf00288964, S2CID  9125259
2. Iwata, Shigeki; Kasai, Takumi (enero de 1994), "El juego de Otelo en un tablero es PSPACE completo", Ciencias de la Computación Teórica , 123 (2): 329–340, doi :10.1016/0304-3975(94)90131-7 ${\displaystyle n\times n}$
3. Mishiba, Shohei; Takenaga, Yasuhiko (2 de julio de 2020). "QUIXO es EXPTIME completo". Cartas de procesamiento de información . 162 : 105995. doi : 10.1016/j.ipl.2020.105995 . ISSN  0020-0190.
4. Fraenkel, Aviezri S.; Lichtenstein, David (septiembre de 1981), "Calcular una estrategia perfecta para el ajedrez requiere un tiempo exponencial en ", Journal of Combinatorial Theory , Serie A, 31 (2): 199–214, doi :10.1016/0097-3165(81)90016- 9 ${\displaystyle n\times n}$ ${\displaystyle n}$
5. Robson, JM (1983), "La complejidad de Go", Actas del 9º Congreso Mundial de Informática del IFIP sobre procesamiento de información : 413–417
6. Robson, JM (mayo de 1984), " by checkers is Exptime complete", SIAM Journal on Computing , 13 (2), Sociedad de Matemáticas Industriales y Aplicadas ({SIAM}): 252–267, doi :10.1137/0213018 ${\displaystyle N}$ ${\displaystyle N}$