Iskazna logika omogućava predstavljanje znanja tako što rečenice označava simbolima i pridružuje im logičku vrednost Tačno ili Netačno. Pridruživanje vrednosti vrši se opažanjem okruženja.
Iskazna logika omogućava zaključivanje nad činjenicama time što ih kombinuje logičkim operacijama, i prethodno smo videli neke načine zaključivanja i algoritme koji pomažu automatizaciji zaključivanja.
Pokazaćemo da iskazna logika može da se upotrebi za implementaciju veštačko-inteligentnog sistema na primeru agenta-bota za igranje igre Vumpus.
Igru možemo da probamo ovde: https://thiagodnf.github.io/wumpus-world-simulator/
Dodatno na ovu temu ovde: https://www.geeksforgeeks.org/propositional-logic-based-agent/
Svet Vumpusa
Svet vumpusa sastoji se od mxn pećina povezanih prolazima levo-desno-gore-dole. Igrač ulazi u prvu pećinu. U nekoj pećini nalazi se zlato – igrač to zna ako uđe u tu pećinu (vidi zlato). U nekim pećinama nalaze se provalije. Igrač to zna tako što upadne u provaliju ako uđe u tu pećinu. Oko provalije pirka vetar, koji se oseća u susednim pećinama. Ako igrač oseti vetar to znači da je u nekoj od susednih pećina provalija. U nekoj od pećina nalazi se vumpus. Igrač to zna ako uće u tu pećinu (pojede ga vumpus). Vumpus smrdi i oseća se u susednim pećinama. Ako igrač oseti smrad to znači da je u nekoj od susednih pećina vumpus. Igrač može da ubaci bombu u susednu pećinu, i ako je vumpus u toj pećini poginuće. Poginuće vumpusa je veoma glasno i čuje se svuda okolo tako da igrač zna da li je ubio vumpusa ili ne. Igrač ima samo jednu bombu.
Neki kažu da je vumpus u stvari mnogo smoren jer sedi tu i smrdi i da kad mu naiđe društvo silno se obraduje i onda uhvati tog naišlog mučenika da igraju šah u beskonačno, pa je cilj igre uzeti zlato i ne ubiti vumpusa (greota). Drugi kažu da vumpus ne sedi i smrdi nego šeta okolo i smrdi svud redom. Ovo dodatno otežava igru. Neki igrači ponesu 3 bombe. Priča se i da ima nekoliko vumpusa (svi smrde podjednako). Sve su ovo varijante igre, ali ćemo ovde da se držimo one osnovne: tabla 4x4, jedna bomba, vumpus sedi i smrdi.
Probajte: https://thiagodnf.github.io/wumpus-world-simulator/
Predstavljanje znanja
Svako polje možemo da predstavimo logičkom promenljivom-parametrom koja ima vrednost smrdi-ne smrdi, piri vetar-ne piri vetar, ima jarugu-nema jarugu, ima zlato-nema zlato, sedi vumpus-ne sedi vumpus.
Ovde vidimo pet različitih osobina koje jedno polje može da ima (ili nema), pa ćemo ih predstaviti zasebno, kao iskaze S (smrdi), P (piri vetar), J (jaruga), Z(zlato), V (vumpus).
Umesto da pišemo 16 slova za svako polje, koristićemo koordinate, od 1,1, gore levo.
Tako možemo da izjavimo sledeće tačne iskaze:
S1,1 = T
V1,2 = T
J3,2 = T
P1,3 = T
Z2,2 = T
itd.
Stvar je u tome što igrač-agent ne zna celu mapu nego je otkriva, pa će i njegovo znanje o svetu biti delimično.
Pored ovih pet imamo i trenutnu poziciju igrača I a možemo da pamtimo da li je igrač posetio neko polje (na tom polju nije ni vumpus ni jaruga) U.
Pravila odlučivanja i izvođenja novih znanja
Vumpus smrdi svuda okolo pa možemo da napišemo sledeći iskaz:
S1,2 AND S2,1 AND S3,1 AND S1,3 -> V2,2
Ne moramo da znamo sva 4 okolna polja, dovoljno je i 3, tako imamo četiri moguće varijante:
S1,2 AND S2,1 AND S3,1 -> V2,2
S1,2 AND S2,1 AND S1,3 -> V2,2
S1,2 AND S3,1 AND S1,3 -> V2,2
S2,1 AND S3,1 AND S1,3 -> V2,2
A ako znamo za dva polja, onda vumpus može da bude ovde ili onde, ali nam i to znači jer možda znamo da na jednom od ta dva moguća polja vumpus nije, pa ćemo sistemom eliminacije zaključiti gde je:
Sx,y AND Sx+1,y-1 -> Vx,y-1 OR Vx+1,y
A ako znamo za samo jedno polje, onda vumpus može da bude na bilo kom od okolnih 4 polja, tačnije mora da bude na jednom od njih:
Sx,y -> Vx,y-1 OR Vx+1,y OR Vx,y+1 OR Vx--1,y
Odnosno, preciznije:
Sx,y -> (Vx,y-1 AND NOT Vx+1,y AND NOT Vx,y+1 AND NOT Vx--1,y)
OR (NOT Vx,y-1 AND Vx+1,y AND NOT Vx,y+1 AND NOT Vx--1,y)
OR (NOT Vx,y-1 AND NOT Vx+1,y AND Vx,y+1 AND NOT Vx--1,y)
OR (NOT Vx,y-1 AND NOT Vx+1,y AND NOT Vx,y+1 AND Vx--1,y)
Pa ako dodamo još neka znanja o svetu imamo:
Sx,y AND Sx+1,y-1 AND NOT(Vx,y-1) -> Vx+1,y
Sx,y AND Sx+1,y-1 AND NOT(Vx+1,y) -> Vx,y-1
a može i ovo, ako pamtimo posećena polja (na njima nije vumpus, jer sedi u mestu):
Sx,y AND Sx+1,y-1 AND Ux,y-1 -> Vx+1,y
Sx,y AND Sx+1,y-1 AND Ux+1,y -> Vx,y-1
Isto ovo možemo da primenimo i za jarugu.
Dalje, znamo da vumpus i jaruga ne mogu biti na istom polju, pa otud:
Jx,y -> NOT(Vx,y)
Zatim ako polje smrdi tu nije vumpus:
Sx,y -> NOT(Vx,y)
Ako piri vetar tu nije jaruga:
Px,y ->NOT(Jx,y)
I eto nam skup pravila, predstavljen logičkim iskazima.
U ovo još umešamo kontrapoziciju, inverziju i konverziju, i moduse zaključivanja i možemo i da izvodimo nova pravila na osnovu ovih.
Otkrivanjem činjenica-vrednosti za polja koja igrač posećuje-opažanjem sveta agenta, dopunjujemo bazu znanja. Zatim, na osnovu baze znanja i pravila izvodimo nova znanja-zaključke, koje dodajemo u bazu znanja, i to radimo dok god možemo. Kada iscrpimo to (saznamo maksimalno moguće o svetu u tom novom potezu) onda biramo šta ćemo sledeće da radimo: pucamo u vumpusa, pređemo na sledeće bezbedno polje, rizikujemo. I izbor akcija možemo da formulišemo kao logičke iskaze, na osnovu znanja koja agent poseduje i njegove trenutne pozicije i raspoloživih akcija.
Matricama 4x4 predstavili smo svaku vrstu činjenica posebno, u nekom trenutku igre, onoliko koliko je agent do tada uspeo da stvori znanje o svetu oko sebe. Da li na osnovu ovakve baze znanja možemo da odredimo gde je vumpus? Šta sve možemo da izvedemo od zaključaka-novih znanja?
Koordinate idu od 1,1 gore levo. Prva koordinata je red, druga je kolona.
Na osnovu pravila izvodimo zaključke i dopunjavamo sliku sveta koliko je moguće.
Uzmimo P1,2 = 1 (piri vetar).
Na osnovu pravila za položaj jaruge imamo sledeće tri (ovo je ivično polje pa jaruga ne može da bude iznad njega) situacije od kojih samo jedna može biti tačna, a ako ubacimo one činjenice koje znamo možemo i da za neke od njih izračunamo vrednosti (dovoljno je da u konjukciji jedan član bude 0 da bismo znali da je cela konjukcija 0):
J1,1 AND P1,2 AND P2,1 = J1,1 AND 1 AND 0 = 0
J1,3 AND P1,2 AND P2,1 AND P1,4 = J1,3 AND 1 AND P2,3 AND P1,4 = ?
J2,2 AND P1,2 AND P2,1 AND P2,3 AND P3,2 = 0 AND 1 AND 0 AND P2,3 AND P3,2 = 0
Odavde smo dobili nov zaključak da J1,1=0, koji upisujemo u bazu znanja (matricu J).
U širem obliku imamo pravilo po kome znamo da je tačno jedno od ova tri polja polje sa jarugom (ako vetar piri, jaruga je negde okolo), pa imamo nešto oblika:
(J1,1 AND NOT J1,3 AND NOT J2,2)
OR (NOT J1,1 AND J1,3 AND NOT J2,2)
OR (NOT J1,1 AND NOT J1,3 AND J2,2)
pa ako ubacimo ovde znanje koje trenutno imamo (prošireno zaključivanjem od malopre):
(0 AND NOT J1,3 AND NOT 0)
OR (NOT 0 AND J1,3 AND NOT 0)
OR (NOT 0 AND NOT J1,3 AND 0)
radimo zamenu negacije (not 0 = 1, not 1 = 0)
= (0 AND NOT J1,3 AND 1)
OR (1 AND J1,3 AND 1)
OR (1 AND NOT J1,3 AND 0)
uklanjamo 1 iz konjukcije
= (0 AND NOT J1,3)
OR (J1,3)
OR (NOT J1,3 AND 0)
uklanjamo konjukcije u kojima se nalazi konjukt 0
= (J1,3)
i dolazimo do zaključka da je iskaz zadovoljiv jedino kada je J1,3 = 1, pa otud izvodimo novo znanje o tom polju, otkrivamo da se jaruga nalazi na polju 1,3, i to upisujemo u bazu znanja.
Pošto smo proširili bazu znanja probaćemo da izvedemo još neka nova znanja.
Po pravilu da oko jaruge piri vetar imamo
J1,3 -> P1,2 AND P2,3 AND P1,4
Pošto je J1,3=1 moraju i P1,2=1 P2,3=1 P1,4=1. Kod P1,2 to već jeste slučaj (da nije imali bismo ozbiljan problem, konflikt u zaključivanju), a za P2,3 i P1,4 imamo novo znanje.
Tablice sada izgledaju ovako:
Po istom pristupu možemo da probamo da zaključimo gde je vumpus.
Imamo S2,2 = 1 i S3,3 = 1
Po pravilu smrdenja imamo Sx,y AND Sx+1,y+1 -> Vx+1,y OR Vx,y+1 a pošto imamo samo jednog vumpusa dodajemo i (Vx+1,y AND NOT Vx,y+1) OR (Vx+1,y AND NOT Vx,y+1) pa je celo pravilo zapravo:
Sx,y AND Sx+1,y+1 -> (Vx+1,y OR Vx,y+1) AND ( (Vx+1,y AND NOT Vx,y+1) OR (Vx+1,y AND NOT Vx,y+1) )
Pošto ne možemo da odredimo ništa iz ovoga, probaćemo pretpostavkama, da li je neko od ovih polja “oborivo”. Imamo dva polja, pretpostavićemo za jedno, ako se pokaže da tu ne može da bude, onda mora da bude na drugom.
V3,2 -> S3,1 AND S2,2 AND S3,3 AND S4,2
V3,2 -> 0 AND 1 AND 1 AND 0
V3,2 -> 0
Odakle sa modus tollens zaključujemo da V3,2 = 0 i to dodajemo u bazu znanja.
Na osnovu pravila (V3,2 AND NOT V2,3 ) OR (NOT V3,2 AND V2,3) tj. da vumpus mora da bude na tačno jednom od ova dva polja, dobijamo
(ubacivanje poznatih vrednosti) (0 AND NOT V2,3 ) OR (NOT 0 AND V2,3)
(primena negacije) (0 AND NOT V2,3 ) OR (1 AND V2,3)
(izbacivanje konjukata sa 0) (1 AND V2,3)
(izbacivanje 1 iz konjukcije) (V2,3)
odakle zaključujemo da se vumpus nalazi na polju 2,3.
Baza znanja sada izgleda ovako:
Dalje bismo mogli da proširimo bazu znanja i dodamo i polja gde smrdi. Možemo i da odredimo gde sve nisu jaruge na osnovu toga gde nema vetra. Dalje, zlato svakako nije tamo gde je jaruga, pa i to možemo da dodamo. Sve u svemu, neki maksimum znanja koji možemo da iscrpimo od trenutne situacije je na slici ispod.
I ono što je interesantno, sada možemo da odredimo sledeći potez.
Po pravilu (ako je vumpus ispred igrača i igrač ima bombu, baci bombu na vumpusa) i činjenicama da je igrač na polju 3,3 a vumpus na polju 2,3 tj. da su premise ispunjene, biramo ovu akciju i odlučujemo da je sledeći potez: baci bombu na polje 2,3.
Čuće se aaaaaaaaa, ubismo vumpusa, znamo gde je jaruga, sad možemo dalje da prođemo kroz tablu da bismo našli zlato. Imamo još dva neodređena polja za jarugu 1,4 i 2,4 ali možemo da dođemo na 2,3 i opažanjem da li piri vetar zaključimo da li je na 2,4 jaruga, pa ako nije, prelazimo na polje 2,4 da osetimo da li tu ima vetra, i time upotpunjujemo i znanje o pozicijama svih jaruga na tabli.
Ako do tada nismo našli zlato, krenućemo ka najbližem neposećenom polju, i posetićemo sva neposećena polja kako bismo našli zlato.
Ovo je ugrubo opisan koncept rešenja. Kompletna implementacija je naravno bitno preciznija, ali svakako prati ovde opisane ideje. Implementacija ovakvog bota je interesantan problem za maturski rad.