Vladan Majerech - domácí stránka

Last Modified: 15.2.2026

Valid HTML 4.01 Strict

Index

kontakt, zápočty, zkoušky, rozvrh, skripta, TeX/METAFONTware, Články k dynamickým datovým strukturám, Analýza hry Quarto, Důchodová reforma, Šifrovací hry, Hádanky, Arimaa

Kontakt

Termín konzultace je nejlépe dohodnout předem e-mailem jmeno.prijmeni@mff.cuni.cz(subj:Konzultace) - odpovím jak bude v mých silách.
Kde mne najdete?
Česká republika, Praha, budova MFF UK Malostranské náměstí 24, 3. patro číslo dveří 302.

Zápočty

NTIN061 Algoritmy a datové struktury II
NTIN090 Základy složitosti a vyčíslitelnosti

NTIN060 Algoritmy a datové struktury
NTIN071 Automaty a gramatiky

Zkoušky

NTIN067 Datové struktury 2
Dynamické grafové datové struktury

Termín(y) se koná(ají) na základě dohody e-mailem.

Rozvrh

Pondělí14:00-15:30 S7cvičím"Automaty a gramatiky NTIN071"
Pondělí17:20-18:50 S6cvičím"Automaty a gramatiky NTIN071"
Čtvrtek15:40-17:10 N4cvičím"Algoritmy a datové struktury 1 NTIN060"

Skripta

"Úvod do složitosti a NP-úplnosti", "Složitost a NP-úplnost" již dlouho nedoznala změn.
Psaní skript k přednášce "Dynamické datové struktury" jsem pozastavil, protože vzhledem k odbornosti tématu je český text nepotřebný, anglických článků je mnoho a obor se stále ještě rozvíjí. Články mohu zapůjčit.
Psal jsem "Povídání o datových strukturách", které se mělo s původně zamýšleným obsahem dynamických datových struktur překrývat. Sudá nebo lichá?
Slovníček "Vnitřnosti TeXu" je napsán do konce expand procesoru.
V září 2008 obhájila (pod mým vedením) rešeršní diplomovou práci koncipovanou jako výukový materiál pro „Testování software“ Anna Borovcová.

TeX/METAFONTware

Jako obdivovatel a intenzivní uživatel TeXu, a v poslední době i META(FONT/POST)u čas od času vytvářím (aspoň spoluvytvářím) nějaké pomůcky pro pohodlnější práci s těmito programy. Jednou z těchto pomůcek je mnou v roce 1994 vytvořené TeXmenu. Druhou je METAFONT-editor vytvořený Alešem Vanclem.

Jako zajímavé cvičení z TeXu a trochu taky z algebry a teorie kódování bylo vytvoření makra pro sazbu QR kódů.

Dynamické datové struktury

Kopie veřejně přístupných článků týkajících se dynamických datových struktur najdete u Martina Mareše v adresáři dga/papers.
U mne můžete najít články Mikkela Thorupa a spol. týkající se amortizovaně polylogaritmických datových struktur
Amortizované polylog datové struktury pro 1 a 2souvislost, 1souvislost s mazáním,
Obecná metoda vylepšující randomizované algoritmy založené na vzorkování.
Kromě toho zde můžete najít článek Moniky Henzinger (Rauch) Worst case datová struktura pro vrcholovou 2souvislost.

Quarto

Na semináři v Josefově Dole 1998 jsem se seznámil s matematickou hrou Quarto. Napadlo nás zkusit nalézt optimální strategii v této hře. První pokusy vedly k tomu, že jsme byli schopni hru prozkoumat do hloubky 7 (z 16). Zkusil jsem aplikovat různé techniky na urychlení výpočtu a podařilo se mi hru prozkoumat úplně. Hra je zajímavá hlavně obrovským množstvím symetrií, které umožnily tak výrazné prořezání prostoru konfigurací, že úloha již byla řešitelná.

Pravidla hry: Hra se hraje na čtverci 4x4, je k dispozici 2^4 figurek. (figurky jsou nízké/vysoké, bílé/černé, hranaté/kulaté, plné/duté ... od každého druhu jedna). Hru hrají dva hráči, kteří se střídají v tazích. Vždy jeden hráč určí figurku a druhý ji položí na desku. Vítězí hráč, kterému se podařilo vytvořit horizontální/verikální/diagonální čtveřici figurek, které jsou alespoň v jedné vlastnosti stejné. V případě, že se to nikomu nepodaří, končí hra remízou.

V adresáři ftp/quarto Naleznete příslušný program i výsledek 14 denního výpočtu.

Výsledkem analýzy je, že při správné hře obou hráčů končí hra remízou.

Variantou hry je hledat čtveřici i ve čtvercích 2x2 (sousední řádky a sloupce). Tuto variantu hry daný program nezkoumá, mám pocit, že pocet symetrii tím klesá na polovinu, a vzhledem k nárůstu rychlosti počítačů za posledních 5 let by neměl být problém upravit program a přepočítat výsledky i pro tuto variantu. Najde se zájemce?

Implementačně nejjednodušší je upravit program pro výpočet varianty hry, kde se čtveřice hledá i ve vrcholech libovolného obdélníku s horizontální a vertikální stranou (tytéž symetrie). Mám pocit, že neexistuje remizová pozice pro takováto pravidla hry.

Příprava podkladů pro rozhodnutí o důchodové reformě

V období duben 2004 - červen 2005 jsem se podílel na přípravě podkladů pro rozhodnutí o důchodové reformě. Více informací o výsledcích modelování se dozvíte zde.

Šifrovací hry

Byl jsem ukecán k účasti na šifrovací hře OSUD. Natolik se mi to zalíbilo, že jsem se účastnil i dalších her. Reportáž účastníka z těchto akcí přináším

Dnem2006 Svíčky2006 Tmou8(podzim2006)
Matrix3(2007) Bedna2007 Svíčky2007 Tmou9(podzim2007)
Matrix4(2008) Bedna2008 Svíčky2008 Tmou10(podzim2008)
Bedna2009 Svíčky2009 Tmou11(podzim2009)
Bedna2010 Svíčky2010 Tmou12(podzim 2010)
Bedna2012 Tmou14(podzim 2012)
PoTrati2013 Bedna2013 PoŠkole2013 Svíčky2013
PoŠkole2014
PoŠkole2015 Svíčky2015 Tmou17(Q)(podzim 2015)
PoŠkole2016 Svíčky2016
TmouXX(podzim 2018)
PoTrati2019
Svíčky2020
Bedna2022 Svíčky2022

(Kalendář šifrovacích her).

Pro výjezdní zasedání kateder ktiml a kdss jsem na 26.9.2019 organizoval teambuilding/šifrovačku.

Malá šifrovací pomůcka a podklady pro dálkově pořádanou šifrovačku pro doktorandy (často zabývající se harmonickou analýzou) na Morávce (Krušné hory). Nehledejte originální šifry, zajímavá byla spíš technika nápovědy formou mnohonásobného výskytu principu šifry, vzhledem k tomu, že se nedaly očekávat velké zkušenosti s šifrovačkama. Autoři šifrovaček Dnem, Matrix a hlavně Haluz určitě znovupoužití principu šifry prominou. Ukázalo se, že

Malá šifrovačka se v roce 2009 zopakovala. Posílal jsem mentiony co to šlo, ale hra která měla končit kolem 19h se protáhla až do 23h 30m. Museli jsme se uchýlit k předložení alternativní startovní šifry protože „typografické stegano“ se ukázalo být těžkým.
P.S.: Pro rok 2009. Když píšu že v anglické gramatice nemáte hledat šifru, myslím to vážně.
P.P.S: Každá šifra ukrývá aspoň 3 tajenky (dvě ukrývají dokonce 4).
P.P.P.S.: Naprosto nechápu, že se nikdo nezamyslel nad tím tiskovým zrcadlem.
4P.S: Pokud byste si tiskli zadání, použijte ghostview. Pokusy s Acrobatem nedávaly dobré výsledky.
5P.S: Kdybych to dělal teď, asi bych i před ROBINem odřádkoval. Ne. To by bylo extrémně snadné!
6P.S: Očekávám bezprostřední dojmy na e-mailu. Ne že to budete sepisovat rok :)

Hádanky

Hádanky považuji za stěžejní „médium“ pro rozvoj matematiky. Jsem přesvědčen že na mé matematické/informatické vzdělání mělo řešení hádanek přinejmenším tak velký vliv, jako celý školský systém. Nebavím se o dětských hádankách typu „leze, leze po železe, ...“, ale o hádankách, které ač mají triviální formulace, nejsou rozumě řešitelné bez zavádění vlastní nové terminologie, případně dobře zdůvodňují, proč k zavedení takové terminologie vůbec došlo ... MMO

Mé oblíbené hádankářské fórum je Wu forum a nejraději mám ty hádanky, co ještě nemám vyřešené ... „n vězňů a k-stavový přepínač“ (známý především pro 100 vězňů a „žárovku“, kde pravděpodobně držím světový rekord ... strategii s průměrem kolem 3430, 3390 3370 návštěv). K oblíbeným patří i hádanky, s řešením typu heuréka, které mi daly hodně zabrat a většina mých kamarádů matematiků je ještě nemá vyřešené. Příkladem je varianta „vězňů s čepičkami“, kteří opouštějí vězení, pokud alespoň jeden z nich oznamí číslo ze své čepičky. (Pro n-vězňů věznitel vytvoří seznam n přirozených čísel z intervalu 1 až n, a i-tému vězni pošle seznam upravený tak, že na místě i-tého čísla je volné místo. Vězni mu nezávisle na ostatních seznamy vrátí s doplněným i-tým číslem a pokud se některý s  věznitelovým shoduje, vězni vítězí. Otázkou je, jakou strategii si mají vězni předem domluvit, aby zvítězili.)

Na daném fóru je spousty hádanek z oblastí, kde naprosto tápu. Příkladem jsou různé hádanky o trojúhelnících s celočíselnými stranami, které vedly k rozvoji teorie eliptických křivek. Své si zde najde každý zvídavý človíček kterému anglický jazyk nebrání v chápání jednoduchého textu.

Zajímavé úlohy (zvláště pak seriály) najdete taky na hacker.org. Stále mne ještě pár úloh čeká.

Jednodušší hádanky poskytujeme středoškolským studentům ve „studentském časopise“ M&M.

Myslíte, že je možno implmentovat Fibonacciho haldy aniž byste potřebovali místo na ukazatele ke kořeni?
Ne! Dostanete strukturu se stejnou asymptotickou složitostí, ale budou to Padovan haldy. Vypadá to, že jsem první, kdo tyto haldy popsal. Prezentaci přikládám v plné verzi česky a anglicky a ve zkratce česky a anglicky (archiv).

Když už jsem se věnoval haldám, dočetl jsem se o worst case verzi hald s DecreaseKey rozhraním. Myslím, že jsem vylepšil dosud nejlepší verze těchto struktur (daleko více si cením již získaných informací první verze, velmi redukuji overhead druhá verze). Mám pocit, že druhá verze by měla být efektivnější než klasické (amortizované) Fibonacciho haldy.

Krátký článek srovnávající rychle rostoucí funkce Zaneprázdněný bobr a Ackermanova funkce nechávám v této sekci. Stejně tak kompilát o rubikově kostce a povídání o dvou jejich modifikacích sun a puppet.

Life

Zaujalo mne, že si dal někdo práci implementovat digitální hodiny ve hře Life. Nelíbilo se mi, že segmenty spínají zcela nezávisle, což brání rychlejšímu taktu hodin. Synchronizaci spínání segmentů jednotlivých číslic jsem vylepšil a hodiny jsem pustil dvakrát rychleji. Taky jsem zmenšil překladové tabulky zapínání/vypínání jednotlivých segmentů a nahradil je přepínáním. Hodiny jsem dále synchronizoval tak, aby i jednotlivé číslice překlápěly současně, a v intervalech neovlivňovaných vzdáleností v překladové tabulce. Opravil jsem taky bug vzniklý urychlením hodin, kdy přepnutí 0 na posledním místě nestíhalo správně filtrovat přepínač PM a nejvyšší hodiny. Rychlejší hodiny by vyžadovaly zmenšení displeje.

No a implementoval jsem i menší, ještě dvakrát rychlejší hodinky. Dělal jsem je zcela od začátku, nejprve jsem zúžil překladové tabulky na polovic, pak jsem využil sudosti počtu stavů každé "číslice" takže jsem redukoval šířku stavového automatu pro každou "číslici" na polovinu, což krásně zapasovalo do polovičních překladových tabulek. Zcela jsem zrušil synchronizaci přepínání stavů původního řešení. Místo toho jsem zvolil spouštění stavů opožděné o to, o kolik kratší trajektorie následuje za stavem v překladové tabulce. Proto nebylo potřeba použít individuální opožďovací bludiště jednotlivých stavů před překladovou tabulkou. To umožnilo synchronizovat přepínání číslic v polovičním čase. Později se ukázalo, že stavy pro nejrychlejší číslici se v dané frekvenci nestihnou resetovat a každé páté přepnutí číslice jeden takt vynechávalo. Nezbylo než rozdvojit stavový automat. Kompaktní část se stará o počítání do 5 a zajišťuje reset automatu. Velká část po resetu postupně vysílá 5(×2) signálů do překladové tabulky. Pak už šlo jen o to, vytvořit zobrazovací část. Rozhodl jsem se vynechat pauzu mezi přepínáním, a radši vytvořit největší segmenty, které se v daném čase ještě stihnou přepnout. Cílem bylo vytvořit plně synchronizované segmenty. Vzhledem k tomu, že signály po pravé straně běží v jiné fázi než po levé, není možné řetězy LWSS udržet ve stejné fázi a ve stejné vzdálenosti. Přesto se podařilo odchýlit od symetrie o jediný pixel. Co se týče přepínání segmentů, zvolil jsem nejrychlejší možnou trajektorii k dolnímu segmentu. Ostatní trajektorie jsem prodloužil tak, aby přepínání segmentů bylo synchronizováno v rámci každé "číslice". Tytéž trajektorie byly použity pro všechny "číslice". (Přepínání mezi trajektorií C/2 LWSS a C/4 glideru umožnily poměrně pohodlné ladění). Po synchronizaci segmentů číslic v rámci "číslic" bylo potřeba ještě sesynchronizovat číslice navzájem. Vyšší řády musí být opožděny ve stavovém automatu, nezbývá proto pro nižší řády počkat před překladovými tabulkami. Rezignoval jsem na nekřížení "drátů" v rámci zpožďovacího bludiště (dostatečné zpoždění v úzkých koridorech by vyžadovalo extrémně dlouhou dráhu). Alternativou by mohlo být přenášet signál část úseku C/2 LWSS. Pak by šlo synchronizovat volbou délky urychlení. Poslední změnou byla implementace AM ukazatele, kde jsem využil přepínače generátoru C/2 LWSS objeveného během zužování překladových tabulek.
Tak jsem přeci jen nahradil brzdící labyrinty urychlením pomocí C/2 LWSS. Určitě by ještě bylo možno místo „kolizních reflektorů“ použít jiné reflektory s periodou dělící 60. Bylo by to čistší (méně živých buněk). Třeba si jěště nekdy pohraju s displejem do 23:59. Hotovo :). Po přednášce na MaM soustředění o Life (a těchto hodinách) jsem se ještě rozhodl hodiny nepatrně zmenšit (hotovo), nějaké úpravy dostal časový strojek (kompaktnější vypínání proudu LWSS, jiné přístupové cesty k logice týkající se nejvyšší cifry), podstatné pak bylo předělání zpomalovacích cest k segmentům displaye (více reflektorů, některé aktivní, ale na menší ploše), končící vždy vertikálním LWSS ve fázi umožňující jemné doladění posunu mod 4 volbou odlišné srážky s LWSS z překladové tabulky. Pro konstrukci hodin do 23:59 byl velice důležitý přechod z Gosper na Simkin technologii. Proud gliderů s periodou 120 místo 30 umožnil díky křížení tras dostatečně kompaktní logiku (režim hodin mezi 20:00 a 0:00 v šířce odpovídající malé překladové tabulce stojí za pozornost). Dále jsem se snažil nahradit Gosper logiku na dalších místech a zmenšit tak počet aktivních objektů.
Ano i k tomu došlo, syringe umožňuje přepínání z glideru na herschel, stabilní herschel obvody umí glidery namnožit a přesměrovat, jen tyto obvody potřebují velký prostor, takže jsem volil estetický kompromis mezi jejich velikostí a počtem aktivních prvků simkin/gosper technologií. Co se týče reflektorů, použil jsem snark, kdekoli bylo dost místa (a nebyl velký problém s „časotrajektorií“). Na půlení frekvence i nadále používám CC-semisnark, na čtvrcení frekvence pak quadrisnark. Pro stavový automat jsem použil stabilní swith používající stop and restart kde glider je zastaven ve formě block.
V další generaci hodin jsem použil na mnoha místech bistable switch který je jak malý, tak velice schopný.

Zaujal mne reverse caber-toser (RCT15), kde pomocí 3 skupin gliderů (dohromady 15 gliderů) umístěných do přesné velké vzdálenosti od sebe je možno zakódovat jakoukoli existující konstrukci v cGoL. Trik připomíná mouchu létající mezi proti sobě jedocími vlaky, kde podle toho, zda k odrazu od vlaku dochází na sudém či lichém metru trati systém vyšle jinou informaci. Vzájemná rychlost vlaku a mouchy je taková, že každý bit čísla vyjadřujícího počáteční vzdálenost určuje sudost metru trati jiné srážky. Zakódování poměrně malého testovacího vzoru vyžadovalo cca $1.5*10^6$ bitů (na konci je potřeba vše uklidit kromě požadovaného vzoru). Projekt v sobě skrýval spoustu zajímavých výzev a rozhodl jsem se zaměřit na optimalizaci řešení. Projekt nejprve mouchou generované bity vnímá jako „binární konstrukční rameno“, které je velice neefektivní v kontrolovaném vysílání gliderů. Tímto ramenem je vybudováno konstrukční rameno řízené „konečným automatem“, kde jednotlivé bity jsou interpretovány jako jednotlivé instrukce. Toto rameno připraví úklid v jednom rohu vzoru a vytvoří další konstrukční rameno, jehož instrukční sada umožňuje ještě mnohem efektivnější kódování pomalých salv gliderů. Toto rameno se postará o zbytek úklidu a vytvoření semínka finálního vzoru. Poslední úklidová loď je na konci úklidu zkonvertována na glider, který pomocí semínka probudí finální vzor.
Optimalizace se týkala všech tří konstrukční ramen a to jak metody kódování vstupu, tak zmenšením kolmogorovské složitosti příslušných interpretů (efektivnější konstrukce interpretrů efektivněji kódovaných salv). Stejně tak se optimalizace týkala plánu úklidu. Při té příležitosti jsme optimalizovali programy počítající pomalá salva vytvářející požadované vzory, ale i programy hledající semínka destrukce poslední konstrukční rameno i reflektory na cestě k němu zaniknou zásahem semínka gliderem. Optimalizace využívá toho, že posílané glidery jsou různě drahé v závislosti na tom, které konstrukční rameno je aktivní, takže neefektivní ramena přenechávají práci efektivnějším, kdykoli je to možné. Například obě vybudovaná konstrukčí ramena jsou vybudovány jen tak aby dokázaly produkovat glidery jedné barvy, na nich je, aby se dostavěly a rozšíily o používání barvy druhé.
Po všech představitelných optimalizacích se podařilo multiplikativní konstantu RCT15 zredukovat cca $2^{10^6}$ krát. Bohužel to znamená, že počet bitů vzálenosti zůstává řádově $0.5*10^6$. Pokud bychom chtěli najednou celý vzor zobrazit a použili bychom displej, kde pixely by měly rozměr Plankovy konstanty, byla by velikost vesmíru zcela zanedbatelná vůči velikosti displeje.
Napadlo mne, že by mohla být zajímavá prezentace RCT15 použít jej ke konstrukci digitálních hodin. Další verze digitálních hodin začíná semínkem (p8 periodické), kde zásah semínka ve správné lince v libovolné fázi mod 8 vede k nastartování hodin. Zbývá (do)vytvořit pomalé salvo, pomocí něhož by šlo semínko vytvořit ... a zařadit jej do RCT15 obálky.

Při optimalizaci RCT15 jsem byl upozorněn na několik let nedokončený projekt lodi, která by v nějaké své fázi měla výšku pouze 1 pixel. Projekt jsem dokončil (a pak i významně zoptimalizoval). Nakonec je to velice podobné RCT15. V první fázi se pomocí hoření blinkerů dvěmi směry vytvoří proudz proti sobě létajících mwss. Rychlost hoření se dá polohou blinkerů ovlivňovat a dají se tím určit polohy srážek mwss. Dvojice srážek vždy vytváří glider. Pomocí pomalého salva tak můžeme vybudovat čtecí mechanizmus, (podobný vlak jako u RCT15), který při čtení posouvá čtené blinkery. Čtené bity překládáme na binární konstrukční rameno. Pomocí něj je vybudováno kostrukční rameno s extrémní kompresí, které uklidí zbytky hoření blinkerů a vybuduje blinkery s příslušným posunem. Kromě toho vytvoří další konstrukční rameno, které se postará o úklid čtecího mechanismu i všech vytvořených konstrukčních ramen (samo je budováno se semínkem destrukce). Poslední úklidová loď (ničící periodický vzor čtecího mechanismu) je na konci zkonvertována na glider, který trefí semínko přechodu na nultou generaci (mod perioda lodi).
Na přehrávání je určitě dobré stáhnout si Golly. Jako chabou náhražku je možno použít online Javascript Conway’s Life Simulator.

Arimaa Challenge

Díky diplomce Tomáše Kozelka jsem zabředl do hry Arimaa. Hra je rozměrově podobná šachům, ale co se týče velikosti stromu hry, převyšuje go. Hra byla navržena tak, aby byla lehká pro lidi a odolávala hrubé síle počítačů. Následuje text, který postupně zastaral, snažil jsem se připisovat dospod aby byl vidět historický vývoj.

Zatím nejlepší lidé odolávají, zkusil jsem zjistit, jak na tom nejlepší lidé jsou a jak jsou na tom boti. Myslím že už mám dobrou představu o nedostatcích obou stran a věřím tomu, že vím, jak se získání Arimaa Challenge výrazně přiblížit. Více na Arimaa gameroom, MS 2010 a MS 2011. Obávám se, že nejsem sám, kdo tuší jak se k zdolání Arimaa Challenge přiblížit. Letošní (2011) vítěz WCC bot_sharp naprogramovaný Davidem Wu (lightvector) používá řazení tahů na základě vektoru popisujícího „smysl tahu“ natrénováno na základě vektorů z her výše hodnocených lidských hráčů. Toto řazení je navíc použito k omezení hloubky prohledávání neperspektivních větví. Zdá se, že po drobném doladění parametrů statické ohodnocovací funkce budou obdobní boti v roce 2012 lidmi neporazitelní. (Stále ještě věřím tomu, že letos challenge odolá, ale nebyl bych překvapen, kdyby jeden nebo dva ze zápasů skončily vítězstvím stroje. A to byli letos zvoleni obránci z top 10 aktivních hráčů.) Challenge v roce 2012 odolala, navíc se objevili další dobří lidští hráči, zatímco na straně strojů k výraznému zlepšení nedošlo. Byl jsem ukecán zúčastnit se mistrovství s 40 účastníky MS 2013. Po krachu internetového spojení pro mne WC2013 skončilo předčasně a tak jsem si to zopakoval MS 2014. Můj bot má zatím spoustu potenciálu na zlepšování (pomalé jádro, možnosti vylepšení prohledávání, slabá ohodnocovací funkce, nevyužití paralelizace), v korespondenčních partiích má v „rozevlátých“ partiích šanci díky množství času, který je ochoten partiím věnovat. Bot mého diplomanta je nesrovnatelně lepší, ukecal jsem jej pro účast na wcc.

V noci ze dne 18.4.2015 na 19.4.2015 Arimma Challenge padla. Bot Sharp od Davida Wu (lightvector) získal vedení 2:0, 2:0, 2:0 v challenge hrách proti 5 násobnému mistru světa, zároveň třetímu z letošního mistrovství, čtvrtému muži z letošního mistrovství a letošnímu mistru světa. Druhý člověk z letošního mistrovství světa (dvojnásobný mistr světa) v „screeningu“ dokázal s botem remizovat 1:1, což se povedlo ještě jednomu hráči. Nakonec challenge zápasy skončily 3:0, 2:1, 2:1. Pětinásobný mistr světa ukázal, že bot nadhodnotil frame koně a za jeho udržení byl ochoten obětovat postupně spoustu materiálu. Aktuální mistr světa pak porazil bota bez zneužití této slabiny. Získal sdílenou kontrolu nad botovou pastí což vedlo k přetížení botova slona a k vynucení výměny koně a psa za dva králíky (v tahu 27). Později bot ztratil i psa, ale materiální ztrátu dokázal po drobné nepřesnosti kompenzovat silným gólovým útokem. Aktuální mistr světa ale nezpanikařil, obětoval kočku a se stále ještě výrazným materiálním vedením získal zpět kontrolu nad gólovými hrozbami a v tahu 72 dovedl hru do vítězního konce.

David odvedl letos na vylepšení Sharpa skutečně velký kus práce. Trochu povídání o Arimaa.

V roce 2020 byla situace taková, že MCTS bot s ohodnocovací funkcí založenou na neuronové síti, která byla trénována na základě hry sama se sebou po dobu 60 dní snadno porážel vítěze challenge. Učitel neuronové sítě ponechal snapshoty sítě po jednotlivých dnech učení. Umožnil rozhraní, kde si hráči mohou vybrat s verzí po kolika dnech si chtějí zahrát (pokud již porazili o nejvýš 5 méně dní trénovanou síť) bot odpovídá téměř okamžitě, protože dostal omezení, že se smí neuronové sítě zeptat nejvýš 3200 krát za tah.

Podařilo se porazit verzi z 50 dne využitím blokády slona, stálo to mnoho experimentů, jak jej vylákat do pozice, v níž je šance jej porazit. Bylo zneužito toho, že bot ve stejné pozici hraje většinou stejně. Fér hrou se podařilo vícenásobnému lidskému mistru světa porazit 37. úroveň, v té době ještě nebylo jednoduché na odehraných hrách zjistit, jaká byla úroveň, takže není jasné, na kolik to bylo pokusů (snad 7).

Mnoho proher bota (přinejmenším na nižších či středních úrovních) je v situaci, kdy má naprostou převahu, a zanedbatelné rozdíly v evaluaci nedokáží přesně navigovat k vítězství. Čas od času se pak při chybě gólového útoku dostane slonem do blokády, což zcela otočí výsledek hry.