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. [1]
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. [2]
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. [2]
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. [2]
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. [3]
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. [3]
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. [3]
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. [3]
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. [3]
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. [3]
2. Deep Blue projekt ja arendamine
tekst
3. Esimene matš
tekst
3. Teine matš
tekst
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. [2]
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 [2].
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 [4].
Allikad
https://chessentials.com/history-of-chess-computer-engines/ (enne deep blue-d ja pärast deep blue-d)
https://www.pcworld.com/article/451599/a-brief-history-of-computer-chess.html (enne deep blue-d)
https://www.ibm.com/ibm/history/ibm100/us/en/icons/deepblue/team/ (tegijad)
https://archive.org/details/behinddeepblue/mode/2up (põhivenna, Feng-Hsiung Hsu memuaarid. Projekt ja arendamine, matš 1 ja matš2)
- ↑ A. Hercules, 15.05.2020, "How does a chess engine work? A guide to how computers play chess", https://herculeschess.com/how-does-a-chess-engine-work/, (vaadatud 15.10.2021)
- ↑ 2.0 2.1 2.2 2.3 2.4 V. Nemec, 23.01.2019, "History of chess computer engines", https://chessentials.com/history-of-chess-computer-engines/, (vaadatud 08.10.2021)
- ↑ 3.0 3.1 3.2 3.3 3.4 3.5 IBM, (n.d.), Deep Blue, https://www.ibm.com/ibm/history/ibm100/us/en/icons/deepblue/team/, (vaadatud 08.10.2021)
- ↑ D. Hassabis, T. Hubert, D. Silver, J. Schrittwieser, 06.12.2018, "AlphaZero: Shedding new light on chess, shogi and Go", https://deepmind.com/blog/article/alphazero-shedding-new-light-grand-games-chess-shogi-and-go, (vaadatud 08.10.2021)
