Kunskapens byggstenar i Prolog

Medan läsaren förhoppningsvis kan förstå principerna för expertsystem generellt, är det mest lärorikt att se hur kunskapen representeras i ett språk som är specialbyggt för ändamålet. Prolog (Programming in Logic) ett sådant programspråk.

Till skillnad från Python eller Java, där man skriver instruktioner för hur datorn ska göra något, handlar Prolog om att deklarera vad som är sant. Man skapar en kunskapsbas av fakta och regler, och sedan kan man ställa frågor till den.

Låt oss se hur en studievägledare skulle kunna se ut i Prolog.

Fakta

Fakta är grundläggande sanningar i vår kunskapsbas. En fundamental princip för att skapa en användbar modell är att varje påstående tydligt definierar vem eller vad det handlar om. Vi undviker därför "implicita subjekt" och använder istället en struktur som liknar en enkel mening: relation(subjekt, objekt).

% Fakta om olika studenters intressen och meriter.
% Vi definierar varje person för tydlighetens skull.
student(anna).
student(bertil).

% Intressen
har_intresse(anna, kreativitet).
har_intresse(anna, problemlösning).
har_intresse(bertil, problemlösning).

% Styrkor
har_styrka(anna, matematik).
har_styrka(bertil, biologi).

% Läsning
har_läst(anna, matte_4).
har_läst(anna, fysik_2).
har_läst(anna, kemi_1).
har_läst(bertil, matte_3).

% Ogillar
ogillar(anna, långa_labbdagar).
% Notera: Bertil ogillar alltså inte långa labbdagar.

Regler

Regler är den verkliga "intelligensen". De låter systemet dra nya slutsatser baserat på kända fakta. En regel i Prolog har formen Huvud :- Kropp. och kan läsas som "Huvudet är sant OM Kroppen är sann."

Eftersom våra fakta inkluderar subjekt, måste våra regler också göra det. Vi använder variabler (som börjar med stor bokstav, t.ex. Person) för att skapa generella regler som kan appliceras på vilken student som helst.

Enkel Regel (OM...)

En rekommendation baseras på ett villkor för en specifik person.

% Rekommendera Arkitektprogrammet till en Person OM den Personen har ett intresse för kreativitet.
rekommendation(Person, arkitektprogrammet) :-
    har_intresse(Person, kreativitet).

Regler med AND ( , )

Ofta krävs flera villkor om samma person.

% Rekommendera Civilingenjör i Datavetenskap till en Person OM den Personen
% har ett intresse för problemlösning OCH är behörig till en ingenjörsutbildning.
rekommendation(Person, civilingenjör_datavetenskap) :-
    har_intresse(Person, problemlösning),
    behörig_till_ingenjör(Person).

Regler med NOT ( + )

Vi kan också kräva att ett visst faktum om en person inte är sant.

% Rekommendera Kandidatprogrammet i Biologi till en Person OM den Personens starkaste
% ämne är biologi AND det INTE är sant att den Personen ogillar långa labbdagar.
rekommendation(Person, kandidat_biologi) :-
    har_styrka(Person, biologi),
    \+ ogillar(Person, långa_labbdagar).

Regler med OR ( ; )

Ibland kan ett mål uppnås på flera olika sätt. Denna regel är en "hjälpregel" som kontrollerar en persons behörighet.

% En Person är behörig till civilingenjörsutbildning OM den Personen har läst matte 4, fysik 2 och kemi 1
% ELLER om den Personen har läst de gamla kurserna (matte_e, fysik_b och kemi_a).
behörig_till_ingenjör(Person) :-
    (har_läst(Person, matte_4), har_läst(Person, fysik_2), har_läst(Person, kemi_1)) ;
    (har_läst(Person, matte_e), har_läst(Person, fysik_b), har_läst(Person, kemi_a)).

Hur man använder kunskapsbasen

Med denna struktur kan vi ställa specifika frågor (queries).

Fråga: Är det sant att Anna har intresset kreativitet?
?- har_intresse(anna, kreativitet).
Svar: true.
Fråga: Vilka program rekommenderas för Anna?
?- rekommendation(anna, Program).
Svar:
Program = arkitektprogrammet ;
Program = civilingenjör_datavetenskap ;
false.
Prolog hittar alla rekommendationer som matchar Annas profil och returnerar false när inga fler finns.
Fråga: Vilka personer rekommenderas till kandidatprogrammet i biologi?
?- rekommendation(Person, kandidat_biologi).
Svar:
Person = bertil.
Regeln lyckas för Bertil eftersom har_styrka(bertil, biologi) är sant och ogillar(bertil, långa_labbdagar) inte kan bevisas vara sant.
Regeln misslyckas för Anna.
Fråga: Ge mig en lista över alla rekommendationer för alla studenter. ?- rekommendation(Person, Program).
Svar:
Person = anna, Program = arkitektprogrammet ;
Person = bertil, Program = kandidat_biologi ;
Person = anna, Program = civilingenjör_datavetenskap ;
false.

Såhär skulle det kunna se ut att bygga ett expertsystem. Genom att konsekvent definiera kunskap med en subjekt-relation-objekt-struktur skapar vi en modell av världen som är logisk, skalbar och kan besvara komplexa frågor på ett meningsfullt sätt.

Optimering och bio-inspirerade algoritmer

Ibland är vi inte intresserade av vägen till målet, utan bara av själva målet. Tänk dig att du ska packa en ryggsäck så effektivt som möjligt (Knapsack problem), eller schemalägga lektioner så att inga krockar sker. Det spelar ingen roll "vilken väg" du tog för att komma fram till lösningen; det enda som räknas är hur bra lösningen är.

För dessa problem använder vi optimeringsalgoritmer. Många av de mest kraftfulla är inspirerade av naturen och fysiken.

Simulated Annealing (simulerad avsvalning)

Tänk dig att du står på toppen av ett bergigt landskap i tjock dimma. Ditt mål är att hitta den absolut lägsta punkten i hela landskapet (globalt minimum). En enkel strategi vore att alltid gå neråt (Hill Climbing). Problemet är att du snabbt fastnar i en liten grop (lokalt minimum) som inte alls är den djupaste punkten, men eftersom alla vägar därifrån leder uppåt, tror algoritmen att den är klar.

Simulated Annealing löser detta genom att hämta inspiration från metallurgi. När man smider metall värmer man upp den så att atomerna kan röra sig fritt, och kyler sedan ner den långsamt så att de kan hitta en stabil kristallstruktur.

Algoritmen fungerar likadant:

Hög temperatur: I början tillåter algoritmen sig själv att ta "dåliga" beslut (gå uppåt i landskapet). Detta gör att den kan hoppa ur små gropar.
Avsvalning: Allt eftersom tiden går sänks "temperaturen". Algoritmen blir mer och mer kräsen och accepterar färre dåliga steg.
Frysning: Till slut beter den sig som vanlig Hill Climbing och finjusterar bara lösningen i det område den landat i.

import math
import random

def simulated_annealing(objective_function, bounds, n_iterations, step_size, temp):
    # Starta slumpmässigt
    best = bounds[0] + (bounds[1] - bounds[0]) * random.random()
    best_eval = objective_function(best)
    curr, curr_eval = best, best_eval

    for i in range(n_iterations):
        # Ta ett steg
        candidate = curr + random.gauss(0, 1) * step_size
        # Håll oss inom gränserna
        candidate = max(bounds[0], min(bounds[1], candidate))
        candidate_eval = objective_function(candidate)

        # Ska vi acceptera den nya punkten?
        diff = candidate_eval - curr_eval
        t = temp / float(i + 1)

        # Acceptera om bättre, ELLER om turen (Metropolis-kriteriet) tillåter det
        if diff < 0 or random.random() < math.exp(-diff / t):
            curr, curr_eval = candidate, candidate_eval
            # Spara om det är det bästa vi någonsin sett
            if candidate_eval < best_eval:
                best, best_eval = candidate, candidate_eval
                print(f"Nytt rekord vid iteration {i}: x={best:.4f} f(x)={best_eval:.4f}")

    return [best, best_eval]

# Testa på funktionen x^2 (enkelt)
# Målet är att hitta x där x^2 är lägst (vilket är x=0)
result = simulated_annealing(lambda x: x**2, [-5, 5], 1000, 0.1, 10)

Evolutionära algoritmer (genetiska algoritmer)

Varför designa en lösning när man kan odla den? Evolutionära algoritmer härmar det naturliga urvalet. Istället för att förbättra en lösning, arbetar man med en hel population av lösningskandidater.

Processen imiterar biologisk evolution:

Population: Skapa 100 slumpmässiga lösningar (t.ex. slumpmässiga scheman).
Fitness (Urval): Testa hur bra varje lösning är. De sämsta dör ut.
Crossover (Parning): De bästa lösningarna får "barn". Man tar delar från Förälder A och delar från Förälder B för att skapa en ny lösning.
Mutation: För att införa variation och inte fastna, ändrar man slumpmässigt någon liten detalj i några barn (t.ex. flyttar en lektion).
Upprepa: Kör detta i tusen generationer.

Resultatet är ofta överraskande effektivt. NASA har använt detta för att designa antenner som ingen människa hade kunnat räkna ut, men som "evolverades" fram för att vara optimala.

import random
import string

mål = "HELLO WORLD"
population_storlek = 100
mutation_rate = 0.01

def fitness(individ):
    # Poäng = antal rätt bokstäver på rätt plats
    return sum(1 for a, b in zip(individ, mål) if a == b)

def skapa_individ():
    return ''.join(random.choice(string.ascii_uppercase + " ") for _ in range(len(mål)))

def crossover(p1, p2):
    split = random.randint(0, len(mål))
    return p1[:split] + p2[split:]

def mutera(individ):
    lista = list(individ)
    for i in range(len(lista)):
        if random.random() < mutation_rate:
            lista[i] = random.choice(string.ascii_uppercase + " ")
    return "".join(lista)

# Huvudloop
population = [skapa_individ() for _ in range(population_storlek)]

for generation in range(1000):
    population = sorted(population, key=fitness, reverse=True)

    if fitness(population[0]) == len(mål):
        print(f"Generation {generation}: {population[0]} (KLAR!)")
        break

    if generation % 10 == 0:
        print(f"Generation {generation}: {population[0]}")

    # Nästa generation: De bästa överlever + barn
    nästa_gen = population[:10] # Elitism (spara de 10 bästa)

    while len(nästa_gen) < population_storlek:
        p1, p2 = random.choice(population[:50]), random.choice(population[:50])
        barn = mutera(crossover(p1, p2))
        nästa_gen.append(barn)

    population = nästa_gen

Swarm Intelligence (svärmintelligens)

En myra är inte smart. Men en myrstack är genialisk. Swarm Intelligence bygger på idén att komplext, intelligent beteende kan uppstå ur interaktionen mellan många enkla individer som följer enkla regler (utan någon central ledare).

Ant Colony Optimization (ACO): Inspirerat av hur myror hittar kortaste vägen till mat genom att lägga ut doftspår (feromoner). Används för att optimera rutter för lastbilar och datatrafik.
Particle Swarm Optimization (PSO): Inspirerat av hur fågelflockar rör sig. Varje "partikel" (lösning) flyger genom lösningsrymden och dras mot både sin egen bästa upptäckta plats och flockens bästa plats.

Spelteori

Vad händer om miljön inte är statisk, utan det finns en motståndare som aktivt försöker hindra dig? Välkommen till spelteori.

Min-Max algoritmen

I spel som Schack, tre-i-rad eller Go, där två spelare har perfekt information och motsatta mål, används Min-Max-algoritmen.

Tänk dig ett spelträd där varje gren är ett möjligt drag.

MAX (Du): Vill maximera poängen.
MIN (Motståndaren): Vill minimera din poäng (vilket maximerar hens egen).

Algoritmen simulerar spelet flera drag framåt. När den når botten av sitt sökdjup, utvärderar den hur bra läget är. Sedan backar den uppåt:

Om det är MINs tur, antar algoritmen att motståndaren kommer spela perfekt och välja det drag som är värst för dig.
Om det är MAX tur, väljer algoritmen det drag som är bäst för dig.

Detta skapar en strategi som utgår från "worst-case scenario".

def minimax(bräde, djup, är_max_spelare):
    # Basfall: Om spelet är slut eller maxdjup nått
    resultat = utvärdera(bräde)
    if spelet_slut(bräde) or djup == 0:
        return resultat

    if är_max_spelare:
        bästa_värde = -float('inf')
        for drag in möjliga_drag(bräde):
            värde = minimax(gör_drag(bräde, drag), djup - 1, False)
            bästa_värde = max(bästa_värde, värde)
        return bästa_värde
    else:
        bästa_värde = float('inf')
        for drag in möjliga_drag(bräde):
            värde = minimax(gör_drag(bräde, drag), djup - 1, True)
            bästa_värde = min(bästa_värde, värde)
        return bästa_värde

Alpha-Beta Pruning

Min-Max är bra men långsam eftersom spelträd växer explosivt. Alpha-Beta Pruning är en optimering som gör det möjligt att "klippa bort" (prune) grenar som inte behöver undersökas.

Idén är enkel: Om du har hittat ett drag som är "tillräckligt bra", och du sedan börjar undersöka ett annat drag och ser att motståndaren har ett motdrag som gör det alternativet katastrofalt dåligt för dig – då behöver du inte fortsätta undersöka resten av det dåliga alternativet. Du vet redan att du aldrig kommer välja den vägen. Det är "slöseri med tid" att se exakt hur dåligt det blir.

Detta var tekniken bakom Deep Blue, datorn som slog världsmästaren Garry Kasparov i schack 1997.

Gamebots

Idag används sällan ren Min-Max i komplexa spel som StarCraft eller Dota 2. Där är tillståndsrummet för stort och informationen ofullständig (Fog of War). Moderna Gamebots kombinerar ofta klassiska sökmetoder och tillståndsmaskiner (State Machines) med modern Maskininlärning (Reinforcement Learning) för att skapa agenter som kan reagera dynamiskt.

Övningar

Övning 1: Bygg en AI-Studievägledare (SYV) i Prolog

Syfte: Att ge en praktisk förståelse för hur man representerar kunskap och logik i Prolog. Vi bygger ett komplett expertsystem från grunden som kan ge programrekommendationer till olika elever baserat på deras unika profiler.

Del 1: Sätt Upp Din Kunskapsbas

Gå till SWISH: Öppna SWISH (SWI-Prolog for SHaring) i din webbläsare.

Klistra in Koden: Klistra in hela kodblocket nedan i kodfönstret. Koden innehåller en mall för elevprofiler (fakta) och en uppsättning färdiga rekommendationsregler.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% DEL 1: FAKTA (KUNSKAPSBASEN)
%
% Här definierar vi all vår kunskap om eleverna. För att Prolog ska fungera
% korrekt måste alla fakta för samma relation (t.ex. alla 'person') stå
% tillsammans i en sammanhängande block.
%
% UPPGIFT: Lägg till fakta för dig själv eller en påhittad person i varje
% relevant block nedan. Följ kommentarerna.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% -- Steg 1: Definiera alla personer --
% Lägg till en rad för din person här. Använd små bokstäver.
% Exempel: person(namn).
person(anna).
person(bertil).

% -- Steg 2: Definiera egenskaper --
% Lägg till din persons egenskaper. Exempel: kreativ, analytisk, nyfiken.
% Exempel: har_egenskap(namn, kreativ).
har_egenskap(anna, kreativ).
har_egenskap(bertil, analytisk).

% -- Steg 3: Definiera intressen --
% Lägg till din persons intressen. Exempel: design, juridik, problemlösning.
% Exempel: har_intresse(namn, problemlösning).
har_intresse(anna, design).
har_intresse(anna, problemlösning).
har_intresse(bertil, juridik).

% -- Steg 4: Definiera mål och planer --
% Lägg till din persons mål. Exempel: studera_vidare, jobba_inom_handel.
% Exempel: har_mål(namn, studera_vidare).
har_mål(anna, studera_vidare).
har_mål(bertil, jobba_inom_handel).

% -- Steg 5: Definiera betyg --
% Lägg till din persons betygssnitt och antal meritkurser.
% Exempel: betygssnitt(namn, 18.5).
% Exempel: meritkurser(namn, 3).
betygssnitt(anna, 19.5).
meritkurser(anna, 2).
betygssnitt(bertil, 17.0).
meritkurser(bertil, 1).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% DEL 2: REGLER (SLUTLEDNINGSMOTORN)
%
% Dessa regler använder informationen från fakta-delen för att dra slutsatser.
% En regel har formen: Huvud :- Kropp.
% Det läses: "Huvudet är sant OM Kroppen är sann."
% Variabler (ord med stor bokstav) kan matcha vilket värde som helst.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Regel för Teknikprogrammet: Kräver kreativitet ELLER intresse för design.
rekommendera(Person, teknikprogrammet) :-
    har_egenskap(Person, kreativ);
    har_intresse(Person, design).

% Regel för Ekonomiprogrammet: Kräver intresse för juridik ELLER en plan att jobba inom handel.
rekommendera(Person, ekonomiprogrammet) :-
    har_intresse(Person, juridik);
    har_mål(Person, jobba_inom_handel).

% Regel för Naturvetenskapsprogrammet: Kräver att personen är analytisk OCH vill studera vidare.
rekommendera(Person, naturvetenskapsprogrammet) :-
    har_egenskap(Person, analytisk),
    har_mål(Person, studera_vidare).

% Regel för Läkarprogrammet: Kräver ett totalt meritvärde på minst 21.5.
rekommendera(Person, läkarprogrammet) :-
    total_meritpoäng(Person, Poäng),
    Poäng >= 21.5.

% Hjälpregel för att beräkna total meritpoäng.
% Totala poängen ÄR (is) betygssnittet + (antal meritkurser * 0.5).
total_meritpoäng(Person, Total) :-
    betygssnitt(Person, Snitt),
    meritkurser(Person, Antal),
    Total is Snitt + (Antal * 0.5).

Del 2: Ställ Frågor till Din AI-SYV

När du har fyllt i fakta för din egen person kan du agera användare och ställa frågor (queries) till din AI i frågefönstret längst ner.

Kör programmet: Tryck på "Run".
Ställ frågor: Skriv följande frågor i fönstret och tryck Enter. Om det finns flera svar kan du trycka på Next.
- Vilka program rekommenderas för en specifik person? (Byt ut anna mot namnet på din person) rekommendera(anna, Program).
- Vem kan vi rekommendera ett visst program för? rekommendera(Person, teknikprogrammet).
- Vad är Annas totala meritpoäng? total_meritpoäng(anna, Poäng).
- Visa alla möjliga rekommendationer för alla elever! rekommendera(Person, Program).

Utmaning: Bygg Ut Din AI

Lägg till ett nytt program: Skriv en regel för ett helt nytt program, t.ex. samhällsvetenskapsprogrammet. Vilka krav ska gälla? Kanske har_intresse(Person, samhällsfrågor)?
Lägg till en ny person: Skapa en komplett profil för en vän genom att lägga till fakta i alla relevanta block och se vilka rekommendationer hen får.

Reflektera

Vad är fördelen med att separera fakta (data) från regler (logik)?
Hur skulle du ändra en regel om kraven för ett program ändrades?
Diskutera: Är det ens önskvärt att en SYV fungerar som ett strikt regelbaserat system? Vilka fördelar och nackdelar skulle det ha?

Övning 5: Evolution i Praktiken

Syfte: Att se evolutionära algoritmer i aktion genom att skriva ett program som "avlar fram" en specifik målsträng.

Skapa en fil: genetic_algorithm.py.
Utgå från koden: Använd exempelkoden från avsnittet "Evolutionära Algoritmer" i textboken som bas.
Experimentera:
- Ändra mål till en längre mening. Hur många fler generationer krävs?
- Ändra population_storlek och mutation_rate. Vad händer om mutationen är för hög (t.ex. 0.5)? Vad händer om den är för låg (0.0001)?
- Utmaning: Försök att få algoritmen att fastna i ett lokalt optimum (där den nästan är klar men aldrig hittar den sista bokstaven) genom att göra fitness-funktionen mer straffande för fel.

Övning 6: Oslagbar på Tre-i-rad

Syfte: Att implementera Min-Max-algoritmen för att skapa en oslagbar AI för Tre-i-rad (Tic-Tac-Toe).

Skapa en fil: minimax_tictactoe.py.
Bygg spelet: Skriv funktioner för att:
- Visa brädet (3x3 lista).
- Kolla om någon vunnit.
- Kolla vilka drag som är lediga.
Implementera Min-Max: Använd pseudokoden från avsnittet "Min-Max Algoritmen".
- Låt AI:n vara MAX (X) och du MIN (O).
- Utvärderingsfunktionen (utvärdera(bräde)) ska returnera +10 om AI vinner, -10 om du vinner, och 0 för oavgjort.
Spela: Skriv en loop där du spelar mot din AI. Kan du vinna? (Tips: Om du implementerat rätt är det omöjligt att vinna, bara spela oavgjort).

Fakta​

Regler​

Enkel Regel (OM...)​

Regler med AND ( , )​

Regler med NOT ( + )​

Regler med OR ( ; )​

Hur man använder kunskapsbasen​

Optimering och bio-inspirerade algoritmer​

Simulated Annealing (simulerad avsvalning)​

Evolutionära algoritmer (genetiska algoritmer)​

Swarm Intelligence (svärmintelligens)​

Spelteori​

Min-Max algoritmen​

Alpha-Beta Pruning​

Gamebots​

Övningar​

Övning 1: Bygg en AI-Studievägledare (SYV) i Prolog​

Del 1: Sätt Upp Din Kunskapsbas​

Del 2: Ställ Frågor till Din AI-SYV​

Utmaning: Bygg Ut Din AI​

Övning 5: Evolution i Praktiken​

Övning 6: Oslagbar på Tre-i-rad​