Úvod do algoritmov umelej inteligencie #1 - HillClimbing

Osobne tieto poznatky využívam v programovaní botov na platforme codingame.com a s niektorými základnými princípmi sa zdieľam so študentami technického lýcea v Novej Dubnici, kde učím niekoľko programátorských predmetov.

Preto aj tento seriál bude vedený takou formou, aby ich vedeli pochopiť všetci, ktorým sa nepáčia písmenká v matematike a chcú vedieť viac.

Optimalizačné algoritmy

Viacero algoritmov umelej inteligencie spočíva vo vytvorení zlého riešenia a v jeho následnom ladení / optimalizácii. Za takéto zlé riešenie vieme napríklad pokladať cestu z Bratislavy do Košíc cez Prahu, alebo omaľovánku vyfarbenú nesprávnymi farbičkami. V prípade umelej inteligencie v počítačových hrách by sme napríklad vedeli hovoriť o náhodnom stláčaní kláves. Optimalizačné algoritmy sa používajú aj pre učenie neurónových sietí.

Pri takýchto problémoch vieme my, ako ľudia, pomerne rýchlo nájsť riešenie, ktoré sa blíži k ideálnemu. Ideál je však extrémne náročné dosiahnuť a to predovšetkým vtedy, ak na naše riešenie vplývajú vonkajšie vplyvy. Stačí napríklad do single-player hry pridať jedného hráča...

Všetky optimalizačné algoritmy fungujú nasledovne:

1. Vytvor n náhodných riešení (vektor, populáciu n jedincov, číslo a pod. alebo radšej ľudsky... vyfarbi 20x kópií omaľovánky náhodnými farbami)
2. Až kým nie si spokojný s riešením / nevyprší ti čas
   a. mierne uprav tieto riešenia (vymeň farbičku v jednom bloku omaľovánky)
   b. ak nájdeš lepšie riešenie zapamätaj si ho

Horolezecký algoritmus - HillClimbing

Predstavme si mobilnú hru, v ktorej budeme ťahom prsta ovládať smer a silu odpalu golfovej loptičky na minigolfovom ihrisku. Našou úlohou je trafiť jamku na čím menej odpalov. Sila a smer sú jediné 2 parametre ktoré vieme ovplyvniť. Ako naučíme našu umelú inteligenciu správne udrieť do loptičky?

Pre tento malý problém nie je až také náročné nájsť dobré riešenie. Poďme na to ale postupom, ktorý som popísal vyššie. Vytvoríme náhodné riešenie a skúsime ho pomaličky upravovať.

1. Vytvorme si 1 náhodné riešenie napr. riesenie = { sila: 50, smer: 60 }
2. Donekonečna
   a. vytvoríme 4 nové riešenia také, kde nove_riesenia = [
    {sila + 1, smer},
    {sila - 1, smer},
    {sila, smer + 1},
    {sila, smer -1} 
   ]
   ‍b. je niektore riešenie z nove_riesenia lepšie ako riesenie?
     i. nie - ukonči cyklus
     ii. áno - riesenie = nove_riesenia[najlepsie]

Výborne! Tomuto algoritmu hovoríme horolezecký algoritmus. Pozrime sa ešte, ako asi vizuálne vyzerá prvá iterácia tohto algoritmu:

Prostredná šípka ukazuje silu a smer úderu bez akejkoľvek úpravy parametrov. Ostatné šípky ukazujú všetkých štyroch susedov, ktorých viem drobnou úpravou parametrov získať.

Ostáva sa nám len zamyslieť nad tým, ako vyhodnotíme nové riešenie za lepšie. Nebudeme programovať celú hru, preto si správny výsledok len stanovme na napr. 92 resp. 15 pre silu a smer. Cena riešenia tak bude súčet rozdielov medzi očakávaným a aktuálnym smerom a silou. Naše riešenie formou horolezeckého algoritmu by vyzeralo nasledovne (Kotlin):

import kotlin.math.abs

const val riesenieSila = 92
const val riesenieSmer = 15

data class Riesenie(val sila: Int, val smer: Int) {
    fun cost() : Int =
        abs(riesenieSila - sila) +
        abs(riesenieSmer - smer)
}

fun main() {
    // vytvorenie nahodneho riesenia
    var riesenie = Riesenie(50, 60)
    while(true) {
        // ziskanie susednych rieseni
        val noveRiesenia = arrayOf(
            Riesenie(riesenie.sila - 1, riesenie.smer),
            Riesenie(riesenie.sila + 1, riesenie.smer),
            Riesenie(riesenie.sila, riesenie.smer - 1),
            Riesenie(riesenie.sila, riesenie.smer + 1)
        )
        val najlepsieNoveRiesenie = noveRiesenia.minByOrNull{ it.cost() }!!

        // vyhodnotenie
        if (najlepsieNoveRiesenie.cost() > riesenie.cost()) { break }
        else { riesenie = najlepsieNoveRiesenie }
    }

    println("najlepsie riesenie - ${riesenie.sila} / ${riesenie.smer}")
}

Toto riešenie by vynikajúco fungovalo pre hraciu plochu bez akýchkoľvek prekážok a ak je úvodný smer odpalu do 45 stupňov od cieľovej pozície. Je to preto, že hillclimbing sa v žiadnom prípade nevie dostať z lokálnych optím. Pri uhle väčšom ako 45 stupňov by algoritmus za optimálne riešenie vyhodnotil to, kde je sila úderu = 0 aby sme sa nevzdialili od cieľa.

Ak by ste si chceli správanie HillClimb algoritmu vyskúšať na príklade podobnom tomu, ktorý som predstavil, môžete tak vyskúšať s týmto gistom. Je v ňom zakomponovaná extrémne jednoduchá simulácia pohybu loptičky a zároveň je v ňom implementovaný HillClimb algoritmus a vizuálna reprezentácia minigolfového ihriska.

Stay tuned

Hoci sme sa do teórie veľmi neopreli, boli sme schopní ukázať si, ako funguje jeden z najzákladnejších optimalizačných algoritmov. HillClimbing prehľadáva najbližšie okolie a z tohto okolia si vždy vyberie len najprívetivejšie riešenie. Ak už žiadne krajšie riešenie nenájde, ukončí vyhľadávanie.

Najbližšie si ukážeme Tabu Search a trošku sa pobavíme o tom aké vlastnosti vlastne tieto algoritmy majú.

Samo-štúdium

K algoritmom umelej inteligencie veľmi odporúčam prednášky z MIT