Prírodou inšpirované algoritmy

Optimalizačné metódy a grafové algoritmy

Väčšinu problémov v umelej inteligencii je možné previesť na hľadanie maxima, alebo minima nejakej úžitkovej funkcie - počítač môže napríklad hľadať najkratšiu cestu k vašej základni, zisťovať, ako rozmiestniť kombajny tak, aby vyťažili čo najviac rudy, alebo premýšľať o tom, kam hodiť "atómovku", aby upražil maximum vašich piadimužíkov.

Optimalizácia má mnoho veľmi prepracovaných algoritmov, ktoré by počítaču umožnili veľmi racionálny boj, keby ... keby neboli tak náročné na čas a pamäť. Programátori upravujú často optimalizačné algoritmy nielen kvôli rýchlosti, kde hľadajú nielen najlepší všeobecný výsledok, ale najlepší výsledok v obmedzenom čase - ale pridávajú tam aj náhodný faktor, aby počítač nehral celkom šablónovite.

Optimalizácia je zásadná vec nielen pre stratégie - napr.Transport Tycoon, Industrie Giant, alebo Railroad Tycoon je jedna takáto obrovská dopravná a ekonomická optimalizácia - ale napodiv aj medzi hrami riešenými grafovými algoritmami a optimalizáciou patrí aj drvivá väčšina plošinových hier, ako sú šachy, ale napríklad aj problém hľadania ciest v bludisku, ktorý v nejakej forme riešia aj väčšina botov, či už v Quake alebo Unreal. Mimo labyrint,tak ako ho vidia hráči. Existuje ešte mapa orientačných uzlov, v ktorých hľadá umelá inteligencia. Stratégie sú najrôznejšie - do máp sa dávajú značky, ktoré napomáhajú elementárnemu (ale nie príliš šikovnému) chodeniu, v zložitejších prípadoch sa kódujú aj celé cesty k dôležitým miestam bludiska, kde je zdravie, alebo munícia.

Optimalizačné algoritmy patria k triede NP-úplných problémov, ktorých náročnosť na riešenie rastie so zložitosťou problému viac ako polynomiálne. Jednoducho povedané - je to veľmi zlé a veľké úlohy tohoto typu je možné dokonale vyriešiť len s obrovskou kapacitou pamäti a veľkou náročnosťou na čas. Nehovoríme tu o drobnostiach, ako že si "budete musieť zohnať lepší procesor" - skôr o tom, že zložité úlohy tohoto typu by počítače riešili tisícky, ba až státisícky rokov. Preto sa väčšinou neriešia tieto úlohy dokonale, ale pomocou zjednodušení. Autori často priamo do máp vložia značky pre robotov, ktorými vykolíkujú dobré cesty a ukážu im, kde je dobré miesto ku schovávaniu a zákernému odstreľovaniu nepriateľov.

Behom hry je totiž umelá inteligencia robota väčšinou rada, keď s ním nájde základné zásoby a na zložité "finty" totiž nemá.Keď ste niekedy skúšali naprogramovať vlastného robota, viete určite dobre, ako ľahko sa roboti stratia a zaseknú o "nejakú blbú bedňu". Hľadanie ciest path searching, patrí medzi tie najzložitejšie funkcie, ktoré boti majú !