Jump to content
Matt & Patts Sjakksnakk
Sign in to follow this  
Inge «Insan» Harkestad

Kunstig intelligens og sjakk

Recommended Posts

DeepMind’s AlphaZero crushes chess (Chess24)

Programmet AlphaZero, som bruker maskinlæring / kunstig intelligens, startet helt på null. Det eneste den fikk vite var sjakkreglene. Den fikk ingen åpningsbok og ingen sluttspillbase. Den spilte rett og slett mot seg selv i skarve fire timer. Deretter ble den satt opp mot Stockfish i en 100 partiers match. 72 partier endte remis, mens AlphaZero vant resten - altså 28 partier, uten å tape ett eneste! Altså etter kun å ha spilt fire timer mot seg selv!

Etter å ha brukt sjakkprogrammer i mange år og observert den sakte, gradvise forbedringen programmererne har oppnådd gjennom nitid algoritmeforbedring, er jeg egentlig i lett sjokk her. Ja, jeg kjenner relativt godt til maskinlæring og kunstig intelligens, ja, jeg kjenner til AlphaGo, og ja, jeg har ventet på at kunstig intelligens skulle gjøre et gjennombrudd i sjakk. Men at gjennombruddet skulle bli så kraftig ... At det skulle være mulig å slå Stockfish med 4 timer selvlæring fra en tilstand av "tabula rasa" (uten annen kunnskap enn sjakkreglene) ... Den så jeg ikke komme.

  • Like 1

Share this post


Link to post
Share on other sites

Jeg er for øvrig enig med forfatteren av Chess24-artikkelen i at dette er litt betryggende:

AlphaZero, som startet uten noen som helst kjennskap til hvilke åpninger som er vanlige (altså uten åpningsbok), er "enig" med hundrevis av år med sjakkutvikling. Etter at den hadde testet ut ulike kombinasjoner av åpningstrekk, ser det ut som om den foretrakk kjente åpninger som engelsk og dronning-gambit.

  • Like 1

Share this post


Link to post
Share on other sites
JEB    486

Utrolig spennende, men også litt skremmende.

Det blir sagt at AlphaZero startet på null og bare fikk vite reglene. Betyr det også at den ikke fikk noen form for evaluering av brikkenes verdi? Du skal spille rimelig mange partier bare for å få et godt estimat for det! I sjakkprogram som Stockfish/Rybka o.l. blir det lagt inn en masse regler for brikkenes relative verdi, verdi av løperparet, bondestruktur, etc. Hvor godt programmet blir avhenger av hvor godt disse verdiene er estimert, relativ betydning etc. Men starte fra scratch, og bare spille mot seg selv i fire timer, for så knuse Stockfish - det er overveldende!

Det er selvsagt interessant i forhold til sjakk, Go o.l., men jeg er utrolig spent på betydningen av slike algoritmer i andre sammenhenger - i mitt tilfelle mest innenfor prosessoptimalisering, utvikling av medisin og diagnose. Vi har jo allerede sett noe av hva IBMs Watson kan, og ikke kan, i forhold til vurdering av "big data". Vi er åpenbart bare helt i starten av denne utviklingen - Alpha Zero kom som et sjokk (her snakker vi definitivt ikke bare om "brute force").

Ah, skulle mer enn gjerne satt sammen et tverrfaglig team og sett på denne typer algoritmer for prosessoptimalisering! Og jeg antar at det er rimelig mange stormestre som håper julenissen godtar en oppdatering av juleønskene rett før jul :-) 

Share this post


Link to post
Share on other sites
JEB    486

Har lest artikkelen grundig - ingen relativ brikkeverdi etc ble gitt. Kun reglene. Utrolig imponerende.

Share this post


Link to post
Share on other sites
Gegga    471

Det er vel litt diskusjon rundt dette med hvor lang betenkningstid det var. Og så fikk vel ikke Stockfish bruke noen åpningsdatabase?

Mens AlphaZero ikke har noen database i det hele tatt.

Den har vel nådd å spille noen millioner partier på 4 timer? :-)

Hvordan blir en slik computer hvis den skal lære seg å hacke seg inn på forskjellige ting?
Den kan jo forsøke alle smutthull. På ganske så kort tid.

Dere har kanskje sett TV-serien Person Of Interest? :-)
 

Share this post


Link to post
Share on other sites
På 7.12.2017 den 18.02, JEB skrev:

Det er selvsagt interessant i forhold til sjakk, Go o.l., men jeg er utrolig spent på betydningen av slike algoritmer i andre sammenhenger - i mitt tilfelle mest innenfor prosessoptimalisering, utvikling av medisin og diagnose. Vi har jo allerede sett noe av hva IBMs Watson kan, og ikke kan, i forhold til vurdering av "big data". Vi er åpenbart bare helt i starten av denne utviklingen - Alpha Zero kom som et sjokk (her snakker vi definitivt ikke bare om "brute force"). 

Enig, det er mange spennende bruksområder, og vi er nok fortsatt bare i starten!

Share this post


Link to post
Share on other sites
4 timer siden, Gegga skrev:

Det er vel litt diskusjon rundt dette med hvor lang betenkningstid det var. Og så fikk vel ikke Stockfish bruke noen åpningsdatabase?

Betenkningstiden var 1 minutt per trekk, ifølge DeepMinds rapport. Men det er nok mange spørsmål om konfigureringen og ikke minst om AlphaZero blir offentlig tilgjengelig, om resultatene kan gjenskapes, hvordan den vil klare seg mot andre sjakkmotorer, om den kan bli enda bedre med mer trening etc.

Share this post


Link to post
Share on other sites
JEB    486
1 time siden, Inge «Insan» Harkestad skrev:

Jeg har skrevet en blogg-artikkel om AlphaZero: 

Kunstig intelligens i sjakk: Algoritmenes tidsalder er over

Meget bra skrevet Inge! 

En kan godt diskutere om Stockfish ville klart seg bedre resultatmessig med åpningsdatabase, tid pr trekk, hardware benyttet osv, men jeg synes ikke det nøyaktige resultatet er det vesentlige. Alpha Zero startet på scratch, "tabula rasa", og nådde et ekstremt nivå på noen få timer. Det er det viktige. Og Alpha Zero kan sikkert også trenes mer spesifikt til et høyere nivå om ønskelig (e.g. ved bruk av sluttspilldatabase og enkelte av prinsippene som brukes i dagens programmer). Det er forøvrig meget interessant at det ved selvlæring når et platå hvor flere timer trening ikke vil gi vesentlig effekt - jeg vet ikke hvordan slikt beskrives i nevrale nettverk, kan det beskrives i form av entropi, støy e.l.? 

Forfatterne har ikke gitt alle detaljer, inkl hardware etc, men de har gitt mer enn nok til at denne type nevrale nettverk vil bli tilgjengelig for sjakk i løpet av begrenset tid. Prinsippene er nå kjent, og det finnes mange miljøer som vil klare å fylle de hullene som mangler (Google har selvsagt enorme ressurser, men uansett). Det er som med relativitetsteorien - ideene og prinsippene var det vanskelige, matematikken i seg selv ville mange klart.

  • Like 1

Share this post


Link to post
Share on other sites
38 minutter siden, JEB skrev:

Det er forøvrig meget interessant at det ved selvlæring når et platå hvor flere timer trening ikke vil gi vesentlig effekt - jeg vet ikke hvordan slikt beskrives i nevrale nettverk, kan det beskrives i form av entropi, støy e.l.? 

Det er et veldig godt spørsmål. Har man nådd grensen for hvor godt det går an å spille sjakk?

Eller har man kanskje nådd grensen for hvor godt man kan spille sjakk med det nevrale nettverket og de metodene som er brukt til AlphaZero? Vil man plutselig kunne få fremgang igjen og nå et nytt platå med mer trening? Eller bør man i stedet justere metoder, oppsett, konfigurering eller lignende?

En ting jeg forresten mistenker, siden AlphaZero så vidt jeg forstår bruker dedikert hardware, er at AlphaZero kun vil bli tilgjengelig som en sky-tjeneste. Det vil på mange måter virke mer logisk fra DeepMinds perspektiv enn å lage en desktop-variant. Men i så fall: Vil andre utvikle et ferdigtrent desktop-program, f.eks. Stockfish BetaChess? :)

Share this post


Link to post
Share on other sites
Sesse    367
1 time siden, JEB skrev:

Det er forøvrig meget interessant at det ved selvlæring når et platå hvor flere timer trening ikke vil gi vesentlig effekt - jeg vet ikke hvordan slikt beskrives i nevrale nettverk, kan det beskrives i form av entropi, støy e.l.? 

Det er helt vanlig i alt av maskinlæring; du når et maksimalt potensiale på noe punkt. Det er sjelden fordi man har truffet perfeksjon i noen form.

Du kan selvsagt også diskutere hva som er «perfekt» sjakk. Alle sjakkstillinger er enten objektivt tapt, remis eller vunnet; vil det være nødvendig for en perfekt sjakkspiller å prøve å f.eks. vinne remisstillinger? Det vil i så fall nødvendigvis vil kreve en eller annen form for psykologi i å styre mot mer kompliserte stillinger. Antageligvis er sjakk remis både etter både 1. e4 og 1. h3, men få vil kalle et sjakkparti som starter med 1. h3 «perfekt».

  • Like 1

Share this post


Link to post
Share on other sites
JEB    486

Kan anbefale dokumentaren AlphaGo om utviklingen av algoritmen med samme navn. Svært lite teknisk, men skildringen av 18 ganger Go-verdensmester Se-dol Lee sin match over 5 partier er veldig fascinerende. Dokumentaren ligger på Netflix

  • Like 1

Share this post


Link to post
Share on other sites

I stillingen over mente Stockfish at hvit og svart sto helt likt (0,00 på dybde 44), mens Leela mente at hvit sto litt bedre (+0,43 på dybde 12; Leela prøver generelt ikke å se like langt fremover som Stockfish).

Jeg lot dem spille videre mot hverandre fra denne stillingen, for å prøve å finne ut hvem som hadde rett.

Stockfish forventet nå 28...Be6 29.Nxe6, men Leelas foretrukne valg var 29.Rf4. Etter 29.Rf4 ga Stockfish umiddelbart en evaluering på rundt -0,5, men den ble ganske raskt justert til cirka 0. Deretter var de to sjakkmotorene enige om fortsettelsen 29...Rhh8 30.Kg2 Nd7 31.Kg3 og relativt enige om 31...c5 32.a4 b6 33.Rf2 Rhg8 34.Ne4 Nf8 35.Rd1 Ke8. Stockfish så ikke ut til å forvente Leelas neste trekk, 36.Bg5, men spilte 36...Nh7 og ga fortsatt 0,00 i evaluering. Leelas evaluering hadde nå steget til +0,94. Hvem hadde rett? Varianten fortsatte med 37.Bh4 g5 38.hxg6 Rxg6 39.Rf4 Kf8 40.Nf6 Rg7.

Her – endelig – justerte plutselig Stockfish evalueringen i hvits favør. Leela, som i utgangsstillingen bare oppga å se 12 halvtrekk fremover, sto nå best ifølge begge sjakkmotorene, så mye som 25 halvtrekk senere. Stockfish' evalueringer svingte opp og ned en stund, men på dybde 46 mente Stockfish, i likhet med Leela, at hvit definitivt sto best:

mvl-grischuk-variant-stockfish-leela-etter-40-Rg7.png

Share this post


Link to post
Share on other sites

Som vi ser, var nå Leela og Stockfish enige om at hvit sto best, men ikke om hvordan partiet ville fortsette. De neste trekkene gikk slik: 41.Nd5 Bxd5 42.Rxd5 Ke8. Nå forventet Stockfish Rf5, men Leela hadde andre planer: 43.Bf6 Rg6 44.Rf1 Ng5 45.Kh4 Ne6 46.g5.

Her forverret Stockfish' evalueringer seg markant. Men etter 46...a6 mente pussig nok Stockfish at hvit bare hadde ett trekk som opprettholdt fordelen, mens Leelas evaluering tydet på at hvit hadde flere muligheter.

Intuitivt tror jeg mer på Leela: I denne stillingen må da hvit stå bedre, selv uten å finne de helt optimale trekkene?

mvl-grischuk-variant-stockfish-leela-etter-46--a6.png

Share this post


Link to post
Share on other sites

Interessant nok hadde de to sjakkmotorene veldig ulike strategier for svart etter 47.Rfd1. Leela foreslo motspill med 47...b5 og evaluerte det til +1,59, mens Stockfish' fremste alternativer var uvirksomme trekk som 47...Kf8 og 47...Rg8. Stockfish evaluerte selv begge disse trekkene til deprimerende +2,75 på dybde 44.

Partiet fortsatte 47...Rg8 48.Rd7 Kf8 49.Kg4 Rc8 50. Kf5 Ng7+ 51.Ke4 Ne6.
Så begynte sjakkmotorenes valg og evalueringer å sprike veldig: 52.Kd5 - et posisjonelt naturlig trekk, men Stockfish mente det var en stor feil. 55...Re8 53.Rg1 c4 54.c3. Nå mente Stockfish at Leela hadde spilt bort mesteparten av fordelen. 54...b5 55.a5. Det siste trekket var knapt på Stockfish' radar før det ble spilt, men det fikk raskt Stockfish' evalueringer til å synke som stein igjen. 55...Ra8 56.Kc6 Rb8 57.Rh1 Re8 58.Rh4. Dette trekket anså Stockfish som svakt - inntil den fikk regnet mer på det. 58...Nxg5 59.Kc7 Ne6+ 60.Kb6 Rb8+ 61.Ka7 Rc8 62.Kb7 Re8 63.Rd5. Igjen et trekk som Stockfish ikke regnet som veldig bra før det ble spilt. Stockfish måtte nå ty til desperate grep: 63...Re7+ 64.Kb6 (ooh, elegant - og nærmest et hån mot svart) Re8 65.Rd6 Rc8 66.Kxa6.

Leela og Stockfish har vært uenige om mye, men er samstemte i at nå er svart fortapt:

mvl-grischuk-variant-stockfish-leela-etter-66-Kxa6.png

Share this post


Link to post
Share on other sites

En kjapp avslutning:

66...b4 67.Kb7 Rc7+ 68.Kb8 b3 69.Rxe6 fxe6 70.Kxc7 Rg1 71.Rh2 Ra1 72.Kd6 Kf7 73.Kc5, med vunnet stilling for svart.

Jeg skal ikke komme med en veldig bastant analyse, men synes å gjenkjenne noen trekk fra partiene mellom AlphaZero og Stockfish:

  • Der Stockfish forventet bytter og evaluerte til 0.00, holdt Leela brikkene sine på brettet
  • Leela jobbet med å aktivisere brikkene sine, mens Stockfish forsvarte seg passivt
  • Da det ble avbytter, satt Leela igjen med aktive brikker, mens Stockfish' brikker var mer innelåst
  • Leela var lite opptatt av materiell, men desto mer opptatt av å forbedre stillingen posisjonelt
  • Til slutt løste det seg opp i et sluttspill der Leela sto best

mvl-grischuk-variant-stockfish-leela-etter-73-Kc5.png

Edited by Inge «Insan» Harkestad
  • Like 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×