Joc generalisat
En la teoria de la complexitat computacional, un joc generalisat és un joc o rompecabezas que s'ha generalisat per a que es puga jugar en un tauler o cuadrícula de qualsevol tamany. Per eixemple, l'escacs generalisat és el joc d'escacs jugat en un tauler de n x n caselles, en peces en cada costat. Un sudoku generalisat inclou sudokus construïts sobre una cuadrícula de n x n caselles.
La teoria de la complexitat estudia la dificultat asintòtica dels problemes, per lo que es necessiten generalisacions dels jocs, ya que els jocs en un tamany fix de tauler són problemes finitos.
Per a molts jocs generalisats que duren un número de moviments polinomiales en el tamany del tauler, el problema de determinar si hi ha una victòria per al primer jugador en una posició donada és PSPACE-complet. Hex i reversi generalisats són PSPACE-complets.[1][2]
Per a molts jocs generalisats que poden durar un número exponencial de moviments en el tamany del tauler, el problema de determinar si hi ha una victòria per al primer jugador en una posició donada és EXPTIME-complet. l'escacs generalisat, go (en regles japoneses de ko), Quixo,[3] i les dames són EXPTIME-complets.[4][5]
Vore també
[editar | editar còdic]Referències
[editar | editar còdic]- ↑ Acta Informatica.15(2)
- 167–191.ISSN 1432-0525.doi:10.1007/BF00288964.Consultat el 2021-02-26.
- ↑ Theoretical Computer Science.123(2)
- 329–340.ISSN 0304-3975.doi:10.1016/0304-3975(94)90131-7.Consultat el 2021-02-26.
- ↑ Information Processing Letters.162
- 105995.ISSN 0020-0190.doi:10.1016/j.ipl.2020.105995.Consultat el 2021-02-26.
- ↑ Journal of Combinatorial Theory, Séries A.31(2)
- 199–214.ISSN 0097-3165.doi:10.1016/0097-3165(81)90016-9.Consultat el 2021-02-26.
- ↑ SIAM Journal on Computing.13(2)
- 252–267.ISSN 0097-5397.doi:10.1137/0213018.Consultat el 2021-02-26.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Juego generalizado» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.