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);
}
}
}