Connect 4 ni mchezo uliotatuliwa: jinsi ya kushinda na kwa nini kuanza ni faida

Inamaanisha nini mchezo kuwa umetatuliwa

Mchezo umetatuliwa pale matokeo yanapojulikana yanayopatikana kama wachezaji wote wawili wanacheza kikamilifu kuanzia nafasi ya mwanzo. Kuna ngazi tatu za kawaida. Katika suluhisho «dhaifu sana» hujulikana tu nani anashinda au kama ni sare, bila kujua mkakati. Katika «dhaifu» hujulikana pia mkakati unaohakikisha matokeo hayo tangu mwanzo. Katika «imara» hujulikana matokeo bora kutoka nafasi yoyote inayowezekana.

Katika kesi ya Connect 4 kwenye ubao wa kawaida wa safu wima 7 kwa safu mlalo 6, matokeo ni wazi: kwa mchezo kamilifu, anashinda mchezaji anayeanza. Hilo halimaanishi anashinda kila mara kwa vitendo, kwa sababu ili afanikiwe lazima apatie hatua sahihi katika kila zamu, na michezo kati ya watu imejaa makosa.

Nani aliutatua na lini

Hadithi ina wahusika wawili waliofikia hitimisho moja kwa kujitegemea mnamo Oktoba 1988. Wa kwanza alikuwa James Dow Allen, aliyetangaza suluhisho lake tarehe 1 Oktoba 1988 katika ujumbe kwa kikundi cha majadiliano rec.games.programmer. Siku kumi na tano baadaye, tarehe 16 Oktoba, mtafiti Mholanzi Victor Allis aliwasilisha suluhisho lake mwenyewe, lililoelezwa katika kazi yake «A Knowledge-based Approach of Connect-Four», ya Vrije Universiteit.

Mbinu ya Allis ilikuwa «inayotegemea maarifa»: badala ya kukagua nafasi zote, alibuni kanuni za kimkakati, kama visanduku vipi vinafaa kudhibitiwa na vitisho vipi vina uzito, na akavichanganya na utafutaji ili kuthibitisha kwamba mchezaji wa kwanza anaweza kulazimisha ushindi. Baadaye matokeo yaleyale yalipatikana kwa nguvu ghafi, kwa hifadhidata za nafasi na kompyuta zenye nguvu; mwandaaji programu John Tromp, kwa mfano, alijenga hifadhidata ya nafasi zote za vipande 8 iliyotumika kama mahali pa kuanzia. Njia zote mbili zinaafikiana.

Ufunguo wa mwanzo: safu wima ya katikati

Si hatua yoyote ya kwanza inatosha. Matokeo hutegemea safu wima ambayo mchezaji wa kwanza anaanzia:

«Anashinda anayeanza» inamaanisha nini kwa vitendo

Nadharia kusema wa kwanza anashinda hakukuhakikishii chochote kama mpinzani anacheza vizuri: faida ni halisi, lakini inahitaji usahihi. Hata hivyo, kuanza kunakupa mambo mawili halisi. La kwanza ni mpango: unasogea kwanza na mpinzani mara nyingi analazimika kujibu vitisho vyako. La pili ni usawa, kanuni ya vitendo inayojulikana sana kati ya wachezaji: kwa kuwa ubao una safu mlalo 6, namba shufwa, na mchezo hufanyika kwa zamu, visanduku vya safu mlalo witiri (ya 1, 3 na 5, kuhesabu kutoka chini) huelekea kubaki kwa aliyeanza, na vya safu mlalo shufwa kwa wa pili. Ndiyo maana kitisho katika safu mlalo witiri mara nyingi ni cha thamani zaidi kwa mchezaji wa kwanza.

Kwa nini katikati ina thamani kubwa hivyo

Diski za safu wima ya katikati hushiriki katika mistari mingi zaidi inayowezekana kuliko za safu wima nyingine yoyote. Kutoka katikati unaweza kuunda nne mfululizo kwa mlalo, kwa wima na kwa mshazari zote mbili kwa michanganyiko mingi tofauti; diski ya ukingoni karibu hutumika tu kwa mielekeo mmoja au miwili. Ndiyo maana programu zenye nguvu hupanga hatua zao kutoka katikati kwenda nje, na ndiyo maana vitabu vya mianzo huanza na safu wima ya 4.

Kwako, kanuni ya vitendo ni rahisi: usipokuwa na hatua iliyo bora wazi, chagua safu wima iliyo karibu na katikati. Na kama mpinzani anakalia katikati kwanza, usikate tamaa: safu wima za pembeni bado ni nzuri sana.

Vidokezo vya kushinda michezo zaidi dhidi ya watu

• Ukianza, anza kwenye safu wima ya katikati. Ni mwanzo pekee unaoshinda, kwa mchezo kamilifu.
• Tafuta vitisho viwili: mistari miwili ya tatu na kisanduku cha kufunga kikipatikana kwa wakati mmoja. Mpinzani anaweza kuzuia kimoja tu. Ni njia ya kawaida zaidi ya kushinda dhidi ya binadamu.
• Fikiria vitisho «hewani»: mstari wa tatu ambao kisanduku chake cha mwisho bado hakiwezi kufikiwa kwa sababu kinakosa diski chini yake. Kama kisanduku hicho kiko kwenye safu mlalo inayokufaa kwa usawa, mpinzani mapema au baadaye analazimika kucheza chini yake na kukupa.
• Kabla ya kudondosha diski, tazama kisanduku gani kinabaki wazi juu yake. Ukimpa mpinzani kisanduku anachofunga nacho mstari, umeshindwa.
• Zuia mistari ya tatu iliyo wazi pande zote mbili kabla haijaundwa: ni kushindwa kwa hakika. Tazamia zamu moja mbele.
• Katika hatua za mwisho unajalisha nani anabaki bila hatua salama: tunza safu wima ambazo bado unaweza kuzicheza bila hatari.
• Ukiwa wa pili, lenga visanduku vya safu mlalo shufwa na uzuie bila haraka kila kitisho cha safu mlalo witiri: ndiyo njia yako bora ya sare au ya mpinzani kukosea.

Kwa hivyo kompyuta haiwezi kushindwa?

Programu ambayo ingecheza kikamilifu tangu mwanzo na kuanza kwanza isingeshindwa kamwe, lakini hiyo ni kauli kuhusu suluhisho la kinadharia la mchezo, si kuhusu programu yoyote. Kutatua mchezo mzima kutoka nafasi ya mwanzo kunahitaji hesabu nyingi sana, na kwenye kivinjari, kwa sekunde moja na nusu tu kwa kila hatua, haiwezekani.

Ndiyo maana kiwango cha «Isiyoshindika» katika Connect 4 yetu kinawasilishwa kama kilivyo: kiwango chenye nguvu zaidi. Kinatumia utafutaji wa alpha-beta na kuongezeka kwa kina hatua kwa hatua, jedwali linalokumbuka nafasi zilizoonekana, mpangilio wa safu wima unaoanza na katikati na kitabu kifupi sana cha mianzo. Huchambua hatua nyingi mapema na karibu haikosi makosa, lakini hatuahidi kwamba haiwezekani kushinda. Ukifanikiwa kuishinda, umeshinda kweli.

Jinsi ya kufanya mazoezi

Njia nzuri ya kuimarika ni kucheza dhidi ya kompyuta katika kiwango cha Ngumu kisha dhidi ya Isiyoshindika, ukibadilishana nani anaanza. Ukishindwa, pitia mchezo na ubaini katika zamu gani kitisho maradufu kilijitokeza: karibu kila mara kinaweza kufuatiliwa hadi hatua tulivu ya awali. Ni vyema pia kujaribu matoleo mengine, kama ubao mkubwa zaidi au hali ya PopOut, yanayokulazimisha kufikiri tofauti na kufunza uoni wa ubao.

Maswali yanayoulizwa mara kwa mara