En la teoría de la complejidad computacional , un juego generalizado es un juego o rompecabezas que se ha generalizado para que se pueda jugar en un tablero o cuadrícula de cualquier tamaño. Por ejemplo, el ajedrez generalizado es el juego de ajedrez que se juega en un tablero, con piezas en cada lado. Sudoku generalizado incluye Sudokus construido sobre un red.
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 de movimientos polinomiales en el tamaño del tablero, el problema de determinar si hay una victoria para el primer jugador en una posición dada es PSPACE-completo . Hex y reversi generalizados son PSPACE-completos. [1] [2]
Para muchos juegos generalizados que pueden durar varios movimientos exponenciales en el tamaño del tablero, el problema de determinar si hay una victoria para el primer jugador en una posición dada es EXPTIME-complete . Ajedrez generalizado , go (con reglas japonesas de ko), Quixo , [3] y las damas son EXPTIME-complete. [4] [5] [6]
Ver también
Referencias
- ^ Reisch, Stefan (1981), "Hex ist PSPACE-vollständig", Acta Informatica , 15 (2): 167-191, doi : 10.1007 / bf00288964
- ^ Iwata, Shigeki; Kasai, Takumi (enero de 1994), "The Othello game on antablero es PSPACE-completo ", Ciencias de la computación teóricas , 123 (2): 329–340, doi : 10.1016 / 0304-3975 (94) 90131-7
- ^ Mishiba, Shohei; Takenaga, Yasuhiko (2 de julio de 2020). "QUIXO es EXPTIME-complete" . Cartas de procesamiento de información : 105995. doi : 10.1016 / j.ipl.2020.105995 . ISSN 0020-0190 .
- ^ Fraenkel, Aviezri S .; Lichtenstein, David (septiembre de 1981), "Computación de una estrategia perfecta para el ajedrez requiere tiempo exponencial en ", Journal of Combinatorial Theory , Serie A, 31 (2): 199-214, doi : 10.1016 / 0097-3165 (81) 90016-9
- ^ Robson, JM (1983), "La complejidad de Go", Actas del 9º Congreso Mundial de Computación de la IFIP sobre procesamiento de información : 413–417
- ^ Robson, JM (mayo de 1984), " por checkers is Exptime complete ", SIAM Journal on Computing , Society for Industrial & Applied Mathematics ({SIAM}), 13 (2): 252–267, doi : 10.1137 / 0213018