mitä tapahtuu, kun sovellamme huipputeknologiaa ikiaikaiseen shakkipeliin? Ja mitä tapahtuu, kun tylsistynyt nörtti, jolla on liikaa laskentatehoa, tekee omat oudot kotikokeilunsa peliin?
tänä vuonna Pennsylvanialainen ohjelmistoinsinööri, joka kutsuu itseään Tom Murphy VII: ksi, päätti luoda naurettavan huonoja shakinpeluualgoritmeja käyttäen kaikkea koneoppimisesta ja neuroverkoista aina vastuuttomaan määrään SUORITINSYKLEJÄ-ja sitten usutti huonot algoritmit toisiaan vastaan luodakseen ”tournament of fools.”
” It ’s my idea of fun…” Murphy sanoo humoristisella videolla, jossa hän kuvailee kokeiluja.
First Moves
Murphylla on älyä vetää se pois. Hän kertoo, että vuonna 2007 hän väitteli tietojenkäsittelytieteen tohtoriksi. Carnegie Mellonissa-joka oli samana vuonna opiskelijat alkoivat pitää vuosittaista sigbovik-konferenssia aprillipäivänä. Sponsoroi ”Association for Computational Heresy,” se oli eräänlainen satiirinen erityinen eturyhmä omistettu kuvitteellinen tutkija nimeltä ” Harry Visailumestari Bovik, ”ja myös kehotus Hessu papereita aiheista kuten” keinotekoinen tyhmyys.”
viimeiset 11 vuotta Murphy on ollut Googlen (sen Pittsburghin toimistoissa) vanhempi henkilöstöohjelmistoinsinööri. Mutta tänä vuonna hän päätti palata jälleen aprillipäivän konferenssiin — ja jälleen, antoi oman humoristisen tutkimuksensa.
Murphy kerskuu ylpeänä, että jotkut hänen aikaisemmat esityksensä siellä sisälsivät naurettavia tutkimuksia, jotka olivat ”erottamattomia ’todellisesta’ tutkimuksesta (esimerkiksi Super Mario Brosin ensimmäinen taso on helppo lexicographic orderings ja aikamatkustuksessa on noin 20 lainausta ’todellisesta’ akateemisesta tutkimuksesta).
mutta tämä oli vuosi, jolloin Murphy käänsi huomionsa shakkiin.
let the Games Begin
Murphyn alkulohkopelissä ihmispelaajien silmät sidotaan, mikä pakottaa heidät muistamaan, missä palaset ovat. Mutta mikä on vastine tietokoneelle? Kerrotaan, missä palaset sijaitsevat, mutta ei mitä paloja ne ovat (tai jopa minkä värisiä)…
tietenkään tietokoneellekaan ei annettaisi asentoon johtavia siirtoja. Se ei edes tietäisi, kenen vuoro oli. Kyllä, on mahdollista, että tietokoneen kuningas on kurissa — jolloin lähes kaikki liikkeet ovat laittomia, paitsi siirto, joka johtaa kuninkaan turvaan. Mutta kiertääkseen sen, Tom loi ohjelman, joka luo listan mahdollisista siirroista, paremmuusjärjestyksessä-josta valitaan ensimmäinen laillinen siirto.
”Tykkään pelata sitä vastaan, koska se ei ole kovin hyvä”, Murphy sanoo videolla. ”Mutta luonnollinen kysymys on, miten ei-kovin-hyvä se on?”Sen testaaminen shakkiohjelmia vastaan todistaa, että kyllä, se häviää hyvin säännöllisesti-kuten aina”.”
sitten hän lähti rakentamaan muita huonoja shakkipelin algoritmeja, jotta voisi verrata niiden suhteellista suorituskykyä …
yksi oli mieluummin sijoittamassa nappuloitaan valkoisille ruuduille, kun se pelaa valkoista, ja mustille ruuduille, kun se pelaa mustaa. (Sen vastustaja? Algoritmi, joka sijoitti nappulansa mieluummin vastakkaisen värisille ruuduille.) Lopulta molemmat pelasivat aika huonosti. ”Heillä on etusija, mutta se ei oikeastaan ole tekemistä voittaa.”Itse asiassa, ne ovat molemmat vain hieman huonompi kuin algoritmi, joka valitsee sen liikkuu sattumanvaraisesti.
jos löydät minun monimutkainen 42min video noin 30 outoa shakkialgoritmit kilpailevat turnaus hölmöjä, jotta arvioida minun ohjelma, joka pelaa shakkia tietämättä, mitä nappulat ovat aluksella on tylsää, niin se on, koska et ymmärrä taidetta:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) July 15, 2019
pelissä oli myös kaksi algoritmia, joille hän antoi nimet ”Huddle” ja ”Swarm” — joissa toinen automaattipelaaja etsii siirtoja pitäen nappulansa lähellä omaa kuningastaan, kun taas toinen etsii siirtoja sijoittaen nappulansa lähelle vastustajan kuningasta. Tämä johtaa joskus Huddle kuningas on pakko seurata omia pelinappuloita kautta linjan, jolloin ainakin muutamia tapauksia sen sotilas sitten vahingossa edistää osaksi tehokkaampi kappaletta ja epähuomiossa checkmated vastapuolen kuningas.
mutta useammin se toimii toisin päin. ”Jos sinulla on etusija hyökätä vastustajan, olet menossa vahingossa shakkimatti se joskus.”Videolla Murphy paljastaa, että huonojen shakkialgoritmien joukossa tämä on yllättäen ei-niin-huono. ”’Parvi ’on itse asiassa paljon parempi kuin’ satunnainen liike.””
ja yksi onnistuneempi strategia on algoritmi, joka priorisoi neljä tietyntyyppistä liikettä (tässä järjestyksessä): shakkimatti, check, kaapata pala tai työntää vastustajan alueelle.
mutta on muitakin kauheita ideoita-kuten algoritmi, joka pyrkii peilaamaan vastustajansa nappuloita tai siirtämään kaikki nappulansa laudan toiselle puolelle. Yksi algoritmi yksinkertaisesti valitsee kumpi siirto tulee ensin aakkosjärjestyksessä.
ja on toinenkin algoritmi, jossa jokainen siirto valitaan mahdollisten siirtojen luettelosta-piin numeroiden mielivaltaisesti sanelemat valinnat…
selviytyminen Chesslandissa
mutta lopulta hänen taidokkain algoritminsa alkoi kysymyksellä: mikä yksittäinen shakkinappula on enimmäkseen todennäköistä ”hengissä” – pysyä laudalla läpi pelin loppuun, ja syntymässä voitokas kaikkien muiden shakkinappuloita? Murphy tutki vastausta kuuliaisesti ja vieraili free / libre – shakkisivustolla. LiChess.org (joka nyt näkee yli miljoona peliä päivässä). Se tarjoaa myös pelejä ladattavaksi-joten Murphy latasi niistä kaikki 506 000 416.
hän teki yhteenvedon tuloksista tutkielmassa ”Survival in Chessland”, jossa hän kertoo metodologiastaan. Murphy latasi jokaisen kokonaisen pelin, joka heillä oli marraskuun 2018 aikana — tosin toiset 200 miljoonaa ovat ilmeisesti tulleet saataville kahdeksan kuukauden aikana. Jopa hänen marraskuinen saaliinsa edusti huimat 875 GT shakkipelejä, ”joten näiden käsittely vaati jonkin verran huolellisuutta tehokkuudesta ja rinnakkaisuudesta”, Murphy kertoo videolla.
” onneksi minulla on tietokone, jossa on vain hävytön määrä ytimiä ja todella liikaa RAM-muistia, joten sitä pitää käyttää johonkin.”
Er, how obscene? Sähköpostissa hän kuvailee ”vastikkeetonta” kotijärjestelmäänsä, 32-ytimistä AMD ThreadRipper 2990wx: ää. Monisäikeisten C++-ohjelmien suorittaminen muutaman tunnin ajan riitti runnomaan läpi koko aineiston. ”Mielestäni ihmiset aliarvioivat, mitä yhdellä koneella voi tehdä tehokkaasti!”
”työ mukana on melko yksinkertainen: Jäsennän PGN: n (joka kuvaa peliä), sitten suoritan pelin liikkeet, pidän kirjaa jokaisen kappaleen kohtalosta, ja sitten lasken jokaisen kohtalon…”
”kirjoitin periaatteessa kaiken koodin tyhjästä, koska tämä on hauskempaa kuin saada muiden ihmisten koodi toimimaan. :)”
Murphyn ”survivalability” – analyysi loi joitakin todella kauniita visualisointeja tiedoista, jotka osoittavat selviytymistodennäköisyyden jokaiselle shakkinappulalle jokaisessa 64 ruudussa (väreillä, jotka ilmaisevat todennäköisyytensä olla tuossa ruudussa pelin lopussa.)
tämä johti huonompiin shakin pelialgoritmeihin. Ensin on se, joka siirtää palasia ruutuihin, joissa ne tilastollisesti selviävät. Tai vain ruutuihin, joissa ne ovat todennäköisimmin pelin lopussa. Ja muut algoritmit tekevät täsmälleen päinvastoin – liikkuvat kappaletta neliöitä, joissa ne ovat vähiten todennäköisesti hengissä (tai päätyä). Kaksi algoritmia laskee, millä neliöllä on korkein eloonjäämisaste (vs. kaappausnopeus) kappaleelle kullakin neliöllä, yksi algoritmi etsii korkeinta suhdelukua suosien eloonjäämistä — ja ”fatalisti” algoritmi etsii alhaisinta tällaista suhdelukua.
” oudosti sillä on näistä strategioista parhaat voittomahdollisuudet.”
ja lopulta hän päätti verrata ’ niitä kaikkia Stockfish-shakkimoottoriin useilla tasoilla (mukaan lukien erityinen algoritmi, jossa sen on pakko pelata vähiten lupaava siirtonsa). ”Kun tarkastellaan tuloksia, ei ole yllättävää, että tämä on kaiken kaikkiaan huonoin strategia, ja se onnistuu häviämään lähes kaikille.”
mutta muistatko Tomin alkuperäisen ”sokkona” – algoritmin, joka ei tiennyt, mikä kappale miehitti neliön (tai edes sen värin)? Hän päätti laajentaa sitä neuroverkolla, joka suoritti koneoppimista — käyttäen hyväksi lichessin peleissä saamia miljardeja asemia.org. Se kykeni nyt ennustamaan oikeat kappaleet-100% tarkkuudella-noin viidesosan ajasta. Ja vaikka se on väärin, se on vain väärin arvattu keskimäärin 3,22 kappaletta jokaista asentoa.
ja tästä tulee hyppypiste vielä hurjemmille laskutoimituksille. Jossain vaiheessa hän päättelee, että kaikki heidän tietokannassaan olevat pelit läpäisevät lopulta 21 553 382 902 ainutlaatuista paikkaa. Kanssa 204gb voit tallentaa ne kaikki — yhdessä seuraavan siirron — mutta siellä on toinen mielenkiintoinen tilasto. Huimat 76 prosenttia paikoista tapahtui tasan kerran. ”Joten nämä vievät paljon tilaa, ja ne eivät ole kovin hyödyllisiä pelaamiseen, koska olen hyvin epätodennäköistä koskaan nähdä niitä uudelleen.”Heittämällä pois nämä kertaluonteiset asennot, joka toinen mahdollinen peliasento voidaan tallentaa noin 500MB muistia. Tämä voidaan helposti muuntaa algoritmiksi, joka toistaa suosituimman siirron mihin tahansa kohtaamaansa asentoon (vaihtaessaan satunnaisella siirrolla, jos se sattuu olemaan ansassa ainutlaatuisessa asennossa).
mutta sitten on yksi helppo kikka sen voittamiseen. ”Heti kun teen hieman outo liikkua, se vain alkaa pelata satunnaisesti. Sitten se on helppo voittaa.”
loppukokeessa on mukana erilaisia Stockfish-Moottorin ”laimennuksia”, joissa sen suosima liike korvataan satunnaisesti valitulla siirrolla x prosenttia ajasta.”
”voimme itse asiassa arvioida, kuinka hyvä pelaaja on nyt, vertaamalla sitä suoraan tiettyyn stockfishin diluutioon…”
kun kaikki Murphyn taidokkaat shakinpeluualgoritmit oli testattu kuuliaisesti, hän tiivisti tulokset yhteen massiiviseen taulukkoon ja päätti videonsa voitonriemuisesti ilmoittamalla, että hän oli vihdoin valmis tavoittelemaan muita etuja.
” nyt on vuorossa seuraava projekti, joka opettaa tätä koiraa pelaamaan shakkia.”
- mitä tapahtuu, kun Koneoppiminen johtaa ihmiskunnan vastauksiin, joita emme ymmärrä?
- tapaa Sophie, nuudeleita valmistava robotti.
- 15 vuoden jälkeen tutkijat paljastavat keinokäden, joka voi tuntua.