Hva skjer Når vi bruker banebrytende moderne teknologi til det gamle sjakkspillet? Og hva skjer når en kjedelig geek med et overskudd av datakraft utfører sine egne rare hjemmeeksperimenter på spillet?
i år bestemte En Pennsylvania-programvareingeniør Som kaller Seg Tom Murphy VII seg for å lage noen latterlig dårlige sjakkspillalgoritmer ved å bruke alt fra maskinlæring og nevrale nettverk til en gratis MENGDE CPU — sykluser-og så satte de dårlige algoritmer mot hverandre for å skape en «tournament of fools.»
«Det er min ide om moro…» Sier Murphy i en humoristisk video som beskriver forsøkene.
Første Trekk
Murphy har hjernekraften til å trekke den av. Han forteller oss at han i 2007 forsvarte sin datavitenskap Ph. D. På Carnegie Mellon – som var samme år begynte studentene å holde den årlige SIGBOVIK-konferansen på April Fool ‘ S Day. Sponset av «Association For Computational Heresy», var det en slags satirisk spesiell interessegruppe viet Til En fiktiv forsker ved navn «Harry Quizmaster Bovik», og inkludert et kall for goofy papirer om emner som «kunstig dumhet.»
I de siste 11 årene Har Murphy vært en senior staff software engineer Hos Google(i Pittsburgh-kontorene). Men i år bestemte han seg for å komme tilbake igjen for April Fool ‘ s day-konferansen-og igjen bidro han med litt humoristisk forskning av seg selv.
Murphy skryter stolt av at noen av hans tidligere presentasjoner der involverte latterlige undersøkelser som var «uutslettelige fra» ekte «forskning (for eksempel Det første nivået Av Super Mario Bros. er enkelt med leksikografiske ordrer og tidsreiser har rundt 20 sitater i «ekte» akademisk forskning).
Men Dette var året Murphy vendte sin oppmerksomhet mot sjakk.
La Spillene Begynne
i Murphys første spill er menneskelige spillere bind for øynene, og tvinger Dem til å huske hvor brikkene er. Men hva er tilsvarende for en datamaskin? Forteller det hvor brikkene er plassert, men ikke hvilke brikker de er (eller hvilken farge)…
selvfølgelig ville ikke datamaskinen bli forsynt med bevegelsene som fører opp til en posisjon heller. Det ville ikke engang vite hvem sin tur det var. Ja, det er en mulighet for at datamaskinens konge er i sjakk-på hvilket tidspunkt stort sett hver bevegelse er ulovlig bortsett fra et trekk som fører kongen i sikkerhet. Men For Å komme seg rundt det, Skapte Tom et program som genererer en liste over mulige trekk, rangert etter preferanse-hvorfra det første lovlige trekket vil bli valgt.
» jeg liker å spille mot det, fordi Det ikke er veldig bra,» Sier Murphy i videoen. «Men det naturlige spørsmålet er hvor ikke-veldig bra er det?»Å teste det mot sjakkspillingsprogrammer viser at ja, det mister med stor regelmessighet-som i, «hver eneste gang.»
så satte han seg for å bygge andre algoritmer for dårlig sjakkspill, slik at han kunne sammenligne deres relative ytelse …
man hadde en preferanse for å plassere brikkene på de hvite rutene når den spiller hvit, og på svarte firkanter når den spiller svart. Din motstander? En algoritme som foretrukket å plassere brikkene på motsatt fargede firkanter.) Til slutt spilte de begge ganske dårlig. «De har en preferanse, men det har egentlig ikke å gjøre med å vinne .»Faktisk er de begge bare litt verre enn algoritmen som velger sine trekk tilfeldig.
Hvis du finner min intrikate 42min video om 30 rare sjakkalgoritmer som konkurrerer i en tournament of fools for å vurdere programmet mitt som spiller sjakk uten å vite hvilke brikker som er på brettet for å være kjedelig, så er det fordi du ikke forstår kunst:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) juli 15, 2019
det var også to algoritmer han kalte «Huddle» og «Swarm» — hvor en automatisert spiller søker etter trekk som holder brikkene nær sin egen konge, mens den andre søker etter trekk som plasserer brikkene nær motstanderens konge. Dette fører noen ganger Til At Huddles konge blir tvunget til å følge sine egne bønder over hele linja, hvor minst noen få tilfeller sin bonde deretter ved et uhell forfremmet til kraftigere stykker og utilsiktet mattet den motsatte kongen.
men oftere fungerer det den andre veien. «Hvis du har en preferanse for å angripe motstanderen, kommer du til å tilfeldigvis matte det noen ganger .»I videoen avslører Murphy at blant de dårlige sjakkalgoritmene er denne overraskende ikke så dårlig. «Swarm» er faktisk mye bedre enn » Tilfeldig Trekk.»
og en mer vellykket strategi er en algoritme som prioriterer fire spesifikke typer trekk( i denne rekkefølgen): å sjakkmatt, sjekke, fange et stykke eller skyve inn i motstanderens territorium.
Men det er andre forferdelige ideer — som en algoritme som søker å speile motstanderens brikker, eller å flytte alle brikkene til den andre siden av brettet. En algoritme velger bare hvilket trekk som kommer først i alfabetisk rekkefølge.
Og det er en annen algoritme der hvert trekk er valgt fra en liste over mulige trekk — med valgene diktert vilkårlig av sifrene i pi…
Survival In Chessland
Men til slutt begynte hans mest forseggjorte algoritme med et spørsmål.: hvilken enkelt sjakkbrikke er mest sannsynlig å » overleve — – å forbli på brettet gjennom slutten av spillet, og fremvoksende seirende med alle sine andre sjakkbrikker? Pliktoppfyllende undersøke svaret, Murphy betalt et besøk til gratis / libre chess nettstedet LiChess.org (som nå ser mer enn en million spill om dagen). Det tilbyr også spill for nedlasting — Så Murphy lastet ned alle 506.000.416 av dem.
han oppsummerte resultatene i en artikkel kalt «Survival in Chessland», som forklarer hans metodikk. Murphy lastet ned hvert komplett spill de hadde gjennom November 2018-selv om en annen 200 millioner tilsynelatende har blitt tilgjengelig i de åtte månedene siden. Selv hans November haul representerte en hel DEL 875 GB sjakkspill ,» så behandling av disse tok litt omsorg for effektivitet og parallellitet, » Sier Murphy i videoen.
» Heldigvis har Jeg en datamaskin med bare et uanstendig antall kjerner og virkelig overdreven RAM, så du må bruke det til noe.»
Er, hvor uanstendig? I en e-post beskriver han sitt» gratis » hjemmesystem, en 32-kjerne AMD ThreadRipper 2990WX. Å kjøre Multi-threaded C++ – programmene i noen timer var nok til å knase gjennom hele datasettet. «Jeg tror folk undervurderer hva du kan gjøre effektivt med en enkelt maskin!»
«arbeidet er ganske enkelt: Jeg analyserer PGN( som beskriver spillet), deretter utfører bevegelsene i spillet, holder styr på skjebnen til hvert stykke, og summerer tellingene for hver skjebne… «
» jeg skrev i utgangspunktet all koden fra bunnen av, fordi dette er morsommere enn å få andres kode til å fungere. :)»
Murphys «overlevelsesevne» – analyse skapte noen virkelig vakre visualiseringer av dataene, og viste sannsynligheten for overlevelse for hvert sjakkstykke på hver av de 64 rutene (med farger som indikerer sannsynligheten for å være på det torget på slutten av spillet.)
Og så førte dette til mer dårlige sjakkspillingsalgoritmer. Først er det den som bare flytter stykker til de rutene der de er statistisk mer sannsynlig å overleve. Eller rett og slett til rutene der de er mest sannsynlig å være på slutten av et spill. Og andre algoritmer gjør det motsatte — flytte stykker til firkanter der de er minst sannsynlig å overleve (eller ende opp). To algoritmer beregner hvilken firkant som har den høyeste overlevelsesraten (versus fangstrate) for et stykke på hver firkant, med en algoritme som søker det høyeste forholdet som favoriserer overlevelse — og den «fatalistiske» algoritmen søker det laveste forholdet.
» Merkelig, det har de beste vinnende sjansene for disse strategiene.»
og til slutt bestemte han seg for å sammenligne dem alle Med Tørrfisksjakkmotoren på flere nivåer (inkludert en spesiell algoritme hvor Den er tvunget til å spille sitt minst lovende trekk). «Ser på resultatene, overraskende er dette den generelle verste strategien, og den klarer å miste til nesten alle.»
men husk Toms originale» blindfoldede » algoritme, som ikke visste hvilket stykke som okkuperte en firkant (eller til og med fargen)? Han bestemte seg for å utvide det med et nevralt nettverk — som utførte maskinlæring-ved hjelp av milliarder av stillinger tilgjengelig i spillene Fra LiChess.org. Det var nå i stand til å forutsi de faktiske brikkene på hver posisjon med 100% nøyaktighet … omtrent en femtedel av tiden. Og selv når det er feil, er det bare feil gjettet et gjennomsnitt på 3,22 stykker for hver posisjon.
Og dette blir et hoppepunkt for enda mer ville beregninger. På et tidspunkt utleder han at alle spillene i databasen til slutt går gjennom 21.553.382.902 unike stillinger. MED 204GB kan du lagre dem alle sammen med neste trekk-men det er en annen interessant statistikk. En hel del 76% av stillingene skjedde nøyaktig en gang. «Så disse tar opp mye plass, og de er ikke veldig nyttige for å spille, fordi jeg er veldig lite sannsynlig å se dem igjen.»Ved å kaste bort disse engangsposisjonene, kan alle andre mulige spillposisjoner lagres med OMTRENT 500 MB minne. Dette kan enkelt konverteres til en algoritme som spiller det mest populære trekket for enhver posisjon det møter (mens du bytter i et tilfeldig trekk hvis det skjer å finne seg fanget i en unik posisjon).
Men så er det ett enkelt triks for å slå det. «Så snart jeg gjør litt av et merkelig trekk, begynner det bare å spille tilfeldig. Og så er det veldig lett å slå.»
et siste forsøk innebærer forskjellige «fortynninger»Av Tørrfiskmotoren – der det foretrukne trekket erstattes av et tilfeldig valgt trekk x prosent av tiden.»
«vi kan faktisk vurdere hvor god en spiller er nå ved å sammenligne den direkte Med en bestemt fortynning Av Tørrfisk…»
Etter At Alle Murphys forseggjorte sjakkspillalgoritmer hadde blitt plikttestet, oppsummerte Han resultatene i et massivt bord, og triumferende avsluttet sin video ved å kunngjøre at han endelig var klar til å forfølge andre interesser.
» nå er det videre til neste prosjekt, som lærer denne hunden å spille sjakk.»
- Hva skjer Når Maskinlæring fører menneskeheten til svar vi ikke forstår?
- Møt Sophie, robot som lager nudler.
- etter 15 år avslører forskere en kunstig arm som kan føle.