Dělení střelby/pohybu/radaru; Predikce

Engine StateSearch by za ideálních podmínek jistě zvládal ovládat střelbu, pohyb i radar najednou pomocí správně definovaných akcí.

Vzhledem však k tomu, že v prostředí Robocode nemá bot kompletní informace o vývoji hry, vyžadovala by implementace všech tří částí (střelba, pohyb, radar) dohromady určitou dávku predikce.

Tato predikce je však velmi složitá a navíc pro pohyb vs střelba/radar oddělená. Rozhodnul jsem se tedy ve své BP zaměřit pouze na predikci vhodnou pro náš pohyb.

Pohyb
Predikce pro náš pohyb vyžaduje správné určení budoucího úhlu střelby protivníka. To provádím pomocí vln (vlna je místo, kde se může střela nalézat - střed má v bodě výstřelu a šíří se zároveň se střelou), únikového úhlu (který určuje, kam až můžeme za daný čas s botem zajet) a pravděpodobností zásahu, které jsou rozsety na tomto úhlu.
S každým zásahem přidáme si pamatujeme (pouze do určité hloubky), pod jakým úhlem nás protivník zasáhnul a zvýšíme pravděpodobnost tohoto úhlu. Pak se snažíme jezdit pouze do takových míst, kde je pravděpodobnost zásahu nejnižší.

To poslední řečené, tedy to, že navštivujeme místa s nejnižší pravděpodobností zásahu je už záležitost enginu StateSearch. Predikce vln pouze udává pravděpodobnosti a StateSearch již s pomocí simulace a akcí určí, které místo je pro nás v budoucnu nejvýhodnější. V evaluační funkci jsou zmíněny naše životy, které pak vyústí ve snahu algoritmu vyhýbat se nebezpečným místům.

Střelba
Střelbu jsem bohužel oddělil od algoritmu StateSearch a provádím ji s použitím GuessGun zbraně a přesnou predikcí únikového úhlu.

Radar
Protože je bot navrhnut pouze na boj 1v1, je radar obsluhován několikařádkovým kódem jako PerfectLock Radar. Tedy stále ukazuje na protivníka.

Aktuální bot

Aktuální bot ke stažení je na adrese http://www.robocoderepository.com/BotDetail.jsp?id=3514

Optimální přístup

Engine popsaný v předchozím příspěvku je hledání Best First Search (BFS), které rozvíjí nejdříve ty uzly, které se jeví jako nejvýhodnější.

Byl jsem požádán o úvahu ohledně algoritmu A*.

Tento algoritmus A* je z definice optimální, protože využívá optimální evaluační funkce. Algoritmus A* JE ve své podstatě také BFS algoritmus, odlišuje ho právě jen sestavení evaluační funkce. Ta se v něm dělí na g(x), která určuje cenu, kterou jsme museli již vynaložit na dosažení daného bodu a h(x), která určuje odhad ceny, kterou budeme muset ještě vynaložit, než dosáhneme cíle.

Výsledná evaluační funkce je součtěm g(x) a h(x).

Navíc funkce g(x) a h(x) musí splňovat určitá kritéria, aby byly optimální.

Přístup se skvěle hodí na problémy, kde lze tyto funkce snadno určit. Je to například hledání cesty v mapě, kde g(x) známe a h(x) odhadneme jako vzdálenost vzdušnou čarou do cíle.

V problémech, které vyvstávají v Robocode, však takovéto funkce nelze s lehkostí určit. Ve skutečnosti nemám žádný nápad, který by mi pomohl je určit. I kdybych byl schopen problém rozdělit do 2 funkcí, nebudu vědět, zda jsou optimální.

Evaluační funkce, kterou používám teď nemusí být nutně optimální, za to však funguje.

Jeden z nápadů zněl: Byl bych nerad, kdyby ste zcela zavrhl dalsi snahu o implementaci A*, tedy nalezeni g(x) a h(x). Jejich nalezeni udela z vaseho bota (z definice) nejinteligentnejsiho. Rozumim Vasim tezkostem, bez strelby nelze smysluplne pocitat h(x), tedy odhad vzdalenosti ze stavu x do ciloveho stavu. Samozrejme ani vhodna volba g(x) neni trivialni zalezitost. Intuitivne, pro vypocet hodnoty g(x) je treba uvazovat vsechny spotrebovane zdroje (od zacatky hry po dosazeni stavu x), tedy nejen spotrebovanou energii, ale take cas potazmo "promarnene prilezitosti".

Samozrejme najit optimalni g a h znamena bud hodne experimentovani nebo pouziti optimalizacnich metod (geneticke algoritmy jsou jednou z nich).

Bohužel si nemumí moc představit použití takových optimalizačních metod ani počítání promarněných příležitostí.

Přístup StateSearch

Pro svou bakalářskou práci jsem nadále zvolil přístup StateSearch, což je pracovní pojmenování pro algoritmus hledání v grafu.

Základní myšlenkou StateSearch jsou:

• akce, které může bot v daném okamžiku vykonávat>
• stavy, které z momentálního stavu tyto akce generují
• ohodnocení každého stavu evaluační funkcí
  
• algoritmus hledání v grafu, který nalezne nejvýhodnější stav a cestu k němu

Akce
jsou zastřešovány třídou Action uvedenou níže:

public abstract class Action {
public abstract World run (World w);
public abstract boolean isRunnable (World w);
public abstract void runReally();
}

run - vrátí modifikovaný stav, akce modifikují zároveň i čas
isRunnable - zjistí, jestli je na daném stavu akce aplikovatelná
runReally - fyzicky spustí akci (například skutečně zrychlí); toho je využito, když už víme, že tato akce je nejlepší

Momentálně definované akce:
Accelerate, NoAction, Steer, Stop

Stavy
jsou definovány třídou World. Nebudu uvádět přímý kód, zájemci nechť si stáhnout kompletního bota z níže uvedené adresy.
Tato třída udržuje stav botů na hracím poli (pozice, rychlost, natočení), střely (respektive vlny) a herní čas. Poskytuje metody pro jejich modifikaci pomocí akcí.
Nejdůležitější metodou této třídy je doulbe evaluate(), která vrátí hodnotu daného stavu dle předem dané evaluační funkce.

Evaluační funkce
Momentálně použitá evaluační funkce bere v úvahu (od nejvyšší priority):

• naše životy
• kolmost našeho natočení k nepřítely (zjednodušuje únik před střelami)
• vzdálenost od nepřítele (ideální je 500)
• vzdálenost od středu hřiště (ideální je ve středu)

Z těchto hodnot vypočítá double hodnotu přičemž platí, že nižší je lepší.

Algoritmus generování a hledání v grafu
Základním motorem celého algoritmu je generování stavů na základě akcí a následné vybrání té nejefektivnější.
Celý přístup vlastně připomíná šachy, kde máme možnosti, jak táhnout, propočteme je do určité hloubky a provedeme tu nejvýhodnější.

Celý algoritmus je (zjednodušeně) ukázán zde. Omluvte formátování, google blog nejspíš není připraven zdrojové kódy:


//--------------------HLAVNÍ ALGORITMUS
ArrayList< Node> bestNodes = null;
while(true){
if(openList.isEmpty())
break;

bestNodes = new ArrayList< Node>(EXPAND_NODES_PER_TICK);

for(int i=0; i< EXPAND_NODES_PER_TICK; i++){
Node n = getBestNode();

openList.remove(n);
closedList.add(n);

bestNodes.add(n);
}

if(bestNodes.get(0).depth >= MAX_DEPTH)
break;

for(Node n: bestNodes){
expandNode(n);
}
}

Node best = bestNodes.get(0);

while(best.previous.previous != null){
best = best.previous;
}

best.action.runReally();
//--------------------TŘÍDA NODE
private class Node {
public Action action;
public World world;

public double value;
public int depth;
public Node previous;
}

//-----------------FUNKCE EXPANDNODE()
private void expandNode(Node n){
if(n.depth >= MAX_DEPTH)
return;

for( Action a : actionList ){
if(a.isRunnable(n.world)){
World newWorld = a.run(n.world);
newWorld.run(TURNS_PER_TICK);

double worldValue = evaluateWorld(newWorld);
Node c = new Node(a, newWorld, n, worldValue, n.depth+1); //create a new node with altered world

if(closedList.contains(c))
continue;

openList.add(c);
}
}
}


Dookious Team

Hi, I announce a new version of Dookious Team.

In this version, Dookious is capable:
* broadcasting messages about our's and enemy fire
* avoiding any bullet we know about (our bot, enemy bot we know he fired)

And NOT capable:
* coordinated shooting, moving, scanning

Pls, use Robocode ver. 1.6.1.4, the new beta is somewhat .. it dont work.

Team creation

Ok, suppose we have our bot (could be Dookious, maybe other)

Good start is with http://robowiki.net/cgi-bin/robowiki?Teams, which says about common team rules.

Let's say we have Dookious, we need to:
- ensure we shoot only at the enemy ;-)
- collision detection
- think about scanning techniques (one2one scan, one bot could continuously update all space, ...)
- modify the waves to support more than 1 opponent, and let them be shared among all of our bots (could I define the class static to share? - I can't :-( see the bottom of game physics)
- add to waves our own bullets (to avoid them)
- shoot in way to maximalize hit probability (eg shoot in a matrix pattern, or randomly distorted..)

Test teams

Unfortunately, robowiki is actually down, I will update this after it's up (links, stats and more teams).


abc.ShadowTeam - the TOP team in roborumble, but as I see it, it has a lot to improve (and thus we can take advantage)
wiki.twin.KomariousTeam_1.0 - I currently use these two bots, they're competitive for my edited Dookious
...