Vlevo: Výchozí pozice na šachovnici 8 × 8 hry Othello. Vpravo: Diagram ukazující realizaci optimální strategie za obě strany. Zápis partie zní: „F5D6C3D3 C4F4F6F3 E6E7D7C5 B6D8C6C7 D2B5A5A6 A7G5E3B4 C8G6G4C2 E8D1F7E2 G3H4F1E1 F2G1B1F8 G8B3H3B2 H5B7A3A4 A1A2C1H2 H1G2B8A8 G7H8H7H6“. Čísla v kamenech označují pořadí tahů a barvy kamenů konečný výsledek. Credit: arXiv (2023). DOI: 10.48550/arxiv.2310.19387

Hra Othello skončí bez chyby remízou

Othello (Reversi) je desková hra populární dnes především v Japonsku. Vznikla ovšem na konci 19. století v Anglii a její název se skutečně odvozuje od Shakespearova díla. Hraje v ní bílý proti černému na desce o rozměrech šachovnice (obdobná je pak i notace, viz obrázek), ovšem použité kameny mohou měnit barvu (obracejí se, když jsou „obklíčeny/zajaty“; tím hra zase trochu připomíná Go).
Japonský bioinformatik Hirokiho Takizawy nyní oznámil, že hra byla „vyřešena“ v tom smyslu, že se podařilo najít optimální strategii za obě strany. Jde o tzv. slabé řešení, kdy použitý algoritmus zajistí buď výhru, nebo remízu – ze základní pozice. Algoritmus není postaven tak, aby dokázal najít nejlepší pokračování z libovolné pozice (PH: tj. pokud některý z hráčů nebude pokračovat optimálně, druhá strana bude mít postačující strategii; ale analyzovány nejsou pozice, které by vznikly chybnou hrou obou stran – tak tomu alespoň rozumím). Těch má být mimochodem asi oktilion (10 na 48).
H. Takizawa využil superpočítačový klastr MN-J. Dále rozšířil program Edax, který byl před lety poprvé použit k analýze strategie Othello. K průlomu došlo podle něj především díky zlepšení efektivity vyhledávání.

Hiroki Takizawa, Othello is Solved, arXiv (2023). DOI: 10.48550/arxiv.2310.19387
Zdroj: arXiv/TechXplore.com

Poznámky PH:
Jak to chápu, řešení bylo provedeno prostě hrubou silou. Se vším, co se vztahuje k počítačově prováděným matematickým důkazům.
Výsledek na konci (viz obrázek) je skutečně 32 kamenů bílého i černého.
Přichází u této hry v úvahu „nevýhoda tahu“? Asi ne, spíš je vždycky výhodnější táhnout, a tedy i začínat… (tj. v úvahu přicházely pouze dva možné výsledky při oboustranně optimální hře?)

Další studie tvrdí, že černé díry na počátku vesmíru nevznikly z hvězd

Opět zde máme již mnohokrát řešenou hádanku. Vesmírný dalekohled Jamese Webba pozoroval galaxii ve velmi …

3 comments

  1. U teto hry je nevyhoda tahu podstatna. Kdysi na staricke Nokii jsem nasel postup na absolutni vitezstvi (vsechny kameny byly me) a v podstate od asi dvacateho tahu mel telefon vzdy jen jeden mozny tah, kterym mi pripravil kameny k zajmuti. Samozrejme ten ppostup fungoval jen na konkretni verzi te hry.

  2. a nebo je rozhodovani o dalsim optimalnim kroku v tak uzkem
    udoli moznosti, ze se strom moznosti nema sanci moc rozvetvit
    a jde to hrubou silou. tipuju, ze rozumnych tahu neni moc v kazdem kole, tak 2 az 4.

  3. dekuji za upresneni, priznam se, ze jsem tu hru nikdy nehral. ani nevim, ze ma vice verzi, respektive tomu nerozumim…

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *