Geschiedenis van schaakcomputers

Het eerste computer schaak programma werd in 1950 gemaakt door Alan Turing, een Britse pionier op het gebied van digitale computers. De computer was eenverschrikkelijke speller, maar het liet wel zien date en computer schaak kan spelen. In dat zelfde jaar maakte Claude Shannon een plan om computers daadwerkelijk goed schaak te laten spleen. Door de snelheid van de computers toen was het nog maar de vraag of computers ooit nog eens goed schaak zouden kunnen gaan spelen.
In 1958 won de eerste computer met schaak van een mens, namelijk de secretares van de programmeurs, die in een uurtje uitgelegd werd hoe schaken werkte. Dit lijkt misschien niets, maar toch was het voor die tijd een grote overwinning, er werd namelijk mee bewezen dat je kennis in een computer kunt stoppen, namelijk 1 uur kennis.
Een aantal mensen dachten toen dat er aan het einde van de jaren 60 een computer zal zijn die schaakkampioen zou zijn. Dit lukte niet, Spassky won, en computers waren nog maar ongeveer zo goed als een gemiddelde middelbare school speller. Dit moedigde bepaalde mensen weer aan om te denken dat computers nooit een intelligente taak zouden kunnen verichten.
Maar opnieuw werd er gezegd dat er binnen tien jaar een computer zal zijn die een "chess master" zal kunnen verslaan. In 1978 werd het beste schaak programma gekozen (CHESS 4.7) om tegen chess master D. Levy te spelen. Van de vijf potjes heeft Levy er drie gewonnen, een gelijk gespeeld, en een verloren. Niet gelukt dus maar toch heeft het programma D. Levy een keer verslagen.
In 1988 won de schaak computer Deep Thought (DT) makkelijk van D. Levy. Maar toen DT in 1989 tegen de wereldkampioen (Garry Kasparov) speelde, werd DT ingemaakt.
Pas in 1997 slaagde Deep Blue (opvolger van Deep Thought) erin om te winnen van Kasparov.


Hoe spelen computers schaak

Een computer kan al snel schaken, als hij maar weet welke zetten mogen, en welke niet. Dit is alleen niet zo goed schaken, zo'n computer kan in vijf zetten al verslagen worden. Een manier voor een computer om "goed" schaak te spleen is om elke mogelijke zet uit te denken, op elk van die zetten weer de mogelijke tegenzet te bedenken, en op al die zetten weer elk mogelijke eigen zet. Net zolang door totdat het einde van het spel bereikt is, en de computer hoeft alleen nog de zet uit te kiezen die er altijd voor zorgt dat hij wint, ongeacht wat de tegenzet van de tegenstander is. Zo'n computer speelt perfect schaak. Een probleem, het aantal mogelijk uitkomsten is ongeveer 10100, het aantal deeltjes in het universum word geschat op 1080. De zoektuimte moet dus beperkt worden.
Het idee was om de zetten die de computer vooruit bedacht te limiteren. Een computer zou dan bijvoorbeeld 6 zetten vooruit denken. Dit heet de minimax strategie, omdat de computer de zet kiest die ervoor zorgt dat hij er na die 6 zetten het beste voor staat, en zijn tegenstander het slechtst. Er zit helaas ook een nadeel in zo'n systeem. Stel dat de computer heeft berekend dat hij zijn koninging zal verliezen in bij zet 6, dan zal hij een zet doen om te voorkomen dat dit gebeurd. Grote kans dat de computer zijn koninging-verlies alleen maar uitsteld, alleen doordat de computer maar 6 zetten vooruit kan kijken, ziet hij dit niet, en denkt hij op dat moment veilig te zijn. Deze strategie heet de A-type strategie, en is door Shannon bedacht.
Shannon heeft ook nog een B-type strategie bedacht. Hierbij bedenkt de computer voor elke zet de 8 beste mogelijkheden. De computer heeft nu en stuk minder snelheid nodig om bijvoorbeeld 6 zetten vooruit te kunnen denken. Deze B-type strategie word vooral gebruikt door computers die op micro-proseccoren werken. Echt snelle computers gebruiken de A-type.
Een schaakcomputer heeft verschillende waardes opgekregen voor de verschillende schaakstukken. Meestal is een koningin 9, een loper 5, een paard 3 en een pion 1, de koning is meestal iets van 200 punten, zodat die niet zomaar opgegeven kan worden. Verder geeft het programma 0.1 punten aan elke mogelijk 'goede' zet. Op deze manier kan een computer uitrekenen welke set van zetten het beste voor hem is.


Hoe zijn schaakcomputers beter gworden

Schaakcomputer 'kijken' een aantal stappen vooruit, hoe meer stappen je vooruit kan kijken, in de diepte en in de breedte, hoe beter je kan bepalen welke stap je het beste kan uitvoeren. Die hoeveelheid hangt af van het geheugen en de snelheid van de computer en die werd in de loop van de tijd natuurlijk steeds beter waardoor schaakcomputers dus ook beter werden. De MANIAC begon met 11.000 instructies per seconden en Deep Thought kon er al 2.000.000 per seconden.
Daarnaast zijn er ook verbeteringen in de software aangebracht waardoor schaakcoputers beter zijn geworden. Zo werd er niet meer, zoals met de eerste schaakcomputers, van elke mogelijke zet doorgerekend wat er daarna mogelijk is, maar alleen van de zetten waarvan al duidelijk is dat ze niet niks opleveren. De schaakcomputers maakten eerst gebruik van schaak concepten en niet van algoritmes om postities te bepalen. Naarmate de computers sneller werden werd het wel mogelijk om gebruik te gaan maken van algoritmes waardoor de shcaakcomputers ook weer beter werden.
Door de schaakcomputers te laten spelen tegen mensen werd duidelijk waar de zwakke punten lagen en konden deze weer verbeterd worden. Ik zal wat voorbeelden geven van problemen die eerdere schaakcomputers hadden. Ten eerste probeerden ze het verliezen van stukken zo lang mogelijk uit te stellen. Wanneer er geen belangrijke zet gedaan kon worden waaren de schaakcomputers vrij voorspelbaar. Het was ook zo dat ze nooit echt met een combinatie van zetten naar een bapaald doel toe probeerden te werken. En ze herberekende een zet als ze in een bijna identieke situatie zaten. David Lavy had ook bepaalde tactieken om van een schaakcomputer te winnen. Dit waren ver vooruit denken, stukken opofferen om op bepaalde posities te komen, een ongebruikelijke zet doen zodat de schaakcomputer het niet helemaal meer 'begrijpt'.
Andere dingen die de schaakcomputers beter maakten waren toevoegingen van de volgende dingen. De schaakcomputer Belle die in 1980 werd hergebouwd maakte gebruik van Encyclopedia of Chess Openings zodat hij een heleboel openings situaties wist. Er bestond ook zoiets maar dan voor eindsituaties. Er werd ook gebruik gemaakt van alpha-beta cuts. Dit zorgt ervoor dat al de tegenstander een goeie tegenzet doet dat de computer dan stopt met te porberen deze situatie nog te verbeter en gaat kijken naar andere dingen die hij zou kunnen doen. Om de computer nog sneller te maken werd er speciale hardware gemaakt voor bepaalde berekeningen voor het spel, de zogenaamde special purpose hardware. Transposition tables worden gebruikt om mogelijke zetten tot een bepaald punt in te zetten. Als de computer dan een bepaalde route vind naar een punt en dat punt staat al in die tabel dan heeft hij dus al een route naar dat punt en hoeft hij de zojuist bedachte route niet op te slaan. Er wordt ook een techniek gebruikt om op verschillende dieptes te zoeken. Dan zoekt hij op betere resultaten dieper dan op resultaten die minder goed lijken te zijn.


Meningen

Alex:	Het komt er dus allemaal nogal op neer dat hoe beter en sneller je computer is, hoe beter deze kan schaken. Natuurlijk is er veel research gedaan en hebben de mensen die de schaakcomputers ontwikkelden door hun steeds toenemende kennis over hoe en computer het beste kan schaken er ook toe geleid dat de schaakcomputers beter werden. Maar als je bedenkt wat voor supercomputer Deep Blue wel niet is (de schaakcomputer die wereldkampioen Kasparov versloeg), dan is het eigenlijk niet meer dan logisch dat deze zo goed is. Ik vind dat je deze computer niet echt intelligent kunt noemen. Je kan wel de makers ervan intelligent noemen, want zij hebben steeds gekeken hoe ze de computer zo konden maken dat hij weer beter kon schaken. Ik denk dat je wel kan zeggen dat een computer 'denkt', omdat de computer met al zijn formules mogelijkheden uitschakeld, en zo tot een beslissing komt. Dit doen mensen in principe ook. Volgens mij kan je beter een computer maken die in eerste instantie niet kan schaken, maar het wel kan leren. Dus door trial & error en onthouden beter worden. Zo'n computer kan je dan ook vrij 'makkelijk' ombouwen zodat hij kan leren dammen. Dan heb je pas echt een intelligente computer!

Boris:	De techniek is erg snel erg veel vooruitgegaan en daarom hebben we nu hele goede computers. De techniek achter de schaakcomputers is mede daardoor ook steeds beter geworden en daarom hebben we nu erg goede schaakcomputers. Ik vind het erg knap hoe die techniek van zo'n schaakcomputer is bedacht en uitgewerkt, het zit erg ingewikkeld in elkaar en weet een menselijke tegenstander te verslaan. Maar odanks dat vind ik het toch ook weer niet een ontzettend slim apparaat. Het is een kwestie van vooruitkijken en hoemeer je vooruit kan kijken hoe beter je kan bepalen wat de beste zet is. Dus met de komst van steeds betere en snellere computers kunnen de schaakcomputers steeds meer stappen vooruit kijken en worden daardoor dus steeds beter. En dus is het vrij logisch dat ze dan op een gegeven moment de mens verslaan, want de mens kan niet zo ver vooruit denken als de computer.


Andreas:	blabla


Bronnen

1.	http://db.uwaterloo.ca/~alopez-o/divulge/chimp.html
2.	http://www.gamedev.net/reference/programming/features/chess1
3.	http://www.computermuseum.li/Testpage/01HISTORYCD-Glossary.htm
4.	http://www.cs.ucf.edu/~dmarino/CompChess.ppt