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í.