Tingnan ang wikitext ng Go at matematika

Ang [[laro]]ng [[Go (laro)|Go]] ay isa sa pinakapopular na laro sa buong [[mundo]]. Dahil sa kaniyang mga eleganteng at simpleng kautusan, ang laro ay matagal na inspirasyon para sa [[matematika]]l na [[pananaliksik]]. Nagtasa si [[Shen Kuo]], isang Tsinong iskolar ng ika-11 na siglo, sa kaniyang [[mga Sanaysay ng Lawa ng mga Panaginip]] ({{lang-zh|t=夢溪筆談|s=梦溪笔谈}}) na dami ng mga posibleng posisyon ng tabla ay mga 10<sup>172</sup>{{citation needed}}. Sa mas kamakailang mga taon, ang pananaliksik ng laro ni [[John Horton Conway]] ay nagdulot ng imbensyon ng mga [[surreal na bilang]] at nag-ambag sa kaunlaran ng [[teorya ng larong kombinatoryal]]. Ang isang espesipikong paggamit ng TLK sa Go ay mga ''Go Infinitesimal''<ref>{{Cite web|title=Go Infinitesimals at Sensei's Library|url=https://senseis.xmp.net/?GoInfinitesimals|access-date=2022-02-10|website=senseis.xmp.net|lang=en}}</ref> (sa Ingles).

== Komputasyonal na komplehidad ==
{{also|Teorya ng komputasyonal na komplehidad}}

Sa heneral nilalaro ang Go sa mga tablang ''n'' × ''n'', at ay [[klaseng komplehidad|komputasyonal na komplehidad]] para magtasa ng nagwagi sa ilang posisyon ng Go ay krusyal na nagdedepende sa [[mga kautusan ng Go|mga kautusang ko]].

Ang Go ay "halos" nasa [[PSPACE]], kasi sa normal na paglalaro, hindi nababawiin ang mga tira, at lang sa pamamagitan ng paghuli may posibilidad ng mga padrong inuulit na kailangan para sa isang mas mahirap na komplehidad.

=== Kung wala ''ko'' ===
Kung wala ''ko'', ang Go ay [[PSPACE-mahirap]].<ref name="sipser1980">{{cite journal|last1=Lichtenstein|first1=David|last2=Sipser|first2=Michael|title=Go Is Polynomial-Space Hard|journal=Journal of the ACM|date=April 1980|volume=27|issue=2|pages=393–401|url=http://webdocs.cs.ualberta.ca/~games/go/seminar/2003/030331/p393-lichtenstein.pdf|doi=10.1145/322186.322201|s2cid=29498352|lang=en}}</ref> Ang pruweba ay sa pamamagitan ng kabawasan ng [[pormulang totoong dinadamihan ni Boole]] ({{lang-en|true quantified Boolean formula}}, o ''TQBF''), na kinikilala bilang PSPACE-kumpleto, sa [[heograpiyang nilalahat]] ({{lang-en|generalized geography}}), sa planar na heograpiyang nilalahat, sa planar na heograpiyang nilalahat na may pinakamataas na digring 3, at sa wakas sa mga posisyong Go.

Hindi alam kung ang Go na may superko ay nasa PSPACE. Maski ang totoong mga laro ay hindi kailanman mukhang magtagal ng mas kay <math>n^2</math> tira, sa heneral hindi alam kung may [[polinomial]] na hangganan sa tagal ng mga larong Go. Kung may, ang Go ay PSPACE-kumpleto, [[EXPTIME]]-kumpleto, o kahit [[EXPSPACE]]-kumpleto.

=== Hapones na kautusang ko ===
Nagsasabi ang Hapones na kautusang ko na bawal lang ang basikong ko, kumbaga, isang tira na nanunumbalik ang tabla sa ''pinakahuling'' posisyon. (Ikumpara ang kautusang superko sa ilalim.) Puwede ang mga paulit-ulit at mas matagal na sitwasyon, kaya sa teorya magpakailanmang nauulit ang isang laro. Halimbawa ang tripleng ko, na may tatlong sabay-sabay na ko, ay tinutulutan ang siklo ng 12 mga galaw.

Kung may Hapones na kautusang ko, ang Go ay EXPTIME-kumpleto.<ref name="robson1983">{{cite journal|last1=Robson|first1=John|title=The complexity of Go|journal=Proceedings of the IFIP 9th World Computer Congress on Information Processing|date=1983|pages=413–417|lang=en}}</ref>

=== Kautusang superko ===
Nagsasabi ang kautusang superko (tinatawag din na posisyonal na kautusang superko) na bawal ang isang ulit ng ''anumang'' posisyon ng tabla. (Ikumpara ang Hapones na kautusang ko sa itaas.) Ito ay kautusang ko na madalas na ginagamit sa [[Tsina]] at [[Estados Unidos]].

Ang [[klaseng komplehidad]] ng Go, sa ilalim ng kautusang superko, ay [[bukas na problema]]. Bagama't EXPTIME-kumpleto ang Go kung may Hapones na kautusang ko, kung idinadagdag ang kautusang superko, sinisira ang parehong mga hangganan (itaas at ibaba) ng pruwebang EXPTIME-pagkakumpleto ni Robson<ref name="robson1983" />.

Alam na ito ay hindi bababa sa PSPACE-mahirap, dahil sa pruweba ni Sipser<ref name="sipser1980" /> ng PSPACE-pagkahirap ng Go ay hindi inaasahan ang kautusang ko o kaniyang kawalan. Alam rin na ang Go ay nasa EXPSPACE.<ref name="robson1984">{{cite book|last1=Robson|first1=J|title=Mathematical Foundations of Computer Science 1984|chapter=Combinatorial games with exponential space complete decision problems|journal=Proceedings of the Mathematical Foundations of Computer Science|volume=176|date=1984|pages=498–506|doi=10.1007/BFb0030333|series=Lecture Notes in Computer Science|isbn=978-3-540-13372-8|lang=en}}</ref>

Ipinakita ni Robson<ref name="robson1984" /> na kung ang kautusang superko, kumbaga, "nauulit ang walang dating posisyon", ay idinadagdag sa ilang mga EXPTIME-kumpletong [[larong dalawang manlalaro]], tapos EXPSPACE-kumpleto ang mga bagong laro. Intuitibo na, ito ay kasi isang [[Pagpapalakas (matematika)|exponensiyal]] na dami ng [[espasyo]] ay kailangan kahit para magtaas ng mga legal na galaw mula sa isang posisyon, kasi ang kasaysayan na laro, hanggang sa itong posisyon, ay puwedeng eksponensiyal na mataas.

Bilang isang resulta, ang mga baryenteng superko para sa [[ahedres]]<ref name="Fraenkel1981">{{cite journal| author = [[Aviezri Fraenkel]] and D. Lichtenstein| title = Computing a perfect strategy for n&times;n chess requires time exponential in n| journal = J. Comb. Theory A| volume = 31| issue = 2| year = 1981| pages = 199–214|doi=10.1016/0097-3165(81)90016-9| doi-access = free|lang=en}}</ref> at [[dama]]<ref name="robson1984checkers">{{cite journal| author = J. M. Robson| title = N by N checkers is Exptime complete| journal = SIAM Journal on Computing| volume = 13| issue = 2| pages = 252–267| year = 1984| doi = 10.1137/0213018|lang=en}}</ref> ay EXPSPACE-kumpleto, kasi ang nilalahit na ahedres at dama ay EXPTIME-kumpleto. Gayunman, hindi nalalapat ang itong resulta sa Go.<ref name="robson1984" />

=== Komplehidad ng ilang mga kumpigurasyong Go ===
PSPACE-kumpleto ang magtasa ng nagwagi ng isang karera para hulihin ang isang hagdan. Pinatutunayan ng [[simulasyon]] ng QBF (Quantum Boolean formula, na kilala bilang PSPACE-kumpleto) sa pamamagitan ng mga hagdan na tumatalbog sa tabla bilang mga [[liwanag na sinag]].<ref>{{cite book|last1=Crâşmaru|first1=Marcel|last2=Tromp|first2=John|author-link2=John Tromp|title=Ladders are PSPACE-Complete|journal=Computers and Games|volume=2063|pages=241–249|date=2000|doi=10.1007/3-540-45579-5_16|publisher=Springer|series=Lecture Notes in Computer Science|isbn=978-3-540-43080-3|citeseerx=10.1.1.24.4665|lang=en}}</ref>

== Mga posisyong legal ==
Kasi puwedeng basyo, itim, o puti ang kada posisyon sa tabla, may 3<sup>''n''<sup>2</sup></sup> posibleng posisyon ng tablang [[parisukat]] na may [[haba]]ng ''n''', ngunit hindi lahat ng mga posisyon ay legal. Nabuo nina [[John Tromp]] at [[Gunnar Farnebäck]] ang isang [[Rekursiyon|rekursibong]] [[pormula]] para sa mga legal na posisyong <math>L(m,n)</math> ng isang tablang [[parihaba]] na may habang ''m'' at ''n''.<ref name="Tromp and Farnebäck 2007">{{citation | last1= Tromp | first1 = J |author-link1=John Tromp| last2 = Farnebäck | first2 = G |year = 2007 | title =Combinatorics of Go | publisher = Springer, Berlin, Heidelberg | isbn = 978-3-540-75537-1 | doi=10.1007/978-3-540-75538-8_8 | lang=en}}</ref> Noong 2016 inalam ang eksaktong [[bilang]] ng <math>L(19,19)</math>.<ref>https://tromp.github.io/go/legal.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</ref> Nahanap din ang isang [[asintota|asintotikong]] pormulang <math>L\approx AB^{m+n}C^{mn}</math>, kung saan <math>A\approx 0.8506399258457145</math>, <math>B\approx 0.96553505933837387</math> at <math>C\approx 2.975734192043357249381</math> Tinaya na ang [[mapagmamasdang uniberso]] ay may mga 10<sup>80</sup> [[atomo]], mas kaunti kaysa sa dami ng mga posibleng legal na posisyon ng isang tabla na may regular na sukat (''m'' = ''n'' = 19). Habang lumalaki ang tabla, nagbabawas ang [[persentahe]] ng mga posisyong legal.

{| class="wikitable"
!Sukat ng tablang n&times;n
!3<sup>''n''<sup>2</sup></sup>
!Persentaheng legal
!<math>L</math> (mga posisyong legal) ({{OEIS link|A094777}})<ref>{{cite web|url=https://tromp.github.io/go/gostate.pdf|title=Combinatorics of Go
|website=github.io|access-date=17 June 2023|lang=en}}</ref>
|-
!1 &times; 1
|align="right"|3
|align="right"|33.33%
|align="right"|1
|-
!2 &times; 2
|align="right"|81
|align="right"|70.37%
|align="right"|57
|-
!3 &times; 3
|align="right"|19,683
|align="right"|64.40%
|align="right"|12,675
|-
!4 &times; 4
|align="right"|43,046,721
|align="right"|56.49%
|align="right"|24,318,165
|-
!5 &times; 5
|align="right"|847,288,609,443
|align="right"|48.90%
|align="right"|414,295,148,741
|-
!9 &times; 9
|align="right"|4.43426488243 &times; 10<sup>38</sup>
|align="right"|23.44%
|align="right"|1.03919148791 &times; 10<sup>38</sup>
|-
!13 &times; 13
|align="right"|4.30023359390 &times; 10<sup>80</sup>
|align="right"|8.66%
|align="right"|3.72497923077 &times; 10<sup>79</sup>
|-
!19 &times; 19
|align="right"|1.74089650659 &times; 10<sup>172</sup>
|align="right"|1.20%
|align="right"|2.08168199382 &times; 10<sup>170</sup>
|}

== Komplehidad ng punong laro ==
Itinala ni [[Victor Allis]], isang [[siyentipikong pangkompyuter]], na ang mga tipikal na laro sa pagitan ng mga dalubhasa ay nagtatagal ng mga 150 tira, na may mga 250 pasiya kada tira, na inimumungkahi ang isang [[komplehidad ng punong laro]] ng 10<sup>360</sup>.<ref>Allis 1994</ref> Para sa dami ng larong ''teoretika na posible'', kabilang sa mga larong imposible sa praktika, ibinibigay nina Tromp at Farnebäck ang mga ibaba at itaas na hangganan ng 10<sup>10<sup>48</sup></sup> at 10<sup>10<sup>171</sup></sup>, ayon sa pagkakabanggit.<ref name="Tromp and Farnebäck 2007"/> Pinabuti ang ibabang hangganan sa isang [[googolplex]] nina Walraet at Tromp.<ref>{{citation | last1= Walraet | first1 = M | last2 = Tromp | first2 = J | author-link2 = John Tromp|year = 2016 | title = A Googolplex of Go Games | publisher = Springer, Berlin, Heidelberg | isbn = 978-3-319-50934-1 | doi=10.1007/978-3-319-50935-8_18 | lang=en}}</ref> Ang bilang na pinakakaraniwang tinutukoy para sa dami ng mga posibleng laro, 10<sup>700</sup><ref name="top ten">{{Cite web|url=https://www.usgo.org/|title=Home - American Go Association|website=www.usgo.org|accessdate=17 June 2023|lang=en}}</ref>, ay batay sa isang simpleng [[permutasyon]] ng 361 tira o {{nowrap|1=361! = 10<sup>768</sup>}}. Ang ibang karaniwang deribasyon ay ipalagay ang mga ''N'' interseksiyon at ''L'' pinakamatagal na laro para sa mga total na larong ''N''{{i sup|''L''}} Halimbawa, ang 400 tira, tulad ng nakikita sa ilang mga propesyonal na laro, ay isa sa 361<sup>400</sup> o 1 &times; 10<sup>1023</sup> posibleng laro.

Ang total na dami ng mga posibleng laro ay isang [[Punsiyon (matematika)|punsiyon]] ng sukat ng tabla, at saka ng dami ng mga tirang nilaro. Ang karamihan ng mga laro ay nagtatagal ng wala pang 400 o kahit 200 tira, mararaming mas ay posible.

{| class="wikitable"
!Sukat ng laro
!Sukat ng tablang ''N'' (mga interseksiyon)
!''N''!
!Tipikal na tagal ng isang larong ''L''
!''N''{{i sup|''L''}}
!Pinakamatagal na laro (# ng tira)
!Ibaba na hangganan ng mga laro
!Itaas na hangganan ng mga laro
|-
!2 &times; 2
|align="right"|4
|align="right"|24
|align="right"|3
|align="right"|64
|align="right"|
|align="right"|386,356,909,593<ref>Tromp 1999</ref>
|align="right"|386,356,909,593
|-
!3 &times; 3
|align="right"|9
|align="right"|{{val|3.6|e=5}}
|align="right"|5
|align="right"|{{val|5.9|e=4}}
|align="right"|
|align="right"|
|
|-
!4 &times; 4
|align="right"|16
|align="right"|{{val|2.1|e=13}}
|align="right"|9
|align="right"|{{val|6.9|e=10}}
|align="right"|
|align="right"|
|
|-
!5 &times; 5
|align="right"|25
|align="right"|{{val|1.6|e=25}}
|align="right"|15
|align="right"|{{val|9.3|e=20}}
|align="right"|
|align="right"|
|
|-
!9 &times; 9
|align="right"|81
|align="right"|{{val|5.8|e=120}}
|align="right"|45
|align="right"|{{val|7.6|e=85}}
|align="right"|
|align="right"|
|
|-
!13 &times; 13
|align="right"|169
|align="right"|{{val|4.3|e=304}}
|align="right"|90
|align="right"|{{val|3.2|e=200}}
|align="right"|
|align="right"|
|
|-
!19 &times; 19
|align="right"|361
|align="right"|{{val|1.0|e=768}}
|align="right"|200
|align="right"|{{val|3|e=511}}
|align="right"|10<sup>48</sup>
|align="right"|10<sup>10<sup>48</sup></sup>
|align="right"|10<sup>10<sup>171</sup></sup>
|-
!21 &times; 21
|align="right"|441
|align="right"|{{val|2.5|e=976}}
|align="right"|250
|align="right"|{{val|1.3|e=661}}
|align="right"|
|align="right"|
|
|}

== Tingnan din ==
* [[Kompleksidad ng laro]]
* [[Algoritmo ni Diyos]]
* [[Bilang ni Shannon]] (sa [[ahedres]])

== Mga sanggunian ==
{{reflist}}

[[Kategorya:Go (laro)]]
[[Kategorya:Teoriya ng laro]]