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 jugado en un tablero de n x n casillas, con piezas en cada lado. Un sudoku generalizado incluye sudokus construidos sobre una cuadrícula de n x n casillas.
Sudoku (4×4)
Sudoku (9×9)
Sudoku (25×25)
El Sudoku generalizado incluye rompecabezas de diferentes tamaños
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 un número exponencial de movimientos 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-completo. El ajedrez generalizado, go (con reglas japonesas de ko), Quixo,[3] y las damas son EXPTIME-completos.[4][5][6]
Reisch, Stefan (1 de junio de 1981). «Hex ist PSPACE-vollständig». Acta Informatica(en alemán)15 (2): 167-191. ISSN 1432-0525. doi:10.1007/BF00288964. Consultado el 26 de febrero de 2021.
Iwata, Shigeki; Kasai, Takumi (31 de enero de 1994). «The Othello game on an n × n board is PSPACE-complete». Theoretical Computer Science(en inglés)123 (2): 329-340. ISSN 0304-3975. doi:10.1016/0304-3975(94)90131-7. Consultado el 26 de febrero de 2021.
«QUIXO is EXPTIME-complete». Information Processing Letters(en inglés)162: 105995. 1 de octubre de 2020. ISSN 0020-0190. doi:10.1016/j.ipl.2020.105995. Consultado el 26 de febrero de 2021.
Fraenkel, Aviezri S; Lichtenstein, David (1 de septiembre de 1981). «Computing a perfect strategy for n × n chess requires time exponential in n». Journal of Combinatorial Theory, Series A(en inglés)31 (2): 199-214. ISSN 0097-3165. doi:10.1016/0097-3165(81)90016-9. Consultado el 26 de febrero de 2021.
Robson, J. M. (1983), «The complexity of Go», Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413-417.
Robson, J. M. (1 de mayo de 1984). «N by N Checkers is Exptime Complete». SIAM Journal on Computing13 (2): 252-267. ISSN 0097-5397. doi:10.1137/0213018. Consultado el 26 de febrero de 2021.
Datos:Q5532477
Enero 14, 2023
juego, generalizado, teoría, complejidad, computacional, juego, generalizado, juego, rompecabezas, generalizado, para, pueda, jugar, tablero, cuadrícula, cualquier, tamaño, ejemplo, ajedrez, generalizado, juego, ajedrez, jugado, tablero, casillas, piezas, cada. En la teoria 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 cuadricula de cualquier tamano Por ejemplo el ajedrez generalizado es el juego de ajedrez jugado en un tablero de n x n casillas con piezas en cada lado Un sudoku generalizado incluye sudokus construidos sobre una cuadricula de n x n casillas Sudoku 4 4 Sudoku 9 9 Sudoku 25 25 El Sudoku generalizado incluye rompecabezas de diferentes tamanos La teoria de la complejidad estudia la dificultad asintotica de los problemas por lo que se necesitan generalizaciones de los juegos ya que los juegos en un tamano fijo de tablero son problemas finitos Para muchos juegos generalizados que duran un numero de movimientos polinomiales en el tamano del tablero el problema de determinar si hay una victoria para el primer jugador en una posicion dada es PSPACE completo Hex y reversi generalizados son PSPACE completos 1 2 Para muchos juegos generalizados que pueden durar un numero exponencial de movimientos en el tamano del tablero el problema de determinar si hay una victoria para el primer jugador en una posicion dada es EXPTIME completo El ajedrez generalizado go con reglas japonesas de ko Quixo 3 y las damas son EXPTIME completos 4 5 6 Vease tambien EditarComplejidad en los juegos Teoria de juegos combinatoriosReferencias Editar Reisch Stefan 1 de junio de 1981 Hex ist PSPACE vollstandig Acta Informatica en aleman 15 2 167 191 ISSN 1432 0525 doi 10 1007 BF00288964 Consultado el 26 de febrero de 2021 Iwata Shigeki Kasai Takumi 31 de enero de 1994 The Othello game on an n n board is PSPACE complete Theoretical Computer Science en ingles 123 2 329 340 ISSN 0304 3975 doi 10 1016 0304 3975 94 90131 7 Consultado el 26 de febrero de 2021 QUIXO is EXPTIME complete Information Processing Letters en ingles 162 105995 1 de octubre de 2020 ISSN 0020 0190 doi 10 1016 j ipl 2020 105995 Consultado el 26 de febrero de 2021 Fraenkel Aviezri S Lichtenstein David 1 de septiembre de 1981 Computing a perfect strategy for n n chess requires time exponential in n Journal of Combinatorial Theory Series A en ingles 31 2 199 214 ISSN 0097 3165 doi 10 1016 0097 3165 81 90016 9 Consultado el 26 de febrero de 2021 Robson J M 1983 The complexity of Go Proceedings of the IFIP 9th World Computer Congress on Information Processing 413 417 Robson J M 1 de mayo de 1984 N by N Checkers is Exptime Complete SIAM Journal on Computing 13 2 252 267 ISSN 0097 5397 doi 10 1137 0213018 Consultado el 26 de febrero de 2021 Datos Q5532477 Obtenido de https es wikipedia org w index php title Juego generalizado amp oldid 141246245, wikipedia, wiki, leyendo, leer, libro, biblioteca,
