Jak postavit krabičkový stroj, neporazitelný v piškvorkách
MENACE — Machine Educable Noughts And Crosses Engine je super nápad na školní projekt!
Autorka: Eva Nečasová
MENACE — čili Machine Educable Noughts And Crosses Engine, vymyslel a sestavil v roce 1961 Donald Michie. 304 krabiček od sirek, které se dokáží naučit hrát piškvorky 3×3 tak, že je nelze porazit. Boží.
Struktura článku
O co jde
Jak to funguje
Jak MENACE sestavit
Další zdroje
O co jde
Říká se, že Donald Michie v roce 1961 původně sestavil MENACE, aby vyhrál sázku s kolegou. Nevěřícímu chtěl dokázat, že pomocí metody pokus omyl lze naučit 304 krabiček vítězit v piškorkách nad člověkem. Když byly krabičky sestavené, Michie s nimi odehrál během 16 hodin 220 her (uff). Postupně upravoval své strategie a MENACE se zdokonaloval ve hře. Po určité době se skutečně stal neporazitelným.
Původní MENACE (Zdroj: Experiments on the mechanization of game-learning, Donald Michie, 1961)
Průkopník umělé inteligence Donald Michie
MENACE je skvělou ukázkou principu tzv. posilovaného strojového učení. To je jedna z metod strojového učení, u které algoritmus opakovaně interaguje s prostředím a na základě odezvy upravuje své chování. Zní to poněkud krkolomně. Ale prakticky to znamená, že je „odměňován“ nebo „trestán“ za svá rozhodnutí a tím zlepšuje své strategie. Skvělým příkladem je program Alpha Zero, kterému vývojáři ukázali pravidla šachu, nechali ho opakovaně hrát proti sobě samému a na základě odezev (za výhru dostal Alpha Zero pozitivní odezvu, za prohru naopak negativní) si vybudoval strategie, díky kterým porazil šachové velmistry. (Více o strojovém učení si můžete přečíst v naší příručce Obecný úvod do umělé inteligence v kapitole Jak se umělá inteligence učí.)
Jak to funguje
Celý princip je překvapivě jednoduchý. Každá krabička reprezentuje jeden stav hry a v celém MENACE jsou obsaženy čtyři tahy (které hrají krabičky). Dohromady je tedy možných osm tahů.
Uvnitř krabiček jsou barevné korálky. Ty zas referují ke konkrétnímu políčku na hrací plošce.
Takto vypadá legenda:
Hru začíná MENACE. Otevřeme tedy první krabičku, vylosujeme korálek a dle legendy nakreslíme za MENACE tah. Takže pokud bychom vylosovali například tmavě modrý korálek, uděláme kolečko na pozici č. 3.
Pak hrajeme my. Nakreslíme křížek — pravděpodobně doprostřed. Dál budeme v rámci 3. tahu hledat následující stav hry mezi krabičkami:
Aby nemuselo být krabiček příliš mnoho, jsou redukovány pomocí zrcadlení nebo otočení. MENACE je jedno, zda je stav otočen o 90°, 180° nebo 270°, případně zrcadlen horizontálně či vertikálně. Důležité je ale mít na paměti, že když budete zakreslovat otočený nebo zrcadlený stav, je třeba úplně stejným způsobem otočit nebo zrcadlit legendu.
Pokračujeme dál, zakreslíme náš křížek a hledáme další stav v 5. a nakonec možná losujeme také 7. tah (hledat otočený, možná zrcadlený stav ve 183 krabičkách, je oříšek i pro ty trpělivější z nás), případně kreslíme náš osmý a dokončujeme hru.
Jak se ale MENACE učí?
Na začátku bylo zmíněno, že metoda posilovaného strojového učení algoritmus „odměňuje“ či „trestá“. Tady je to prováděno následovně: pokud ve hře MENACE prohraje, „potrestáme“ ho tak, že všechny vylosované korálky konkrétní barvy v konkrétních krabičkách odstraníme. Pokud MENACE vyhrál, naopak ho „odměníme“ přidáním stejných barev korálků (po 3 kusech) do konkrétních krabiček, ze kterých jsme losovali. Při remíze přidáváme jeden korálek. Tak se stane, že po určitém množství her přestávají být v krabičkách ty barvy korálků, které vedly k prohře. Naopak ty, které vedly k výhře, jsou násobeny.
MENACE v roce 2015 dle vzoru Donalda Michieho vyrobil také Mathew Scroggs a moc hezky o tom mluví zde:
Mimo krabičkové verze MENACE ale také naprogramoval jeho online verzi, se kterou si jde skvěle hrát. Můžete měnit různé parametry, například počet korálků, kterými krabičky odměníte, postavit MENACE proti MENACE a tak dále. Tuhle fantastickou věc najdete u něj na webu.
Hry mohou dopadnout čtyřmi způsoby: prohrajeme, vyhrajeme, nastane remíza nebo rezignace. Rezignace znamená, že v krabičce už nejsou korálky, že kterých bychom losovali. Pokud si vyzkoušíte Mathewovu online verzi, vpravo uvidíte, jak se během hraní mění poměry korálků v krabičkách. Úplně dole na stránce je také graf, který ukazuje nárust korálků v prvním tahu. Necháme-li za sebe hrát hráče typu „Perfect“, brzy jich začínají být v první krabičce stovky. Rozdíl je také, pokud zvolíme hráče „Perfect“ nebo „Random“. Čím lépe hráč hraje, tím dříve se MENACE stává neporazitelným.
Jak MENACE sestavit
Sestavit krabičky může být skvělý školní projekt. Navíc na nich můžete krásně ukazovat princip posilovaného strojového učení. Stejným způsobem se učí třeba také fascinující Agent57, který dokáže hrát 57 her z konzole Atari 2600 lépe než lidé. A to aniž by mu někdo předtím poradil, jak na to.
Co budete potřebovat:
— 305 krabiček od zápalek (tento typ)
— arch A4 samolepící etikety pro laserové nebo inkjetové tiskárny (např. tento typ)
— na etiketu natiskněte toto PDF
— lepidlo a lepenku
— korálky (ty z IKEA jsou levné)
Možná vás potěší (nebo také ne), že po vyprázdnění všech krabiček vám zbyde necelých 11 000 zápalek. 🙂
PDF se stavy, které jste vytiskli na samolepící arch (aniž byste přizpůsobovali velikost PDF papíru v tiskárně), nařezejte na jednotlivé tahy. To znamená, že budete mít malý aršík s prvním a třetím tahem, pak druhý větší aršík s pátým tahem a největší aršík se sedmým tahem. V PDF je od sebe snadno rozlišíte — jednotlivé tahy končí černým čtvercem s počtem jednotlivých stavů.
Takto rozdělené tahy dle růžových tečkovaných čar nařezejte na jednotlivé stavy. Ty poté nalepte na jednotlivé bloky krabiček, které jste si předtím spojili lepidlem a obmotali lepenkou (aby se nerozpadly).
Z 305. krabičky dejte dohromady legendu:
Korálky
Do krabiček se nevkládají vždy všechny korálky, ale jen ty, které je v tahu ještě možné zahrát. Znamená to, že pokud plníte krabičku například ve třetím tahu, nevkládáte 9, ale pouze 7 korálků, protože 2 už byly zahrány. Vkládáte jen ty barvy, které zahrány nebyly.
Také je rozdíl v počtu vložených korálků v různých tazích. Z důvodu toho, že se první tahy hrají nejčastěji, vložte od každé barvy:
— v prvním tahu každá barva korálku 3×
— ve třetím tahu 2×
— v dalších tazích 1×
Tento remake MENACE sestavil žák 6. třídy ZŠ. Hodně štěstí!
Další zdroje
— MENACE lze hrát online
— Článek o MENACE na webu Mathewa Scroggse
— Návod na sestavení na blogu Mathewa Scroggse
— MENACE na Wiki
— Experiments on the mechanization of game-learning od Donalda Michieho
— Jak se MENACE učil během víkendu v Muzeu vědy v Manchesteru
— Historie umělé inteligence přehledně na časové ose
— Strojové učení jednoduše
AI dětem, z.s.
IČ: 17914582
Datovka: 4czjq6u
Číslo účtu: 2002446742/2010
Poptáváte vzdělávací akci či spolupráci?
Ozvěte se Kláře na: klara@aidetem.cz
Další kontakty naleznete v sekci Lidé.