Vladan Majerech - domácí stránka

Last Modified: 28.6.2017
Kdo a odkud jsi? ?

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 nejlepe 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

Body pro zápočty z NTIN090

Příklady:

  1. Ukažte, jak lze libovolný jednopáskový Turingův stroj $M$ převést na Turingův stroj $M'$, který v každém kroku provádí jen dvě ze tří možných akcí (tj. každá instrukce buď změní stav a pozici hlavy, změní stav a písmeno na pásce, nebo změní písmeno na pásce a pozici hlavy, ale neučiní všechny tyto akce najednou). [1 bod]
  2. Ukažte, že je-li $L$ částečně rozhodnutelný jazyk, pak i jazyk $L^*=\{w\;|\;(\exists k\in{\mathbb N})(\exists u_1, \dots, u_k\in L)[w=u_1u_2...u_k]\}$ je částečně rozhodnutelný. Při řešení mějte na paměti, že pokud $L=L(M)$ pro nějaký TS $M$, pak se může stát, že $M(w)$ se nezastaví pro $w\not\in L$. [2 body]
  3. Ukažte, že jazyk $L$ je rozhodnutelný, právě když existují rozhodnutelné jazyky $A$ a $B$, pro které platí, že $L=\{x\;|\;(\exists y)[\langle x, y\rangle\in A]\}= \{x\;|\;(\forall y)[\langle x, y\rangle\in B]\}$ (Nápověda: Vzpomeňte si na Postovu větu.) [2 body]
  4. Popište algoritmus (pro Turingův stroj), který ignoruje svůj vstup a na výstup vypisuje postupně všechna prvočísla v rostoucím pořadí. [1 bod]
  5. Ukažte, že rozhodnout, zda existuje vstup Turingova stroje $M_i$, pro nějž stroj použije stav $q_k$, je algoritmicky nerozhodnutelné. [2 body]
  6. Nechť $A\leq_mB$ a víme, že $B$ je jazyk přijímaný konečným automatem. Vyplývá z toho že i $A$ je přijímané konečným automatem? Proč? [1 bod]
  7. Nechť $S=\{w_e\mid |L(M_e)|\leq 3\}$, rozhodněte, zda $S$ je rozhodnutelný, či je alespoň $S$ či $\overline{S}$ částečně rozhodnutelné. (Zdůvodněte.)[3 body]
  8. O kterých inkluzích mezi následujícími dvojicemi tříd jste schopni dokázat že platí a o kterých, že neplatí. Za každý dokázaný vztah je jeden bod.
    1. $\mathrm{DTIME}(2^n)$$\mathrm{NSPACE}(\sqrt{n})$
    2. $\mathrm{NSPACE}((\log n)^3)$ $\mathrm{DSPACE}(n)$
    3. $\mathrm{NTIME}(n^3)$ $\mathrm{DSPACE}(n^6)$
Studentcelkem1221213?
Anton Khodos11
Patrik Pasterčík41001002
Monika Daniláková211
Josef Janoušek110
Matěj Klofnar202
Alexandr Mansurov3101001
Dominik Turák31101
Martin Milota21/22/20/21/200

Domácí úlohy ADS2(NTIN060)

Pokud není uvedeno jinak, počet přidělených bodů rychle klesá v případě použití časově neoptimálních algoritmů.

KódBodyZadání
rekur110Zjednodušte popis co nejmenší funkce t (stačí Θ(t)) splňující pro každé n1 a n2 vztah: t(n1+n2)≥t(n1)+t(n2)+c·log2(1+n2), kde n1≥n2≥1 a t(1)=1.
rekur210Zjednodušte popis funkce t (stačí Θ(t)) dané následující rekurencí: t(n)=2t(⌈√n⌉)+c, pro n≥3 a kde t(n)=n pro 1≤n≤2.
medián10Je dán „komprimovaný“ seznam čísel. Nalezněte jejich medián. Komprimace spočívá v tom, že místo čísel dostáváme dvojice čísel, kde první udává hodnotu a druhé počet výskytů dané hodnoty v nekomprimované posloupnosti (stejná hodnota může být ve více dvojicích, dokonce ani není zakázáno její použití v ihned následující dvojici).
lrb12Ukažte, jak asymptoticky nejrychleji je možno z libovolného binárního stromu vytvořit červenočerný strom zachovávající inorder pořadí.
rbt8Nakreslete posloupnost červenočerných stromů, odpovídající provedením následujících operací (uváděny pouze klíče) nad prázdným stromem: insert(6), insert(5), insert(2), insert(1), insert(3), delete(6), insert(4), delete(1).
řeka18Máme mapu úzkého povodí bez ostrovů (strom soutoků zakořeněný v ústí). Na povodí jsou mola (ne nutně na soutocích). Znáte vzdálenosti mezi soutoky (i se vzdálenostmi k molům na každém úseku toku) Popište algoritmus, který pro daná A a B zjstí, zda existují dvě mola mohou být na různých přítocích pro jejichž (říční) vzdálenost V platí, že leží v intervalu ⟨A,B⟩.
řeka212Máme mapu úzkého povodí bez ostrovů (strom soutoků zakořeněný v ústí). Na povodí jsou mola (ne nutně na soutocích). Znáte vzdálenosti mezi soutoky (i se vzdálenostmi k molům na každém úseku toku) Popište algoritmus, který zjstí, zda existují dvě mola mohou být na různých přítocích vzdálená (říční vzdálenost) přesně V.
řeka310Máme mapu úzkého povodí bez ostrovů (strom soutoků zakořeněný v ústí). Na povodí jsou mola (ne nutně na soutocích). Znáte vzdálenosti mezi soutoky (i se vzdálenostmi k molům na každém úseku toku) Popište algoritmus, který zjstí, zda existují dvě mola kde jedno je po proudu od druhého vzdálená (říční vzdálenost) přesně V.
perm2n5Pro danou permutaci čísel od 1 do K nalezněte její „abecední“ pořadí mezi všemi takovými permutacemi.
n2perm5Nalezněte permutaci která je mezi permutacemi čísel od 1 do K na daném n tém „abecedním“ pořadí.
permBi10Algoritmicky popište zobrazení a k němu inverzní zobrazení, mezi čísly od 1 do K! a permutacemi čísel od 1 do K.

Studentcelkemrekur1(10)rekur2(10)medián(10)lrb(12)rbt(8)řeka1(8)řeka2(12)řeka3(10)perm2n(5)n2perm(5)
Radek Chalupa44510845444
Marek Čermák431091284
Jiří Vančura50101010128
Sebastián Hricko401010128
Jan Koštejn400.5100.51282223
Anna Yaghobová42101283333
Matej Štrbka401081282

Zápočtové písemky (Automaty a gramatiky)

7.5.2003 E3 10:40-12:10 zadání řešení
12.5.2003 M4 12:20-13:50 zadání řešení V řešení je v redukci automatu chyba, nemám zdrojové kódy, abych to opravil, nic to nemění na tom, že automat je redukovaný. Jako cvičení se můžete pokusit chybu najít:).
12.5.2003 M4 14:00-15:30 zadání řešení
19.5.2003 M4 12:20-13:50 zadání řešení
19.5.2003 M4 14:00-15:30 zadání řešení
21.5.2003 E3 10:40-12:10 zadání řešení
4.5.2004 E3/E4 zadání řeše
18.5.2005 E1/E2 zadání řešení


Ti co letos za písemku zápočet nedostali, dostali místo toho několik malých nezáporných celých čísel. Každému z nich odpovídá zadání pro domácí úkol. Prosím zaslat řešení úkolu e-mailem (například fotografie či pdf). Pokud bude příklad chybně, budete jej muset vypracovat znovu a jako bonus dostanete další malé nezáporné celé číslo ...

Příklad pro číslo n: zapište (n+17) ve dvojkové soustavě a odstraňte jedničku v nejvyšším řádu. Dostanete tak řetězec r_17 binárních číslic, který může začínat nulami. Obdobně získejte řetězec r_7 z čísla (n+7). Odevzdejte redukovaný konečný automat (nejraději ve formě grafu bez zbytečných křížení hran) přijímající jazyk nad abecedou {0,1} obsahující r_17 jako podslovo a neobsahující r_7 jako podslovo.

Zkoušky

Teorie složitosti

13.1.2017T205 9:00 - se pro nezájem nekoná
27.1.2017T205 9:00 - se konal
3.2.2017T205 9:00 - se konal
10.2.2017T205 9:00 - se konal
17.2.2017T205 9:00 - se konal

Další termín(y) se bude(ou) konat na MFF UK (MS 302), na základě dohody e-mailem. Platí dohoda, že není potřeba se hlásit na termíny, u nichž je napsáno „se bude konat“. Nemá smysl hlásit se na termíny, u nichž je napsáno „nekoná se“ či „nebude se konat“. V ostatních případech, to, že je termín uveden v „kalendáři“ znamená, že přihlášení se na něj (nejpozději do 0:00 dne předcházejcího termínu) povede (nejpozději do 24:00 dne předcházejcího termínu) k tomu, že se objeví status „se bude konat“. Pokud v průběhu dne předcházejícího danému termínu bude uvedeno „se bude konat“, tento status již nebude do termínu zkoušky měněn. Snahou samozřejmě je, aby se termíny se statusem „se bude konat“ skutečně konaly.


Rozvrh

Zkouškové období


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.
Aktuálně píšu "Povídání o datových strukturách", které by 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

(Kalendář šifrovacích her).
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.

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.

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 vyniklý 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 súž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 gliderů 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 glideru 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 glidery. 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 gliderů 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 gliderů. 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).
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.