kunstig dumhed: en Google-ingeniørs algoritmer til dårlig skakspil

Hvad sker der, når vi anvender banebrydende moderne teknologier til det ældgamle skakspil? Og hvad sker der, når en kedelig nørd med et overskud af computerkraft udfører sine egne underlige hjemmeeksperimenter på spillet?

i år besluttede en Pennsylvania-programmelingeniør, der kalder sig Tom Murphy VII, at skabe nogle latterligt dårlige skakspilalgoritmer ved hjælp af alt fra maskinindlæring og neurale netværk til en gratis mængde CPU — cyklusser-og derefter pittede de dårlige algoritmer mod hinanden for at skabe en “turnering af narre.”

” det er min ide om sjov… ” siger Murphy i en humoristisk video, der beskriver eksperimenterne.

første træk

Murphy har hjernekraften til at trække den af. Han fortæller os, at han i 2007 forsvarede sin datalogi Ph. D. på Carnegie Mellon – hvilket var samme år begyndte de studerende at afholde den årlige sigbovik-konference på April Fool ‘ s Day. Sponsoreret af” Association for Computational kætteri, “det var en slags satirisk særlig interessegruppe viet til en fiktiv forsker ved navn” Harry ekspert Bovik, “og inklusive en opfordring til tåbelige papirer om emner som” kunstig dumhed.”

i de sidste 11 år har Murphy været senioringeniør hos Google (i sine Pittsburgh-kontorer). Men i år besluttede han at vende tilbage til April Fool ‘ s Day — konferencen-og igen bidrog han med sin egen humoristiske forskning.

Murphy praler stolt over, at nogle af hans tidligere præsentationer der involverede latterlige undersøgelser, der “ikke kunne skelnes fra ‘rigtig’ forskning (for eksempel er det første niveau af Super Mario Bros. let med leksikografiske ordrer, og tidsrejser har omkring 20 citater i ‘rigtig’ akademisk forskning).

men dette var året, hvor Murphy vendte sin opmærksomhed mod skak.

lad spillene begynde

i Murphys første spil er menneskelige spillere bind for øjnene og tvinger dem til at huske, hvor brikkerne er. Men hvad svarer det til en computer? Fortæller det, hvor stykker er placeret, men ikke hvilke stykker de er (eller endda hvilken farve)…

selvfølgelig ville computeren heller ikke være forsynet med bevægelserne, der fører op til en position. Det ville ikke engang vide, hvis tur det var. Ja, der er en mulighed for, at computerens konge er i skak — på hvilket tidspunkt stort set hver bevægelse er ulovlig undtagen et træk, der fører din konge til sikkerhed. Men for at omgå det oprettede Tom et program, der genererer en liste over mulige træk, rangeret i rækkefølge efter præference — hvorfra det første lovlige træk vælges.

“jeg kan godt lide at spille imod det, fordi det ikke er meget godt,” siger Murphy i videoen. “Men det naturlige spørgsmål er, hvor ikke-meget-godt er det?”At teste det mod skakspilsprogrammer beviser, at ja, det taber med stor regelmæssighed — som i “hver eneste gang.”

så satte han sig for at bygge andre dårlige skakspilalgoritmer, så han kunne sammenligne deres relative ydeevne…

man havde en præference for at placere sine brikker på de hvide firkanter, når det spiller hvidt, og på sorte firkanter, når det spiller sort. Hans modstander ? En algoritme, der foretrak at placere sine stykker på modsat farvede firkanter.) I sidste ende spillede de begge ret dårligt. “De har en præference, men det har ikke rigtig at gøre med at vinde.”Faktisk er de begge bare lidt værre end algoritmen, der vælger sine bevægelser tilfældigt.

der var også to algoritmer, han kaldte “Huddle” og “sværm” — hvor den ene automatiserede spiller søger efter bevægelser, der holder sine brikker tæt på sin egen konge, mens den anden søger efter træk, der placerer sine brikker nær modstanderens konge. Dette fører undertiden til, at huddles konge bliver tvunget til at følge sine egne bønder over hele linjen, hvor i det mindste nogle få tilfælde dets bonde derefter ved et uheld blev forfremmet til mere magtfulde stykker og utilsigtet skakmerede den modsatte konge.

men oftere fungerer det den anden vej. “Hvis du foretrækker at angribe modstanderen, vil du ved et uheld kontrollere det nogle gange.”I videoen afslører Murphy, at blandt de dårlige skakalgoritmer er denne overraskende ikke så dårlig. “‘Sværm ‘er faktisk meget bedre end’ tilfældig bevægelse.'”

og en mere vellykket strategi er en algoritme, der prioriterer fire specifikke former for bevægelse (i denne rækkefølge): at skakmat, kontrollere, fange et stykke eller skubbe ind i modstanderens territorium.

men der er andre forfærdelige ideer — som en algoritme, der søger at spejle sin modstanders brikker eller flytte alle sine brikker til den anden side af brættet. En algoritme vælger simpelthen, hvilken bevægelse der kommer først i alfabetisk rækkefølge.

og der er en anden algoritme, hvor hvert træk er valgt fra en liste over mulige træk — med valgene dikteret vilkårligt af cifrene i pi…

overlevelse i Skakland

men i sidste ende startede hans mest detaljerede algoritme med et spørgsmål, der: hvilket enkelt skakbrik er mest sandsynligt at “overleve” – at forblive på tavlen gennem slutningen af spillet og komme sejrrige med alle sine andre skakbrikker? Pligtskyldigt undersøge svaret, Murphy besøgte free / libre chess site LiChess.org (som nu ser mere end en million spil om dagen). Det tilbyder også spil til hentning — så Murphy hentede alle 506.000.416 af dem.

han opsummerede resultaterne i et papir kaldet “Survival in Chessland”, som forklarer hans metode. Murphy hentede hvert komplet spil, de havde gennem November 2018 — selvom yderligere 200 millioner tilsyneladende er blevet tilgængelige i de otte måneder siden. Selv hans November-træk repræsenterede en kæmpe 875 GB skakspil,” så behandling af disse tog en vis omhu for effektivitet og parallelisme, ” siger Murphy i videoen.

“heldigvis har jeg en computer med bare et uanstændigt antal kerner og virkelig overdreven RAM, så du skal bruge det til noget.”

Er, hvor uanstændigt? I en e-mail beskriver han sit “gratis” hjemmesystem, en 32-core AMD ThreadRipper 2990. At køre de multi-threaded C++ – programmer i et par timer var nok til at knuse gennem hele datasættet. “Jeg tror, at folk undervurderer, hvad du kan gøre effektivt med en enkelt maskine!”

“det involverede arbejde er ret simpelt: Jeg analyserer PGN (som beskriver spillet), udfører derefter bevægelserne i spillet, holder styr på skæbnen for hvert stykke og opsummerer derefter tællingerne for hver skæbne…”

“jeg skrev dybest set al koden fra bunden, fordi det er sjovere end at få andres kode til at fungere. :)”

og så førte dette til mere dårlige skakspilalgoritmer. For det første er der den, der bare flytter stykker til de firkanter, hvor de statistisk set er mere tilbøjelige til at overleve. Eller bare til de firkanter, hvor de mest sandsynligt er i slutningen af et spil. Og andre algoritmer gør det nøjagtige modsatte-flytter stykker til firkanter, hvor de er mindst tilbøjelige til at overleve (eller ende). To algoritmer beregner, hvilken firkant der har den højeste overlevelsesrate (versus fangsthastighed) for et stykke på hver firkant, hvor en algoritme søger det højeste forhold, der favoriserer overlevelse — og den “fatalistiske” algoritme, der søger det laveste sådant forhold.

“underligt har det de bedste vinderchancer for disse strategier.”

og endelig besluttede han at sammenligne dem alle med Stockfish-skakmotoren på flere niveauer (herunder en speciel algoritme, hvor den er tvunget til at spille sit mindst lovende træk). “Når man ser på resultaterne, er det overraskende den overordnede værste strategi, og det lykkes at tabe for næsten alle.”

men husk Toms originale” bind for øjnene ” algoritme, som ikke vidste, hvilket stykke der besatte en firkant (eller endda dens farve)? Han besluttede at udvide det med et neuralt netværk, der udførte maskinlæring — ved hjælp af de milliarder af stillinger, der var tilgængelige i spillene fra LiChess.org. Det var nu i stand til korrekt at forudsige de faktiske stykker på hver position med 100% nøjagtighed…omkring en femtedel af tiden. Og selv når det er forkert, er det kun forkert gættet et gennemsnit på 3,22 stykker for hver position.

og dette bliver et springpunkt for endnu mere vilde beregninger. På et tidspunkt udleder han, at alle spil i deres database til sidst passerer gennem 21.553.382.902 unikke positioner. Med 204GB kan du gemme dem alle sammen med det næste træk — men der er en anden interessant statistik. Hele 76% af positionerne fandt sted nøjagtigt en gang. “Så disse tager meget plads, og de er ikke særlig nyttige til at spille, fordi det er meget usandsynligt, at jeg nogensinde vil se dem igen.”Når man smider disse engangsstillinger væk, kan enhver anden mulig spilposition gemmes med omkring 500 MB hukommelse. Dette kan let konverteres til en algoritme, der spiller det mest populære træk for enhver position, den støder på (mens du bytter i et tilfældigt træk, hvis det tilfældigvis befinder sig fanget i en unik position).

men så er der et let trick til at slå det. “Så snart jeg gør lidt af et underligt træk, begynder det bare at spille tilfældigt. Og så er det meget nemt at slå.”

et sidste eksperiment involverer forskellige “fortyndinger” af Tørfiskmotoren — hvor dets foretrukne træk erstattes af et tilfældigt valgt træk med procent af tiden.”

“vi kan faktisk vurdere, hvor god en spiller er nu ved at sammenligne den direkte med en bestemt fortynding af tørfisk…”

efter at alle Murphys detaljerede skakspilalgoritmer var blevet pligtskyldigt testet, opsummerede han resultaterne i et massivt bord og afsluttede triumferende sin video ved at meddele, at han endelig var klar til at forfølge andre interesser.

“nu er det videre til det næste projekt, der lærer denne hund, hvordan man spiller skak.”

• Hvad sker der, når maskinlæring fører menneskeheden til Svar, Vi ikke forstår?
• Mød Sophie, noodle-making robot.
• efter 15 år afslører forskere en kunstig arm, der kan føle.