Deep Blue

Malearvuti

Malearvutid on arvutid, mis on mõeldud male mängimiseks. Malearvutid suudavad analüüsida male seisu ning koostada nimekirja parimatest võimalikest käikudest. Mängu seisu hinnatakse algoritmiga, mis vaatleb mitmeid komponente: näiteks malendite arvu laual ja kummagi poole malendite ühisväärtust, võimet malendeid liigutada, kuninga kaitset ja nii edasi. Igale komponendile on määratud tähtsuse järgi väärtus ning nende kokkuliitmisel saadakse kogu seisu hinnanguline väärtus. Kui seisu väärtus on väga väike, jäetakse see automaatselt lõpphinnangust kõrvale. Seejärel vaadeldakse oponendi võimalikke vastaskäike, siis taas enda võimalikke käike ja nii edasi, nii palju kui malearvuti riistvara võimaldab. Kui käikudele on hinnangud antud, hakkab malearvuti liikuma parimat lõpptulemust mööda tagasi hetkelise seisu suunas, leides seeläbi parima tegutsemistee. Üldiselt eeldavad malearvutid, et ka vastane teeb enda jaoks parima võimaliku käigu.

Enne Deep Blue-d

Mõte luua malet mängiv masin on juba mitu sajandit vana. 1770. aastal esitles ungari leiutaja Wolfgang von Kempelen Viinis oma uut leiutist, mida hakati rahvasuus kutsuma “Türklaseks”. Tegemist oli idamaistes rõivastes robotiga, mis näiliselt suutis enda ees oleval laual inimeste vastu edukalt malet mängida. Reaalsuses oli laua alla jäetud tühi ruum, kus peitis end robotit juhtiv inimene.

Tõeliste malearvutite areng algas pärast teist maailmasõda. 1949. aastal avaldas Ameerika matemaatik Claude Shannon referaadi teemal “Arvuti programmeerimine male mängimiseks”. Aasta hiljem valmis Briti matemaatiku ja arvutiteadlase Alan Turingu maleprogramm Turbochamp. Turing kirjutas Turbochampi paberil, ilma et tal oleks olnud ligipääsu arvutile. Tolleaegsed arvutid olid Turingu maleprogrammi jaoks veel liiga nõrgad. 1951. aastal paigaldas Dietrich Prinz Ferranti Mark I arvutile algoritmi, mis suutis lahendada olukordi, kus matti oli võimalik saavutada kahe käiguga. 1957. aastal lõi IBM-i insener Alex Bernstein esimese malet otsast-lõpuni mängida suutva programmi.

Kuue- ja seitsmekümnendatel hakkas malearvutite võimsus tempokalt kasvama. Riistvara paranes ning muutus kiiremaks ja algoritmid läksid peenemaks ja osavamaks. Lisaks hakkasid malearvutid avalikkuse seas laiemat populaarsust koguma. Esimene arvutitevaheline malevõistlus peeti 1970. aastal New Yorgis ja esimene malearvutite maailmameistrivõistlus peeti 1974. aastal Stockholmis. Malearvutid suutsid aina tugevamaid vastaseid võita. 1967. aastal sai MacHack VI esimene malearvuti, mis suutis võita inimest, arvuti reitinguks hinnati 1300. Kümme aastat hiljem võitis aga Chess 4.5 Minnesota Openi, võites A-klassi mängijat Stenbergi ja saades reitingu 2271. Samas tugevaimatele mängijatele jäid malearvutid alla.

Deep Blue tegijad

Feng-hsiung Hsu: Dr. Feng-Hsiung Hsu sai bakalaurusekraadi elektrotehnikas Taiwani Riiklikus Ülikoolis ning doktorikraadi arvutiteaduses Carnegie Melloni ülikoolis. 1988 lõi ta esimese malearvuti, mis jõudis suurmeistri taseme reitinguni. Aasta hiljem ühines ta IBM-iga, kus ta jätkas oma malearvuti arendamist teiste IBM-i teadlastega. Tema peamiseks ülesandeks oli riistvara paigaldamine ja katsetamine.

Murray Campbell: Dr. Murray Campbell sai arvutiteaduses bakalaureuse- ja magistrikraadi Alberta ülikoolis ning doktorikraadi Carnegie Melloni ülikoolis. Ta hakkas 1986. aastal tegema koostööd Feng-Hsiung Hsuga, et luua malearvuti, millest lõpuks kasvas välja Deep Blue. IBM-iga ühines ta koos Feng-Hsiung Hsuga. Deep Blue kallal töötamise ajal oli tema rolliks malemängu hetkeseisu hindamisvõime arendus.

Chung-Jen Tan: Dr. Chung-Jen Tan sai bakalaureusekraadi elektrotehnikas Seattle´i ülikoolist 1963. aastal ja doktorikraadi Columbia ülikoolist 1969. aastal. Samal aastal asus ta tööle IBM-i T. J. Watsoni Uurimiskeskuses. 1992. aastal ühines ta vanemjuhina Deep Blue meeskonnaga. Ta oli projekti peamine eestkõneleja ning meeskonna tööfilosoofia väljatöötaja.

Joseph Hoane Jr.: Joseph Hoane Jr. lõpetas Illinoisi Urbana Ülikooli 1984. aastal arvutiteaduse bakalaureusekraadiga ning Columbia ülikooli 1994. aastal arvutiteaduse magistrikraadiga. Deep Blue meeskonnaga ühines ta 1990. aasta novembris, kuid IBM-is töötas ta juba varem. Hoane tegeles Deep Blue parima käigu otsimise algoritmiga.

Jerry Brody: Jerry Brody asus IBM-is tööle 1978. aastal. Pikka aega töötas ta T. J. Watsoni Uurimiskeskuses ning 1990. aastal ühines ta Deep Blue projektiga abistava insenerina.

Joel Benjamin: Joel Benjamin sai 1977. aastal kolmeteistkümneselt noorimaks Ameerika Ühendriikide malemeisteriks. 1980 sai temast rahvusvaheline meister. Benjamin tegi Deep Blue meeskonnaga lühidalt aastatel 1996-1997 koostööd, olles Deep Blue treeneriks.

Deep Blue

Deep Blue eellased

Enne Deep Blue’d leidsid esimesed katsetused ehitada malearvutit aset Carnegie Mellon ülikoolis aastal 1985 Feng-hsiung Hsu, Thomas Anantharaman ja Murray Campbelli poolt. Too süsteem - nimega Chip Test - kasutas ühe-kiibilist maleliigutuse generaatorit, mis oli võimeline uurima 500,000 positsiooni sekundi kohta. Hiljem nimetati projekt ümber Deep Thought’iks, mis tulenes Douglas Adamsi romaaniseeriast. Deep Thought oli võimeline uurima 700,000 positsiooni sekundi kohta. Aastal 1988 saatis Deep Thoughti, projekti mille rahastus oli nigel, edu ning IBM kutsus arendajad liituma IBM Researchiga, et välja arendada järgmise generatsiooni malearvuti, mille nimeks sai Deep Blue. IBM soovis välja selgitada, kas andekates malemängijates on midagi nii erilist, mida arvutid ei ole võimelised õppima.

Deep Blue

Deep Blue on paralleelsüsteem võimeline uurima kõiki võimalikke käike malemängu algusest peale. Deep Blue kasutab 30-sõlmelist IBM RS/6000 SPT arvutit, mis kasutas ühekiibilist otsingumootorit. Igal SP protsessoril on 16 malekiipi. SP süsteemil on 28 sõlme MHz P2SC protsessoriga ning 2 sõlme 135 MHz P2SC protsessoriga. Iga kiip oli võimeline uurima kuni 2,5 miljonit malepositsiooni sekundi kohta. Deep Blue algoritmil on erinevaid funktsioone, nt erinevate ründamiste välja mõtlemine. Kuigi Deep Blue genereerib ühe käigu korraga, kalkuleerib ta kõikvõimalikud käigud enne ära ja valib kõige parema neist välja. Maleprogramm kirjutati C keeles ning seda jooksutati IBM AIX süsteemil. Kui Deep Blue oli aastal 1989 võimeline uurima 2 miljonit malepositisooni sekundis ja aastal 1991 7 miljonit, siis aastaks 1996 oli Deep Blue võimekus tõusnud 100 miljoni malepositsioonimi sekundi kohta ning 1997 aastaks sai Deep Blue 200 miljonit positsiooni uurimisega hakkama. Kokku läks IBM-il aastate 1985 - 1997 jooksul üle 100 miljoni dollari, et rahastada Deep Blue projekti.

Deep Blue arendus

Deep Blue II jaoks loodi uue generatsiooni riistvara, mistõttu muutus süsteem kiiremaks pea kaks korda. Samuti täiendati süsteemi maleteadlikkust, lisades erinevaid funktsiooni malekiibile, mistõttu süsteem hakkas paremi aru saama positsioonidest ja malekontseptsioonist. Malekiibid uurisid erinevaid positsiooni ning samuti lisati positsioonidele kaalud, mistõttu muutus käigu efektiivsuse hindamine täpsemaks. 1997 aasta Deep Blue oli võimeline uurima 100 - 200 miljonit käiku sekundis, olenevalt positisoonist. Kuigi Deep Blue arendajate arust oli Deep Blue II palju võimekam, saavutati turniiril kõigest viik.

Esimene matš

Esimene matš toimus 1996. aasta veebruaris Philadelphias ning Deep Blue vastaseks oli tolleaegne maailmameistri Garry Kasparov. Kohtumine koosnes kuuest mängust ning auhinnarahaks oli 500 000 dollarit. Garry Kasparov oli oma võidus nii kindel, et soovis matši auhinnaraha määrata ainult võitjale, kuid lõpuks lepiti kokku, et raha jagatakse mõlema osapoole vahel, võitja saab 400 000 ning kaotaja 100 000 dollarit. Garry Kasparov oli 1984 aastast kuni oma karjääri lõpuni (2005 aastani) maailma edetabelis esimesel kohal.

Esimene mäng kuuest toimus 10. veebruaril. Deep Blue alustas valgete malenditega ning Kasparov mustadega. Males on valgete malenditega alustajal alati eelis. Mängu pikkuseks oli 37 käiku ning võitjaks osutus Deep Blue. Tegemist on väga märgilise võiduga, sest see oli esimene mäng, kus malearvuti suutis võita valitsevat maailmameistrit, mängides tavaliste malemängu reeglite järgi.

Järgmisel päeval toimunud teise mängu võitis Garry Kasparov, kuid see mäng ei möödunud Deep Blue arendajate jaoks viperusteta. Nimelt uuendati öö enne mängu Deep Blue avangufaili, kuid üleslaadimisel tekkinud probleemi tõttu ei olnud Deep Blue’l uut avanguraamatut. Sellest hoolimata suutis Deep Blue end suhteliselt heasse seisu mängida, kasutades eelnevalt loodud hindamissüsteemi. Hiljem mängu analüüsides selgus, et lisaks laadimata jäänud avanguraamatule, oli Deep Blue koodis viga, mis analüüsis ning hindas valesti odade paiknemist.

Kolmas ning neljas omavaheline mäng lõppes mõlema osapoole jaoks viigiga. Kolmandas mängus oli Deep Blue’l taas võimalus mängida valgete malenditega ning tegemist oli väga tasavägise kohtumisega. 39 käigu ajal otsustasid mõlemad osapooled, et on rahul viigiga, kuid Deep Blue tiim tundis, et raiskasid ühe oma võimalustest valgete malenditega mängus võita. Neljanda mängu puhul tuli ette ootamatu olukord, kus Deep Blue oli ühel hetkel läinud ekraanisäästja režiimile. Nimelt oli Deep Blue operaatoritel võimalus lahkuda malearvuti kõrvalt ainult siis, kui malearvuti teeb või on just teinud oma käigu. Deep Blue kõrval olnud operaator Feng-Hsiung Hsu, kasutaski võimalust tualeti külastamiseks, hetkel mil Deep Blue oli oma käigu teinud, kuid ei saanud koheselt oma positsioonile naasta, sest Garry mõtlemisperioodi jooksul ei olnud see lubatud. Operaator sai naasta alles siis, kui Kasparov oli oma käigu sooritanud. Selle tulemusena, oli malearvuti ekraanisäästja režiimis ning kui operaator sisestas Garry käigu, jooksis Deep Blue kokku. Vajalik oli Deep Blue uuesti käivitamine, kuid mängukella selleks ajaks ei peatatud ehk Deep Blue tiim kaotas vajalikku aega. Sellest hoolimata ei suutnud Kasparov mängu enda kasuks kallutada, nii lepiti viimaks viigiga ning selle tulemusena oli kogu matš ka viigiseisus, 2:2.

Viiendas mängus, peale 23 käiku, pakkus Garry, Deep Blue tiimi üllatuseks, võimalust lõpetada mäng viigiga. Deep Blue tiim oli varasemalt kokku leppinud, et viigipakkumised arutatakse läbi kogu meeskonnaga ehk operaatoriga mängulaua juures ning ülejäänud tiimiga tagaruumis. Keegi neist ei oodanud sellist pakkumist, sest eelnevad viigid olid alles siis kokku lepitud, kui mäng oli pikemalt kestnud ning viigiseis oli kindlalt näha. Deep Blue tiim keeldus sellest pakkumisest ning mäng jätkus. 24 käiku hiljem oli aga selge, et mängu võidab Kasparov. Peale seda võitu oli seis 3:2 Garry kasuks, kes vajas kogu matši võitmiseks viimasest mängust vähemalt viiki.

Viimases mängus seisis Deep Blue tiimil ees raske ülesanne, võita Garry Kasparovi, kasutades musti malendeid. Kõik nende eelnevad avanguraamatud, olid üles ehitatud eesmärgile, proovida musti malendeid kasutades viigistada, kuid nüüd piisas neile eelmise mängu kaotuse tõttu ainult võidust. Mäng lõppes Kasparovi võiduga ning ühes sellega võitis Garry Kasparov ka matši üldskooriga 4:2.

Teine matš

Kordusmatš toimus 1997. aasta mais New Yorkis, mis andis Deep Blue arendajatele võimaluse aasta jooksul oma malearvutit muuta ning arendada, et olla uueks matšiks rohkem valmis. Esimese ja olulise muudatusena, disainiti Deep Blue jaoks uus malemikroprotsessor, millel oli uus ja võimsam hindamisfunktsioon, suutes eelneva 6400 positsiooni asemel hinnata umbes 8000 positsiooni. Lisaks suurendati oluliselt ka otsingu kiirust ning treeningmängude puhul kasutati võimekate male suurmeistrite abi, kellel lasti Deep Blue vastu mängida. Teise mängu auhinnafond oli 1,1 miljonit dollarit, millest võitjale kuulus 700 000 dollarit. Melu ning kajastus kordusmatši ümber oli kordades suurem kui esimese matši puhul, nii oli ka pingetega võistlejate vahel, sest erinevalt esimesest mängust, oli Deep Blue’l üsna suur šanss matš võita. Mängiti esimesele kohtumisele sarnaste reeglite alusel, kus matš koosnes kuuest mängust ning mängude puhul olid kasutusel tavalised malereeglid.

Esimese mäng algas üsna tavapäratult, kus mõlemad osapooled kasutasid suurmeistrite poolt tuntuid käike, kuid peale Garry ootamatut käiku, sai Deep Blue meeskonnale selgeks, et Kasparov on otsustanud kasutada anti-computer taktikat. Sellise taktika puhul üritatakse ebaoptimaalsete käikudega kasutada ära malearvuti nõrkusi positsioonide hindamisel. Mäng lõppes Kasparovi võiduga ning selle tulemusena asus ta kohtumist 1:0 juhtima.

Teise mängu puhul jätkas Kasparov oma anti-computer taktikat, kuid mäng lõppes Deep Blue jaoks võidukalt. Selle tulemusena, oli koguseis viigiline. Mängu hiljem analüüsides selgus, et Kasparovil oli märkamata jäänud vähemalt üks kriitiline käik, mille tulemusena oleks tal olnud võimalik kohtumine viigiga lõpetada.

Järgmised kolm mängu lõppesid viigiseisus, mis tähendas, et kogu matši võitja selgub alles viimases kohtumises, seis oli 2.5:2.5. Erinevalt eelnevatest mängudest, ei kasutanud Kasparov viimase mängu alguses kummalisi käike, vaid jäi truuks tuttavatele lahendustele. Rahulikule algusele vaatamata, tegi Kasparov ühe riskantse anti-computer käigu, mis ei toonud soovitud tulemust ning pärast 19 käiku oli võitjaks Deep Blue, võites seega korduskohtumise tulemusega 3.5:2.5.

Pärast Deep Blue-d

Deep Blue võitu Kasparovi üle peeti inimeste ja masinate vahelise võistluse lõpuks, kuid siiski oli veel mõnda aega malearvutitel parimate maletajate vastu mängimisel raskusi. 2002 mängisid maailmameister Vladimir Kramnik ja malearvuti Deep Fritz viiki. Sama juhtus ka 2003. aastal peetud Kasparovi ja Deep Junior 7 ning Kasparovi ja X3d Fritzi vahelistel mängudel. Pärast 2003. aastat on aga vahe malearvutite ja inimeste vahel pidevalt kasvanud ning arvutid on suutnud maailma parimaid inimmängijaid aina kindlamini võita.

Malearvutite võimekus on kasvanud küll pidevalt, kuid aeglaselt. 2017. aastal tuli aga suur muutus, kui ilmus teade, et Google AI firma Deep Mind on arendamas uut malearvutit, AlphaZerot. AlphaZero lähenemine malemängule erineb radikaalselt varasematest masinatest . Arvutil on tehisnärvivõrk ning üldised algoritmid, mis ei tea mängust midagi muud peale peamiste reeglite. AlphaZero mängib esiteks enda vastu miljoneid mänge. Alguses on käigud täiesti suvalised, kuid aja jooksul õpib masin oma vigadest ning hakkab tulevikus tegema käike, mis on toovad tõenäoliselt parima tulemuse. Käikude valimiseks kasutatakse Monte-Carlo puu uurimise algoritmi. Kuna mängimistiili või muid reegleid pole ette antud, võimaldab see AlphaZerol mängida väga dünaamiliselt ja loominguliselt, sarnanedes rohkem inimestele kui muudele malearvutitele. AlphaZero on tunduvalt osavam kui klassikalised malearvutid. Muuseas suudeti võita valitsevat malearvutite maailmameistrit Stockfishi, mille vastu mängiti tuhat mängu. AlphaZero suutis neist võita 155 ning viiki mängida 839. Kaotati vaid kuus mängu .