Joc posicional

Un joc posicional^[1]^[2] és una espècie de joc combinatori per a dos jugadors. Està descrit per:

$X$ Plantilla:Sndun conjunt finito d'elements. A sovint $X$ es diu tauler i els seus elements es denominen posicions.
$ℱ$ Plantilla:Snduna família de subconjunts de $X$ . Estos subconjunts generalment es denominen conjunts guanyadors.
Un criteri per a guanyar el joc.

Durant el joc, els jugadors reclamen alternativament posicions no reclamades anteriorment, fins que un dels jugadors guanya. Si totes les posicions en $X$ es prenen mentres cap jugador guanya, el joc es considera un empat.

L'eixemple clàssic d'un joc posicional és tic-tac-toe. En ell, $X$ conté els 9 quadrats del tauler de joc, $ℱ$ conté les 8 llínees que determinen una victòria (3 horisontals, 3 verticals i 2 diagonals), i el criteri guanyador és: el primer jugador que tinga un conjunt guanyador complet gana. Atres eixemples de jocs posicionals són Hex i el joc de canvi de Shannon.

Per a cada joc posicional hi ha exactament tres opcions: o el primer jugador té una estratègia guanyadora , o el segon jugador té una estratègia guanyadora, o abdós jugadors tenen estratègies per a fer complir un empat.^[2] La principal qüestió d'interés en l'estudi d'estos jocs és quin d'estes tres opcions es manté en qualsevol joc en particular.

Un joc posicional és finito, determinista i té informació perfecta; per lo tant, en teoria, és possible crear l'arbre complet del joc i determinar quin d'estes tres opcions és vàlida. En la pràctica, no obstant, l'arbre del joc pot ser enorme. Per lo tant, els jocs posicionals generalment s'analisen per mig de tècniques combinatòries més sofisticades.

Terminologia alternativa

A sovint, l'entrada a un joc posicional es considera un hipergrafo. En este cas:

Els elements de $X$ es diuen vèrtiços (o punts ), i es denoten per V;
Els elements de $ℱ$ es denominen vores (o hiperredges ) i es denoten per I o H.

Variants

Hi ha moltes variants de jocs posicionals, que diferixen en les seues regles i en els seus criteris de guany.

Diferents criteris guanyadors

Joc posicional fort (també cridat jugue Creador-Creador): el primer jugador en reclamar tots els elements d'un set guanyador gana. Si el joc termina en tots els elements del tauler reclamats, pero cap jugador ha reclamat tots els elements d'un conjunt guanyador, és un empat. Un eixemple és el clàssic tic-tac-toe.
Jugue Creador-Destructor: els dos jugadors es diuen Creador i Destructor. Creador guanya en reclamar tots els elements d'un conjunt guanyador. Si el joc termina en tots els elements del tauler reclamats i Creador encara no ha guanyat, llavors Destructor gana. Els empats no són possibles. Un eixemple és el joc de canvi de Shannon.
Joc de Evitador-Ejecutor: els jugadors es diuen Evitador i Ejecutor. Ejecutor gana si Evitador alguna volta reclama tots els elements d'un set guanyador. Si el joc termina en tots els elements del tauler reclamats, i Evitador no ha reclamat un set guanyador, Evitador gana. Com en els jocs Creador-Destructor, no és possible empatar. Un eixemple és Sim.
Joc de discrepància

els jugadors es diuen Balanceador i Desbalanceador. Balanceador gana si assegura que en tots els conjunts guanyadors, cada jugador té aproximadament la mitat dels vèrtiços. De lo contrari, Desbalanceador gana.

Diferents regles de joc

Jugue Cambrer-Client (també cridat joc Elector-Elecció): Els jugadors es diuen cambrer i client. En cada tanda, el cambrer elegix dos posicions i li les mostra al client, qui pot elegir una d'elles.
Joc posicional biaixat: Cada joc posicional té una variant biaixada, en la que el primer jugador pot prendre p elements al mateix temps i el segon jugador pot prendre q elements al mateix temps (en la variant insesgada, p = q = 1).

Jocs específics

La següent taula enumera alguns jocs posicionals específics que varen anar àmpliament estudiats en la lliteratura.


Nom	Posicions	Conjunts guanyadors
Tic-tac-toe multidimensional	Tots els quadrats en una caixa multidimensional	Totes les llínees rectes
Joc de canvi de Shannon	Totes les vores d'un grafo	Tots els camins de s a t
Sim	Totes les vores entre 6 vèrtiços	Tots els triànguls [conjunts perdedors]
Joc de caçola (també conegut com a joc de Ramsey)	Totes les vores d'un grafo complet de tamany n	Totes les caçoles de tamany k
Joc de conexió	Totes les vores d'un grafo complet	Tots els spanning trees
Joc de hamiltoncidad	Totes les vores d'un grafo complet	Tots els camins hamiltonianos
Joc de no planaridad	Totes les vores d'un grafo complet	Tots els subgrafos no plans
Joc de progressió aritmètica	Els números {1, ..., n}	Totes les progressions aritmètiques de tamany k

Vore també

Referències

↑ Combinatorial Games: Tic-Tac-Toe Theory, Cambridge: Cambridge University Press. ISBN 978-0-521-46100-9.
↑ ^2,0 ^2,1 Hefetz, Donen; Krivelevich, {{{nom2}}}; Stojaković, {{{nom3}}}; Szabó, {{{nom4}}}. Birkhäuser Verlag GmbH (ed.). Positional Games. Oberwolfach Seminars, Basel. ISBN 978-3-0348-0824-8.

Referències

Este artícul conté una traducció derivada de «Juego posicional» 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.

[beck08-1] Combinatorial Games: Tic-Tac-Toe Theory, Cambridge: Cambridge University Press. ISBN 978-0-521-46100-9.

[pg14-2] 2,0 ^2,1 Hefetz, Donen; Krivelevich, {{{nom2}}}; Stojaković, {{{nom3}}}; Szabó, {{{nom4}}}. Birkhäuser Verlag GmbH (ed.). Positional Games. Oberwolfach Seminars, Basel. ISBN 978-3-0348-0824-8.

[1]

[2]