The Knowledge Frontier

Kompyuta na akili bandiaChapisho la awaliNadhariaDakika 4 za kusoma

KANUNI YA MCHEZO WA GO INAYOBADILISHA JIBU

Kutatua mchezo kunamaanisha kujua matokeo yake pande zote mbili zinapocheza kikamilifu. Kwenye ubao wa go, matokeo hayo ni thamani: idadi ya pointi ambazo Mweusi anashinda kwazo akicheza kikamilifu — 28 kwenye ubao wa 4×7 inamaanisha Mweusi anamiliki makutano yote 28. Drafti (checkers) ulitatuliwa mwaka 2007, na vivyo hivyo Hex kwenye mbao ndogo. Kwa go, uthibitisho wa kompyuta upo kwa mbao nyingi zenye hadi makutano 30, hasa kutoka kwa programu iitwayo MIGOS (2003 na 2009).

Kuna kizingiti. Matokeo hayo ya jadi yanatumia kanuni iliyorahisishwa kwa hali zinazojirudia — kanuni ya msingi ya “ko” — mchezaji hawezi kuteka tena moja kwa moja jiwe moja lililoteka punde jiwe lake moja, jambo ambalo lingezungusha hatua hizo mbili milele — pamoja na makubaliano maalum: kupitisha zamu kunaondoa marufuku ya ko, mchezo unasimama kwenye hali iliyojirudia, na kadhalika. Makubaliano haya yalibuniwa ili thamani ya hali isitegemee jinsi ilivyofikiwa.

Kanuni ambayo watu wanacheza kweli

Kanuni za Kichina kama zilivyoandikwa, na go ya kompyuta, zinatumia superko ya kihali (positional superko): hakuna hatua inayoweza kuunda upya hali yoyote ya ubao mzima ambayo tayari imetokea katika mchezo. Kutatua chini ya kanuni hii ni kugumu zaidi sana, kwa sababu uhalali wa hatua sasa unategemea historia nzima ya mchezo. Inavunja zana tatu zinazofanya utatuzi uwezekane:

  • kutumia tena matokeo ya hali ileile iliyofikiwa kwa njia nyingine — njia hizo mbili zinaweza kukataza hatua tofauti;
  • kutambua makundi salama na eneo bila utafutaji, jambo linalodhani kwamba mmiliki anaweza kila mara kuwateka wavamizi — chini ya superko, kuteka huko kunaweza kukatazwa;
  • kupogoa hatua zisizosaidia kamwe, kama kujaza jicho lako mwenyewe — mojawapo ya pointi tupu ambazo kundi linahitaji ili libaki hai — chini ya superko, hatua kama hiyo inaweza kuwa ya kuamua.

Gharama ilikuwa kubwa: kwa aina moja ya superko, MIGOS ilihitaji saa 1.1 kwa ubao wa 4×4, ikilinganishwa na sekunde 3.3 chini ya ko ya msingi. Suluhisho la kwanza la superko la 5×5, mwaka 2024, lilichukua saa 5.25 kwenye michakato sita. Zaidi ya 5×5, hakuna ubao wenye angalau safu mbili uliokuwa umetatuliwa chini ya superko.

Njia ya mkato inayobaki sahihi

Sami Kharma na Florian Schintke, wa Zuse Institute Berlin, walijenga Sanko. Kiini chake ni nadharia rahisi ya uhamishaji wa uthibitisho (proof-transfer theorem): uthibitisho uliohifadhiwa kwamba mchezaji mmoja anashinda unabaki halali kwenye njia mpya isipokuwa ubao ambao mshindi lazima auunde umeshatokea. Mbao za mshindi pekee ndizo zenye maana — kama aliyeshindwa hawezi tena kuunda upya hali fulani, aliyeshindwa anapoteza tu chaguo moja. Kukagua hili kunachukua muda unaolingana na urefu wa njia, si ukubwa wa uthibitisho. Kwenye ubao wa 3×7, njia hii ya mkato peke yake inapunguza kazi kutoka hatua bilioni 664 hadi milioni 112.

Pia walirekebisha utambuzi wa jadi wa makundi salama ili ubaki sahihi chini ya superko, na walipogoa hatua za upande ambao walikuwa wakijaribu kuthibitisha ushindi wake tu, ili utafutaji ulioshindwa uripotiwe kama haujulikani, kamwe si kama ushindi kwa upande mwingine.

Thamani mpya

  • 5×5 kwa dakika 15.7 kwenye nyuzi sita — takriban mara 20 haraka zaidi kuliko awali, kwa sehemu kutokana na vifaa bora; kwenye nyuzi moja, 4×4 inatatuliwa mara 58 haraka zaidi. Kwenye mashine moja yenye nyuzi 192, 5×5 inachukua takriban dakika moja na nusu.
  • Thamani za kwanza za superko za mbao nyingine 23; 11 kati yake hazijawahi kutatuliwa chini ya kanuni yoyote. 3×10 ina thamani ya pointi 8 kwa Mweusi — MIGOS ilikuwa imethibitisha angalau 6 tu, na miezi miwili ya utafutaji haikupata kikomo cha juu.
  • Kwenye mbao za safu moja, thamani kutoka 1×9 hadi 1×15 zinajirudia 0, 1, 2, 2 — lakini 1×16 inavunja mpangilio, ikiwa na thamani ya 1 badala ya 2.

Mshangao wa 4×7

Chini ya kanuni za zamani, 4×7 ni ushindi wa ubao mzima: Mweusi anateka kila kitu, 28–0. Chini ya superko thamani yake ni 12. Waandishi walirudia mfululizo bora wa hatua 31 uliochapishwa kwa MIGOS: kila hatua ni halali, na bado Mweusi anachukua ubao wote. Wakitatua mfululizo huo kinyume, walipata mvunjiko mara tu baada ya hatua ya 25: katika hali baada ya hatua ya 25, iliyochezwa na Mweusi, Mweupe anapaswa kucheza G2 (au C1) badala ya A2.

Kinachofuata ni ko ya ajabu. Mweupe anateka; kuteka tena kwa Mweusi kungeunda upya ubao wa awali — jambo lililokatazwa. Kila hatua nyingine ya Mweusi inaweka kundi lake mwenyewe hatarini. Mweusi analazimika kupitisha, Mweupe anapitisha, na mchezo unaisha huku kundi la Mweupe likiwa hai: kile ambacho waandishi wa MIGOS walikuwa tayari wamekiita “uhai wa mbalamwezi” (moonshine life). Chini ya kanuni za zamani, kupitisha kungeondoa marufuku na Mweusi angeteka tena na kushinda kila kitu. Chini ya superko, bora zaidi kwa Mweusi katika mfululizo huu ni uhai wa pamoja (seki) wenye thamani ya pointi 3 tu, kwa hivyo mchezo kamili unaacha mfululizo uliochapishwa mapema zaidi — na bora zaidi ambacho Mweusi anaweza kujihakikishia kuanzia ubao mtupu ni 12.

Hakuna utafutaji uliokosea. Tofauti inatokana na kanuni zenye maana tu mwishoni kabisa mwa mchezo. Ushauri wa waandishi: thamani zilizokokotolewa chini ya makubaliano yanayofanya marudio yasiwe na madhara hazipaswi kunukuliwa kama thamani za go ya superko bila kukaguliwa.

Inakaguliwa na yeyote

Kila thamani inategemea uthibitisho miwili huru, na kitatuzi kilipita makumi ya maelfu ya ukaguzi mtambuka bila tofauti yoyote. Tofauti na masuluhisho ya awali ya mbao tupu za go, msimbo chanzi wa kitatuzi na amri kamili iliyo nyuma ya kila tokeo ni za umma; mnyororo wa uthibitisho wa 4×7 unarudiwa chini ya sekunde ishirini. Uthibitisho huo bado si vyeti ambavyo mtu wa nje anaweza kuthibitisha kivyake, na 6×6 bado iko nje ya uwezo — kwa makadirio ya waandishi, takriban siku 50 kwenye mojawapo ya mashine zao, au zaidi.