L'Enciclopèdia, la wikipedia en valencià

Go i matemàtiques

El joc de go és un dels jocs més populars del món. Com a resultat de les seues regles elegants i simples, el joc ha segut durant molt temps una inspiració per a l'investigació matemàtica. Shen Kuo, un erudit chinenc en el XI, va estimar que el número de possibles posicions en la junta és d'al voltant de 10172 en Dream Pool Essays. En anys més recents, l'investigació del joc per John H. Conway va dur a l'invenció dels números surreales i va contribuir al desenroll de la teoria de jocs combinatoris (en Go Infinitesimals[1] sent un eixemple específic del seu us en go).

Complexitat computacional

El go generalisat es juga en taulers de n × n, i la complexitat computacional de determinar el guanyador en una posició donada del go generalisat depén de manera crucial de les regles del ko.

El go és "casi" en PSPACE, ya que en el joc normal, els moviments no són reversibles, i és solament per mig de la captura que existix la possibilitat de que es repetixquen els patrons necessaris per a una complexitat més difícil.

Sense ko

Sense ko, el go és PSPACE-difícil.[2] Açò es demostra reduint la fòrmula booleana quantificada verdadera, que se sap que és PSPACE-completa, a la geografia generalisada, a la geografia generalisada plana, a la geografia generalisada plana en grau màxim 3, finalment a les posicions del go.

El go en superko no se sap que estiga en PSPACE. Encara que els jocs reals mai semblen durar més de n2 moviments, en general no se sap si hi ha un llímit polinòmic en la llongitut dels jocs de go. Si ho hi haguera, el go seria PSPACE-complet. Tal com està actualment, podria ser PSPACE-complet, EXPTIME-complet o inclús EXPSPACE-complet.

Regla japonesa del ko

Les regles japoneses del ko establixen que solament el ko bàsic, és dir, un moviment que revertix el tauler a la situació anterior, està prohibit. Es permeten situacions repetitives més llargues, lo que potencialment permet que un joc es repetixca per a sempre, com el triple ko, a on hi ha tres kos al mateix temps, lo que permet un cicle de 12 moviments.

En les regles de ko japoneses, Go és EXPTIME-complet.[3]

Regla del superko

La regla de superko (també cridada regla de superko posicional) establix que està prohibida la repetició de qualsevol posició en el tauler que haja ocorregut prèviament. Esta és la regla ko utilisada en la majoria dels conjunts de regles chinencs i nortamericanes.

És un problema obert quin és la classe de complexitat del go baix la regla del superko. Encara que el go en la regla japonesa del ko és EXPTIME-complet, tant el llímit inferior com el superior de la prova de completitud EXPTIME de Robson[3] es trenquen quan s'agrega la regla del superko.


Se sap que és a lo manco PSPACE-hard, ya que la prova[2] de la durea PSPACE del go no es basa en la regla del ko ni en la falta de la regla del ko. També se sap que el go està en EXPSPACE.[4]

Robson[4] va demostrar que si s'agrega la regla superko, és dir, “mai es podrà recrear cap posició anterior”, a certs jocs de dos jugadors que són EXPTIME-complet, llavors els nous jocs serien EXPSPACE-complets. Intuitivamente, açò es deu a que es requerix una cantitat exponencial d'espai inclús per a determinar els moviments llegals des d'una posició, perque l'historial del joc que conduïx a una posició podria ser exponencialment llarc.

Com a resultat, les variants superko (moviments que repetixen una posició anterior en el tauler no estan permeses) del escacs generalisat i les dames són EXPSPACE-complet, ya que l'escacs generalisat[5] i les dames[6] són EXPTIME-complet. No obstant, este resultat no s'aplica al go.[4]

Complexitat de certes configuracions del go

Un final de go comença quan el tauler es dividix en àrees que estan aïllades de totes les demés àrees locals per pedres vives, de modo que cada àrea local té un arbre de joc canònic de tamany polinomial. En el llenguage de la teoria de jocs combinatoris, succeïx quan un joc de go es descompon en una suma de subjuegos en arbres de joc canònics de tamany polinomial.

En eixa definició, els finals de go són PSPACE-difícils.[7]

Açò es demostra en convertir el problema de la fòrmula booleana quantificada, que és PSPACE complet, en una suma de chicotets subjuegos de go (en arbres de joc canònics de tamany polinomial). Tinga's en conte que el document no prova que els finals de go estiguen en PSPACE, per lo que és possible que no estiguen complets en PSPACE.


Determinar qué costat guanya una carrera de captura d'escala és PSPACE-complet, ya siga que la regla japonesa de ko o la regla superko estiga en el seu lloc.[8] Açò es demostra per mig de la simulació de QBF, conegut per ser PSPACE-complet, en escales que reboten al voltant de la taula com a rajos de llum.

Posicions llegals

Ya que cada ubicació en el tauler pot estar buida, negra o blanca, hi ha un total de 3n2 possibles posicions de tauler en un tauler quadrat en llongitut n ; no obstant, no tots són llegals. John Tromp i Farnebäck varen derivar una fòrmula recursiva per a posicions llegals L(m,n) d'un tauler de tamany m i n.[9] El número exacte de L(19,19) es va obtindre en 2016.[10] També troben una fòrmula asintòtica L≈ABm+nCmn, a on A≈0.8506399258457145, B≈0.96553505933837387 i C≈2.975734192043357249381. S'ha estimat que l'univers observable conté al voltant de 1080 àtoms, molt manco que el número de possibles posicions llegals per al tauler de tamany regular (m=n=19). A mida que el tauler es fa més gran, el percentage de posicions llegals disminuïx.

Tamany del tauler n&claves;n 3n2 % llegal L (posicions llegals)[11][12]
1 &claves; 1 3 33.33% 1
2 &claves; 2 81 70.37% 57
3 &claves; 3 19,683 64.40% 12,675
4 &claves; 4 43,046,721 56.49% 24,318,165
5 &claves; 5 847,288,609,443 48.90% 414,295,148,741
9 &claves; 9 4.43426488243 &claves; 1038 23.44% 1.03919148791 &claves; 1038
13 &claves; 13 4.30023359390 &claves; 1080 8.66% 3.72497923077 &claves; 1079
19 &claves; 19 1.74089650659 &claves; 10172 1.20% 2.08168199382 &claves; 10170

Vore també

Notes

  1. ↑ «Go Infinitesimals at Sensei's Library». senseis.xmp.net. Consultat el 2021-04-03.
  2. ↑ 2,0 2,1 «GO Is Polynomial-Space Hard».Journal of the ACM.27(2)
    393–401.ISSN 0004-5411.doi:10.1145/322186.322201.Consultat el 2021-04-03.
  3. ↑ 3,0 3,1 “The complexity of Go” . Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417.
  4. ↑ 4,0 4,1 4,2 «Combinatorial games with exponential space complete decision problems».Mathematical Foundations of Computer Science 1984.Springer.
    498–506.doi:10.1007/BFb0030333.Consultat el 2021-04-03.
  5. ↑ «Computing a perfect strategy for n × n chess requires clave exponential in n».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-04-03.
  6. ↑ «N by N Checkers is Exptime Complete».SIAM Journal on Computing.13(2)
    252–267.ISSN 0097-5397.doi:10.1137/0213018.Consultat el 2021-04-03.
  7. ↑ “Go endgames llaure PSPACE-hard” . More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125–136.
  8. ↑ «Ladders Llaure PSPACE-Complete».Computers and Games.Springer.
    241–249.doi:10.1007/3-540-45579-5_16.Consultat el 2021-04-03.
  9. ↑ «Combinatorics of Go».Computers and Games.Springer.
    84–99.doi:10.1007/978-3-540-75538-8_8.Consultat el 2021-04-03.
  10. ↑ https://tromp.github.io/go/llegal.html 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
  11. ↑ «A094777 - OEIS». oeis.org. Consultat el 2021-04-03.
  12. ↑ https://tromp.github.io/go/gostate.pdf

Referències


Referències


Obtingut de «https://lenciclopedia.org/w/index.php?title=Go_i_matemàtiques&oldid=1595272»