Van 3 tot 10 mei bindt Garri Kasparov in New York de strijd aan met IBM’s supercomputer Deep Blue, een machtige rekenaar met 256 parallel geschakelde processoren. Daarna wil Big Blue het rekenmonster inzetten bij wetenschappelijke vraagstukken. Computerschaak zou de basis leggen voor allerlei wetenschappelijke toepassingen. Daartegenover staat de opvatting dat het niets oplevert – behalve sterke schaakprogramma’s.
In de Tweede Wereldoorlog was het Alan Turings taak de code van de Duitse vloot te breken. Tijdens vrije uren op het hoofdkwartier van de Britse afdeling voor cryptologie, Bletchley Park, besprak de excentrieke, briljante geleerde graag algoritmes voor het schaakspel met zijn collega’s. Nu zouden zijn hersenspinsels schaakprogramma’s worden genoemd. Toen niet, want de eerste elektronische computer werd pas jaren later gemaakt.
Turing moest nog even geduld uitoefenen voordat hij een computer kon laten schaken. Pas in 1950 was het zover. Zijn programma werkte volgens principes die in 1944 waren beschreven door collega-wiskundigen Morgenstern en Von Neumann, de grondleggers van de speltheorie. Deze geleerden hadden ontdekt dat een spel is voor te stellen als een boom, waarbij de mogelijkheden zich na elke zet vertakken. Turings computer zocht steeds naar de beste vertakking, ofwel de beste zet.
Het schaakspel had intussen ook de interesse gewekt van Claude Shannon, de belangrijkste architect van de informatietheorie. Evenals vele andere wetenschappers in die tijd dacht hij bij computers meteen aan kunstmatige intelligentie. Het schaakspel leek hem bij uitstek geschikt om de jonge computer enige ontwikkeling bij te brengen.
De mogelijkheden van de computer schenen onbeperkt en de toekomst leek zo dichtbij. Vóór 1970 zou de computer de heerschappij over de 64 velden overnemen, en die triomf zou de weg openen naar andere toepassingen. Aldus luidden de voorspellingen van programmeurs aan het eind van de jaren vijftig, nadat de computer voor het eerst een mens op het schaakbord had verslagen.
‘Brute kracht’-methode
Nu, bijna veertig jaar later, is de vraag of de voorspellingen van de toenmalige programmeurs alsnog zullen uitkomen – of is alle hoop vervlogen? Van 3 tot 10 mei zal Garri Kasparov in New York de strijd aanbinden met de IBM supercomputer Deep Blue, een machtige rekenaar met 256 parallel geschakelde processoren. Daarna zal volgens IBM het rekenmonster worden ingezet bij wetenschappelijke vraagstukken.
Deze computer vormt een serieuze bedreiging voor de menselijke schaker. Vorig jaar versloeg de wereldkampioen het apparaat met vier tegen twee, maar in de eerste partij werd hij aan de kant gezet door het sluwe bakbeest. Voor iedereen, inclusief Kasparov, was dat een daverende verrassing. "Ik kon het me niet voorstellen. Maar zo’n speelsterkte had ik echt niet verwacht", verzuchtte hij enige dagen na de verliespartij.
Onder schaakcomputers is Deep Blue een vreemde eend in de bijt. De meeste computers gebruiken tegenwoordig selectieve zoekmethoden naar de beste zet. Het apparaat neemt dan alleen de zetten in beschouwing die hij op grond van een evaluatiefunctie het sterkst acht. Shannon noemt dit een type-B-aanpak. Deep Blue met zijn 256 parallelle processoren opereert onder een type-A-strategie, ook wel de ‘brute kracht’-methode genoemd. De computer gebruikt zijn brute rekenvermogen om de beste zet te vinden. Deep Blue kan wel vijfhonderd miljoen stellingen per seconde bekijken. Van schaken ‘begrijpt’ de computer minder dan een beginneling. IBM doet zelfs de boude bewering dat de computer helemaal geen gebruik maakt van kunstmatige intelligentie.
Geavanceerde zoektechnieken
Volgens Jaap van den Herik, hoogleraar informatica aan de Rijksuniversiteit Limburg, heeft de bewering dat Deep Blue geen kunstmatige intelligentie gebruikt, te maken met de verscheidenheid aan definities die de ronde doen. "Vroeger verstond men onder kunstmatige intelligentie dat de computer zo moest denken als de mens. Later is men daarvan afgestapt en vond men dat de resultaten hetzelfde moesten zijn. Ik behoor tot een groep wiens mening het midden houdt van tussen twee stellingen: kunstmatige intelligentie houdt zich bezig met programma’s die inzicht geven in het menselijk denken."
"Toch is Deep Blue niet alleen maar op Shannons type-A-strategieën gebaseerd, maar gebruikt hij heel geavanceerde zoektechnieken", vervolgt Van den Herik, expert op het gebied van kunstmatige intelligentie en computerschaak. Ook het gebruik van parallelle processoren brengt moeilijkheden met zich mee. Terwijl hij een boomdiagram tekent op een kladblaadje doceert Van den Herik: "Er is overhead nodig voor het zoeken, de communicatie tussen de processoren, de synchronisatie en complexity" – de algemene problemen die optreden bij het gebruik van parallelle processoren.
Juist voor onderzoek op dat laatste gebied heeft IBM het project binnengehaald. Het bedrijf hoopt met de schaakcomputer kennis te vergaren over hardware en software voor parallelle processoren. Dat is zeer waardevol bij de studie en simulatie van processen die tegelijkertijd plaatsvinden. Na deze match zal Deep Blue het schaakspel dan ook vaarwel moeten zeggen. Er wacht hem een nieuwe carrière. De computer moet zich gaan wijden aan de zuivere wetenschap: de moleculaire biologie.
Deep Thought
Deep Blue is niet van het begin af aan in handen van de IBM geweest. De computer heeft al een lange geschiedenis achter de rug. Hij is de opvolger van Deep Thought, een machine die deel uitmaakte van een promotieonderzoek aan de Carnegie-Mellon Universiteit aan het eind van de jaren tachtig. Deep Thought had in het begin slechts twee processoren en kon 750.000 schaakstellingen per seconde te bestuderen. De hardware werd al snel verbeterd, wat de computer in staat stelde twee miljoen stellingen per seconde te verwerken.
Vanaf dat moment boekte Deep Thought het ene succes na het andere. In 1988 deelde hij met de Engelse grootmeester Tony Miles de eerste plaats in het Open Amerikaanse kampioenschap. In 1989 werd hij wereldkampioen bij de computers en versloeg hij een Deense en een Amerikaanse grootmeester. Later dat jaar verloor hij echter met 2-0 van Kasparov, die ook toen al de wereldtitel bezat.
In datzelfde jaar vertrokken de twee belangrijkste ontwerpers van Deep Thought, Feng-Hsiung Hsu (voornamelijk ontwerper van de hardware) en Murray Campbell (die zich hoofdzakelijk bezighield met de software en in het begin de enige schaker was in het team) naar IBM. Big Blue nam het project over, maar herdoopte het om voor de hand liggende redenen om tot Deep Blue.
De twee oorspronkelijke ontwikkelaars kregen hulp van experts op het gebied van parallelle processoren. Verder werd de Amerikaanse schaakgrootmeester Joel Benjamin aan het team toegevoegd. Hij moest zich met het schaaktechnische deel bemoeien, en zijn voornaamste taak was het maken van het gigantische openingsboek voor de computer.
Hoe meer, hoe beter
Een machine ontwikkelen die duizend maal sneller is dan de oude Deep Thought was de doelstelling van het team. Dat is nodig, omdat Deep Blue een type-A-strategie gebruikt. Daarom moet hij een gigantische hoeveelheid posities berekenen om een schaakpartij op niveau te spelen. Het schaakspel kent namelijk tien tot de macht 120 mogelijke posities. Het is onmogelijk om ze allemaal te berekenen. Derhalve is het devies ‘hoe meer, hoe beter’.
In 1996 was de doelstelling al bijna bereikt: Deep Blue haalde toen tussen de vijftig- en honderd miljard posities per drie minuten, de gemiddelde bedenktijd per zet in een gewone schaakpartij. Toch is die snelheidswinst niet zaligmakend. Het systeem mag dan wel sterk zijn verbeterd, in schaaktermen valt het behoorlijk tegen. Deep Thought keek standaard vijf zetten vooruit, terwijl Deep Blue er 6,5 berekent. Als de computer de variant belangrijk vindt, rekent hij veel dieper. (Eén zet betekent bij schaakprogrammeurs een zet van wit en een zet van zwart samen; een zet van wit of zwart alleen geldt als een halve zet.)
Nu, een jaar later, is de computer verder verbeterd. Volgens de schaakgrootmeester in dienst van IBM, Benjamin, kan de computer nu met alle schaakstukken beter omgaan, maar weet niemand er het fijne van. In afwachting van de revanchematch wordt Deep Blue angstvallig verborgen gehouden in de heuvels van Yorktown Heights (New York), waar het T.J. Watson onderzoekscentrum van IBM zich bevindt.
Stijl aanpassen
Aan de vooravond van de match tussen Deep Blue en Kasparov was Den Haag het toneel van een groot computerschaaktoernooi. Vijftig schakers voerden een gevecht over zes ronden tegen vijftig computers. Dit evenement is dè jaarlijkse krachtmeting tussen mens en computer, en het vormt een graadmeter voor de vooruitgang van de schaakprogramma’s. Het toernooi is geopend met simultaanseances van Jan Timman en de Indiër Viswanathan Anand tegen zes computers.
Dat tweetal heeft nog maar weinig ervaring met schaakprogramma’s, wat een absoluut nadeel is. Terwijl hij zijn rondjes draait tussen de zes computers, beginnen Timmans ogen dan ook steeds triester te staan. Anand redt het wel, want hij is fit en in vorm, maar Timman delft het onderspit. Zijn nederlaag van twee tegen vier is niet iets om over naar huis te schrijven. Tegen menselijke tegenstanders van dezelfde speelsterkte had hij het beslist beter gedaan.
Grootmeester John van der Wiel laat zich niet meer afschrikken door een elektronische tegenstander. Hij geldt als expert in het bestrijden van computers en won al tweemaal in Den Haag. "De manier waarop je het succesvolst kunt opereren tegen een computer is niet met de normale manier van schaken. Het is beter als je een andere stijl gebruikt." Yasser Seirawan, die hem vorig jaar opvolgde als toernooiwinnaar, beaamt dat. "Ik heb zeer zeker mijn stijl aangepast en speel niet op mijn gewone manier. Het is belangrijk om je niet op het terrein te begeven waarop de computer uitblinkt."
Slecht in strategie
Van der Wiel vult zijn strijdplan op zijn eigen manier in. "Wat ik meestal doe, is van begin af aan streven naar een stelling waarin een computer slecht is", vertelt hij. "De computer is slecht in het opzetten van de partij, maar wordt vaak gered door het openingsboek." De meeste programma’s beschikken over een geweldige kennis van grootmeesterpartijen. Zolang er een stelling op het bord staat die eerder is gespeeld, kunnen ze uit oude bronnen citeren. "Als het je lukt om de computer al vroeg uit het openingsboek te lokken, dan is de slag al half gewonnen."
Seirawan heeft een iets andere benadering. "Ik probeer zo flexibel mogelijk te spelen en wil geforceerde posities vermijden. Bij scherpe tactische berekeningen overtreffen de computers zelfs de beste grootmeesters. Ik bedien me van een stijl waarmee ik alle opties open houdt en probeer een stelling te bereiken waarin er nauwelijks concrete plannen zijn."
De computer rekent goed en diep. Daardoor is hij vooral sterk in scherpe stellingen en slecht in de strategie. "In sommige posities speelt de computer als iemand met een elo van 3000, maar het niveau kan terugvallen tot 2200", verklaarde een opgeluchte Kasparov na zijn match tegen Deep Blue. (Elo is een waarde die de speelsterkte van een schaker aangeeft; Kasparov heeft 2795 – LR.)
Patroonherkenning
Schaakprogramma’s spelen op een andere manier dan de mens, omdat ze niet in staat zijn te ‘denken’ als de mens. Bij de menselijke schaker speelt de herkenning van patronen een hoofdrol. De beste computer is met moderne software echter nauwelijks in staat om het gezicht van een mens te herkennen. Met patronen in het schaakspel is het al weinig beter gesteld. De patroonherkenning vormt zo’n groot probleem dat de computer zelfs in de eenvoudigste gevallen faalt, laat staan dat hij kan wedijveren met de schaakgrootmeester. Posities waarvan de grootmeester in één blik de essentie doorgrondt, zijn voor het schaakprogramma nietszeggend.
Elke programmeur probeert op zijn eigen manier dit gebrek te compenseren. Gevolg is dat alle programma’s, net als schakers, een eigen stijl hebben. "Rebel speelt levendig en probeert de balans te houden. Het is het meest strategische programma van alle, omdat ik dat zo wil", vertelt Ed Schröder enthousiast over zijn geesteskind Rebel, dat Timman heeft verslagen in de simultaanwedstrijd.
"Je hebt de keuze tussen programma’s die zo snel mogelijk zoeken, en versies met veel schaakkennis", licht de andere Nederlandse topprogrammeur Frans Morsch toe. Hij is de ontwikkelaar van het Fritz 4 schaakprogramma, dat in 1995, vóór de toenmalige versie van Deep Blue, wereldkampioen werd bij de computers. Fritz 4 is niet een selectief programma als Rebel, maar gebruikt, net als Deep Blue, een Shannon type-A-strategie. In tegenstelling tot Deep Blue gebruikt Fritz 4 een belangrijke verfijning: het null move-algoritme.
‘Null move’
Met behulp van het null move-algoritme wordt de stelling bekeken alsof de tegenstander nog een keer aan zet is. Het programma rekent de stelling even snel door alsof hij geen zet hoeft te doen maar kan passen (wat in het schaakspel overigens niet geoorloofd is). Dat levert belangrijke informatie op voor het berekenen van de eigen zetten. Dit algoritme is een belangrijke vondst bij het programmeren van schaakcomputers. "De null move maakt type-A weer interessant", vertelt Morsch – zonder een spoortje van trots, terwijl hij zelf de pionier is van deze zoekmethode.
Dankzij soortgelijke technieken kon Fritz 4 in 1995 Deep Blue verslaan, terwijl die toen al miljoenen posities per seconde kon evalueren. Deep Blue maakte al vroeg in de partij een grote fout en werd als een kind van het bord gezet. Met de techniek die Deep Blue gebruikt, was er volgens Schröder maar één conclusie mogelijk over het falen van de supercomputer. "Het ging puur om een gebrek aan rekenkracht." Hij voegt daaraan toe dat commerciële programma’s met hun afwijkende zoektechnieken het binnen een minuut zagen.
Morsch gelooft niet dat zulk soort technieken enig belang hebben voor de wetenschap. "Computerschaak is vaak aangeduid als de fruitvlieg van de kunstmatige intelligentie, maar het levert niets op, geloof ik, behalve sterke schaakprogramma’s." (In de genetica deden wetenschappers aan het begin van deze eeuw kennis en ervaring op met fruitvliegjes – LR.) Schröder, vroeger een collega van Morsch bij een Duits bedrijf, is wat optimistischer. "Misschien is de technologie bruikbaar op gebieden waar het gaat om snelheid en zoeken in boomstructuren."
De perspectieven
Van den Herik onderstreept dat er wel toepassingsgebieden zijn. In zijn openingswoord voor het Aegon-toernooi van 1996 noemde hij een lange lijst voortbrengsels van het onderzoek naar computerschaak. Een kleine greep: zoektechnieken, kennisvoorstelling en -manipulatie, leerconcepten en technieken voor patroonherkenning. Ook heeft Van den Herik een leerstoel aan de Leidse rechtenfaculteit, naast zijn werk in Maastricht. Hij beschouwt computerschaak als "een inspirerende achtergrond voor rechtsprekende programma’s".
Net als over de toepassingsgebieden heerst er onenigheid over de perspectieven van computerschaak. Van den Herik verwacht dat al in 1998 de computers de vloer zullen aanvegen met de meesters en grootmeester in het jaarlijkse Haagse toernooi. Morsch antwoordt: "Dat is niet reëel. Ze zullen zeker niet meer dan 50 procent halen." Schröder is evenmin optimistisch. "Computers zullen in staat zijn het niveau te halen van een goede grootmeesters met een elo van 2600 tot 2650 en dan houdt het op. Een computer zal nooit een match winnen tegen Kasparov." Net als Kasparov onderscheidt hij twee speelsterktes van de computer: een tactische en een strategische. Schröder denkt dat de computer strategisch te zwak blijft om de top te bereiken.
In een enkele partij acht hij de computer niet geheel kansloos tegen de wereldkampioen: "Als Kasparov op positioneel terrein blijft, zal hij blijven winnen. De vraag is alleen of Kasparov zich daaraan kan houden. Hij wil de beste zet doen. Hij past zich niet aan zijn tegenstander aan en dan gaat hij voor de bijl." Hierbij kan Van der Wiel zich aansluiten. "In zijn algemeenheid is het wel waar dat Kasparov leunt op zijn enorme rekenvermogen. Hij speelt als een computer en daardoor is hij niet de meest gevaarlijke tegenstander voor een computer."
"Kasparov wint"
Toch is de algemene opinie dat Deep Blue een pak slaag zal krijgen. Zelfs rasoptimist Van den Herik verwacht een 3,5-2,5 overwinning voor Kasparov. "Maar het zou ook anders kunnen uitvallen", voegt hij toe. "Het verschil met een 3,5-2,5 nederlaag is niet zo groot. Het zou me wel verbazen als Kasparov met grote cijfers wint."
Yasser Seirawan, vorig jaar winnaar van het computerschaaktoernooi met een zes-nul score tegen de rekenaars, weegt zijn woorden zorgvuldig. "De ervaring die Kasparov heeft opgedaan in de vorige match is heel belangrijk. Daarnaast heeft Deep Blue problemen met de opening, dat is ook vorig jaar gebleken. Ik betwijfel of het lukt om hier iets aan te doen, want het is heel moeilijk om je op Kasparov voor te bereiden." Zijn oordeel is onverbiddelijk: "Kasparov gaat zijn score verbeteren, zelfs al is de snelheid van Deep Blue verdubbeld."
Al met al ziet het ernaar uit dat de kunstmatige intelligentie niet op korte termijn de zo lang verwachte doorbraak zal beleven. Als Kasparov begin mei stand heeft kunnen houden, moeten de programmeurs uit de jaren vijftig nog even geduld hebben.
Li Riemersma, freelance medewerker Computable
