Kapitola 19: AI v praxi 1 – Řešení stavových úloh

Vstupujeme do světa opravdové umělé inteligence. Jedním ze základních úkolů AI je plánování. Jak se dostat z bodu A do bodu B, když neznáme cestu? Představte si, že hrajete šachy nebo řešíte hlavolam. Každý tah mění situaci na hrací desce. Všechny možné situace tvoří obrovskou mapu, které říkáme stavový prostor. Prolog je mistr v hledání cesty na této mapě.

19.1 Problém: Vlk, koza a zelí

Znáte tu starou hádanku? Máte převozníka, vlka, kozu a zelí na levém břehu řeky. Chcete je všechny dostat na pravý břeh.

Vlk, koza a zelí
Obrázek 19.1: Klasická hádanka, která je ideální pro demonstraci hledání ve stavovém prostoru.

19.2 Jak to říct počítači?

Nejdříve musíme definovat, jak vypadá "svět" v jednom okamžiku.

STAV (STATE) Popis situace v jednom konkrétním čase. V naší úloze je to informace o tom, kde se kdo nachází.

Stav popíšeme jako seznam 4 položek: [Prevoznik, Vlk, Koza, Zeli].
Každá položka může být l (levý břeh) nebo p (pravý břeh).
Například [l, l, l, l] znamená, že všichni jsou vlevo (start).
Cíl je [p, p, p, p].

19.3 Řešení v Prologu

Místo abychom psali algoritmus "jak to vyřešit", popíšeme jen pravidla hry. Prolog najde řešení sám.

% Změna břehu (l -> p, p -> l)
opacny(l, p).
opacny(p, l).

% Bezpečný stav: Vlk není s kozou bez převozníka, Koza není se zelím bez převozníka.
bezpecny([P, V, K, Z]) :-
    (V \= K ; P = V),  % Buď vlk není s kozou, NEBO je tam převozník (aby to hlídal)
    (K \= Z ; P = K).  % Buď koza není se zelím, NEBO je tam převozník

% Přechod (Tah): Z jednoho stavu do druhého
% 1. Převozník jede sám
tah([P, V, K, Z], [NP, V, K, Z]) :- opacny(P, NP).
% 2. Převozník bere vlka (oba musí být na stejném břehu P)
tah([P, P, K, Z], [NP, NP, K, Z]) :- opacny(P, NP).
% 3. Převozník bere kozu
tah([P, V, P, Z], [NP, V, NP, Z]) :- opacny(P, NP).
% 4. Převozník bere zelí
tah([P, V, K, P], [NP, V, K, NP]) :- opacny(P, NP).

% Hledání cesty (DFS - Prohledávání do hloubky)
reseni(Start, Cil, Cesta) :-
    cesta(Start, Cil, [Start], Cesta). % [Start] je seznam navštívených stavů

% Základní případ: Jsme v cíli.
cesta(Stav, Stav, _, [Stav]).

% Rekurzivní krok:
cesta(Stav, Cil, Navstivene, [Stav | Zbytek]) :-
    tah(Stav, NovyStav),              % Zkus udělat tah
    bezpecny(NovyStav),               % Je nový stav bezpečný?
    \+ member(NovyStav, Navstivene),  % Nebyli jsme tu už? (Prevence cyklů)
    cesta(NovyStav, Cil, [NovyStav | Navstivene], Zbytek).

19.4 Jak Prolog hledá cestu (DFS)

Prolog používá strategii zvanou Prohledávání do hloubky (Depth-First Search - DFS). Představte si to jako průzkumníka v jeskyni:

  1. Jde jednou chodbou tak dlouho, dokud to jde.
  2. Pokud narazí na slepou uličku (nebezpečný stav nebo stav, kde už byl), vrátí se o krok zpět (Backtracking).
  3. Zkusí jinou chodbu.

Seznam Navstivene je jako klubíčko nití, které si průzkumník odmotává, aby věděl, kudy už šel, a nechodil v kruzích.

Klíčový koncept: Stavový prostor

Představte si všechny možné kombinace poloh (stavy) jako body na mapě. Tahy jsou cesty mezi nimi. Některé body jsou "smrtící" (vlk sežere kozu). Úkolem Prologu je najít cestu z bodu Start do bodu Cíl, která neprochází žádným smrtícím bodem a nechodí v kruzích.

Otázky k zamyšlení

  1. Proč musíme v predikátu cesta používat seznam Navstivene? Co by se stalo, kdybychom ho tam neměli? (Převozník by mohl jezdit tam a zpět donekonečna).
  2. Kolik existuje celkem možných stavů? (4 položky, každá 2 možnosti = 2^4 = 16 stavů). Kolik z nich je bezpečných?
  3. Jak by se změnil program, kdyby loďka uvezla převozníka a DVA pasažéry?

🧪 Laboratoř: Misionáři a lidožrouti