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?)

Rakovinu by mohla léčit umělá lymfatická uzlina

Vědci z Johns Hopkins Medicine tvrdí, že podle nové studie na myších a lidských buňkách …

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 *

Používáme soubory cookies pro přizpůsobení obsahu webu a sledování návštěvnosti. Data o používání webu sdílíme s našimi partnery pro cílení reklamy a analýzu návštěvnosti. Více informací

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close