Matematika v Minecraftu pro pokročilé

Kdo jsem

• Otaku, gamer
• výzkum AI a ML inženýr v Avastu/Gen Digital
• Ing. z umělé inteligence FEL, ČVUT
• https://www.facebook.com/matej.racinsky
• https://github.com/racinmat
• https://www.linkedin.com/in/matej-racinsky/
• Discord: Azathoth42#4577

​

Odkazy a Zdroje

• 69 odkazů v seznamu zdrojů
• Zdroje a materiály https://bit.ly/ff-2024-minecraft-sources
• Prezentace samotná https://bit.ly/ff-2024-minecraft-slides
• Kdyby vás zajímaly další zdroje (vědecké články atd.), napište mi

Zdroje

Prezentace

Co nás čeká

• Úvod
• Procedurálně generované světy
• Rozbité světy a kdy to nefunguje
• Komunitní projekt – pack.png
• Seed finding (hledání seedů)
• Reverse engineering seedů
• Žádný redstone
• Pouze java verze

​

TRIGGER WARNING

• Budou se objevovat matematické vzorce.
• Občas zazní složitě znějící slovo.
• Nebojte se zeptat.
• Nebojte se zeptat.

​

Co je matematika?

• z řeckého μαθηματικός (mathematikós) = milující poznání
• μάθημα (máthema) = věda, vědění, poznání
• vědní obor
• zabývá se z formálního hlediska kvantitou, strukturou, prostorem a změnou
• zabývá vytvářením abstraktních entit a vyhledáváním zákonitých vztahů mezi nimi

Co je to Minecraft?

• Úspěšná původně PC hra
• Nyní na 18 platformách
• Sandbox, single i multiplayer RPG
• Vydána 18.11.2011 (alpha od 17.5.2009)
• Nejvíce prodávaná PC hra na světě (>200 milionů prodaných kopií)
• Cíl je zabít draka
• Stavíte věci z kostek

Proč zrovna Minecraft

• Dostupné všechny verze od 13.5.2009
• Umožňuje prozkoumávat staré verze a vracet se v čase, replikovatelnost experimentů
• Jar (Java) lze snadno dekompilovat
• Lze se relativně snadno dostat ke zdrojovým kódům
• Usnadňuje reverse engineering a komunitní tvorbu obsahu
• Jednoduchý generátor náhodných čísel
• Lze hledat nebo manipulovat seed
• Velká komunita sdílející znalosti
• Seed: 1 číslo generuje celý svět

Co se zkoumá na videohře?

• Generování vlastností světa z jednoho čísla
• Inverze vysoce nelineárních funkcí
• Celočíselná aritmetika, ILP
• High performance computing – distribuované výpočty, GPU
• Computer vision, hledání parametrů kamery a neuronové sítě
• Tvorba heuristik pro hledání ve vysoké dimenzi
• Podobná infrastruktura a techniky jako u computer science výzkumu

Procedurálně generované světy

Náhoda? Nemyslím si!

• Náhoda v PC a IT neexistuje. Vše v počítači je deterministické.
• Náhoda se dodává externím zdrojem (proudění vzduchu atd.)
• Uvnitř PC pseudonáhoda – deterministické, ale „náhodně“ vypadající programy
• Náhoda možná neexistuje vůbec (záleží na interpretaci kvantové fyziky)

Procedurální generování v

• Výška mapy -> Perlinův šum
• Původně na textury u CGI modelů
• 1983, použito ve filmu Tron (před formalizací)
• Seed k tvorbě deterministického světa
• Hierarchický = oktávový šum – více perlinových šumů s různým zvětšením, v MC 16 vrstev

Tvorba mapy �vrstvu po vrstvě

• Tvorba biomů po vrstvách.
• 50 vrstev
• Směrem od hrubých k jemným
• Jak velikostí, tak variabilitou biomů
• Generováno ve verzi 1.16

Biomy

Zde pár vrstev vynecháno

Tvorba mapy�vrstvu po vrstvě

Na kraji světa

Proč se světy na okrajích rozbíjí

Příznaky

• Infdev-1.7.3 beta
• Far Lands
• Přetečení intu pro Perlin Noise
• Na souřadnicích ±12 550 821-5 (12.5k km)
• Fake chunks
• Za souřadnicemi ± 32 000 000 jsou chunky nehmotné, vyplněné pouze travou, kameny nebo vodou, reálný terén se negeneruje
• Později limit 30M

​

Far lands

Far Lands

• Na všech 4 stranách, ve vzdálenosti 12 550 821
• Cca 12 550 km
• Ze středu jako cesta z Prahy do Hirošimy

Far lands beta 1.7.3

Far lands pohyb-12M

Fake chunks – 30M

Fake chunks-1004M

Far lands - příčina

Co je to seedfinding

• Hledání seedu, většinou
• Hledání konkrétního seedu ze světa
• Taky známo jako seed cracking
• Seed mapy PewDiePie
• Seed z obrázku, videa, serveru apod.
• Hledání seedu jehož svět splňuje nějaké podmínky
• Ideální seed na spedrunning
• Mansion a vesnice blízko spawnu
• 4 swamp hut blízko sebe

Pack.png

Pack.png

• Kde začít
• Verze minecraftu podle doby vytvoření souboru
• Z souřadnice podle pozice mraků
• Znovuvytvoření v mapě – základ pro další pátrání
• Co bylo dál
• Nalezení X souřadnice - umláceno statistikou z perlin noise, jinak tráva
• Hledání patternu písku a hlíny – MC@home, 3500 lidí GPU ~brutefoce
• 700k world seedů pro které zkontrolovali na cpu výšky bloků v kopci
• Výsledek
• Alpha 1.2.2
• Seed: 3257840388504953787
• Souřadnice kopce: X=116, Z=-31

Další seedfinding projekty

• Původní main menu screen - done
• Obraz s lebkou - done
• Ostatní main screen pozadí do 1.16 - done
• Herobrine - done
• Pewdiepie hardcore mapa - done
• Markiplier letsplaye - done
• Supersmash bros trailer mapa - WIP

Seed

• 64bitové celé číslo
• Budovy apod. – dolních 48 bitů
• Horních 16 bitů pouze biomy
• Dolních 16 bitů = pillar seed
• Shadow seed
• seed se stejnými biomy, ale vším ostatním jiným
• Každý seed má 1 svůj shadow, -7379792620528906219 - <seed>
• Viètovy vzorce pro n=2
• Funguje jenom pro overworld
• Nether i End používají jen dolních 48 bitů

​

Shadow seed

• Stejné biomy, jiné struktury
• nextInt v biomech
• L*=L*A+B; return L+L2
• Return (L*A+B)*L+L2
• Return AL^2+BL+L2

​

​

Shadow seed

Hledání seedů po domácku

• Hledání seedu konkrétního světa
• Hledání seedu (světa) s nějakými vlastnostmi
• Pozor na verze minecraftu

Hledání seedu pro daný svět bez modů

• Seed ze spawnerské místnosti
• SeedCandy, ostatní SW ve zdrojích

​

Spawn

• Najděte místnost se spawnem
• Jsou v následujících velikostech, pokud jsou menší, rozbijte zdi: 7x7,7x9,9x7,9x9

SeedCandy

• Jednoduché, snáze se ovládá, GUI
• nejde pauznout, pokud pustíte seed finding s málo daty
• Čtěte readme
• Spawn->structure seed
• Structure seed+biomy na souřadnicích->world seed

SeedCandy

• Stůjte facing north
• Překlikejte mech
• Souřadnice targeted block

SeedCandy

• Z mechu získány structure seeds
• Vyplníme souřadnice biomů
• 2 jsou málo->hodně výpočtů a seedů
• Mělo by stačit 5-6->heureka. Máme world seed

SeedCandy

• Když už máte world seed
• Nalezení quadhuts, výpočet shadowseed, sisterseeds…

Hledání seedů po domácku

• Hledání světa splňujícího nějaké podmínky
• Nejjednodušší způsob: zkoušet seedy popořadě nebo náhodně a zahodit je když nesplňují požadavky
• Snadno paralelizovatelné (16 cores go brrrr)
• Jednoduché na použití, univerzální
• Stále poměrně pomalé při složitějších podmínkách

GUI aplikace

• https://github.com/Zodsmar/SeedSearcherStandaloneTool
• StandAlone Seed Searcher Application (Sassa)
• Java aplikce, exe, stahnete z githubu
• Naklikáte požadavky a vzdálenost hledání
• Spustíte a čekáte, postupně vypisuje seedy

Seedy na domácí hraní

• Hledání seedů s většinou budov blízko spawnu
• https://github.com/racinmat/MinecraftSeedFindingPlayground

Seed finding - bruteforce

Seed cracking - chytřejší

• Java RNG není kryptograficky bezpečné
• Úmožňuje cracking, mnohem rychlejší než brute-forcing

​

Seed cracking

Seed cracking

Vykreslení možných řešení

• Osa x = iterace, pořadí seedu
• Osa y = hodnota seedu
• Výsledky generátoru náhodných čísel jsou mají pravidelnost!
• Proto snadno prolomitelné

Seed cracking

• Vše ve světě je skrze RNG, vše updatuje seed
• Když známe výsledky callů, odvodíme z nich seed
• Musíme vědět kolik RNG callů přibližně bylo

Seed cracking

• Hledání portálu s 12 spawnutými ender eyes
• 12 callů nextFloat musí být >0.9

Formulování ILP

• Trik nahrazení (mod m) za konstanty

Formulování ILP

• Hledání portálu se všemi 12 částmi otevřenými

Formulování ILP

• Trik nahrazení (mod m) za konstanty

Vykreslení možných řešení�jednoduchý příklad

• Parametry LCG

​

• Další parametry

​

• Maticový zápis

​

• Rozložení na vektory

Lattice reduction

• ILP je hledání bodů, které náleží do rovnoběžnostěnu
• Výpočetně poměrně náročné

Lattice reduction

Lattice reduction

Závěrem

• V minecraftu se dá dělat spousta zajímavých věcí
• Aktivní komunity okolo skoro všeho co vás napadne
• Spousta zdrojů a materiálů

​

Poděkování

• Minecraft komunitě za množství materiálů
• Monkey serveru, Minecraft@home discordu a jeho členům kteří vedou minecraft výzkum

Mé další přednášky

• Psychologické triky v gača hrách GameLine, Středa 3.7. 12:00
• Kam kráčíš, umělá inteligence? FutureCon, Čtvrtek 4.7. 10:00
• IT aspekty organizace conů, FutureCon, Sobota 6.7. 9:00
• Dočkáme se AI waifu? OrientCon, Sobota 6.7. 18:00

Odkazy a Zdroje

• 69 odkazů v seznamu zdrojů
• Zdroje a materiály https://bit.ly/ff-2024-minecraft-sources
• Prezentace samotná https://bit.ly/ff-2024-minecraft-slides
• Kdyby vás zajímaly další zdroje (vědecké články atd.), napište mi

Zdroje

Prezentace

Časoprostor pro dotazy