shashki35 Vologda ru

Het toernooi was perfect georganiseerd door Krzysztof Grzelak, met live weergave van alle partijen. Voor de partijen werden twee identieke computers ingezet met een AMD Ryzen Threadripper 1950X (16 cores), een clock frequentie van 3.4GHz en 128 GByte geheugen. Vrijwel alle bekende programma’s waren present, zie onderstaand overzicht.

Naast het bedanken van Krzysztof voor het organiseren van het toernooi, alle programmeurs voor het ontwikkelen en ter beschikking stellen van de programma’s, gaat een speciaal dankwoord uit naar Eric van Dusseldorp voor de partijanalyses in dit artikel, en Joost Buijs voor de technische details ten aanzien van Ares.

De (hoofdrol)spelers

Op grond van de resultaten bij voorgaande toernooien was het de logische verwachting dat Dragon, Kingsrow (1e WK 2020), Maximus, Scan (1e WK 2018) en Sjende Blyn (1e WK 2019) de grote kanshebbers zouden zijn. Weliswaar spreken programma’s als Truus en Flits waarschijnlijk nog steeds tot de verbeelding, maar omdat zowel Stef Keetman (Truus) als Adri Vermeulen (Flits) al enige tijd niet meer actief zijn op dit gebied, is de kloof met de koplopers (te) groot geworden. De enige twee “dark horses” in dit veld waren Ares NNUE en Damage NNUE. Omdat NNUE een vrij onbekende techniek is voor velen, behandel ik deze separaat.

NNUE onder het vergrootglas

In dit artikel ga ik ervan uit dat de anatomie van een computerdamprogramma (min of meer) bekend is, en dat woorden als zetten-generator, searchfunctie en evaluatiefunctie bekend zijn. Van al deze componenten is de evaluatiefunctie de grootste uitdaging en het meest complex. De evaluatie bepaalt voor een groot gedeelte de sterkte en identiteit van het programma en vereist kennis van het specifieke domein. Het is dan ook geen toeval dat in het verleden de sterkste programma’s geschreven zijn door mensen met een programmeerachtergrond die ook nog eens het damspel vrij goed beheersten. Het beste voorbeeld is waarschijnlijk Stef Keetman met Truus.

Tegenwoordig zien we dat neurale netwerken in vele complexe gebieden tot zeer goede resultaten komen en in staat zijn om de tot dan toe gangbare methoden die veel specifieke domain kennis verlangen, te vervangen. De betekenis van NNUE is “Efficiently Updatable Neural Network” (een acroniem, maar dan achterstevoren gespeld). Kortom, een neuraal netwerk met een efficiënte manier om de inputlaag te berekenen. Door de specifieke architectuur is het mogelijk om dit netwerk te berekenen met een CPUkaart, terwijl andere netwerkvarianten een up-to-date grafische kaart met een geavanceerde GPU nodig hebben (voorbeeld Leela Chess Zero).

NNUE is als eerste toegepast in Shogi (een Japans strategisch bordspel, verwant met schaken) en in de zomer van 2020 in Sockfish (het sterkste open source schaakprogramma) geïmplementeerd. Dit leverde al snel een enorme ELO-winst op. Toen NNUE ook bruikbaar bleek te zijn binnen Checkers (GuiNN Checkers, Jonathan Kreuzer) was dit het startsein om een en ander ook toe te passen bij 10x10 dammen.

Trainen van het AresNNUE netwerk

Voor het trainen van het door Ares gebruikte neurale netwerk (NN) is in eerste instantie begonnen met het tegen zichzelf te laten spelen van 8 miljoen (random) partijen met alleen materiaalevaluatie. Het genereren van deze partijen (bedenktijd 33 milliseconden per zet) duurde op een 32 core AMD computer ruim 2 weken.

Tijdens het spelen van bovengenoemde partijen werden in real time posities uit het zoekproces bewaard, en na afloop van een partij gelabeld met de uitkomst van de partij en opgeslagen op disk. Uiteindelijk resulteerde dit in 1,7 miljard gelabelde posities. Het aantal posities werd met name zo groot doordat de partijen zonder gebruik te maken van een eindspeldatabase tot het eind zijn doorgespeeld.

De eerste versie van het NN is getraind met behulp van de met uitslagen gelabelde posities. Hierna zijn de posities opnieuw gelabeld met de uitkomst van een 4 zetten diep zoekproces dat de eerste versie van het NN als evaluator gebruikt. De uiteindelijke versie van het NN is getraind door de met evaluatiewaarden gelabelde posities als voorbeeld voor het leerproces te gebruiken.

Het programma waarmee het NN getraind is, is geschreven in C++ en maakt gebruik van de door Facebook ontwikkelde ‘libTorch’ bibliotheek. Het trainen van het uiteindelijke NN op een Nvidia RTX-3090 GPU nam ongeveer 24 uur in beslag (211 iteraties van ieder 6,8 minuten).

Het toernooi

Al in ronde 1 zette Ares de damwereld op haar kop door het traditionele ‘Truus’ van Stef Keetman te verslaan. ‘Truus’ was zo’n dertig jaar geleden nog ‘s werelds sterkste damprogramma. Na de openingszet van Ares 1. 34-29,… kwam Truus met het veel gespeelde 1…, 17-21; waarna het door AI aangestuurde Ares reageerde met 2. 29- 24(!),… Huh? Dat speelt geen mens. De exacte zettenreeks na anderhalve zet is nog maar één keer in een half miljoen partijen voorgekomen. Maar de kern is dat Ares zich niet door mensen laat beïnvloeden, maar alleen door zichzelf. En 2. 29-24,… is allerminst zwak. De voorpost is onaantastbaar dus zwart moet zich in bochten wringen om deze te elimineren – en dan helpt het al gespeelde (17-21) allerminst - of kiezen voor een constructieve omsingeling. Truus koos voor het laatste en verloor na een perfect gespeelde witte aanval!

Flitsend combinatiespel is in partijen tussen damprogramma’s zelden te bewonderen. Zelfs vrij diepe slagzetten worden door beide partijen in de regel snel onderkend. Maar er zijn uitzonderingen, zoals een geweldige forcing die werd uitgevoerd in de 15e ronde van het WK

Eindstand WK Computerdammen 2021

Diagram 1

Moby Dam - Damage

Na 21. 49-43?,… volgde er iets geweldigs: een offer gevolgd door een ‘onmogelijke’ zet: 21…, 25-30!; 22. 34x25, 12-18; Wit heeft niets anders dan de aangeboden dam te accepteren. 23. 43-38, 18x27; 24. 32x3 (nog de beste), 23x34; 25. 40x29, 2-8! 26. 3x1, 13-18; 27. 1x23, 19x50; met winst. In de diagramstand is 48-43 een redding. Er kan dan volgen (25-30) 34x25 (12-18) 26-21! en omdat op (16x29) 47-41 volgt met na (18x27) 39-33 (23x32)

37x28 (29x38) 43x3 winst voor wit, moet wel (18x29) 21x1 (23x41) 1x34 met gelijk spel.

De overwinning in ronde 26 van Damage op het als (gedeeld) tweede geëindigde Dragon was weliswaar niet beslissend voor de wereldtitel, maar feitelijk de enige niet-remise tussen de topprogramma’s.

Diagram 2

Damage - Dragon

Zwart dreigt (17-21), maar Damage had het allang zien aankomen. Er volgde een prachtig gambiet. 29. 26-21!!, 17x26; 30. 40-34, ...Wat nu? Op (11-17) volgt 37-31 (28x37, anders slaat wit naar achteren) 38-32 (37x28) 34-30! (26x37) 30x10 (22x31) 33x2. Op (13-19) wint 37-32 (28x37) 38-32 (37x28) 34-29! etc. Op (14-19) volgt 34-29 en de zwarte stand lijkt amper te verdedigen. Er volgde 30…, 12-17; 31. 37-32, 28x37; 32. 38-32, 37x28; 33. 42-38, 26x37; 34. 38-32, 22x31; 35. 32x1, met een volgens de computer gewonnen stand, bijvoorbeeld (17-21) 36x27 (21x32) 35- 30 (24x35) 25-20 (14x25) 34-30 (25x34) 39x30 (35x24) 33-28 (32x23) 1x42.

Partijverloop: 35. ...24-29; 36. 33x24, 14-19; 37. 36x27, 19x30; 38. 35x24, 37-41; 39. 39-33, 41-47; 40. 33-29, 17-21; 41. 1-23, 21x32; 42. 23x37, 47-36; 43. 37-26, 9-14; 44. 26x20, 36-27; 45. 20-15, 27x49; 46. 29-23, 13-18;

47. 23x12, 49-21; 48. 24-20 21x8; 49. 20-14, 16-21; 50. 14-10, 21-26; 51. 10-5, 11- 17; 52. 25-20, 8-12; 53. 34-30, 12-18; 54. 20-14, 18-13; 55. 14-10, 13x35; 56. 10-4 met winst door overmacht.

Uiteindelijk wist Damage het toernooi te winnen met een groep van vijf (!) achtervolgers die alle 50 punten behaalden op een gedeelde 2e plaats.

Na het toernooi was er nog een levendige discussie op het internet over de vraag of het aantal winstpartijen of S.B. bepalend was bij een gelijk aantal punten. Bij toepassing van S.B. zou Sjende Blyn 2e geworden zijn met Kingsrow op een 3e plaats.

Nawoord

Tot slot nog een aantal opmerkingen, bespiegelingen en gedachten.

• De relatief grote voorsprong van Damage (4 punten) is zeker geflatteerd. Het is niet onwaarschijnlijk dat als het toernooi opnieuw gespeeld zou worden er een andere winnaar uit de bus zou komen (weliswaar uit de groep “The Magnificant Seven”: Damage, Dragon, Sjende Blyn, Kingsrow, Scan, Ares en Maximus).

• Hoewel de sterkste programma’s meestal remise spelen tegen elkaar, is het juist de middenmoot (zoals Truus, Edeon, Moby Dam) die bepaalt wie kampioen wordt. En dan moet je ook soms geluk hebben dat het minder sterke programma een (beslissende) fout maakt.

• Een optimaal programma voor een toernooi is mogelijkerwijs niet hetzelfde als een optimaal programma voor een 1-op-1 match. Bij een toernooi is het belangrijk om te winnen van de mindere programma’s, terwijl je bij een match niet moet verliezen. Waarschijnlijk (op grond van verschillende testen) is en blijft Kingsrow het sterkste matchprogramma.

• De topprogramma’s spelen niet perfect, maar vanwege de sterke remise black-hole (ofwel de grote remisemarge) zijn onderlinge winst/verliespartijen schaars. Volgens Ed Gilbert (Kingsrow) is deze waarschijnlijkheid met 16 cores en 15 minuten bedenktijd rond de 1 winst/verliespartij in 300/400 partijen.

• Het is niet onwaarschijnlijk dat programma’s met een op NN gebaseerde evaluatiefunctie dominant zullen worden in de toekomst. De drie belangrijkste redenen hiervoor zijn:

1) Enorm veel research en nieuwe concepten die worden ontwikkeld.

2)Toekomstige processoren hebben steeds meer ingebouwde hardware neuraal netwerkversnellers.

3)Enorm ecosysteem met open source software tools, ondersteunende documenten, cursussen op YouTube.

• Een volgende uitdagende stap voor de computerdamprogramma’s is reinforcement learning. Hierbij leert het programma constant bij door tegen zichzelf (of andere programma’s) te spelen, waarbij geen coach of supervisor nodig is, en waarbij ook geen enkele verdere startkennis van het damspel nodig is, met uitzondering van de spelregels.

Tekst: Bert Tuyt