mi történik, ha a legmodernebb modern technológiákat alkalmazzuk az ősrégi sakkjátékra? És mi történik, ha egy unatkozó geek, akinek többlet számítási teljesítménye van, saját furcsa otthoni kísérleteket végez a játékon?
ebben az évben egy pennsylvaniai szoftvermérnök, aki Tom Murphy VII-nek nevezi magát, úgy döntött, hogy nevetségesen rossz sakkozási algoritmusokat hoz létre, amelyek mindent felhasználnak a gépi tanulástól és a neurális hálózatoktól kezdve az ingyenes CPU — ciklusokig-majd a rossz algoritmusokat egymás ellen állította, hogy létrehozzanak egy “bolondok versenyét”.”
“ez az én ötletem a szórakozásról…” – mondja Murphy egy humoros videóban, amely leírja a kísérleteket.
első lépések
Murphynek megvan az agya, hogy lehúzza. Azt mondja, hogy 2007-ben megvédte a számítástechnika Ph. D. Carnegie Mellonban — amely ugyanabban az évben volt, amikor a hallgatók április bolond napján elkezdték tartani az éves SIGBOVIK konferenciát. Az “Association for Computational Heresy” szponzorálta, ” egyfajta szatirikus különleges érdekcsoport volt, amelyet egy “Harry Quizmaster Bovik” nevű fiktív kutatónak szenteltek,”, beleértve a “mesterséges ostobaság” témájú ostoba papírok felhívását.”
az elmúlt 11 évben Murphy a Google vezető szoftvermérnöke volt (Pittsburghi irodáiban). De ebben az évben úgy döntött, hogy újra visszatér az április bolondok napi konferenciájára — és ismét hozzájárult néhány humoros kutatáshoz.
Murphy büszkén dicsekszik azzal, hogy néhány korábbi előadása nevetséges vizsgálatokat tartalmazott, amelyek “megkülönböztethetetlenek voltak a “valódi” kutatásoktól (például a Super Mario Bros.első szintje könnyű a lexikográfiai sorrendekkel, az időutazás pedig mintegy 20 idézetet tartalmaz a “valódi” tudományos kutatásokban).
de ez volt az az év, amikor Murphy a sakk felé fordította figyelmét.
kezdődjenek a játékok
Murphy kezdeti játékában az emberi játékosokat bekötik, arra kényszerítve őket, hogy emlékezzenek a darabok helyére. De mi a megfelelője egy számítógépnek? Megmondja, hogy hol vannak a darabok, de nem azt, hogy mely darabok vannak (vagy akár milyen színűek)…
természetesen a számítógépet sem látják el a pozícióhoz vezető mozdulatokkal. Azt sem tudja, ki következik. Igen, fennáll annak a lehetősége, hogy a számítógép királya ellenőrzés alatt áll — ekkor nagyjából minden lépés illegális, kivéve egy olyan lépést, amely a király biztonságához vezet. De hogy ezt megkerülje, Tom létrehozott egy programot, amely elkészíti a lehetséges lépések listáját, preferencia sorrendben rangsorolva — amelyből az első jogi lépést választják.
“szeretek ellene játszani, mert nem túl jó” – mondja Murphy a videóban. “De a természetes kérdés az, hogy mennyire nem-nagyon-jó?”A sakkozási programok elleni tesztelés bizonyítja, hogy igen, nagy rendszerességgel veszít — mint minden egyes alkalommal.”
aztán nekilátott más rossz sakkjáték algoritmusok felépítésének, hogy összehasonlíthassa azok relatív teljesítményét…
az egyik előnyben részesítette a darabjait a fehér négyzetekre, amikor fehéret játszik, és a fekete négyzetekre, amikor feketét játszik. (Az ellenfél? Olyan algoritmus, amely inkább ellentétes színű négyzetekre helyezte a darabjait.) A végén mindketten nagyon rosszul játszottak. “Van egy preferenciájuk, de ennek valójában nincs köze a győzelemhez.”Valójában mindkettő csak egy kicsit rosszabb, mint az algoritmus, amely véletlenszerűen választja meg a mozdulatait.
ha megtalálja a bonyolult 42 perces videómat 30 furcsa sakk algoritmusok versenyeznek a bolondok versenyén annak érdekében, hogy felmérjem a sakkot játszó programomat anélkül, hogy tudnám, milyen darabok vannak a táblán, hogy unalmasak legyenek, akkor az azért van, mert nem érted a művészetet:https://t.co/DkaEBGrwAf
— Tom 7 (@tom7) július 15, 2019
két algoritmust is elnevezett “Huddle” és “Swarm” – amelyben az egyik automatizált játékos olyan mozdulatokat keres, amelyek darabjait a saját királyához közel tartják, míg a másik olyan mozdulatokat keres, amelyek darabjait az ellenfél királya közelében helyezik el. Ez néha oda vezet, hogy Huddle királyát arra kényszerítik, hogy kövesse saját gyalogjait az egész táblán, ahol legalább néhány esetben a gyalogja véletlenül erősebb darabokra lépett elő, és akaratlanul is ellenőrizte az ellenfél királyát.
de gyakrabban fordítva működik. “Ha előnyben részesíted az ellenfél megtámadását, akkor néha véletlenül mattot adsz neki.”A videóban Murphy elárulja, hogy a rossz Sakk algoritmusok között ez meglepően nem olyan rossz. “A” Swarm “valójában sokkal jobb, mint a “Random Move”.”
és még egy sikeres stratégia egy olyan algoritmus, amely négyféle mozgást rangsorol (ebben a sorrendben): sakk-matt, ellenőrzés, egy darab elfogása vagy az ellenfél területére tolása.
de vannak más szörnyű ötletek is — például egy algoritmus, amely arra törekszik, hogy tükrözze ellenfele darabjait, vagy az összes darabját a tábla másik oldalára mozgassa. Az egyik algoritmus egyszerűen kiválasztja azt a lépést, amelyik előbb lép, ábécé sorrendben.
és van egy másik algoritmus, ahol minden mozdulatot a lehetséges mozdulatok listájából választanak ki — a döntéseket a pi számjegyei önkényesen diktálják …
túlélés Sakkföldön
de végül a legbonyolultabb algoritmusa egy kérdéssel kezdődött: melyik egyetlen sakkfigura valószínűleg “túléli” — hogy a játék végéig a táblán maradjon, és győztesen kerüljön ki az összes többi sakkfigurával? Kötelességtudóan vizsgálja a választ, Murphy látogatást tett a free / libre chess oldalon LiChess.org (amely ma már több mint egymillió játékot lát naponta). Játékokat is kínál letöltésre — így Murphy letöltötte mind az 506 000 416-ot.
összefoglalta az eredményeket egy “Survival in Chessland” című cikkben, amely elmagyarázza módszertanát. Murphy 2018 novemberéig letöltötte az összes teljes játékot-bár az azóta eltelt nyolc hónapban nyilvánvalóan további 200 millió vált elérhetővé. Még a novemberi fogása is óriási 875 GB-os sakkjátékot jelentett, “tehát ezek feldolgozása némi figyelmet fordított a hatékonyságra és a párhuzamosságra” – mondja Murphy a videóban.
“szerencsére van egy számítógépem, amely csak obszcén számú magot és valóban túlzott RAM-ot tartalmaz, tehát ezt fel kell használni valamire.”
mennyire obszcén? Egy e-mailben leírja “ingyenes” otthoni rendszerét, egy 32 magos AMD ThreadRipper 2990wx-et. A többszálú C++ programok néhány órán át történő futtatása elegendő volt a teljes adatkészlet átlapolásához. “Azt hiszem, az emberek alábecsülik, hogy mit lehet hatékonyan csinálni egyetlen géppel!”
“a munka nagyon egyszerű: Elemezem a PGN-t (amely leírja a játékot), majd végrehajtom a mozdulatokat a játékban, nyomon követve az egyes darabok sorsát, majd összegezem az egyes sorsok számát…”
“alapvetően az összes kódot a semmiből írtam, mert ez szórakoztatóbb, mint mások kódjának működése. :)”
Murphy” túlélhetőség ” elemzése valóban gyönyörű vizualizációkat hozott létre az adatokról, bemutatva a túlélés valószínűségét minden sakkfiguránál a 64 négyzet mindegyikén (a színek jelzik annak valószínűségét, hogy a játék végén ezen a téren tartózkodnak.)
és ez még több rossz sakkozási algoritmushoz vezetett. Először is, ott van az, amely csak mozgatja a darabokat azokra a négyzetekre, ahol statisztikailag nagyobb valószínűséggel élnek túl. Vagy egyszerűen a négyzetekre, ahol valószínűleg a játék végén vannak. És más algoritmusok pontosan az ellenkezőjét teszik — a darabokat olyan négyzetekre mozgatják, ahol a legkevésbé valószínű, hogy túlélik (vagy végül). Két algoritmus kiszámítja, hogy melyik négyzetnek van a legmagasabb túlélési aránya (szemben a rögzítési sebességgel) minden négyzeten egy darab esetében, az egyik algoritmus a legmagasabb arányt keresi a túléléshez — a “fatalista” algoritmus pedig a legalacsonyabb ilyen arányt keresi.
“furcsa módon ezeknek a stratégiáknak a legjobb nyerési esélyei vannak.”
végül úgy döntött, hogy összehasonlítja őket a Stockfish sakkmotorral több szinten (beleértve egy speciális algoritmust, ahol kénytelen játszani a legkevésbé ígéretes mozdulatát). “Az eredményeket nézve nem meglepő, hogy ez a legrosszabb stratégia, és szinte mindenki ellen veszít.”
de emlékszel Tom eredeti “bekötött szemmel” algoritmusára, amely nem tudta, melyik darab foglal el egy négyzetet (vagy akár annak színét)? Úgy döntött, hogy egy neurális hálózattal bővíti, amely gépi tanulást hajtott végre — a lichess játékaiban elérhető több milliárd pozíció felhasználásával.org. Most már képes volt pontosan megjósolni a tényleges darabokat minden helyzetben 100% – os pontossággal … az idő körülbelül egyötödével. És még akkor is, ha ez rossz, csak helytelenül kitalálta átlagosan 3,22 darabot minden pozícióra.
és ez lesz az ugrópontja még vad számítások. Egy bizonyos ponton arra a következtetésre jut, hogy az adatbázisukban szereplő összes játék végül 21 553 382 902 egyedi pozíción halad át. Az 204gb segítségével mindent tárolhat-a következő lépéssel együtt -, de van egy másik érdekes statisztika. A pozíciók óriási 76% – a pontosan egyszer történt. “Tehát ezek sok helyet foglalnak el, és nem nagyon hasznosak a játékhoz, mert nagyon valószínűtlen, hogy valaha is látom őket.”Eldobva ezeket az egyszeri pozíciókat, minden más lehetséges játékpozíció körülbelül 500 MB memóriával tárolható. Ez könnyen átalakítható algoritmussá, amely a legnépszerűbb mozdulatot játssza le minden olyan helyzetben, amellyel találkozik (miközben véletlenszerű mozdulattal cserél, ha véletlenül csapdába esik egy egyedi helyzetben).
de akkor van egy egyszerű trükk a veréshez. “Amint egy kicsit furcsa mozdulatot teszek, csak véletlenszerűen kezd játszani. Aztán nagyon könnyű legyőzni.”
az utolsó kísérlet a Stockfish motor különféle “hígításait” foglalja magában — amelyben az előnyben részesített mozdulatot véletlenszerűen kiválasztott mozdulat váltja fel az idő X százalékában.”
“valójában felmérhetjük, hogy egy játékos mennyire jó most, ha közvetlenül összehasonlítjuk a tőkehal specifikus hígításával…”
miután Murphy bonyolult sakkjáték-algoritmusait kötelességtudóan tesztelték, összefoglalta az eredményeket egy hatalmas táblázatban, és diadalmasan zárta videóját azzal, hogy bejelentette, hogy végre készen áll más érdekek követésére.
“most jön a következő projekt, amely megtanítja ezt a kutyát sakkozni.”
- mi történik, ha a gépi tanulás olyan válaszokhoz vezeti az emberiséget, amelyeket nem értünk?
- bemutatom Sophie-t, a tésztakészítő robotot.
- 15 év után a kutatók egy mesterséges karot mutatnak be, amely képes érezni.