Mikor lehet végre Nekem is saját AI-m?

Mutatok egy egyszerű példát. A feladat legyen az, hogy van három korsód, egy 5 literes, egy 3 literes és egy két literes. Az 5 literes van tele sörrel, és azt kell elérni, hogy az egyik korsóban 4 liter legyen.

Kezdésnek ezt a problémát valami olyan formába kéne önteni, amit meg lehet a géppel etetni. Szóval kezdjük azzal, hogy milyen kérdéseket tudunk feltenni (ezeket jelöljük el valami módon), és azokra milyen válaszokat tudunk adni:

H1) Hány liter sör van az 5 literes korsóban? {0, 1, 2, 3, 4, 5}

H2) Hány liter sör van a 3 literes korsóban? {0, 1, 2, 3}

H3) Hány liter sör van a 2 literes korsóban? {0, 1, 2}

Jól fog jönni majd később, ha a válaszok halmazait bepakoljuk egy tömbbe: H = [H1, H2, H3]

Tisztázzuk, hogy mi lesz egy állapot. Egy állapot nem más, mint hogy mindhárom kérdésre a rá adható lehetséges válaszok közül válaszolunk valamit. Ezt egy kicsit pontosabban megfogalmazva, vesszük a H1...Hn halmazok Descartes-szorzatát:

ÖsszesÁllapot = H1 x H2 x H3

Ez alapján egy állapot lehet ez: (5, 0, 0), ami azt jelenti, hogy az 5 literesben 5 liter sör van, a másik kettő üres.

De ez tartalmazhat lehetetlen állapotokat is: (5, 3, 2), ami azt jelenti, hogy mindhárom korsó tele van (ami azért nem lehetséges, mert egen-földön 5 liter sörünk van, nem több, nem kevesebb).

Szóval ezekre rá kell ereszteni egy szűrést, hogy megkapjuk csak a lehetséges állapotok halmazát.

Állapotok = {(a1, a2, a3) eleme az ÖsszesÁllapotnak | a1+a2+a3=5}

Ez azt jelenti, hogy azokat az állapotokat válasszuk ki, ahol a korsókban összesen 5 sör van.

Most, hogy idáig eljutottunk, azt kell tudnunk, hogy miből indulunk ki, és mit akarunk elérni. Előbbit általában konkrétan tudjuk, ezt hívjuk kezdőállapotnak. Utóbbit nem biztos, hogy konkrétan tudjuk, de azt biztosan meg tudjuk fogalmazni, hogy mikor érjük el a célunkat; ezek lesznek a célállapotok.

Kezdő = (5, 0, 0) az Állapotok halmazból

Cél = {(a1, a2, a3) az Állapotok halmazból | a1 = 4}

Magyarul azokat az állapotokat tekintjük célállapotnak, ahol az 5 literes korsóban 4 liter sör van.

Már majdnem kész vagyunk, csupán annyi van hátra, hogy azt leírjuk, hogy milyen cselekvéseket végezhetünk a probléma megoldásához (ezeket hívjuk majd operátoroknak). Ilyen művelet lesz az Átöntés.

Átöntés[Honnan, Hová](Állapot) { //A Honnan-Hová indexek, ahol 0 az 5 literes, 1 a három literes, 2 a két literes korsó)

.. ÚjÁllapot = Állapot //Ha csinálunk valamit, egy új állapot fog előállni

.. //Először is tudnunk kell, mennyi folyadékot önthetünk át.

.. ÁtöntöttFolyadék = minimum(Állapot[Honnan], Állapot[Hová]);

.. ÚjÁllapot[Honnan] = ÚjÁllapot[Honnan] - ÁtöntöttFolyadék

.. ÚjÁllapot[Hová] = ÚjÁllapot[Hová] + ÁtöntöttFolyadék

.. Az operátor eredménye az ÚjÁllapot

}

Ezt a leírást nevezzük az operátor hatásdefiníciójának.

Persze nem minden esetben végezhetünk átöntést. Ahonnan átöntünk, az nem lehet üres, és ahová átöntünk, az nem lehet tele. Ez lesz az operátor értelmezési tartománya.

Dom Átöntés[Honnan, Hová] = {Állapot az Állapotok halmazból | Állapot[Honnan] != 0 ÉS Állapot[Hová] != maximum(H[Hová])}

A != azt jelenti, hogy nem egyenlő.

Ezt a nagy maszlagot nevezzük állapottér-reprezentációnak.

Most, hogy a problémát leírtuk a gépnek, nézhetünk valamilyen megoldáskeresőt, ami utat keres a Kezdő-től valamely Cél-ig. Erre van sokféle, például ez a körmentesített backtrack:

A kereső adatbázisa: Az aktuális út, amely a Kezdő-ből indul és a végén az aktuális állapot szerepel. Csúcsonként tároljuk:

- Az állapotot

- A szülő állapotot

- Az operátort, amellyel a szülő állapotból a mostani állapotba jutottunk

- A ki nem próbált, de alkalmazható operátorokat

Műveletei:

- Az állapottér-reprezentáció operátorai

- Visszalépés: Eltávolítjuk az út végéről az aktuális csúcsot.

És így működik:

1) Beizzítjuk az adatbázist így:

Az állapot a Kezdő; Nincs szülő állapot; Nincs előállító operátor; Az összes alkalmazható operátor (ezért kellett meghatározni az értelmezési tartományát az operátoroknak)

2) Célállapot az aktuális állapot?

Ha igen, sikeresen véget ér az algoritmus és megoldás állt elő.

Ha nem, lépünk tovább.

3) Van még ki nem próbált, de alkalmazható operátor?

Ha igen, választunk és alkalmazunk egyet (eltávolítva az operátort az alkalmazhatóak közül). Ha az újonnan előállt állapot már szerepel az úton, visszalépés és újra a 3. lépés jön.

Ha nem, lépünk tovább.

4) Tudunk még hová visszalépni (nem egyelemű-e az aktuális út)?

Ha tudunk és nem egyelemű az aktuális út, akkor visszalépést alkalmazunk, majd folytatjuk a 3. lépéstől.

Ha nem tudunk visszalépni, akkor nincs megoldása a problémának.

Ha ezt leprogramozod, meg is van az első mesterséges intelligenciád.