jaký je optimální algoritmus pro hru 2048?
Úvod
2048 je vzrušující dlaždice-měnící hra, kde jsme se pohybovat dlaždice kolem, aby je kombinovat s cílem stále větší dlaždice hodnoty.
V tomto tutoriálu, budeme vyšetřovat algoritmus hrát 2048, který vám pomůže rozhodnout nejlepší pohyby, aby se na každý krok, aby se nejlepší skóre.
jak hrát 2048
hra roku 2048 se hraje na desce 4×4., Každá pozice na desce může být prázdná nebo může obsahovat dlaždici a každá dlaždice bude mít číslo.
když začneme, deska bude mít dvě dlaždice v náhodných místech, z nichž každá má buď „2“ nebo „4“ – každá má nezávislou 10% šanci být „4“, nebo jinak a je „2“.
pohyby se provádějí posunutím všech dlaždic směrem k jedné hraně-nahoru, dolů, doleva nebo doprava., Když to děláš, všechny dlaždice se stejnou hodnotou, které jsou vedle sebe a jsou pohybující se spolu sloučí a skončit s novou dlaždice se rovná součtu předchozích dvou:
Poté, co jsme udělali pohybu, nové dlaždice budou umístěny na palubě. To je umístěn v náhodném místě, a bude „2“ nebo „4“ stejným způsobem jako počáteční dlaždice – „2“ 90% času a „4“ 10% času.
hra pak pokračuje, dokud nejsou možné žádné další pohyby.
obecně je cílem hry dosáhnout jedné dlaždice s hodnotou „2048“., Hra se zde však nezastaví a můžeme pokračovat ve hře, pokud je to možné, a zaměřit se na největší možnou dlaždici. Teoreticky se jedná o dlaždici s hodnotou“131 072″.
vysvětlení problému
řešení této hry je zajímavý problém, protože má náhodnou komponentu. Není možné správně předpovědět nejen to, kde bude umístěna každá nová dlaždice, ale zda to bude „2“ nebo „4“.
jako takový není možné mít algoritmus, který pokaždé správně vyřeší hádanku., Nejlepší, co můžeme udělat, je určit, co je pravděpodobné, že bude nejlepší tah v každé fázi a hrát pravděpodobnostní hru.
v každém okamžiku existují pouze čtyři možné pohyby, které můžeme provést. Někdy některé z těchto pohybů nemají žádný vliv na desku, a proto nestojí za to – například ve výše uvedené desce nebude mít pohyb „dolů“ žádný dopad, protože všechny dlaždice jsou již na spodním okraji.
úkolem je pak určit, který z těchto čtyř tahů bude ten, který má nejlepší dlouhodobý výsledek.,
náš algoritmus je založen na algoritmu Expectimax, který je sám o sobě variací algoritmu Minimax, ale kde jsou možné cesty přes náš strom váženy pravděpodobností, že k nim dojde.
v Podstatě, jsme se brát hru jako je dva-hráč hru:
- Hráč Jeden lidský hráč – může posunout desku v jednom ze čtyř směrů
- Hráč Dvě počítačové hráče – můžete umístit dlaždici do prázdné místo na palubě
na tomto Základě, můžeme vytvořit strom výsledků z každého pohybu, vážená pravděpodobností každého pohybu děje., To nám pak může poskytnout podrobnosti potřebné k určení, který lidský pohyb pravděpodobně poskytne nejlepší výsledek.
3.1. Vývojový diagram Hry
obecné tok, jak hra funguje:
můžeme okamžitě vidět náhodný aspekt hry v „Přidat Náhodný Dlaždice“ proces – a to jak v tom, že jsme najít náhodné náměstí chcete-li přidat dlaždice do, a vybíráme náhodné hodnoty pro dlaždice.
naším úkolem je pak rozhodnout, co dělat v kroku „určit další tah“. Toto je náš algoritmus pro hraní hry.,
obecné přetečení se to zdá zdánlivě jednoduché:
Vše, co musíme udělat, je simulovat každý z možných tahů, určit, který z nich dává nejlepší výsledek, a pak použít, že.
takže jsme nyní snížili náš algoritmus na simulaci daného pohybu a generování nějakého skóre pro výsledek.
jedná se o dvoudílný proces. První průchod je zjistit, zda je pohyb dokonce možný, a pokud ne, pak brzy přerušte skóre „0“., Pokud je pohyb možný, přejdeme k reálnému algoritmu, kde určíme, jak dobrý je tah:
3.2. Určení dalšího tahu
klíčová část našeho algoritmu je zatím v simulaci pohybu a klíčovou částí je to, jak generujeme skóre pro každý možný pohyb. Tady přichází náš algoritmus Expectimax.
budeme simulovat každý možný pohyb od obou hráčů na několik kroků, a uvidíme, který z nich dává nejlepší výsledek. Pro lidského hráče to znamená každý z“ nahoru“,“ dolů“,“ vlevo „a“ vpravo“.,
Pro počítačové hráče, to znamená, že uvedení obou „2“ nebo „4“ dlaždice do všech možných prázdné místo:
Tento algoritmus je rekurzivní, přičemž každá rekurzivní krok, zastavení pouze tehdy, pokud je to určité hloubky od skutečného pohybovat v reálném hře.,ulating skóre pro aktuálně simulované palubě rozvržení
- Simulovat všechny možné lidské pohybovat
- Pro každou z těchto
- Recurse zpět do algoritmu
- Návrat skóre vypočtené z této lidské pohybovat
- Přidat skóre vypočtené z tohoto počítače přesunout, vážené pravděpodobnosti, že tento krok děje
Když jsme skončili, jsme pak sečíst všechny vypočtené skóre, a to je konečné skóre pro pohyb chceme, aby se z aktuálního herního plánu., Protože to děláme čtyřikrát-jeden pro každý možný pohyb ze současného herního plánu-skončíme se čtyřmi skóre a nejvyšší z nich je tah.
3.3. Bodování pozice desky
v tomto okamžiku zbývá pouze vypočítat skóre pro desku. To není stejné bodování jako hra používá, ale je třeba vzít v úvahu, jak dobré pozici to je pokračovat ve hře od.
existuje mnoho způsobů, jak toho lze dosáhnout přidáním několika faktorů spolu s vhodnými váhami., Například:
- Počet prázdných míst
- Počet možných spojuje – tj. počet, kolikrát je stejné číslo ve dvou sousedních míst
- největší hodnotu v každém místě
- Součet všech míst
- Monotónnost desky – to je to, jak dobrá rada je strukturována tak, že místo hodnoty zvyšují v jednom směru.
Pseudocode
Nyní, když víme, jak bude algoritmus fungovat, jak to vypadá? Podívejme se podrobněji na nějaký pseudokód popisující algoritmus.,
Jsme nemají zájem na skutečné hraní hry, jen v algoritmu pro určení tahů, takže umožňuje začít tam:
stejně Jako předtím, se to dostane do bodu, kdy jsme simulaci každý z možných tahů z výchozí desky a vrátí ten, který získá nejlepší. To nám ponechává potřebu generovat skóre pro nově simulované desky.
přidali jsme hloubkový limit, abychom mohli po chvíli zastavit zpracování., Protože pracujeme s rekurzivní algoritmus, potřebujeme způsob, jak to zastavit jinak to bude potenciálně spustit navždy:
Tohle nám dává rekurze, simulující všechny možné lidské a počítačové přesunout na určitý počet kroků a rozhodování o tom, které lidské pohyby dát to nejlepší možný výsledek.
jediné, co zbývá, je vypracovat konečné skóre pro danou pozici desky. Neexistuje žádný dokonalý algoritmus a různé faktory poskytnou různé výsledky.,
Optimalizace Výkonu
zatím máme algoritmus, který se pokusí vyřešit hru, ale to není tak efektivní, jak by to mohlo být. Vzhledem k náhodné povaze hry je nemožné mít dokonale optimalizovaný řešitel – vždy bude určitá úroveň opakování jednoduše kvůli povaze procesu.
můžeme alespoň udělat vše pro to, abychom snížili práci, kterou však nemusíme dělat.,
ve výše uvedeném algoritmu již děláme trochu optimalizace tím, že nezpracováváme žádné pohyby, které nemají žádný vliv na hru. Existují i jiné způsoby, jak můžeme snížit práci dělat, ačkoli, jako je sledování kumulativní pravděpodobnost pohybů, a zastavení, když to dostane příliš nízká. To má riziko odstranění dokonalého řešení, ale pokud je pravděpodobnost tak nízká, téměř jistě se tak nestane.
můžeme také dynamicky určit limit hloubky pro práci., Náš výše uvedený pseudokód se pevně limit 3, ale mohli jsme dynamicky vypočítat na základě tvaru desky na začátku našich výpočtů – například, nastavení na počet prázdných čtverců nebo počtem různých dlaždic na desce. To by znamenalo, že procházíme méně tahů z desek, které mají menší prostor pro expanzi.
Navíc, protože je možné vrátit se na stejné palubě pozice několikrát, můžeme si tyto a cache skóre pro ty pozice místo re-computing je pokaždé, když., Potenciálně můžeme vytvořit všechny možné rady polohy dopředu, ale tam jsou obrovské množství z nich – 281,474,976,710,656 různých možných palubě pozice pomocí dlaždice až 2048 – tak to asi není možné.
nejdůležitější optimalizací, kterou můžeme udělat, je úprava algoritmu pro generování skóre desky. To se snaží rozhodnout, jak dobrá deska je pro pokračování ve hře a faktory a váhy, které k tomu používáme, jsou přímo spojeny s tím, jak dobře náš algoritmus hraje.,
závěr
2048 je nesmírně zajímavá hra, která se snaží vyřešit. Neexistuje žádný dokonalý způsob, jak to vyřešit, ale můžeme napsat heuristiku, která bude hledat nejlepší možné cesty ve hře.
stejné obecné zásady fungují pro jakoukoli hru pro dva hráče – například šachy-kde nemůžete předvídat, co druhý hráč udělá s jakoukoli mírou jistoty.
proč nezkusit napsat implementaci a zjistit, jak dobře to funguje?