Go at matematika

Sa heneral nilalaro ang Go sa mga tablang n × n, at ay komputasyonal na komplehidad para magtasa ng nagwagi sa ilang posisyon ng Go ay krusyal na nagdedepende sa 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.^[2] Ang pruweba ay sa pamamagitan ng kabawasan ng pormulang totoong dinadamihan ni Boole (Ingles: true quantified Boolean formula, o TQBF), na kinikilala bilang PSPACE-kumpleto, sa heograpiyang nilalahat (Ingles: 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 ${\displaystyle n^{2}}$ 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.^[3]

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^[3].

Alam na ito ay hindi bababa sa PSPACE-mahirap, dahil sa pruweba ni Sipser^[2] ng PSPACE-pagkahirap ng Go ay hindi inaasahan ang kautusang ko o kaniyang kawalan. Alam rin na ang Go ay nasa EXPSPACE.^[4]

Ipinakita ni Robson^[4] 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 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^[5] at dama^[6] ay EXPSPACE-kumpleto, kasi ang nilalahit na ahedres at dama ay EXPTIME-kumpleto. Gayunman, hindi nalalapat ang itong resulta sa Go.^[4]

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.^[7]

Kasi puwedeng basyo, itim, o puti ang kada posisyon sa tabla, may 3ⁿ² posibleng posisyon ng tablang parisukat na may habang n', ngunit hindi lahat ng mga posisyon ay legal. Nabuo nina John Tromp at Gunnar Farnebäck ang isang rekursibong pormula para sa mga legal na posisyong ${\displaystyle L(m,n)}$ ng isang tablang parihaba na may habang m at n.^[8] Noong 2016 inalam ang eksaktong bilang ng ${\displaystyle L(19,19)}$ .^[9] Nahanap din ang isang asintotikong pormulang ${\displaystyle L\approx AB^{m+n}C^{mn}}$ , kung saan ${\displaystyle A\approx 0.8506399258457145}$ , ${\displaystyle B\approx 0.96553505933837387}$ at ${\displaystyle C\approx 2.975734192043357249381}$ Tinaya na ang mapagmamasdang uniberso ay may mga 10⁸⁰ 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.

Sukat ng tablang n×n	3n2	Persentaheng legal	${\displaystyle L}$ (mga posisyong legal) (Padron:OEIS link)[10]
1 × 1	3	33.33%	1
2 × 2	81	70.37%	57
3 × 3	19,683	64.40%	12,675
4 × 4	43,046,721	56.49%	24,318,165
5 × 5	847,288,609,443	48.90%	414,295,148,741
9 × 9	4.43426488243 × 1038	23.44%	1.03919148791 × 1038
13 × 13	4.30023359390 × 1080	8.66%	3.72497923077 × 1079
19 × 19	1.74089650659 × 10172	1.20%	2.08168199382 × 10170

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³⁶⁰.^[11] 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¹⁰⁴⁸ at 10¹⁰¹⁷¹, ayon sa pagkakabanggit.^[8] Pinabuti ang ibabang hangganan sa isang googolplex nina Walraet at Tromp.^[12] Ang bilang na pinakakaraniwang tinutukoy para sa dami ng mga posibleng laro, 10^700[13], ay batay sa isang simpleng permutasyon ng 361 tira o 361! = 10⁷⁶⁸. Ang ibang karaniwang deribasyon ay ipalagay ang mga N interseksiyon at L pinakamatagal na laro para sa mga total na larong NPadron:I sup Halimbawa, ang 400 tira, tulad ng nakikita sa ilang mga propesyonal na laro, ay isa sa 361⁴⁰⁰ o 1 × 10¹⁰²³ posibleng laro.

Ang total na dami ng mga posibleng laro ay isang 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.

• Kompleksidad ng laro
• Algoritmo ni Diyos
• Bilang ni Shannon (sa ahedres)