Znano število vseh možnih postavitev plošče za go

V zadnjem članku o strojnem učenju smo omenili, da je ena izmed redkih trdnjav človeškega uma klasična igra Go, kjer je možnih potez enostavno preveč, da bi računalnik lahko kaj pametnega izračunal. Raziskovalci so minuli teden šele izračunali, koliko možnih pozicij obstaja, ker pred tem ni bilo dovolj zmogljivih računalnikov (lastniki superračunalnikov pa niso bili navdušeni nad projektom).

Na veliki plošči 19 x 19 je 361 polj in na vsakem je lahko bel ali črn kamen ali pa je prazno. To pomeni, da ima lahko plošča 3³⁶¹ postavitev, ki pa so povečini nedovoljene. Bistveno težji problem je izračunati število dovoljenih postavitev, ki so v skladu s pravili igre. Po več mesecih računanja v več računalniških centrih je John Tromp izračunal točno število vseh dovoljenih pozicij (približno 2,08 10¹⁷⁰). To pomeni, da bi za zapis potrebovali 171 cifer. Koda je javno dostopna na Githubu, zato lahko rezultat preveri vsakdo, če ima nekaj mesecev časa. Mimogrede, med vsemi možnimi postavitvami (če torej naključno namečemo kamne na ploščo) je 1,2 % legalnih.

Bistveno večje pa je število vseh možnih iger, ki jih lahko odigramo pri goju. Tega števila ne poznamo in ga najbrž ne bomo nikoli. Zadnje ocene kažejo, da je število večje od 10^{(10^100)}, kar imenujemo googolplex.

Da bi te ogromne številke postavili v perspektivo povejmo, da Zemljo sestavlja približno 10⁵⁰ atomov, celotno vesolje pa 10⁸⁰. Vseh možnih postavitev na plošči za go je torej bistveno več, kot je atomov v vesolju. Vseh možnih iger pa je toliko, da bi samo za zapis te številke potrebovali več cifer, kot je atomov.

To ne pomeni, da je igra go rešena. Še vedno nimamo algoritma, ki bi povedal, kaj je v dani situaciji optimalna poteza. Zato tudi ne moremo izračunati idealne igre.

To so razlogi, zakaj goja in podobnih iger računalniki nikoli ne bodo mogli igrati s surovo silo. Vseh iger ne morejo preračunati ne danes in jih tudi nikoli v prihodnosti ne bodo mogli, ker na svetu preprosto ni dovolj snovi. Toda ljudje igrajo go povsem dobro, pa ne preračunavajo v nedogled. Računalniki bodo morali za uspešno igranje goja uporabljati principe strojnega učenja in se v večji meri zanašati na intuicijo in občutek za postavitev na plošči. To pa je eden najtežjih problemov, pred katere lahko postavimo Turingove stroje.