Metoda “Monte Carlo”

Jako šachistu mě baví sledovat, jaké souvislosti a analogie existují mezi královskou hrou a oborem softwarového vývoje. Je jich poměrně dost, často jsou zajímavé a dneska bych chtěl napsat o tom, jaké poučení si do SW vývoje můžeme odnést z metody používané šachovými motory zvané “Monte Carlo”.

Když se programuje šachový motor, tedy kus softwaru, jehož cílem je hledat a nacházet co nejlepší tahy, dá se na to jít různě. Základní cesta, které se drží více méně všechny motory na světě, je snažit se co nejvíce napodobit lidský mozek. Motory se tedy snaží předvídat tahy soupeře, zakódovává se do nich co nejvíce taktických i strategických znalostí, autoři se je snaží naučit pravidla vedení útoku nebo naopak obrany a podobně. Kvalita jednotlivých motorů se pak liší tím, jak kvalitně je autoři dokázali šachy “naučit”.

Existují však pozice, které počítačům dlouhodobě dělají nebo dělaly problém, protože na ně běžné algoritmy nefungují. Například pozice s krajním pěšcem a střelcem, který nekontroluje pole proměny – pokud je král bránící strany na poli proměny, je partie remíza, ačkoliv počítač vidí mohutnou výhodu silnější strany. Počítač tak bude spokojeně tahat tam a zpátky a udržovat materiální výhodu a nedojde mu, že se vlastně pozice nijak neposouvá ke konečnému cíli, tedy k matu.

Podobných pozic, nebo lépe řečeno typů pozic, je mnoho, a je řada způsobů, jak se s nimi vypořádat. Autoři motorů tak například do kódu začali přidávat detekci speciálních případů, kde běžné hodnocení selhává (a téměř každý motor tak dnes “ví”, že pěšec plus špatný střelec je remíza). Nebo se začaly sestavovat databáze koncovek, kdy se do určitého počtu kamenů na šachovnici přesně ví, že taková a maková pozice je při nejpřesnější hře obou stran např. mat 38. tahem (nebo remíza). (Takové databáze jsou ale reálné jen pro několik málo kamenů, dnes cca 6 včetně králů, a už i to znamená mnoho gigabajtů dat. Každá figurka navíc přidává exponenciálně mnoho možností navíc, což je důvod, proč se nepočítá s tím, že by se šachy za našeho života “vyřešily”.)

Jednou z nápaditějších metod, jak se popasovat s problematickými typy pozic, je tzv. “Monte Carlo”. Spočívá v tom, že se motor nesnaží jít na pozici “chytře”, ale prostě sehraje mnoho velmi rychlých a klidně nekvalitních partií a na konci se podívá na statistiku výsledků. Pokud mu například v pozici s krajním pěšcem a špatným střelcem jeho ohodnocovací algoritmus říká, že má bezpečnou převahu k výhře, ale tisíc rychlých partií z tisíce skončí remízou (např. kvůli padesátitahovému pravidlu nebo patu), usoudí motor, že je asi pozice skutečně remízová.

A jak to souvisí se světem softwarového vývoje? Když stojíme před problémem, jehož řešení není evidentní, jsme v podstatě v pozici šachového motoru, který se kouká na nějakou pozici a zpočátku netuší, jak pokračovat dál. A stejně jako motor má řadu různých algoritmů a heuristik, aby v nekonečné spleti variant našel tu relativně nejlepší, i my můžeme zkoušet a rozvíjet řadu různých přístupů k řešení problému.

Osobně jsem hodně velký příznivec důkladného přemýšlení, podobně jako to dělá šachový motor i lidský mozek po většinu partie. Snažím se přijít na to, proč třeba můj kód nefunguje, zjistit příčinu, jít do hloubky. Ale někdy to zkrátka nevede k žádoucím výsledkům – kód je třeba příliš spletitý, jsem už moc unavený, je málo času nebo jsem zkrátka na problém příliš hloupý. A v tu chvíli je vhodné přepnout. Vzdát se ambicí pokořit problém intelektuálně a prostě začít házet kostky, až to tam jednou padne. Včera jsem fixnul kód způsobem, který netuším, proč funguje, ani proč vyšel až desátý pokus z deseti, ale dokud testy procházejí, jsem spokojený.

Neříkám, že bych takto doporučoval k vývoji přistupovat vždy. Právě naopak, největší problém mám obvykle s kódem, který psal programátor, který nic než “Monte Carlo” nedělá. Ale pokud jste si vědomi toho, co děláte, a víte, jak důkladné testy vám kryjí záda, je metoda “pokus omyl” v některých speciálních případech možnost, jak se hnout z místa.

5 thoughts on “Metoda “Monte Carlo”
  1. Reading your blog gave me a lot of interesting informations , it deserves to go viral, you need some initial traffic only.
    How to get initial traffic??? Search for: masitsu’s effective method

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax