NLPbot - popis strategie

Stručně v bodech:
- minmax s alfa-beta prořezáváním
- iterativní prohlubování vyhledávacího stromu
- odřezání autodestrukčních tahů, které nezničí žádného soupeřova robota
(nemohou přinést žádnou výhodu)
- ohodnocení pozice zohledňuje:
  - vzdálenosti od soupeřovy vlajky pro tři nejbližší roboty
  - počty robotů jednotlivých stran
  - počet tahů, který zbývá do konce hry (ke konci hry je důležitější mít roboty
blízko soupeřovy vlajky, než mít více robotů než soupeř)

Podrobněji:

Minmax, alfa-beta

Minmax funguje standardně. Máme herní strom, kořen odpovídá počáteční pozici.
Potomci uzlu odpovídají pozicím, do kterých se lze dostat na jeden tah. Strom
držíme v paměti, ale v uzlech si nedržíme pozice na herním plánu (šetříme
paměť), držíme si jen seznam přípustných tahů (= větve vedoucí k potomkům). Při
průchodu stromem začínáme s počáteční pozicí na plánu a přejdeme-li po větvi,
provedeme tah, který větvi odpovídá. Při návratu tah vrátíme. Před provedením
autodestrukčního tahu si musíme zapamatovat pozice zničených robotů, abychom tah
mohli vrátit. Vracení pohybových tahů je bez problémů.

Strom budujeme postupně po jednotlivých úrovních. Nejprve do hloubky 1, následně
do hloubky 2 atd. Přitom používáme alfa-beta ořezávání, takže téměř nikdy
nevytvoříme úplný strom. V dalších iteracích tak může být potřeba kromě poslední
(nejhlubší) úrovně dovytvořit i některé další uzly.

Ohodnocení uzlů z přechozí iterace využíváme k řazení uzlů. V následující
iteraci tedy procházíme uzly (tahy) od potenciálně nejsilnějšího po nejslabší.
To je výhodné z hlediska alfa-beta ořezávání.

Strom budujeme tak dlouho, dokud máme čas a dokud nám stačí paměť. (100 MB je
pro 2 sekundy běhu tak akorát. :))


Odřezání autodestrukčních tahů

Odřezání autodestrukčních tahů, které nezničí žádného soupeřova robota, je
poměrně zásadní. Tyto tahy jednak zvyšují větvení herního
stromu, druhak jsou náročné na provádění a vracení. Přitom si lze celkem snadno
rozmyslet, že takový tah nikdy nemůže přinést žádnou výhodu.


Ohodnocení pozice

Je-li konec hry (poslední tah nebo někdo dosáhne vlajky), používá se reálná
hodnotící funkce (podle pravidel). Jinak...

Pro hodnocení pozic robotů používáme dvě funkce:
- mtf(b) = počet tahů, na které robot dosáhne soupeřovy vlajky na prázdném plánu
- dist(b) = aproximace euklidovské vzdálenosti robota od vlajky (součet
vzdáleností na x-ové a y-ové ose)

mtf lze předpočítat pro každé pole na plánu a uložit do tabulky (výrazně
rychlejší, než pokaždé znovu počítat).

dist používáme místo euklidovské vzdálenosti kvůli efektivitě. Používá jen
jednoduché operace (sčítání, odčítání) vs. počítání druhé odmocniny u eukl. vzd.
(Pozn: Bylo by samozřejmě rovněž možné eukl. vzd. předpočítat a uložit do
tabulky jako v případě mtf.)

Pozici robota b pak hodnotíme následovně:
dist(b) + pocet_tahu_do_konce_hry * mtf(b)

Čím více se blíží konec hry, tím je důležitější být blízko u vlajky, než být
schopný vlajku dosáhnout na méně tahů.

Z těchto hodnocení vezmeme tři nejnižší s1, s2, s3 a provedeme následující
vyvážení:
penalty = 8*s1 + 4*s2 + 2*s3

Tedy "nejbližší" (nejlépe hodnocený) robot je nejdůležitější. Druhý méně
důležitý, třetí ještě méně. Další roboty vůbec neuvažujeme. Výsledné skóre je
negativní, proto "penalty". (Čím jsem dál, tím hůř.)

Dále se hodnotí počty robotů na plánu, a to následovně:
score = 10 * počet_tahů_do_konce_hry * počet_mých_robotů /
počet_soupeřových_robotů

(Toto skóre se přičítá jen straně, která má více robotů.)

Důležitý je tedy poměr mezi počty robotů, ne rozdíl. Mám-li 2 roboty a soupeř 1,
je to jistě lepší situace, než mám-li 10 robotů a soupeř 9. Význam počtu robotů
se snižuje s blížícím se koncem hry.

No, a to je asitak všechno. :)

27. 11. 2008 16:06, RNDr. Jan Pomikálek (CZPJ FI MU), učo 45523