Kunstmatige intelligentie

Het vak Kunstmatige intelligentie, ook wel AI (van Artificial Intelligence) genoemd, wordt verzorgd door dr. W.A. (Walter) Kosters, geassisteerd door drs. Edgar de Graaf, en wordt in het voorjaar van 2005 gegeven.

Note that the course is given in DUTCH.

Voorjaar 2006: maandagen, 13.45-15.30 uur; data: 6 februari-8 mei (niet: 17 april); zaal 174.

Collegetijden: maandagen, van 11.15 tot 13.00 uur, in zaal 405 van het Snellius, het gebouw van Wiskunde en Informatica, Niels Bohrweg 1, Leiden. Data: 31 januari tot en met 21 maart en 4 april tot en met 2 mei 2005 (dus niet op 28 maart 2005).

Het vak levert 6 (zes) ECTS punten op in het nieuwe systeem (vanaf 2002/2003; voorheen waren dit 4 (vier) "oude" studiepunten). Naast het voldoende maken van het tentamen is het hiervoor ook nodig het practicum voldoende te hebben. Het eindcijfer wordt voor 99% bepaald door het tentamencijfer, eventueel enigszins afgerond in de richting van het gemiddelde practicumresultaat, mits beide voldoende zijn. Ten einde het practicum voldoende te maken, moeten de vier opgaven alle met minstens een 6 of een "OK" beoordeeld zijn.
Het college is in eerste instantie bedoeld voor derde- en hogerejaars studenten Informatica, maar is ook interessant voor andere belangstellenden; voorkennis van de programmeertaal C++ is sterk aan te raden.

Tentamendata

De tentamendata in 2005 zijn:

Alle cijfers (college voorjaar 2005) zijn te zijner tijd hier te vinden. Zie ook vroeger; in het bijzonder vorig jaar (2004).

Materiaal

BOEK RN Gebruik wordt gemaakt van het boek Artificial intelligence, A modern approach van Stuart J. Russell en Peter Norvig, second edition, Prentice Hall, 2003. Het kost in de winkel circa 60 euro; soms is de versie met slappe kaft goedkoper.
In het bijzonder worden uit dit boek de volgende hoofdstukken behandeld: 1 (Introduction; lezen), 2 (Intelligent agents; lezen), 3 (Solving problems by searching; uitgebreid), 4 (Informed search and exploration; uitgebreid), 5 (Constraint satisfaction problems; uitgebreid), 6 (Adversarial search; uitgebreid), 7 (Logical agents; lezen, met name Wumpus), 8 (First order logic; lezen, met name Wumpus), 14 (Probabilistic reasoning; uitgebreid; lees ook 13, Uncertainty), 18 (Learning from observations; uitgebreid, met name beslissingsbomen), 19.1 (Knowledge in learning; lezen), 20.5 (Statistical learning methods; uitgebreid: neurale netwerken), 21.1,2,3 (Reinforcement learning, geillustreerd met 17.1,2; uitgebreid, aangevuld met 4.3 Genetische algoritmen) en 25 (Robotics; lezen, + Lego-robots), grotendeels in deze volgorde. Lees ook eens Hoofdstuk 26 (Philosophical foundations).
Daarnaast werd in voorgaande jaren nog speciaal aandacht besteed aan het onderwerp Data mining, maar aangezien er nu een apart derdejaars vak is met die titel ...

Overige literatuur (niet kopen — tenzij je erg veel geld hebt):

Archief

Compilatie 2001/04 (in PDF, 10 pagina's); enkele antwoorden (in PDF).

Er is meer informatie te vinden over het college de afgelopen jaren; hier zijn onder andere nog meer oude tentamens (gefabriceerd door andere docenten!) te bekijken, zoals het redelijk representatieve tentamen van 8 juni 1998 [hiervan NIET Opgave 4] met uitwerking [beide gezipt PostScript]. Ook staan hier alle cijfers vanaf voorjaar 2001.
Let op: vanaf voorjaar 2005 hoort het onderwerp Data mining niet meer bij de tentamenstof.


Het practicum

Voor iedere practicumopgave moeten worden ingeleverd: een minstens drie pagina's (laten we zeggen vijf pagina's, afgezien van de Appendix) tellend verslag in LaTeX (dit is een GROTE tekst in PDF; zie ook hier voor een zeer korte inleiding, en daar voor een langere; of een heel korte zichzelf uitleggende voorbeeldfile), en een werkend programma (digitaal (mailen aan de docent) en uitgeprint in de Appendix van het verslag; stuur geen LaTeX/PS/PDF-files en ook geen executables). Het verslag moet een duidelijke opbouw hebben, bijvoorbeeld:
  1. Inleiding ("dit is de tweede opdracht van het college ...")
  2. Uitleg probleem (plaatje; "de spelregels zijn ...", gebruikte definities)
  3. Theorie ("stelling zegt dat ...")
  4. Aanpak (plaatje; "een drielaags neuraal netwerk ...")
  5. Implementatie ("een dubbel array"; kort)
  6. Experimenten (tabel, grafiek)
  7. Conclusie ("ging fout als de testopstelling niet verlicht was")
  8. Referenties (genummerd; naar alle wordt verwezen; "handleiding Lego-robots ...", "Russell en Norvig ...")
    Een fatsoenlijke referentie ziet er uit als:
    [1] S.J. Russell en P. Norvig, Artificial intelligence, A modern approach, second edition, Prentice Hall, 2003
  9. Appendix: het programma; tip: vervang tabs door spaties, kies kleiner lettertype, en zet het tussen \begin{verbatim} en \end{verbatim}; liefhebbers: gebruik package verbatim en het commando \verbatiminput{eigen.file}
Zie ook diverse opmerkingen.

De deadlines zijn strikt, overleg eventueel met de docent(en). Voor alle opdrachten geldt dat ze nog voorlopig zijn, aanvullingen tijdens het semester zullen zeker voorkomen. Eigen initiatief wordt —na overleg— op prijs gesteld.
De opgaven worden per stuk als volgt beoordeeld: er wordt gekeken naar het verslag en het programma (met name werking en leesbaarheid); originaliteit beinvloedt de eind-afronding. De cijfers zijn hier te vinden (vorig jaar (2004)).
Het practicum bestaat zoals gezegd uit vier opgaven:

  1. Tetris; deadline 21 februari 2005
    Gebruik het C++-voorbeeldprogramma van de website. Dit genereert random Tetris-stukken, die naar beneden vallen. Geheel gevulde regels verdwijnen. Je algoritme moet het zolang mogelijk hier tegen volhouden — als er (gedeeltes van) stukken boven de rand van de "put" uitsteken stopt het proces. Het enige wat het programma moet doen is het kiezen van 1. de oriëntatie van het huidige stuk en 2. de kolom(men) waarin het stuk valt (positie). Er mag — in tegenstelling tot bij het "echte" spel — daarna niet meer geroteerd of geschoven worden. Eventueel mag je informatie over het volgende stuk gebruiken — pas hiertoe het programma zelf aan.
    Er is hier en daar meer informatie over Tetris te vinden.
    Denk bij het verslag ook aan rapportage over experimenten. Geef alleen de aangepaste delen van het C++-programma als Appendix bij het verslag.
    [Met dank aan Joris Huizer; zie ook bastet en tetris in Google:]
    In deze tarball zitten files om steeds (in plaats van random) moeilijke Tetris-stukken aan te bieden. Gebruik patch <change.patch om aitetris.cc iets aan te passen. Compileer bast.cpp en aitetris.cc.
  2. Robotica; deadline 14 maart 2005
    Zie Robot-opgave.
  3. Neuraal netwerk; deadline 11 april 2005
    Schrijf in C++ een neuraal netwerk, dat van een hit op een webserver de status-code (200, 404, ...) voorspelt. Meer informatie hier.
  4. Genetisch algoritme; deadline 2 mei 2005
    Schrijf in C++ een Genetisch algoritme, dat een graafkleuringsprobleem oplost. Meer informatie hier.

De colleges

Tijdens de colleges wordt het volgende behandeld. Het programma is uiteraard voorlopig, zelfs als het semester voorbij is — op deze webpagina is steeds de meest actuele versie te vinden. Voor sheets van voorgaande jaren raadplege men de oude pagina's. Tijdens de colleges vinden ook discussies plaats over de genoemde hoofdstukken van Russell/Norvig. De sheets zijn voornamelijk gebaseerd op die van deze beide heren, en op sheets die vorige docenten fabriceerden.
En voor de liefhebbers: alle 318 sheets (in PDF, 1.6 MB).
Er wordt op het tentamen nog wel eens iets gevraagd wat niet (letterlijk) op de sheets staat ...

  1. maandag 31 januari 2005
    Algemene introductie; het practicum, met name de eerste opgave.
    Hoofdstuk 1 (Introductie) in vogelvlucht, zie de sheets:
        Algemene introductie  |  Introductie
    Leuk leesvoer: Jason Hutchens' "How to pass the Turing test by cheating"
  2. maandag 7 februari 2005
    Hoofdstuk 2 (Intelligente agenten), zie de sheets:
         Intelligente agenten
  3. maandag 14 februari 2005
    Hoofdstuk 3 (Probleemoplossen en zoeken), zie de sheets:
         Probleemoplossen en zoeken
  4. maandag 21 februari 2005
    Robotica, onder meer Lego-robots, zie de handleiding (288 kB, PDF; geschreven door Mark Overmars); lees ook Hoofdstuk 25 (Robotica) van Russell en Norvig. Dit alles ten behoeve van de tweede practicum-opgave. Zie ook de sheets:
         Robotica
    Hoofdstuk 3, vervolg.
    Leuk leesvoer: Rodney Brooks' "Intelligence without representation"
  5. maandag 28 februari 2005
    Hoofdstuk 3, vervolg.
    Hoofdstuk 4 (Gericht zoeken), zie de sheets:
         Gericht zoeken
  6. maandag 7 maart 2005
    Hoofdstuk 4, vervolg.
    Hoofdstuk 5 (Constraint Satisfaction Problemen), zie de sheets:
         CSP's
  7. maandag 14 maart 2005
    Algemene informatie over de derde practicum-opgave; Perl.
    Hoofdstuk 20.5 (Neurale netwerken; voorheen Hoofdstuk 19), zie de sheets:
         Neurale netwerken
  8. maandag 21 maart 2005
    Hoofdstuk 6 (Spel(l)en; in de eerste druk was dit Hoofdstuk 5), zie de sheets:
         Spel(l)en
    Leuk leesvoer: H.J. van den Herik, J.W.H.M. Uiterwijk en J. van Rijswijck, Games solved: Now and in the future, Artificial Intelligence 134 (2002) 277-311 (ophalen vanaf PC binnen universiteit)
  9. maandag 4 april 2005
    Hoofdstukken 7 (Logisch redenerende agenten; voorheen Hoofdstuk 6), 8 (Eerste orde logica; voorheen Hoofdstuk 7) en 10.3, zie de sheets:
         Logische agenten
  10. maandag 11 april 2005
    Algemene informatie over de vierde practicum-opgave.
    Vervolg van vorige keer.
    Hoofdstuk 4.3 (Genetische algoritmen), zie de sheets:
         Genetische algoritmen
  11. maandag 18 april 2005
    Hoofdstuk 18 (Leren van/uit observaties), met name ID3, en Hoofdstuk 19.1, kort; Hoofdstuk 21.1,2,3 (Reinforcement leren, geillustreerd met 17.1,2; kort); zie de sheets:
         Leren
  12. maandag 25 april 2005
    Hoofdstuk 13 (Onzekerheid, vroeger Hoofdstuk 14; kort) en Hoofdstuk 14 (Bayesiaanse netwerken, vroeger Hoofdstuk 15), zie de sheets:
         Bayesiaanse netwerken
  13. maandag 2 mei 2005
    Van alles.
    Oude tentamens, zie het archief, in het bijzonder opgaven 2, 7a/c, 11, 12 en 18 van Compilatie 2001/04 (in PDF, 10 pagina's); enkele antwoorden (in PDF).
Genoemde hoofdstukken komen steeds uit het boek van Russell en Norvig, tweede druk — met dank voor de sheets en de meeste plaatjes.


Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.

27 juni 2005 — http://www.liacs.nl/home/kosters/AI/index.html