umělá hloupost: algoritmy jednoho inženýra Google pro špatné hraní šachů

co se stane, když použijeme nejmodernější moderní technologie na starodávnou šachovou hru? A co se stane, když znuděný geek s přebytkem výpočetního výkonu provádí své vlastní podivné domácí experimenty ve hře?

Tento rok se Pensylvánský softwarový inženýr, který si říká Tom Murphy VII, rozhodl vytvořit několik směšně špatných algoritmů pro hraní šachů využívajících vše od strojového učení a neuronových sítí až po bezdůvodné množství cyklů CPU — a pak postavil špatné algoritmy proti sobě, aby vytvořil “ turnaj bláznů.“

„je to moje představa zábavy…“ říká Murphy v humorném videu popisujícím experimenty.

první pohyby

Murphy má mozkovou sílu, aby ji vytáhl. Říká nám, že v roce 2007 obhájil titul Ph.D. v Carnegie Mellon-což byl stejný rok, kdy studenti začali pořádat výroční konferenci SIGBOVIK v den blázna. Sponzorováno „Asociací pro výpočetní kacířství,“ byla to jakási satirická zájmová skupina věnovaná fiktivnímu výzkumníkovi jménem „Harry Quizmaster Bovik,“ a včetně výzvy k praštěným dokumentům na témata jako “ umělá hloupost.“

za posledních 11 let byl Murphy vedoucím softwarovým inženýrem společnosti Google (v jejích kancelářích v Pittsburghu). Ale letos se rozhodl vrátit se znovu na aprílovou konferenci-a znovu, přispěl svým vtipným výzkumem.

Murphy se hrdě chlubí, že některé z jeho minulých prezentací zahrnovaly směšná vyšetřování ,která byla „nerozeznatelná od“ skutečného „výzkumu (například první úroveň Super Mario Bros. je snadná s lexikografickými objednávkami a cestování v čase má asi 20 citací v „skutečném“ akademickém výzkumu).

ale to byl rok, kdy Murphy obrátil svou pozornost k šachu.

nechte hry začít

v Murphyho počáteční hře jsou lidští hráči zavázáni očima a nutí je, aby si pamatovali, kde jsou kousky. Ale jaký je ekvivalent pro počítač? Říkat to, kde jsou umístěny kusy, ale ne, které kusy jsou (nebo dokonce jakou barvu)…

tom Murphy VII chess robot

počítač by samozřejmě neměl být vybaven pohyby vedoucími k pozici. Ani by nevěděl, na koho je řada. Ano, existuje možnost, že král počítače je pod kontrolou-v tom okamžiku je téměř každý pohyb nezákonný, kromě pohybu, který vede vašeho krále do bezpečí. Ale obejít to, Tom vytvořil program, který generuje seznam možných tahů, seřazené podle preferencí-ze kterého bude vybrán první legální krok.

„rád proti tomu hraju, protože to není moc dobré,“ říká Murphy ve videu. „Ale přirozenou otázkou je, jak to není moc dobré?“Testování proti šachovým programům dokazuje, že ano, ztrácí s velkou pravidelností — jako v, „pokaždé.“

pak se rozhodl postavit další špatné algoritmy pro hraní šachů, aby mohl porovnat jejich relativní výkon …

jeden měl přednost pro umístění svých figurek na bílých čtvercích, když hraje na bílé, a na černých čtvercích, když hraje na černé. (Jeho soupeř? Algoritmus, který dává přednost umístění jeho kousky na opačně barevné čtverce.) Nakonec oba hráli dost špatně. „Mají přednost, ale ve skutečnosti to nemá nic společného s vítězstvím.“Ve skutečnosti jsou oba jen o něco horší než algoritmus, který náhodně vybírá své pohyby.

pokud najdete Moje složité 42min video o 30 podivné šachové algoritmy soutěží v turnaji bláznů, aby posoudily můj program, který hraje šachy, aniž by věděly, jaké kousky jsou na desce nudné, pak je to proto, že nerozumíte umění:https://t.co/DkaEBGrwAf

— Tom 7 (@tom7) červenec 15, 2019

existovaly také dva algoritmy, které pojmenoval „Huddle“ a „Swarm“ – ve kterých jeden automatizovaný hráč hledá pohyby, které udržují své kousky blízko svého vlastního krále, zatímco druhý hledá pohyby, které umisťují své kousky poblíž soupeřova krále. To někdy vede k tomu, že je král Huddle nucen sledovat své vlastní pěšce napříč deskou, přičemž alespoň v několika případech jeho pěšec náhodně povýšil na silnější kousky a neúmyslně zkontroloval nepřátelského krále.

ale častěji to funguje opačně. „Pokud máte přednost útoku na soupeře, občas to omylem zaškrtnete.““Ve videu Murphy odhaluje, že mezi špatnými šachovými algoritmy není tento překvapivě špatný. „“Roj“ je ve skutečnosti mnohem lepší než “ náhodný pohyb.'“

a další úspěšnou strategií je algoritmus, který upřednostňuje čtyři specifické druhy pohybu (v tomto pořadí): šach mat, zkontrolovat, zachytit kus nebo tlačit na území soupeře.

ale existují i jiné hrozné myšlenky-jako algoritmus, který se snaží zrcadlit své soupeřovy kousky, nebo přesunout všechny své kousky na druhou stranu desky. Jeden algoritmus jednoduše vybere podle toho, který krok je na prvním místě v abecedním pořadí.

a je tu další algoritmus, kde je každý tah vybrán ze seznamu možných tahů – s volbami diktovanými libovolně číslicemi pi …

přežití v Chesslandu

ale nakonec jeho nejpropracovanější algoritmus začal otázkou: která jednotlivá šachová figurka je většinou pravděpodobné, že “ přežít — – zůstat na palubě až do konce hry, a objevující se vítězný se všemi svými kolegy šachových figurek? Murphy, který svědomitě zkoumal odpověď, navštívil šachový web zdarma / libre LiChess.org (který nyní vidí více než milion her denně). Nabízí také hry ke stažení-takže Murphy stáhl všech 506 000 416 z nich.

Tom VII.

shrnul výsledky v článku nazvaném „přežití v Chesslandu“, který vysvětluje jeho metodologii. Murphy stáhl každou kompletní hru, kterou měli do listopadu 2018-i když dalších 200 milionů se zjevně stalo dostupnými za osm měsíců od té doby. Dokonce i jeho listopadový zátah představoval neuvěřitelných 875 GB šachových her, „takže jejich zpracování vyžadovalo určitou péči o efektivitu a paralelismus,“ říká Murphy ve videu.

“ naštěstí mám počítač s jen obscénním počtem jader a opravdu nadměrnou pamětí RAM, takže to musíte použít pro něco.“

Er, jak obscénní? V e-mailu popisuje svůj „bezplatný“ domácí systém, 32jádrový AMD ThreadRipper 2990WX. Spuštění vícevláknových programů C++ po dobu několika hodin stačilo k tomu, aby se protáhlo celou datovou sadou. „Myslím, že lidé podceňují, co můžete udělat efektivně s jedním strojem!“

AMD 2. Gen RYZEN threadripper 2990WX (přes Newegg) 19-113-541-V01

„práce je velmi jednoduchá: Analyzuji PGN (který popisuje hru), poté provedu pohyby ve hře, sleduji osud každého kusu a pak sečtu počty pro každý osud…“

„v podstatě jsem napsal celý kód od nuly, protože je to zábavnější než dostat kód jiných lidí do práce. :)“

Murphyho analýza „přežití“ vytvořila některé opravdu krásné vizualizace dat, ukazující pravděpodobnost přežití pro každou šachovou figurku na každém ze 64 čtverců (s barvami označujícími jejich pravděpodobnost, že budou na tomto čtverci na konci hry.)

a pak to vedlo k dalším špatným algoritmům hraní šachů. Za prvé, je tu ten, který jen přesune kousky do těch čtverců, kde je statisticky pravděpodobnější, že přežijí. Nebo jednoduše na náměstí, kde jsou s největší pravděpodobností na konci hry. A jiné algoritmy dělají přesný opak-přesouvají kusy na čtverce, kde je nejméně pravděpodobné, že přežijí(nebo skončí). Dva algoritmy vypočítají, který čtverec má nejvyšší míru přežití (versus míra zachycení) pro kus na každém čtverci, přičemž jeden algoritmus hledá nejvyšší poměr upřednostňující přežití – a“ fatalistický “ algoritmus hledá nejnižší takový poměr.

“ kupodivu má nejlepší šance na výhru těchto strategií.“

a nakonec se rozhodl porovnat je všechny s šachovým strojem Stockfish na několika úrovních (včetně speciálního algoritmu, kde je nucen hrát svůj nejméně slibný tah). „Při pohledu na výsledky není překvapením, že se jedná o celkově nejhorší strategii a dokáže ztratit téměř každého.“

ale pamatujete si Tomův původní algoritmus „se zavázanýma očima“, který nevěděl, který kus zabírá čtverec (nebo dokonce jeho barvu)? Rozhodl se jej rozšířit neuronovou sítí, která prováděla strojové učení-pomocí miliard pozic dostupných ve hrách od LiChess.organizace. Nyní byl schopen správně předpovědět skutečné kusy na každé pozici se 100% přesností … asi pětinu času. A i když je to špatně, je to jen nesprávně odhadl v průměru 3,22 kusů pro každou pozici.

Tom VII-strojové učení a šachové algoritmy

a to se stává skokovým bodem pro ještě divočejší výpočty. V určitém okamžiku odvodí, že všechny hry v jejich databázi nakonec projdou 21 553 382 902 jedinečnými pozicemi. S 204GB je můžete uložit všechny-spolu s dalším tahem – ale je tu další zajímavá statistika. Neuvěřitelných 76% pozic se objevilo přesně jednou. „Takže tyto zabírají spoustu místa a nejsou příliš užitečné pro hraní, protože je velmi nepravděpodobné, že je někdy uvidím.“Zahodit tyto jednorázové pozice, každá další možná herní pozice může být uložena s přibližně 500 MB paměti. To lze snadno převést na algoritmus, který hraje nejoblíbenější tah pro jakoukoli pozici, se kterou se setká (při výměně v náhodném tahu, pokud se stane, že se ocitne v pasti v jedinečné pozici).

ale pak je tu jeden snadný trik, jak ho porazit. „Jakmile udělám trochu divný tah, začne to hrát náhodně.“ A pak je velmi snadné porazit.“

závěrečný experiment zahrnuje různá „ředění“ motoru Stockfish-ve kterém je jeho preferovaný pohyb nahrazen náhodně zvoleným tahem x procent času.“

„můžeme skutečně posoudit, jak dobrý hráč je nyní porovnáním přímo se specifickým zředěním Stockfish…“

poté, co byly všechny Murphyho propracované šachové algoritmy poslušně testovány, shrnul výsledky do jedné masivní tabulky a triumfálně uzavřel své video oznámením, že je konečně připraven sledovat Jiné Zájmy.

“ nyní je na dalším projektu, který učí tohoto psa, jak hrát šachy.“

om Murphy VII hraje šachy proti psovi a robotovi

  • co se stane, když strojové učení vede lidstvo k odpovědím, kterým nerozumíme?
  • seznamte se s Sophie, robotem na výrobu nudlí.
  • po 15 letech vědci odhalují umělou ruku, která může cítit.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.