dinsdag 15 januari 2013

Voortgang van schaakprogramma’s

Onlangs zag ik op Talkchess een kop "Houdini 3 - Shredder 7.04: 99,5-0,5". Dit was een match tussen de actuele nummer 1 en de nummer 1 van tien jaar terug, op dezelfde hardware. Doel van de match was om eens te kijken hoe groot de vooruitgang was in tien jaar tijd. De Merckx van de schaakprogramma’s steekt duidelijk met kop en schouders boven de concurrentie. Daar waar vroeger de versnelling in hardware bijna even belangrijk was als het beter programmeren, is sinds de intrede van Fruit, de focus terug verlegd naar het optimaliseren van het programma zelf. In latere testmatchen kon Shredder nog wat hele en halve puntjes meer pakken, maar veel betekende het niet.
Hiermee werd tevens de oude strijd beslecht tussen programma’s gebaseerd op “kennis” en deze op “snelheid”. Aangezien het belangrijk is om binnen een bepaalde tijd met een goede oplossing voor de schaakstelling te komen, is “positionele kennis” van het programma A minder relevant, als programma B, door een sneller zoekproces ziet dat een paar zetten verder in de voortzetting van A diens positionele zet weerlegd wordt. Een match met gelijke zoekdiepte werd door Shredder wel met 12,5-7,5 gewonnen, wat zou kunnen aantonen dat Shredder misschien wel het betere en positioneler uitgebalanceerder programma is, maar dat helpt weinig op praktisch vlak.
Die vooruitgang in het verfijnen van programma's was jarenlang met beperkte stapjes gegaan, eigenlijk vaak wat gerommel in de marge. Toch werd quasi elk jaar een nieuwe versie van Fritz, Shredder en co uitgebracht. Wie er nu de ratinglijsten op nakijkt, ziet dat er tussen bepaalde versies nauwelijks verbeteringen waren. De marketingmachine haalde dan maar andere argumenten boven: een “betere” GUI, meer opties om te analyseren, multimedia enzovoort.
Maar met Fruit (vanuit het niets tweede op het WK in 2005 na ééndagsvlieg Zappa), werd alles anders. Fabien Letouzey gaf wat later zijn broncode openbaar en van toen af werd er duchtig aan “open programmeren” gedaan. Rybka kon als eerste programma de verbeteringen van Fruit incorporeren en verder optimaliseren. Het lichtend pad werd al snel gevolgd door enkele “piraatklonen”, die via reverse engineering (met disassembers) de code konden achterhalen en door programmeurs, die openlijk steunden op public source, zoals onze eigen Robert Houdart met Houdini. The war of the clones lijkt voorlopig voorbij – voorlopig kan zelfs nog geen enkel ander programma tippen aan freeware Houdini 1.5 (zie de CCRL40-lijst). Andere open source programma’s zijn best interessant (Critter, Stockfish), maar zijn waarschijnlijk nog niet zo tot in de perfectie getuned als Houdini of Rybka.
De andere kant van de medaille (het delen van kennis) is gekend – zonder correcte bronvermelding reageert de ICGA onverbiddelijk (het vroeger al dubieuze programma Loop, maar ook Thinker worden geschorst) – de ICGA die trouwens in 2012 door al die commotie geen WK kan organiseren. Men geeft als reden de economische crisis, maar de anti-reclame rond de illegale klonen en de vrees/onzekerheid bij de programmeurs zat er vermoedelijk ook voor iets tussen.

Het is duidelijk dat een wereldwijd delen van kennis de vooruitgang het meest bevordert (een onderzoek naar het effect van patenten leverde ooit op dat een maatschappij waarin minder nieuwe kennis werd vastgelegd in patenten, sneller vooruit ging dan één waarin streng werd toegezien op de toepassing ervan – slechts twee voorbeelden van deze interessante discussie vind je hier en hier.

Voor het microscopische kennisgebied (in het licht van alle menselijke kennis) van het schaakprogrammeren, heeft kennisdeling duidelijk een significante stijging in speelsterkte betekend. Robert Houdart geeft als één van de eerste topprogrammeurs toe dat hij kon starten met een goede basis en zich “enkel” hoefde toe te leggen op het implementeren van de nodige algoritmes om tot een topprogramma te komen. Dat een beetje programmeur zo met een basis van 80 à 90% “kant en klaar” programma kan vertrekken, wordt geïllustreerd door weer een nieuwkomer aan het firmament: Bouquet (versienummer amper 1.5) staat nu op een top-vijf plaats (met 3145, amper 100 punten achter Houdini) in de toonaangevende CCRL-40 lijst. Van de oorspronkelijke Chessbase-stal staat enkel nog Hiarcs 14 in de top tien (toestand januari 2013).

Maar dit artikel gaat over de (vaak diep geanalyseerde) vondsten die programma’s soms maken in stellingen. Ik laat mijn PC wel eens automatisch analyseren op de Let's Check server van Chessbase, maar ik kruip ook graag nog eens zelf achter het stuur en speel dan wel eens partijen van clubspelers tot grootmeesters na, waarbij de engine (Rybka4, Fritz11, Houdini2, Stockfish2.3 of Critter1.6) mag meekijken. De lijntjes die dan soms in het analysevenster verschijnen zijn vaak enorm diep (ik heb er al een gehad van 80 (!) halve zetten) en bieden zo een unieke kijk op sommige openingen, middenspelen of eindspelen. Ik geef uit elke fase een indicatief voorbeeld. Dat computers zo goed als alle "geniale" grootmeesterzetten vinden uit hedendaagse en historische partijen, hoef ik niet te illustreren. Maar een paar bijzondere prestaties mogen wel eens uitgelicht worden.

De opening
Dit is er eentje uit mijn keuken. Zo'n 20 jaar geleden analyseerde ik de "weerlegging" van 9.h3 in de Blackburne-variant van het Pruissisch - het heeft me één keer een zeer vlotte winst opgeleverd. De actuele analyse - zovele jaren later - ontnuchterde me wel enigszins: te pas en te onpas werden gaten in mijn hoofdlijn gevonden. Maar de weerlegging zelf (9...cxb5) houdt stand: 9.h3 is gewoon fout. Houdini geeft vanuit deze stelling wel een lijntje tot op zet 36. Ik weet wel dat zo'n lange lijn niet steeds een opeenvolging is van de beste zetten, maar het blijft indrukwekkend om zoiets door te spelen: van opening tot in het eindspel! In elk geval - het is en blijft een interessante stelling om te analyseren: houdt wit gelijk spel of niet?

Het middenspel
Dit (Short-Timman) is een bekende stelling bij computertesters en komt ook nog vaak voor in schaakrubrieken wanneer het gaat om "out of the box" te denken of in thematische artikelen, om de kracht van de koning weer te geven. Ook hier biedt Let's Check een mat: Houdini 3x64 kondigt mat in 15 aan na 1.Kg3 - op mijn hardware wordt 1.Kg3 binnen de minuut gevonden. Op het einde van de analyselijn heeft wit het hele bord in handen en dreigt om nog een paar dames extra te maken.

Het eindspel
Volgende stelling (van Herbstmann) is een touchstone van computerschaak (zie ook deze pionierssite). Wie een beetje kijkt, ziet dat wit na 1.Kxa2 in een vierkant gevangen zit en zwart altijd schaak kan geven met zijn toren. De juiste oplossing is 1.Kb2! Lange tijd konden programma's niet diep genoeg gaan, maar met wat tijd en nog meer RAM (voor hashtabellen), lukt het de programma's van vandaag binnen twee minuten om de juiste zet te vinden. Op de Let's Check server zie ik trouwens dat de Rybka Cluster 140 dit beoordeelt als... mat in 22 (na 1.Kb2 a1D 2.Kxa1).
Ik kan nog andere voorbeelden geven (zo is Shirovs Lh3 (tegen Topalov) ook al gevonden), maar ik hou het hierbij. Bedoeling was gewoon om een korte blik te werpen op wat programma's nu al kunnen. Een volgende keer zal ik het hebben over wat programma’s nog niet kunnen - en dat is nog verrassend veel...

HK5000

7 opmerkingen:

  1. Ik heb vastgesteld dat ik alle analyses ouder dan 2007 sowieso moet opnieuw doen. Een titanenwerk als je weet hoeveel analyses ik gemaakt heb dus iets van lange adem. Trouwens zelfs in recentere analyses zitten weer al heel wat onnauwkeurigheden. In mijn vorig blogartikeltje kan je al lezen dat ik in 2010, de analyses verbeter op mijn partij tegen Jan Rooze, gemaakt in 2009. In de commentaren onderaan hetzelfde artikeltje kan je zien dat we met Houdini vandaag alweer een variant kunnen optimaliseren met Db7 i.p.v. De6.

    De vooruitgang was de laatste jaren (sinds 2005) zo snel dat ik als amateur onmogelijk ervoor kon zorgen dat mijn analyses die evolutie konden volgen. Meer dan wat rommelen in de marge met het bekijken van nichevarianten kan je mijn analyses dus niet noemen.

    BeantwoordenVerwijderen
  2. Tof artikel! Toch voor iemand die niets van computerschaak kent.

    Als ik het statement over schredder en Houdini goed begrijp is vooral de snelheid/algoritmes waarmee Houdini varianten elimineerd tov Schredder de reden dat Houdini beter is?

    Iets dat ik me al een tijdje afvraag, hoe sterk zou een schaakcomputer zijn op de huidige hardware indien die enkel de spelregels (natuurlijk) en de waarde van de stukken kent (D9/T5/PL3/Pi1)? Geen openingskennis, geen positiespel, activiteit, ontwikkeling, niets.....

    Haalt hij 1500 elo? De brute force op huidige hardware moet toch al tot 10 halve zetten geraken of vergis ik mij en is de boom te breed zonder eliminatie van varianten?

    BeantwoordenVerwijderen
  3. Ik ben zeker geen specialist in het programmeren van spelletjes maar ik weet wel dat er zelfs op gebied van brute force heel wat variatie bestaat dus zonder dat er openingskennis, positiespel, activiteit, ontwikkeling in zit.
    1 voorbeeldje:
    Variant 1 ontstaat na de zetten A,B,C
    Variant 2 ontstaat na de zetten C,B,A
    De slotpositie is in beide varianten hetzelfde dus als je verstandig programmeert dan geef je variant 2 hetzelfde resultaat als variant 1 zonder processingtijd te verbruiken om opnieuw de evaluatie te achterhalen.
    Met het optimaliseren van het algoritme, kan je al snel het programma vele keren sneller/ dieper laten rekenen.

    Een modern algoritme zonder openingskennis, positiespel, activiteit, ontwikkeling,... zal een fantastische verdediger zijn (ver boven 1500 elo) maar ik vraag mij af of zulk programma uberhaupt kan aanvallen als het zelfs niet weet dat de stukken moeten samenwerken en voorwaarts moeten gaan om de partij te winnen. Misschien zal zulk programma gewoon Pf3-Pg1-Pf3-Pg1-Pf3 spelen en zich beperken met verdedigen. Het lijkt mij in elk geval zinloos om zulk programma te testen.

    BeantwoordenVerwijderen
  4. Het statement dat Houdini het haalt door in te zetten op snelheid en efficiëntie (tegenover de "kennis" van Shredder) lijkt me correct.
    Zoals Helmut aangeeft zal een puur brute force programma redelijk doelloos spelen - een minimum aan kennis (zoals centrumbeheersing of koningsveiligheid) zal nodig zijn, om het op iets te laten lijken.
    Maar zelfs een naakt brute force programma zoals je suggereert, lijkt me toch in staat om eerder 2000 elo te halen (als ik naar mijn eigen partijen kijk, zit daar vaak wel ergens een misstap (of twee, drie...) in).

    BeantwoordenVerwijderen
  5. Ik betwijfel sterk dat een brute force programme 2000 kan halen. Ook wel akkoord met Brabo dat het niet zo duidelijk is wat de definitie van brute force is maar ik denk toch dat de boom snel heel breed zal worden als je niet kan snijden.

    Akkoord, je maakt in elk partij als gewone sterveling enkele blunders die de brute force computer kan doorrekenen en dus zal afstraffen, alleen moet hij in zo een stelling geraken. Als Brabo gelijk heeft en de computer enkel Pf3 - Pg1 blijft spelen dan denk ik toch wel dat ik kan winnen door zoveel druk op te bouwen in een aanval die voorbij de horizon van zijn rekenkracht gaat, zelf op de huidige hardware en een blunder links of rechts doet er dan niet meer toe.

    Maar akkoord, een redelijk zinloze discussie maar toch vraag ik het me af :)

    BeantwoordenVerwijderen
  6. Ik ben redelijk zeker dat een brute force programma zeker 2000 elo haalt. Ik heb hier het boekje "How to Use computers to Improve Your Chess, Christian Kongsted" naast me liggen. Het is 10 jaar oud en het beschrijft hoe computerprogramma's werkten. De huidige programma's kunnen nog veel meer dan de technieken die daarin beschreven worden.
    Vergeet niet, wanneer een programma geen ingewikkelde evaluatiefunctie heeft, dan heeft het nog meer tijd om dieper te rekenen.
    Daarnaast, hoeveel keer heb ik al niet gehoord van een computeranalyse dat het 'dom' was, want gebaseerd op voorgeprogrammeerde regeltjes (nl de evaluatiefunctie).
    Een deftig geprogrammeerde brute force engine kan zeker 20 ply diep rekenen, zelfs in blitztimings.
    Probeer maar eens een drukpartij te spelen zonder gelijk welke tactische blunder met een horizon van 20 ply. Op intuitie spelen lukt echt niet tegen een computer. Anticomputerschaak bestaat (daarover gaat precies het boek net naast me), maar dan mag je echt nooit een pion of meer blunderen.
    Nu, anyway, als de discussie zou verdergezet worden, wil ik gerust nog eens het boekje herlezen, of uitlenen, of zelfs nog beter, de vraag stellen aan Robert Hyatt.

    BeantwoordenVerwijderen
  7. Wel, je kan alles toch redelijk inschatten? Bvb, stel dat een simpel bruteforce programma met een simpele evaluatiefunctie (bvb enkel materiaal tellen) 100 seconden tijd krijgt. Met de natte vinger beweer ik dat hij 10^10 stellingen per 100 seconden kan bekijken (30 berekeningen voor de evaluatie en boekhouding per stelling met een 3GHz processor). Als we 32 mogelijke zetten (en dus ook resulterende stellingen nemen), dan raakt zo'n programma 6 ply diep (10^10 ~= 32^6). Dat is 3 zetten...

    Ergo, zelfs met de huidige rekenkracht is een brute force programma redelijk sucky :D Zelfs al zit ik er een factor 1000 naast, dat scheelt maar 2 ply aka 1 zet. Je zal toch ergens moeten je boom moeten snoeien...

    BeantwoordenVerwijderen