Generalized game (original) (raw)
In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid. Complexity theory studies the asymptotic difficulty of problems, so generalizations of games are needed, as games on a fixed size of board are finite problems.
| Property | Value |
|---|---|
| dbo:abstract | In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid. Complexity theory studies the asymptotic difficulty of problems, so generalizations of games are needed, as games on a fixed size of board are finite problems. For many generalized games which last for a number of moves polynomial in the size of the board, the problem of determining if there is a win for the first player in a given position is PSPACE-complete. Generalized hex and reversi are PSPACE-complete. For many generalized games which may last for a number of moves exponential in the size of the board, the problem of determining if there is a win for the first player in a given position is EXPTIME-complete. Generalized chess, go (with Japanese ko rules), , and checkers are EXPTIME-complete. (en) 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. 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. 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, y las damas son EXPTIME-completos. (es) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Minisudoku1.png?width=300 |
| dbo:wikiPageID | 746550 (xsd:integer) |
| dbo:wikiPageLength | 3716 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1099942803 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Reversi dbr:PSPACE-complete dbr:Go_(board_game) dbr:Combinatorial_game_theory dbr:Computational_complexity_theory dbr:Game_complexity dbc:Combinatorial_game_theory dbr:Checkers dbr:Asymptotic dbc:Computational_complexity_theory dbr:Chess dbr:Hex_(board_game) dbr:Sudoku dbr:EXPTIME-complete dbr:Quixo |
| dbp:alt | Sudoku (en) |
| dbp:caption | Sudoku (en) |
| dbp:footer | Generalized Sudoku includes puzzles of different sizes (en) |
| dbp:image | 25 (xsd:integer) Minisudoku1.png (en) Sudoku_Puzzle_R2.png (en) |
| dbp:width | 180 (xsd:integer) |
| dbp:wikiPageUsesTemplate | dbt:Multiple_image dbt:Reflist dbt:Short_description dbt:Comp-sci-theory-stub dbt:Gametheory-stub |
| dct:subject | dbc:Combinatorial_game_theory dbc:Computational_complexity_theory |
| gold:hypernym | dbr:Game |
| rdf:type | dbo:VideoGame |
| rdfs:comment | In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid. Complexity theory studies the asymptotic difficulty of problems, so generalizations of games are needed, as games on a fixed size of board are finite problems. (en) 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. (es) |
| rdfs:label | Juego generalizado (es) Generalized game (en) |
| owl:sameAs | freebase:Generalized game wikidata:Generalized game dbpedia-es:Generalized game https://global.dbpedia.org/id/4kQYZ |
| prov:wasDerivedFrom | wikipedia-en:Generalized_game?oldid=1099942803&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/25by25sudoku.png wiki-commons:Special:FilePath/Minisudoku1.png wiki-commons:Special:FilePath/Sudoku_Puzzle_(Tourmaline)R2.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Generalized_game |
| is dbo:wikiPageWikiLink of | dbr:List_of_computability_and_complexity_topics dbr:Reversi dbr:PSPACE-complete dbr:Rush_Hour_(puzzle) dbr:English_draughts dbr:Game_of_the_Amazons dbr:Game_complexity dbr:EXPTIME dbr:Checkers dbr:Gomoku dbr:List_of_NP-complete_problems dbr:List_of_PSPACE-complete_problems dbr:Atomix_(video_game) |
| is foaf:primaryTopic of | wikipedia-en:Generalized_game |
