Tämä blogi sisältää kirjojani sivuavia aiheita. Aihealue on hyvinkin laaja ja artikkelien on tarkoitus tuoda esiin uutta, mielenkiintoista ja joskus kiistanalaistakin informaatiota.

My blog in English: http://spreadingmyfinns.blogspot.fi/

Thursday, December 28, 2017

Alien Chess - vieraiden entiteettien ylivertaista shakkia

Shakkia ulkoavaruudesta



Kun SM Peter Svidleriltä kysyttiin aikanaan, kenet hän valitsisi edustamaan maapalloa hypoteettisessa ottelussa avaruusolioita vastaan, hän vastasi empimättä: ”Houdini”. Kyseessä ei ollut edesmennyt taikuri, vaan kuin puskista shakkiohjelmien rankingin kärkeen noussut uusi tulokas. Sen jälkeen shakkiohjelmat ovat jatkaneet tasaista kehitystä ja parhaiden ns. moottoreiden vahvuus on noussut noista ajoista yli 200 pistettä. Kun sitten 5.12.2017 julkaistiin yleiskäyttöisen AlphaZero -tekoälyohjelman (AZ) sadan pelin ottelun tulokset maailman vahvimpiin kuuluvaa shakkimoottoria, Stockfish 8:aa vastaan, epäusko valtasi shakkimaailman. AZ ei ainoastaan voittanut ottelua, vaan murskasi vastustajansa täydellisesti. 28 voittoa, 72 tasapeliä, eikä yhtään tappiota on huippushakissa suoranainen teurastus. Kaiken lisäksi Stockfish pyöri koneessa, joka on 20 kertaa nopeampi kuin hyvä kannettava tietokone. Monet varmaan epäilivät huijausta ja joillain saattoi jopa käydä mielessä, että kamppailu avaruusolioita vastaan oli alkanut. Onneksi kummastakaan ei kuitenkaan ollut kyse.


Millaisen vastuksen ihmiskunnan shakkitietämys antaa?


Clevelandin julkinen kirjasto 


Shakki on kiistatta eniten tutkittu peli maailmassa. Luis Ramírez de Lucena julkaisi vanhimman säilyneen shakkikirjan vuonna 1497 ja nykyään Clevelandin julkinen kirjasto on suurin yksittäinen shakkikirjallisuuden kokoelma. Sen yli 32000 kirjaa ja yli 6000 sidottua kausijulkaisua muodostavat valtavan shakkitietämyksen keskittymän. 500 vuoden aikana käytännössä kaikki merkittävät pelit on taltioitu digitaalisiin tietokantoihin, joista niitä voi tutkia mitä mielikuvituksellisimmin tavoin. Lähes kymmenen miljoonan pelimäärä yhdistettynä matemaattisiin työkaluihin ja tietokoneiden tarjoamiin mahdollisuuksiin suorastaan pakottaa teoriaa kehittymään. Loppupelien osalta on supertietokoneilla ratkaistu kaikki mahdolliset asemat aina seitsemän nappulan loppupeleihin asti. Siinä ehkä suurin haaste on ollut informaation tiivistäminen, sillä pelkkinä asemina tuo loppupelikanta veisi muistitilaa kymmeniä petatavuja. Nyt se kaikki on saatu mahdutettua 100 teratavuun. Tuon tietokannan ihmeellisyydestä kertoo ehkä se, että parhaimmillaan se ilmoittaa miettimättä matin 489:ssä siirrossa!

Kaikki shakkitietämys on tiivistynyt shakkiohjelmissa ja niiden heuristiikka kehittynyt 65 vuoden ajan. Kesti 40 vuotta haastaa parhaat ihmispelaajat, 15 vuotta ohittaa lopullisesti ihmisen taso ja 10 vuotta tulla ylivoimaiseksi ihmiseen nähden. Nykyään paras tietokoneohjelma voittaisi parhaan ihmisen 90% peleistä ja loput 10% olisivat tasapelejä. Voitot tietokoneesta olisivat ihmiselle mahdottomia. (kts. historia artikkelin lopussa). Ei siis ole ihme, että shakkiyhteisö kuvitteli saavuttaneensa shakkiosaamisen ylimmän tason tai ainakin päässeen lähelle sitä. Silti huippupelaajien ja monien teoreetikoiden ajattelussa eli uskomus, että loppujen lopuksi ihmisen tapa pelata olisi kuitenkin ylivertainen shakkimoottoreihin nähden. Ihminen tarvitsisi vain koneen virheettömyyden ja muistin. Ehkä ihmisen opastama moottori edustaisi ylintä osaamista?

Kun sitten AlphaZero tuli kuin taivaalta ja murskasi ihmisosaamisen keulakuvan ja vieläpä ainoastaan muutaman tunnin opettelulla lähtien täysin nollasta, ei ole ihme, että jopa avaruusoliot kävivät monen mielessä. Tarkempi tutkinta paljastaa kuitenkin, että kyseessä on lopulta ihmiskunnan jättiloikka, mutta tuo loikka on samalla varoitus vieraista olioista, joita olemme itse luomassa.


Mitä peleissä oikeastaan tapahtui?


Valitsin esimerkkipeleiksi kaksi Kuningatarintialaista avausta, koska yhdessä ne vihjaavat, että meidän on ehkä ajateltava uusiksi jo vakiintunut avausteoria. Toisekseen molemmissa peleissä AlphaZero murskaa vastustajansa samalla taktiikalla, vaikka peleissä Stockfish tekee täysin erityyppiset virheet.

Monet koneshakin asiantuntijat ovat kritisoineet sitä, ettei Stockfishin ole annettu käyttää avaustietokantaansa. Tavallaan tämä on aiheellinen argumentti, mutta avaustaktiikka on ihmisen eikä koneen luomaa, eikä näin ollen vastassa olisi ollut puhtaasti kone. Olihan myös AlphaZero itse luonut omat avauksensa. Tilannetta voisi verrata kuuluisaan otteluun Garry Kasparovin ja Deep Bluen välillä vuonna 1997, jossa joukko shakkiasiantuntijoita valmisteli konetta juuri Kasparovia vastaan ja viritteli sitä vielä pelin aikana. Oikeudenmukaista sen sijaan olisi ollut antaa Stockfishille käyttöön Cerebellum-avaustietokanta, joka on luotu Stockfishillä. Se olisi kaiken lisäksi ollut parempi kuin perinteiset avaustietokannat, sillä takautuvan solmukohtien arvotuksen ansiosta jokainen solmu antaa siinä arvoksi sen, mikä se syvimmillään Stockfishin mukaan on. Testeissä Cerebellum on antanut ohjelmille 50 pistettä korkeamman suorituskyvyn kuin perinteiset avauskirjastot. Vaikka tämä olisi ollut tilanne, en usko lopputuloksen silti olleen kovinkaan erilainen. Stockfish pystyi pelaamaan ilman avaustietokantaakin nykyteorian mukaisesti ja ratkaisut tapahtuivat vasta keskipelissä tavalla, joka olisi voinut syntyä avauksesta riippumatta. Stockfishin uudemmat tai siitä kehitetyt viritetyt versiot sen enempää kuin nopeampi alustakaan eivät olisi auttaneet ratkaisuasemissa, jotka osoittautuivat Alfa-Beta -hakualgoritmin sokeiksi pisteiksi.


Shakkimoottoreiden kärjen kehitys


Oheisissa peleissä (5. ja 10.) AlphaZeron taktiikka muistuttaa ulkoisesti hyvin paljon Suomen armeijan taktiikkaa Talvisodan korpitaisteluissa. Kaikki perustui liikkuvuuden hyväksikäyttämiseen vihollisen materiaalisesta ylivoimasta piittaamatta. Tuloksena oli yleensä motti, jossa aika riitti tuhoamaan vastustajan kylmyydessä ja huollon puutteessa. Kaikista kuvaavin vertaus lienee kuitenkin Raatteen tien taistelu, jossa Suomen joukot hyökkäsivät läpi vihollisryhmittymän pilkkoen sen pieniin palasiin ja eristäen nämä toisistaan. Shakkilaudalla AlphaZeron tarvitsi tämän jälkeen hyökätä ainoastaan paikallisesti materiaalisesti alakynteen jääneen kuningasaseman kimppuun. On syytä huomata, ettei mitään taktiikkaa tai strategiaa ole opetettu AlphaZerolle, vaan nämä kumpuavat asemasta itsestään parhaana mahdollisena juonena.


Valkoinen: AlphaZero Musta: Stockfish (5. peli)


1.d4 Rf6 2. c4 e6 3. Rf3 b6 4. g3 Lb7 5. Lg2 Le7 6. 0-0 0-0 7. d5 
Tähän saakka AZ on noudattanut avauksen vaihtoehtojen yleisimpiä variaatioita. 7. d5 on vasta kolmanneksi yleisin, lukumäärässä kaukana yleisimmästä 7. Rc3.

exd5 8. Rh4 c6 9. cxd5 Rxd5 10. Rf5 Rc7 11. e4 Lf6
11…Lf6 on jotenkin konemainen ja tietokoneiden avaustietokannat sulkevat se pois. Se ei silti ole virhe.

12. Rd6!
12. Rc3 on yleisin siirto ja kaikki johtavat ohjelmat siirtäisivät juuri niin. AlphaZero ajattelee omalla tavallaan. Tässä tulee ensimmäisen kerran esiin hermoverkon aseman (hahmon) tunnistus, joka ei perustu yksittäisten asioiden summaan. On mahdotonta sanoa, miksi AZ näkee tämän parhaimmaksi.

La6 13. Te1 Re8 14. e5 Rxd6 15. exf6 Dxf6 16. Rc3 Rb7?


16...Rb7?


Tämä on ratkaiseva virhe, minkä kaikki huippuohjelmat tekevät, koska ne eivät näe valkean seuraavaa siirtoa. Toisessa pelissä Stockfish valitsee siirron 16…Lc4 ja olettaa jatkoksi 17. Lf4 Re8 18. h4 h6 19. Lxb8 Txb8 20. Dxd7 c5 21. Dxa7 Rd6 tai 17. b3 Le6 18. La3 Lxc3 19. Lxd6 tasa-asemin. Ainakin 16…Lc4 estää siirron  17. Re4.

6. peli menee kuitenkin näin: 16…Lc4 17. h4 h6 18. b3 Dxc3 (tai 18…Le6) 19. Lf4 Rb7 (?)
(19…Le6 vaikuttaisi paremmalta ja jopa Stockfish valitsisi sen hetken pidempään mietittyään. Peli voisi jatkua 20. Lxd6 Ra6 21. Tc1 Df6 22. Lf1 Rc5 23. Lxf8 Txf8 24. b4 Rb7 Stockfish tulkitsee tämän tasa-asemaksi, mutta R+2xs vs. T voisi olla mielenkiintoinen asetelma AlphaZeroa vastaan.)
20. bxc3 Df6?
Ratkaiseva virhe, jonka tietokoneohjelmatkin huomaavat. Tietokonepeleissä tämä riittää jo tappioon. (Oikein olisi ollut 20…Rc5 21. Ld6 Td8 22. Le7 Tc8 23. Lxc5 bxc5 24. Dg4 Df6 tai 20…f5 21. Dh5 Df6 22. Tad1 Df7 23. Dxf7+ Txf7 24. Te8+ Tf8 25. Txb8… Molemmissa tapauksissa valkealla on kuitenkin pieni etu.)
21. Le4 Ra6 22. Le5 De6 23. Ld3 f6 24. Ld4 Df7 25. Dg4 Tfd8 26. Te3 Rac5 27. Lg6 Df8 28. Td1 Tab8 29. Kg2 Re6 30. Lc3 Rbc5 31. Tde1 Ra4 32. Ld2 Kh8
1-0 siirron 70 jälkeen

17. Re4!!
Yksikään huippuohjelma ei näe tätä siirtoa edes ajan kanssa. Jostain syytä se on kaikille sokea piste.
Jälleen kerran hermoverkon aseman tunnistus toimii paremmin kuin yksittäisten asioiden summaus.
Dg6 18. h4 h6
Edelleenkään Stockfish ei näe valkean etua, vaan kuvittelee olevansa niskan päällä.
19. h5 Dh7
Tässä kohtaa kuvitelmat mustan edusta alkavat rapista, mutta tappio ei silti vielä häämötä.
20. Qg4 Kh8


20...Kh8


Vasta tässä vaiheessa Stockfish näkisi häämöttävän tappion, jos se saisi käyttää riittävästi aikaa ja/tai sitä pyörittäisi riittävän tehokas prosessori. Siirtoa 17. Re4 se ei pelkällä ajalla ja teholla olisi näin ollen voinut mitenkään nähdä.
Ohjelmat tahtovat myös uskoa siirtoon 20…f5, mutta ne eivät näe AZ:n sitä luultavasti seuraavaa siirtoa 21. Dd1!!! Lc4 22. Rd6 Rxd6 23.Dxd6 Ra6 24.b4 Tae8 25.Txe8 Tx8 26.Dxd7

Stockfish tai mikään muukaan ohjelma ei näe myöskään pelissä tapahtuvaa seuraavaa siirtoa.

21.Lg5!!!

jos 21…hxg5? 22.Rxg5 Dg8 23.Le4!!! f5 24.Lxf5 Rd6 25.Lg6 Dc4 26.f4 Dd4+ 27.Kg2 Lc4 28.Tad1 Ld5+ 29.Kh3 Df6 30.Rh7 Dd8 31.h6 gxh6 32.Dh5 Kg7 33.Lb1 Tf6 34.g4 Rf7 35.g5 Txf4 36.Dg6+ Kh8 37.Kg3 Tf3+ 38.Kg4 Dg8 39.Rf6 Re5+ 40.Txe5 mustan asema on toivoton.


f5 22. Df4 Rc5 23. Le7 Rd3?

23…Re6 24.Dd6 fxe4 olisi paljon parempi, mutta silläkin tasapeli olisi kiven takana.
24. Dd6 Rxe1 25. Txe1 fxe4 26. Lxe4 Tf5 27. Lh4 Lc4 28. g4 Td5 29. Lxd5 Lxd5 30. Te8+ Lg8 31. Lg3 c5 32. Dd5 d6 33. Dxa8
Tämä siirto on valkean ainoa, jota voi edes vähän kritisoida. 33.Lxd6 Rd7 34.Txa8 olisi vahvempi, mutta pelin lopputulokseen sillä ei olisi vaikutusta.

Loput pelistä ei ole aiheen kannalta enää merkittävää. Peli päättyi 1-0 siirrossa 117.


Valkoinen: AlphaZero Musta: Stockfish (10. peli)

1. d4 Rf6 2. c4 e6 3. Rf3 b6 4. g3 Lb7 5. Lg2 Le7 6. 0-0 0-0 7. d5 exd5 8. Rh4 c6 9. cxd5 Rxd5 10. Rf5 Rc7 11. e4 d5
Tämä on yleisin jatko ja jos Stockfish olisi käyttänyt avauskirjastoa, se olisi siirtänyt näin.

12. exd5 Rxd5 13. Rc3 Rxc3
Teorian yleisin siirto on 13…Bf6 ja Stockfish pitää sitä tarpeeksi pitkällä mietintäajalla parhaana. Silti ihmisten peleissä valkean tulos on selvästi parempi. 13…Bf6 14.Nxd5 cxd5 15.Ne3 (Bf4) Nc6 16.Nxd5 Be5 17.Re1 Re8= Esim. (Lysyj, Igor (2670) – Krishmatullin, Denis (2671) ½-½; Buhmann, Rainer (2584) – Kraemer, Martin (2520) ½-½.
Stockfishin jatko valkeana olisi 18.h4 h6 19.Qh5

14. Dg4 g6 15. Rh6+ Kg7 16. bxc3
Stockfish siirtäisi 16.Nf5+ Kg8 17.bxc3 h5

Lc8 17. Df4 Dd6 18. Da4 g5


18...g5

Mustan pitäisi olla huolissaan tornin ja ratsun jäämisestä mottiin a8-kulmaan, mutta sitähän ei laskemalla näe. Parempi siirto tässä suhteessa olisi 18…Rd8,joka ennakoi tornin vapauttamista a8:sta. 19.Re1 Be6 20.Bf4 Qa3

19. Te1
Tämän valkean siirron Stockfish tulkitsee sotilaan arvoiseksi virheeksi.

Kxh6 20. h4 f6 21. Le3
Tässä vaiheessa harha mustan edusta alkaa valjeta Stockfishille.

Lf5 22. Tad1 Da3 23. Dc4 b5 24. hxg5+ fxg5 25. Dh4+ Kg6
26. Dh1
Ihmissilmin outo siirto, mutta myös Stockfish näkee tämän helposti.

Kg7 27. Le4


27. Le4

27…Lg6
Musta on autuaan tietämätön tukalasta asemastaan. Laskemalla ei sitä pysty näkemään, mutta lautaa katsomalla ja tunnistamalla uhan motista tämä siirto lienee viimeinen oljenkorsi.
27…Lxe4 28.Dxe4 Kg8 29.De6+ Tf7 30.Dc8+ Lf8 31.Lxg5 Dxc3 Jatkovariaatioissa mustalla on hyvät mahdollisuudet saada purettua motti Ra8/Nb8. Ilman sitä tappio tulee väkisin.

28. Lxg6 hxg6 29. Dh3 Lf6 30. Kg2 Dxa2 31. Th1 Dg8 32. c4 Te8 


32...Te8

33. Ld4!
Tässä on jälleen yksi Stockfishin sokea piste. Jostain syystä se ei sitä millään näe, mutta siirron jälkeen ymmärtää heti seuraukset.

Lxd4 34. Txd4 Td8 35. Txd8 Dxd8 36. De6 Rd7 37. Td1 Rc5 38. Txd8 Rxe6 39. Txa8 Kf6 40. cxb5 cxb5 41. Kf3 Rd4+ 42. Ke4 Rc6 43. Tc8 Re7 44. Tb8 Rf5 45. g4 Rh6 46. f3 Rf7 47. Ta8 Rd6+ 48. Kd5 Rc4 49. Txa7 Re3+ 50. Ke4 Rc4 51. Ta6+ Kg7 52. Tc6 Kf7 53. Tc5 Ke6 54. Txg5 Kf6 55. Tc5 g5 56. Kd4 1-0

Näiden pelien perusteella herää väistämättä kysymys kuningatarintialaisen tulevaisuudesta. Pieni henkireikä mustalla näyttäisi olevan, mutta toisaalta niiden testaaminen AlphaZeroa vastaan voisi osoittautua sittenkin turhaksi toivoksi. Varmaa on, että nämä pelit tulevat muokkaamaan teoriaa ihmistenkin peleissä.


Mitä luonto edellä, sitä AlphaZero perässä


AlphaZero perustuu kahteen asiaan. Ensinnäkin se pyrkii jäljittelemään ihmisaivojen joustavuutta, yleiskäyttöisyyttä ja itseoppivuutta. Toiseksi se pyrkii hyödyntämään satunnaisilmiöitä, joista suurten yksikkömäärien ollessa kyseessä kumpuaa yllättäviäkin ilmiöitä ja jotka eivät ole kovinkaan kaukana oikeasta taikuudesta.

Shakkipelin erilaisten mahdollisten asemien määrästä on kiistelty melkein yhtä kauan, kuin peliä on pelattu. S. Steinerberger esitti International Journal of Game Theory (2014) -julkaisussa laskelman, jonka mukaan tuo luku olisi 2^155= 4.6*10^46. . Luvun mittakaavasta antaa käsityksen se, että atomien määrä maapallolla on luokkaa 10^50.

Uskallan väittää, ettei meillä ole aavistustakaan siitä, mitä salaisuuksia tuo asemien joukko pitää sisällään. Hyvän analogian antaa monen kappaleen fysiikka (many-body physics), joka luo raamit suuren, vuorovaikutuksessa olevan partikkelimäärän kollektiiviselle käyttäytymiselle. Vaikka yksittäisten partikkeleiden liikettä kuvaavat fysiikan lait olisivatkin yksinkertaisia, kokonaisuuden tutkiminen voi olla äärimmäisen vaikeaa. Usein esiin nousee ilmiöitä, joilla ei juurikaan ole tekemistä pohjalla vaikuttavien fysiikan lakien kanssa ja joita parhaimmillaan voi pitää ihmeinä.


Many-body physics


Perinteiset heuristiset shakkiohjelmat (kuten Stockfish) tarkastelevat asemia deterministisesti lukuisten kriteerien perusteella ja arvot saattavat olla dynaamisiakin riippuen pelin vaiheesta. Tärkeimmät kriteerit ovat materiaali, kuningasasema, nappuloiden aktiivisuus, keskustan ja diagonaalien hallinta, tilan (ruutujen) kontrollointi ja sotilasasema. Näitä kokenut shakkipelaajakin saattaa pelissä miettiä ja shakkiohjelma laskee asemalle arvon summaten numeerisia arvioita eri asioista. Suurin ongelma ohjelmalla on tasapainottaa asemalliset, ei-materiaaliset arvot nappuloiden pitkälti materiaalisten arvojen kanssa. Näennäisestä monimutkaisuudesta huolimatta matematiikka asemien arvioinnin taustalla on hyvinkin suoraviivaista. Nappuloiden kollektiivinen käyttäytyminen sen sijaan on kaikkea muuta kuin suoraviivaista, minkä AlphaZero on osoittanut.

AlphaZero käyttää myös toista satunnaisuuden tai kuten fysiikassa sitä kutsutaan, stokastisuuden voimaa. Luonto on rakentanut keinot hallita monen-kappaleen ongelmaa. Kaasut muuttuvat nesteeksi, jäätyvät ja kristalloituvat, metalli jäähtyy ja jähmettyy. Jos jäähdytys on riittävän hidasta, lämpöliikkuvuus katoaa. Atomeilla on mahdollisuus linjata itsensä ja muodostaa puhdas kide, joka on täysin järjestetty etäisyydellä, joka vastaa miljardeja kertoja yksittäisen atomin kokoa kaikissa suunnissa. Kysymyksessä on systeemin vähimmäisenergian löytäminen ja luonto pystyy sen löytämään, jos systeemiä ensin kuumennetaan riittävästi ja sitten jäähdytetään riittävän hitaasti. Siinä siis kaaoksesta nousee esiin järjestys. Tämän ilmiön simulointia on käytetty menestyksellä jo vuosikymmeniä monien laskennallisesti mahdottomien ongelmien ratkaisemiseen. Ns. simuloitu jäähdytys kykenee systemaattisesti löytämään globaaleja optimeja paikallisten optimien sijaan valtavasta vaihtoehtojen joukosta.


Simuloitu jäähdytys


AlphaZero hyödyntää simuloitua jäähdytystä sekä periaatetasolla että myös konkreettisesti. Se, ettei AZ hyödynnä olemassa olevaa teoriaa, vaan rakentaa sen itse tyhjästä, on puhdasta kaaosteoriaa. Toisaalta hakuprosessissaan se käyttää Monte-Carlo -metodia, joka on läheistä sukua simuloidun jäähdytyksen kanssa. Aikaisemmat yritykset käyttää Monte Carlo puuhakumenetelmää shakissa ovat epäonnistuneet ja kaikki parhaat shakkiohjelmat ovat päätyneet käyttämään sinänsä tehokasta Alfa-Beta -algoritmia. Kaikki deterministiset heuristiikat löytävät kuitenkin vain paikallisia optimeja. AlfaZeron hermoverkkoon perustuva asema-analyysi mahdollistaa kuitenkin stokastisen Monte-Carlo puuhaun ja yhdessä nämä kaksi aikaisemmasta täysin poikkeavaa menetelmää tuovat shakista esiin jotain aikaisemmasta täysin poikkeavaa.


AlphaZeron toimintaperiaate


Shakkia on hyödynnetty monenlaisissa aivotutkimuksissa. Eräässä kokeessa näytettiin erilaisia shakkiasemia muutaman sekunnin ajan sekä tavallisille ihmisille että shakin suurmestareille ja heitä pyydettiin sitten asettamaan nappulat uudelleen samoihin ruutuihin. Kun kyseessä oli todellisissa peleissä ja varsinkin huipputason peleissä esiintyneitä asemia, suurmestarit olivat nappuloiden asettamisessa nopeita ja virheettömiä. Jos taas asemat olivat satunnaisesti valittuja, suurmestarit olivat yhtä heikkoja kuin tavalliset ihmisetkin. Tutkimuksissa on myös havaittu, että huippupelaajat keskittävät automaattisesti huomionsa aseman kriittisiin kohtiin. Tästä on kuvaava esimerkki vuonna 2006 käyty ottelu Vladimir Kramnikin ja Deep Fritz shakkiohjelman välillä. Siinä pelin ollessa selvästi tasan Kramnik ei huomannut vastustajan yhden siirron mattia, minkä melkein kuka tahansa amatööri olisi helposti nähnyt. Kramnik oli itse täysin hämmennyksen vallassa. Hän oli laskenut kyseistä asemaa jo monta siirto aiemmin ja laski jälleen uudelleen yhä syvemmälle. Hän ei missään nimessä ollut väsynyt. Selityksen virheelle antoi venäläinen huippuluokan pelaaja ja kouluttaja, Alexander Roshal. Hänen mukaansa kyseinen asema, jossa valkean ratsu ruudussa f8 suojaa ruutua h7 ja jota valkea daami uhkaa, on äärimmäisen harvinainen. Sellainen ei synny suurmestareiden peleissä ja oli siten Kramnikille täysin sokea kohta. Kuvaavaa on, että peliä selostanut suurmestari ei myöskään tajunnut mattia, vaan jatkoi Kramnikin siirron jälkeen selostusta miettien valkealle aivan muita jatkoja.

AlphaZero pyrkii jäljittelemään ihmisen intuitiivista kokonaiskuvaa asemasta hermoverkon avulla. Se opettelee ns. vahvistusoppimisen avulla yrityksen ja erehdyksen kautta lähtien liikkeelle itse generoimistaan peleistä. Kyse on syväoppimisesta syvien hermoverkkojen avulla. Hyvien ja huonojen päätösten kokonaisvaikutus kuvataan ns. Q-verkon avulla, jossa pidetään taulukkoa pelin kaikista mahdollisista tiloista ja kaikista pelaajan mahdollisista toimenpiteistä kullekin tilalle. Jokaisessa taulukon solussa on seuraus pelaajan valinnasta kussakin pelin tilassa. Aikaisemmin vahvistusoppiminen yhdistettynä hermoverkkoihin on tuottanut epävakaita tuloksia. DeepMind Technologies yhtiön kehittämä Syvä Q-verkot -algoritmi (Deep Q-Networks (DQN)), joka käyttää satunnaisuutta hyväkseen, on onnistunut ratkaisemaan nämä ongelmat.


Syvä Q-verkko


AlphaZero rakentaa kokemustaan asemista pelaten pelejä Monte Carlo -puuhaun avulla ja simuloidut pelit päivittävät hermoverkon parametrejä pelien lopputulosten perusteella.

Se, että AlphaZero saavutti pelitasonsa muutamassa tunnissa, on harhaanjohtavaa. Hermoverkkoa oli opettamassa 5000 hermoverkkojen opettamiseen erikoistunutta prosessoria. Vaikka kyseessä olisivat olleet tavalliset prosessorit, tavallisella kotikoneella vastaavaan olisi mennyt melkein 6 vuotta. Mutta kun vertailuna ovat sovellutuskohtaiset prosessorit, voidaan tavallisella tietokoneella olettaa samaan menevän vuosikymmeniä.



Real AC = Alien Chess


Jos ihmiskunta sittenkin joutuisi otteluun kehittyneiden avaruusolioiden kanssa, AlphaZero ei ehkä sittenkään takaisi voittoa. Nuo toisesta dimensiosta tulevat entiteetit esittelisivät meille OmegaInfinity -shakkiohjelman, jossa kiteytyisi shakin perimmäinen periaate: shakki on lopulta äärimmäinen loppupeli 32:lla nappulalla. OmegaInfinity ei tekisi valkoisilla ensimmäistäkään siirtoa, vaan julistaisi matin 16986:lla siirrolla. Ihmiskunta ei tietenkään sitä uskoisi ja vielä vähemmän sitä, että nuo entiteetit tekisivät sen varsin yksinkertaisella tietokoneella ja Brute Force -algoritmilla.

Shakin täydellinen ratkaiseminen on mielipuolisen vaativa tehtävä. Tämän päivän tehokkain supertietokone, kiinalainen Sunway TaihuLight, on yli 10 miljoonaa kertaa tehokkaampi kuin tehokas kotitietokone. Yksinkertaista Brute Force -algoritmia käyttämällä se laskisi satoja miljoonia, jopa miljardi kertaa nopeammin asemia, kuin nopea kotitietokone. Silti edes Universumin historia ei riittäisi täydelliseen tulokseen. Itse asiassa siihen tarvittaisiin 64 tuhatta miljardia Universumin ikää. Mahdotonta?


Sunway TaihuLight


Jos Mooren laki toteutuisi ja prosessorien nopeus kaksinkertaistuisi joka vuosi, ei menisi kuin 80 vuotta ja supertietokone laskisi vuodessa kaikki shakkiasemat. Todellisuudessa nopeuden kehitys on ollut hidastumassa ja viimeisen 5 vuoden perusteella tähän menisi jo 126 vuotta. Jos nopeuden tuplaus veisikin 5 vuotta, aikaa tuohon kuluisi 400 vuotta. Todellisuudessa saatetaan puhua tuhannesta tai tuhansista vuosista, ennen kuin tietokone käytännössä voisi ratkaista shakin täydellisesti. Oli miten oli, mutta aivan mahdoton tehtävä ei ole, vaikkakin meidän sukupolvemme kannalta ehdottomasti tavoittamattomissa.

Jos äärimmäisen loppupelin ratkaiseminen 32:lla nappulalla on lievästi sanoen haastava tehtävä, se on silti lievä ongelma tuon datan tallentamisen rinnalla. Shakissa on siis 4,6 x 10^46 asemaa ja jokaisen aseman viemä tallennustila on 70 tavua. Tietokannan koko olisi siis 3,22 x 10^48 tavua. Kuinka paljon se on? Lasketaanpa.

Maailman suurin SSD-kovalevy on Samsung PM1633a, johon mahtuu 15,36 TB. Dimensioiltaan se on 9,9x7,1x1,5 senttiä. Kyseessä on melkoinen teknologinen ihme ja hintakin sen mukainen, n. 10500 dollaria. 26 tällaista älypuhelimen kokoista laitetta pystyisi tallentamaan kaikki, kaikilla mahdollisilla kielillä koskaan kirjoitetut kirjat. Jos olisi mahdollista pakata näitä kovalevyjä tiiviisti vieri viereen, niitä mahtuisi kuutiometriin 9314 kpl. Tuon kuution tallennuskapasiteetti olisi 143 petatavua. Hintaa sille kertyisi n. 100 miljoonaa dollaria.


Samsung PM1633a


Tarvittaisiin ainoastaan kaksi kuutiota tallettamaan kaikki puhelut Yhdysvalloissa vuoden ajalta. Siihen liittyen joidenkin villien arvailujen mukaan NSA:n Utahin datakeskuksen tallennuskapasiteetti olisi jottatavun luokkaa. Se vaatisi laskemiamme kuutioita peräti 7 miljoonaa kpl. Jos ne koottaisiin kuutioksi, sen sivun mitaksi tulisi melkein 200m. Energiaa pelkät kovalevyt söisivät puolet Olkiluodon ydinvoimalan sähköntuotannosta. Mahdottomimmaksi sen tekisi kuitenkin hinta. Tallennuskapasiteetti tällä tekniikalla maksaisi peräti kolme kertaa maailman kokonaisvarallisuuden verran.

Shakkitietokannan kannalta jottatavu ei riittäisi mihinkään. Shakin tietokanta vaatisi laskemiamme kuutioita niin monta, että ne täyttäisivät yhteensä 16000 aurinkoa, melko tarkkaan Arcturuksen verran. Energiaa se käyttäisi niin paljon, että fuusioreaktiossa kuluisi kuun verran materiaa alle tunnissa.


Arcturus


DNA pystyy tallentamaan perinteistä teknologiaa enemmän (215*10^15 tavua per gramma). Siltikään se ei riittäisi, sillä sitäkin tarvittaisiin 2500 x maapallon massa.

Kaikkein äärimmäisin tietokone on materia itsessään ja entropian perusteella yhteen kilogrammaan ja yhteen litraan pystyy teoriassa säilyttämään 2,66*10^30 tavua. Shakkiasemien tallentamiseen tarvittaisiin silti veden muodossa tilavuudeltaan kuutio, jonka sivut olisivat 100 km. Todellisuudessa se olisi mahdotonta virhehallinnan takia. Helpompi olisi toteuttaa tietokone, jossa materian jokainen atomi vastaisi yhtä bittiä, mutta silloin vaadittava massa olisi 2 miljoonaa kertaa edellistä suurempi.

Ratkaisu materiaalisessa maailmassa on siis sula mahdottomuus.


OmegaInfinity -shakkiohjelma käytännössä


Shakin pelaaminen 32 nappulaisena loppupelinä vaatisi aivan mahdottomia laskentatehoja ja vieläkin mahdottomamman datan tallennustilan. Silti sen toteuttaminen on mahdollista, kunhan lakkaamme ajattelemasta kuin Stockfish ja muut ”materialistiset” ohjelmat ja otamme mallia intuitiivisesta AlphaZero -ohjelmasta. Ratkaisuna ei voi olla laskentatehon, rationaalisen päättelyn ja/tai teknologian kehittäminen. Tarvitaan ratkaisu laatikon ulkopuolelta, tässä tapauksessa aika-avaruuden ulkopuolelta. Siis todellinen ”Alien technology” -ratkaisu. Sitä kutsutaan myös henkiseksi teknologiaksi vastakohtana materialistiselle teknologialle eli termi voisi olla myös ei-materialistinen. Kyse ei siis ole hengellisestä näkökulmasta - ei puolesta eikä vastaan. Eikä kyse ole uskonnosta, vaan teknologista.

Laskentaongelma


Ratkaisu vaatimukseen laskentatehoista on yllättävän yksinkertainen. Prosessoriksi riittää yksinkertaisen kännykänkin prosessori, sillä ratkaisu on prosessorin ulkopuolella. Jos nimittäin iteraatiot tapahtuvat menneisyydessä, mikään ratkaistavissa oleva ongelma ei ole liian vaikea. Itse asiassa vastaus on olemassa jo ennen ongelman esittämistä!


Iteraatio menneisyydessä


Aikasiirtymät saattavat kuulostaa tieteistarinalta, mutta tieteen valtavirran ulkopuoliset tieteelliset artikkelit ja -tutkimukset esittävät paljonkin teorioita ja jopa kokeellisia tuloksia. Pyörivät magneettikentät, niiden ryhmänopeudet ja vaihemodulaatiot, eksoottisen materian taivuttama aika-avaruus, negatiivisen energian lähettäminen menneisyyteen… Mitkään näistä eivät vaadi teknologisesti suuriakaan ponnisteluja, vaan sen sijaan avointa mieltä ja rohkeutta todellisuuden tutkimisessa.


Muistiongelma


Musta aukko olisi ainoa mahdollinen materialistinen ratkaisu 3.22 x 10^48 tavun tallentamiseen. Itse asiassa siihen pystyisi pelkästään vetyatomin kokoinen musta aukko. Ongelmana on kuitenkin se, että mustan aukon tapahtumahorisonttia lähestyttäessä aika on käynyt kiihtyvällä vauhdilla Universumin historian loppuun, eikä informaatio enää ole käytettävissä tässä Universumissa. Eli se siitä vaihtoehdosta.

Ehkä vastaus tähän laskentaongelmaakin suurempaan ongelmaan on tämän ulottuvuuden ulkopuolella. Vedalaisen sanskriitin kielessä on termi "akasha", joka tarkoittaa ”avointa avaruutta, tyhjyyttä ja näkyväksi tulevaa”. Pythagoras kutsui sitä termillä eetteri, minkä materialistisen reduktionismin mukainen fysiikka tulkitsi joksikin väliaineeksi. Ehkä sitä voisi nykytermein kutsua matriisiksi. NDE (near death experience) -kokemusten kuvauksissa esiintyy usein menneitä elämäntapahtumia sellaisella tarkkuudella, ettei niitä ole ikinä voinut sillä tarkkuudella havaita tai kokemus on jonkun toisen läsnäolijan näkökulmasta. Johonkin informaatio on tallentunut, koska havaitsijan aistit eivät ole voineet ottaa sitä informaatiota vastaan. Muistin täytyy olla mittaamaton, jos jokaisen mahdollisen havainnoitsijan kokemukset pienintäkin yksityiskohtaa myöten on tallentunut johonkin.

Jos on vaikea uskoa tällaisiin kokemuksiin, ehkä helpompi on ottaa vastaan matemaattisfysikaalisia kuvauksia imaginäärisistä maailmoista. Jos maailma ei ole materiaalinen, ei myöskään informaatiolla ole materiaalisia rajoitteita. Jos johonkin tieto mahtuisi, niin sinne.




AlphaZeron pelit tuntuivat ensivaikututelmana taikuudelta. Miltä ne olisivat tuntuneet 20 vuotta sitten? Aikasiirtymät ja hyperdimensiot voivat tuntua taikuudelta juuri nyt, mutta samoin kuin AlphaZeron kohdalla, mullistavastakin asiasta tulee saman tien arkipäivää, kun se tuodaan kollektiiviseen tietoisuuteen.


Shakkitietokoneiden historiaa


Alan Turing määritteli ensimmäisen shakkiohjelman tietokoneille vuonna 1947 ja kirjoitti sellaisen vuonna 1950. Ohjelmalle sopivaa tietokoneympäristöä ei vielä ollut olemassakaan, joten ohjelmalla pystyi pelaamaan ainoastaan niin, että Turing itse emuloi tietokonetta. Ohjelman, TurboChamp nimeltään, ainoassa käymässä pelissä Turing käytti jokaiseen siirtoon puoli tuntia. Lopulta tuon pelin voitti Alick Glennie, josta tuli historian ensimmäinen tietokoneen voittanut ihminen.

Ensimmäisen tietokoneessa oikeasti toimineen shakkiohjelman kirjoitti vuonna 1951 Dr. Dietrich Prinz ja sillä pystyi ratkaisemaan yksinkertaisia kahden siirron matteja. Ensimmäisen täysiverisen shakkiohjelman kirjoitti Alex Bernstein MIT:ssa ja tuo ohjelma pystyi sen aikaisella huipputietokoneella nopeuteen 4 puolisiirtoa 8 minuutissa.

Vuonna 1958 shakkiohjelmat tekivät läpimurron, kun NSS-niminen ohjelma voitti ensimmäistä kertaa ihmisen. Vastustajana oli sihteeri, joka oli oppinut tunnissa shakin säännöt juuri ennen peliä. 


NSS


Ensimmäinen tietokoneiden välinen ottelu pelattiin vuonna 1966, kun neuvostoliittolainen tietokone voitti MIT:n tietokoneen kirjepelissä 3-1. Samana vuonna tietokone osallistui ensimmäistä kertaa shakkiturnaukseen. Yksi tasapeli ja neljä tappiota amatööriturnauksessa antoi sille USCF -vahvuuden 1243. Ensimmäinen puhtaasti tietokoneturnaus (Pohjois-Amerikan ACM) tapahtui vuonna 1970 ja sen voittaja CHESS piti eri versioilla titteliä hallussaan aina vuoteen 1973 asti. Ensimmäisen MM-turnauksen voitti vuonna 1974 ylivoimaisesti neuvostoliittolainen KAISSA brittiläisellä tietokoneella. Vihdoin vuonna 1976 tapahtui ensimmäinen vakavasti otettava kohtaaminen ihmisten ja koneen välillä. Paul Masson turnauksen B-ryhmän voitto antoi amerikkalaiselle CHESS 4.5: lle vahvuusluvun 1950. Viisi vuotta myöhemmin (1981) Cray Blitz voitti Missisipin osavaltion mestaruuden 5-0 -tuloksella ja vahvuusluvulla 2258. Vuonna 1985 HITECH saavutti jo vahvuusluvun 2530. Toisaalta samana vuonna Garry Kasparov pelasi simultaanin 32:a huipputietokonetta vastaan voittaen ottelun 32-0.

Ihmiskunnan viimeisen taistelun koneita vastaan aloitti DEEP THOUGH vuonna 1988. Se jakoi Yhdysvaltain avoimen mestaruuden Tony Miles:n kanssa suorituksella, joka vastasi peräti vahvuutta 2745. Vuoden lopulla sen virallinen vahvuus oli kuitenkin ainoastaan 2550. Bent Larsenista tuli ensimmäinen turnauksessa koneelle hävinnyt suurmestari. Seuraavana vuonna Garry Kasparov voitti kuitenkin DEEP THOUGH:n 2-0. Sen kehittäjät väittivät ihmiskunnan häviävän heidän koneelleen kolmessa vuodessa, mutta siihen oli menevä vielä paljon pidempään.

1992 oli käänteentekevä tietokoneshakissa, sillä silloin mikrotietokone voitti ensikertaa tietokoneiden avoimen mestaruuden. Tässä vaiheessa tietokoneet alkoivat pärjätä maailman parhaille shakin pelaajille pikapeleissä, mutta samaan aikaan tasokkaiden ohjelmien saaminen kotikoneisiin opetti myös ihmiset pelaamaan koneita vastaan. Koneiden tehot kasvoivat ja ohjelmat kehittyivät, mutta niiden ihmisiä vastaan pelatuissa peleissä ansaitsemat vahvuusluvut eivät kasvaneet. Vuonna 1996 järjestetyssä ihmiskunta vastaan kone -turnaukseen osallistui 50 ihmistä mestareista suurmestareihin ja 50 shakkiohjelmaa. Turnaus päättyi Yasser Seirawanin 6-0 voittoon ja paras shakkiohjelma oli QEST 4.5/6 -tuloksella, mikä vastasi vahvuutta 2652. Tietokoneiden vahvuudet ihmistä vastaan eivät tuon jälkeen juurikaan nousseet kymmeneen vuoteen.

Hyvin tunnettu ja koneiden voittona ihmisistä julistettu Deep Bluen ja Kasparovin välinen ottelu vuonna 1997 ei kuitenkaan ole koko totuus ja tuskin osatotuuskaan. Deep Blue tosin voitti ottelun 3.5-2.5, mutta ottelun asetelmat olivat vähintäänkin epäoikeudenmukaiset. Ohjelman kehittäjät olivat keskittyneet luomaan ensisijaisesti Kasparovin kaatajan ja kaiken lisäksi ohjelmoijat säätivät ohjelmaa kesken ottelun. Kasparovilla ei vastaavasti ollut muuta tietoa ohjelmasta, kuin mitä oli itse nähnyt voittamassaan edellisessä ottelussa. Tavallaan nurinkurista on, että koneen takana oli armeija ihmisiä, kun taas Kasparov oli täysin yksin. Uskallan väittää, ettei Deep Blue olisi pärjännyt samoilla asetuksilla johtavia mikrotietokoneohjelmia vastaan tai jos Kasparoville olisi annettu tilaisuus revanssiin, voittaja olisi ollut ihminen huomattavalla marginaalilla.


Deep Though - Kasparov 1997


Vuosina 2002-2005 ihmiskunnan kärkipelaajat Garry Kasparov, Vladimir Kramnik ja Rustam Kasimdzhanov pelasivat otteluissaan tasan johtavia shakkiohjelmia vastaan, kunnes viimein vuonna 2006 Deep Fritz 10 voitti Kramnikin 4-2. Kramnikin vahvuusluku ottelun aikaan oli 2760 ja Deep Fritzin voitto antaa +120 pistettä eli sen vahvuus tuossa ottelussa olisi ollut ihmisten rankingissa 2880. Seuraavat detaljit saattavat kuulostaa puuduttavilta, mutta tässä tapauksessa niillä on yllättävä merkitys.

Ottelussa käytössä olleen koneen prosessori oli 2x Intel Core 2 Duo 5160. Yhden prosessorin benchmark on 1971 ja kahden tällaisen hyöty moniprosessoidussa shakkiohjelmassa olisi luokkaa 3500.  Nykyään kaikkien aikojen tietokoneiden listalla (CCRL 40/40) Deep Fritzin vahvuusluku on 2832. Tuon listan referenssiprosessori on AMD Athlon 64 X2 4600+, jonka benchmark on 1365. Kramnik-Deep Fritz -ottelun koneen tehokkuus oli siis reilut 2x CCRL 40/40 -rankingin referenssi ja nyrkkisääntönä koneen nopeuden tuplaus tarkoittaa +50 pistettä vahvuusluvussa. Näin ollen Deep Fritz 10 vahvuus Kramnik – Deep Fritz -ottelussa on täysin linjassa CCRL 40/40 listan vahvuuden kanssa (2880-50 = 2830 ~2832).

Tästä taas seuraa, että CCRL 40/40 -rankingia voi verrata suoraan ihmisten vahvuuslukuihin. Tietokoneiden listan kärjessä on tällä hetkellä AsmFish 051117, joka on Stockfish -ohjelman pohjalta rakennettu paranneltu versio. Tämän vahvuus listalla on 3426, kun AlphaZeroa vastaan pelannut Stockfish 8 on vahvuudeltaan 3389. Magnus Carlsenin kaikkien aikojen korkein ihmisen vahvuusluku oli toukokuussa 2014 2882. Eroa esimerkiksi Stockfish 8 -ohjelmaan on 507 pistettä, mikä tarkoittaa, että Stockfish voittaisi Carlsenin 90% peleistä ja 10% menisi tasan. Voitto huippukoneista on nykyaikana jo käytännössä mahdottomuus.