Es noklausījos čempiona lekciju — un uzvarēju ar 2 MB bitu masku

Progmeistars notika datorprogrammu turnīrs: katrai kārtai bija sava spēle, un dalībnieku programmas to spēlēja viena pret otru. Mana programma 11. turnīrā spēlēja „matricas pokeru”: 5×5 laukums, 25 kārtis ar cipariem 0–4, spēlētāji pēc kārtas tās izliek, un katram pieder piecas līnijas plus diagonāle, kas tiek vērtētas kā pokera kombinācijas. Lielāko spēles daļu mana programma spēlēja alkatīgi — uzlaboja savas līnijas un bojāja pretinieka līnijas — un pēdējām septiņām kārtīm pārslēdzās uz pilnu pārlasi. Komentārs pirmkoda sākumā pasaka visu: „dators mani uzvarēja”.

Viens no pasniedzējiem šajos turnīros uzvarēja atkal un atkal. Kādu dienu viņš nolasīja lekciju par to, kā šādas programmas rakstīt pareizi, — par minimax un to, kā paātrināt pārlasi.

Es noklausījos, izmantoju viņa padomus nākamajā turnīrā — un 2003. gadā uzvarēju 12. Datorprogrammu turnīrā.

Bija arī jautrs sarežģījums. Tieši tad salūza mana datora operatīvā atmiņa — kaut kāda atmiņas kļūme —, un man nebija laika to nodot remontā. Tāpēc es atgriezos DOS: tas izmanto tikai pirmo atmiņas megabaitu, un līdz bojātajai daļai nekad netika. Turnīra programmu es uzrakstīju Pascal zem DOS. Solis atpakaļ laikā, bet tas mani aizveda tieši tur, kur gribēju.

Spēle notika uz 8×6 laukuma. Spēlētāji pēc kārtas nosedza blakus esošas šūnas ar sloksnēm — pārsvarā divu šūnu garām, plus trīs sloksnes pa trim; spēle beidzās, kad brīvas vietas vairs nebija. Pilna pārlase uz tāda laukuma nebija iespējama, tāpēc plāns bija apmānīt uzdevuma izmēru:

1. Laikus atbrīvoties no trīs šūnu sloksnēm, lai paliktu tikai divu šūnu gājieni.
2. Sadalīt laukumu divās daļās. Kad vidējās kolonnas ir aizpildītas, kreisā un labā puse kļūst par neatkarīgām spēlēm, katra 4×6 — tikai 2²⁴, aptuveni 16 miljoni iespējamo pozīciju.
3. Iepriekš aprēķināt katru pusi. Katrai no šiem 16 miljoniem pozīciju programma zināja, vai, pretiniekam spēlējot vislabāk, atlikušo gājienu skaits būs pāra vai nepāra. Viens bits uz pozīciju: visa tabula ietilpa 2 MB bitu masku failā.
4. Spēlēt pēc paritātes. Ja ir divas neatkarīgas puses, pareizais gājiens ir tas, pēc kura kopējā paritāte nostrādā tev par labu, — tā ir uzmeklēšana tabulā, nevis pārlase.

Pozīcija spēles vidū (ilustrācija, nevis īsta spēle). Katra rinda ir noslēgta pie centrālās līnijas, tāpēc no šī brīža kreisā un labā puse ir divas atsevišķas spēles — katra pietiekami maza, lai to aprēķinātu iepriekš.

Spēles notika ar rokām: pasniedzējs palaida divas programmas uz diviem datoriem un pārnesa gājienus no viena uz otru. Visvairāk viņu pārsteidza tas, ka jau otrajā vai trešajā gājienā mana programma gandrīz droši paziņoja, ka uzvarēs.

Kas man palika atmiņā: labākā optimizācija bieži vien ir nevis ātrāka pārlase, bet cits uzdevuma attēlojums — sadali uzdevumu neatkarīgās daļās un iepriekš aprēķini to, kas nekad nemainās.