3.3.2 ŠPÁS a SUP - počítače z krabiček od zápalek

Účastník si zahraje zjednodušené piškvorky nebo šachy proti fyzickému počítači z krabiček od zápalek, který si na základě odehraných partií upravuje způsob hry tak, aby zvýšil svou šanci na výhru. Účastník tak uvidí svůj přímý vliv na proces strojového učení.

Existují počítačové programy, které se dokáží naučit komplexní úkol (např. hrát šachy) opakovanými pokusy o splnění (partie proti sobě samému, případně proti dalšímu hráči) a následným zpracováním zpětné vazby.

Provádění pokusů, pozorování, diskuze.

Metody a formy

• Komunikace v mateřském jazyce je rozvíjena:
  • nácvikem porozumění pravidel hry a diskuzí o pravidlech a fungování systému.
• Matematická schopnost a základní schopnosti v oblasti vědy a technologií jsou rozvíjeny:
  • pozorováním chování stroje při hře a analýzou vzorů chování systému,
  • zobecňováním pravidel chování stroje na celkový koncept chování umělé inteligence.

Jednotlivci hrají piškvorky 3×3 proti počítači vytvořenému z krabiček od zápalek, čím více zápasů odehrají, tím lépe dokáže počítač reagovat.

Program ukazuje žákům proces programového učení a umožňuje jim prostor na analytické myšlení.

Samotná demonstrace počítače z krabiček od zápalek a hra proti této primitivní umělé inteligenci navazuje na předchozí teorii týkající se umělé inteligence. Účastníci jsou seznámeni s primitivním zápalkovým počítačem a mají možnost si proti němu zahrát jednoduché 3×3 piškvorky. U toho sledují, jakým způsobem se tento počítač učí a funguje, a jak postupně dosahuje své výherní strategie.

Před uvedením je potřeba:

• nastavit ŠPÁS do startovní konfigurace (v případě SUPu je vhodné, aby měl za sebou cca 50 her),
• obsluhující organizátor by se měl naučit rychle orientovat ve výčtu jednotlivých herních situacích, aby nevznikaly prostoje při vyhodnocování (v případě ŠPÁSu je to poměrně snadné, pro SUP to vyžaduje trochu cviku, viz metodické poznámky),
• přichystat si do mističek dostatek korálků všech používaných barev pro ubírání a doplňování,
• dobře si promyslet vysvětlení celé aktivity, ideálně to předem vyzkoušet na nezávislé osobě,
• v případě sázení na výsledek připravit žetony.

Ideální je navázat aktivitu na povídání o umělé inteligenci. Organizátor vysvětlí pravidla, zodpoví případné dotazy a nechá účastníky, aby se pustili do hry. Samotná hra probíhá způsobem uvedeným níže, pokud má někdo z účastníků zájem, může si vyzkoušet obsluhu ŠPÁSu, případně SUPa.

Účastníci se střídají u počítačů a v deskovkovém kasinu, jsou instruováni, aby se po určité době zkoušeli k počítačům vracet a všímali si změn/ zlepšení strategie počítačů.

Vysvětlení zkratek:

• ŠPÁS = ŠestiPěšcový Adaptující se Stroj (originál HER - HexaPawn Educable Robot)
• SUP = Stroj Učící se Piškvorky (originál MENACE - Machine Educable Noughts And Crosses Engine)

Průběh hry:

1. (pokud začíná počítač, v opačném případě začínáme bodem 2.) Organizátor náhodně vylosuje korálek z krabičky, která označuje počáteční situaci (prázdná mřížka 3×3, popř. 3 pěšci proti 3 pěšcům na šachovnici 3×3) a vykoná tah. Krabičku nechá vytaženou a před ní nechá ležet vylosovaný korálek.
2. Hráč zahraje svůj tah a tím změní situaci na mřížce/šachovnici.
3. Organizátor najde krabičku, která odpovídá herní situaci, vylosuje korálek a vykoná tah. Opět nechá vytaženou krabičku a před ní ležet vylosovaný korálek.
4. Předchozí dva body se opakují, dokud hra neskončí vítězstvím hráče, počítače nebo remízou (zaplnění celé mřížky, pouze v případě piškvorků), nyní přichází ta nejdůležitější část týkající se vytažených korálků (= zahraných tahů):
   1. v případě prohry se krabičky vrátí zpět bez vytažených korálků, ty se dají bokem (tím pádem se sníží pravděpodobnost, že počítač v příští hře zahraje tyto stejné tahy, které vedly k prohře),
   2. v případě remízy (ta nemůže nastat při hře šesti pěšců) se zahrané korálky vrátí zpět do vytažených krabiček a přidá se k nim ještě jeden korálek stejné barvy (remízu bereme jako dobrý výsledek, přidáním dalších korálků zvýšíme pravděpodobnost, že remíza nastane znovu),
   3. v případě výhry se zahrané korálky vrátí zpět do vytažených krabiček a přidají se k nim ještě tři korálky stejné barvy (přidáním dalších korálků zvýšíme pravděpodobnost, že příště počítač vybere stejné tahy, které vedou k vítězství).

Pravidla piškvorek 3×3:

• standardní piškvorky, vítězí ten, kdo vytvoří řadu/sloupec/diagonálu ze svých třech symbolů,
• pokud se zaplní celé pole a nikdo nemá vítěznou trojici, je to remíza.

Pravidla hry šesti pěšců:

• začíná bílý hráč,
• pěšci se pohybují rovně dopředu o jedno pole, případně mohou brát jiného pěšce šikmo vpředu o jedno pole, stejně jako v šachách,
• na rozdíl od klasických šachů se pěšec nemůže posunout najednou o dvě pole ani na začátku,
• pokud hráč dojde se svým pěšcem na opačný konec šachovnice, vyhrává,
• pokud je hráč na tahu a nemůže zahrát žádný tah, prohrává.

Na závěr je vhodné svolat všechny účastníky a uzavřít blok věnovaný umělé inteligenci.

Po svolání všech se zeptáme, jaké můžou být způsoby, jak vytvořit umělou inteligenci, která zvládne hrát nějakou složitější hru, jedno z možných zakončení může vést k tomu, že existují tři stupně, jak taková inteligence může vypadat:

1. Čistě náhodná: (ŠPÁS a SUP úplně na začátku) program ví, jaké tahy může v dané situaci udělat a vybírá je zcela náhodně, k výhře nad takovým programem stačí danou hru aspoň trochu umět.
2. Znající herní zásady: (takový jsme tu dnes neměli) ideálním příkladem je šachový program, který ví, jakou hodnotu mají jednotlivé figury, jaké jsou herní zásady (vývin lehkých figur, uvést krále do bezpečí, věže na volné sloupce, …) a jak může dát mat. Program se pak při výběru tahu dívá na to, aby se po jeho zahrání dostal do co nejlepší pozice, podle zadaných kritérií. Nevýhoda tohoto přístupu je v tom, že daná pozice může vypadat dobře „na první pohled“, ale po několika tazích získá hráč svou výhodu zpět i s úroky (v šachách např. obětování figury, abych mohl dát v třetím tahu mat). Čím více tahů dopředu dokáže program promyslet, tím lépe, náročnost však roste exponenciálně.
   • Příklad: Pokud můžeme v dané šachové situaci zahrát 30 tahů, snadno vyhodnotíme 30 pozic, pokud se chceme dívat dva tahy dopředu, musíme se u každého podívat, co všechno nám může soupeř odpovědět. Tedy u každé ze třiceti situací zhodnotit 30 možných odpovědí soupeře, což je najednou 30*30 = 900 situací. Pro vyhodnocení všech možností pro pět následujících tahů už máme 24 300 000 kombinací, přičemž pro zkušené šachisty není promyšlení pěti tahů zas tak náročné. Není proto divu, že první počítač tohoto typu porazil nejlepšího lidského hráče své doby teprve v roce 1997 (necelých třicet let poté co dokázaly počítače zvládnout cestu na Měsíc).
3. Učící se: (ŠPÁS a SUP) program hraje zpočátku zcela náhodně, ale z každé hry se „poučí“ a upraví tak svůj další styl hry (odebereme/přidáme korálek), pro naše zápalkové počítače stačilo pár desítek her, ale šachové programy musejí takto odehrát miliony her, aby si „zažily“ co nejvíce situací. Když už jsou naučené, tak u konkrétní situace pak nemusí procházet všechny možnosti, ale jen ty, u kterých dříve zjistily, že pravděpodobně vedou k výhře, díky tomu můžou zkoumat více do hloubky. Dalo by se říct, že jde o jakousi strojovou intuici, schopnost poznat, nad čím má vůbec smysl „přemýšlet“, lidský hráč taky nezkoumá všechny tahy pěšcem, když ví, že mu soupeř hrozí matem.
   • I pro šachy bychom teoreticky mohli sestrojit počítač z krabiček od zápalek, potřebovali bychom však pro každou jednotlivou pozici jednu krabičku, všechny dohromady by pak zaplnili kouli, jejíž poloměr by odpovídal vzdálenosti mezi Sluncem a Uranem. Pokud bychom chtěli pokrýt všechny situace ve hře GO, nevešly by se nám krabičky do známého vesmíru.

Jednodušší a přehlednější je pracovat se ŠPÁSem, SUP může zůstat v záloze pro případ, že to bude účastníky hodně bavit. Vyhodnocování je popsáno níže, u ŠPÁSu je to podstatně jednodušší, ale ani SUPu se není třeba zaleknout.

Výroba ŠPÁSu a SUPu:

• Každé herní situaci odpovídá jedna krabička od zápalek, do každé krabičky se vloží korálky podle návodu níže.
• Před začátkem naplňování je dobré mít krabičky zbavené zápalek, očíslované a slepené (osvědčila se nám tavná pistole).
• Kreativitě se meze nekladou, lze použít i jiné schránky než krabičky od zápalek a celý výtvor případně ještě nějak vyzdobit, důležitá je ale možnost rychlého nalezení hledaného čísla, proto se nám osvědčilo mít (v případě SUPu) uspořádané krabičky po 10 sloupcích.

Nastavení ŠPÁSu:

• Situace 1-3: pro každý tah, který jde zahrát, se doplní 4 korálky podle barvy, která je v barevné tabulce.
• Situace 4-23: stejně jako 1-3, ale doplňují se pouze 2 korálky.
• Ostatní situace: stejným způsobem, ale doplňuje se jen jeden korálek.

Nastvení SUPu:

• Podle souboru sup-pocatecni-nastaveni.xlsx doplníme korálky, barvy určuje barevná tabulka v souboru sup-situace-a-barvy.xlsx, pokud na daném políčku není žádné číslo, žádný korálek tam nedáváme, a to proto, že daný tah je symetrický s jiným tahem, viz další odstavec.

Vyhodnocování SUPu aneb jak se vypořádat se symetrií:

• U piškvorek 3×3 existuje přes 1200 situací, které mohou nastat pro bílého hráče, abychom nemuseli vyrábět 1200 krabiček, ale stačilo nám 300, díváme se na situace, které se liší jen tím, jak jsou otočené/překlopené, jako na stejné (pokud je na herním poli pouze jedno kolečko a nic víc, je jedno, jestli je vlevo dole nebo vpravo nahoře). Podrobněji je tento přístup vysvětlený v článku níže.
• Při hledání dané herní situace je potřeba ji překlopit/otočit tak, aby „co nejvíce koleček a křížků bylo vlevo dole“, níže uvedená tabulka označuje, jakou „prioritu“ mají jednotlivá pole, při hledání se díváme střídavě na kolečko (tím začínáme) a na křížek, více napoví příklad níže.

Příklad:

• máme situaci (pomlčka značí prázdné pole):

• a vyhodnocujeme:
  • hledáme kolečko na co nejnižší pozici, kolečko je uprostřed, tam není třeba rotovat ani překlápět
  • teď se díváme, jestli můžeme situaci otočit tak, aby byl křížek na pozici 1, to můžeme, dostaneme:

• pokračujeme ve vyhodnocování:
  • opět se díváme na kolečko, můžeme ho nějak dostat do pozice 2, aby zůstal křížek v pozici 1?
  • to už nejde, ale můžeme ho dostat do pozice 3:

• a je hotovo, zbývající křížek je v pozici 2, takže už se na nižší pozici překlopit nedá.

Podle popisu to vypadá velmi složitě, ale po zažití a pochopení lze pracovat rychle a intuitivně.

Podle systému „vlevo dole“ jsou seřazeny herní situace i v dokumentu, např. pro dvě kolečka a dva křížky máme:

• napřed kolečko: 0, křížek: 1, kolečko: 2, křížek: 3
• pak kolečko: 0, křížek: 1, kolečko: 2, křížek: 4 … 8
• pak teprve kolečko: 0, křížek: 1, kolečko: 3, křížek 2 (potom 4-8)
• atd.

Aktivita v jednu chvíli zabaví jen jednoho hráče a pár pozorovatelů/čekajících hráčů (v případě zájmu lze šikovnému účastníkovi svěřit obsluhu počítače) a plyne poměrně pomalu, je proto dobré ji zařadit v rámci bloku, kdy si mohou účastníci vybrat z více aktivit, například propojit s deskovými hrami a vytvořit tak několik stanovišť, na kterých se mohou žáci střídat.

• http://chalkdustmagazine.com/features/menace-machine-educable-noughts-crosses-engine/
• https://www.mscroggs.co.uk/blog/52

Obsahové přílohy