Umjetna inteligencija — domaće zadaće (2014/2015)

Zadnja promjena: 16. veljače 2015.  (26. svibnja 2018.)

• Link na forum za kolegij za pregled izabranih zadataka i prijavu.

Domaće zadaće: većina zadataka je iz pretraživanja prostora stanja i igranja igara. Popis s linkovima na literaturu je ispod.

Zadatak: Treba napisati program koji rješava osnovni problem ili neku varijaciju (dozvoljeno je i više njih, po izboru).

• Napomene:
  • U literaturi je dan samo opis osnovnog problema, eventualno i opis raznih varijacija na temu problema.
  • Sve ostalo: izbor varijacije, planiranje ulaza, izlaza, izbora raznih algoritama, implementacije, vizualizacije, testiranja i sl.,
    je ``slobodno'' i nagrađuje se kao dio rješenja.
  • U zadacima za pretraživanje prostora stanja dozvoljeno je testirati i usporediti razne algoritme
    za neinformirano i informirano traženje, s proizvoljno odabranim heuristikama.
  • U zadacima s igrama, program treba simulirati igrača, a dozvoljeno je testirati i usporediti razne algoritme i varijacije,
    na pr., minimax, alfa–beta podrezivanje, variranje poretka pretrage.
  • Ne morate se ``ubiti'', napravite nešto razumno u razumnom vremenu. Ovo je samo zadaća, a ne veliki projekt!


• Rješenje je program koji radi to što treba — predajete osobno (vaš laptop ili praktikum).



• Kako se bira zadatak?
  • Za zadaću se bira 1 (jedan) od ponuđenih zadataka.
  • Dozvoljeno je raditi u grupi (timu) od najviše 2 studenta.
  • Svaki od zadataka smije biti izabran od najviše 2 studenta ili jedne grupe.
  • Izbor zadatka ide po sistemu: tko se prvi (pri)javi, njegov je!
  • U prijavi za grupni rad, treba navesti: ``grupni rad'' i oba člana grupe.
  • Realizacija prijave ide preko foruma za kolegij, na temi za domaće zadaće.
  • Prije izbora zadatka, prvo pogledajte na forum koji zadaci su već izabrani. To je jedini mjerodavni popis!

Na ovom popisu povremeno će se dodavati imena studenata uz već izabrane zadatke.


• Termini za predaju zadaća:
  • prije kolokvija:  ponedjeljkom iza predavanja (u 15 sati) i petkom u vrijeme konzultacija (12–14 sati)
  • za vrijeme kolokvija:  petkom u vrijeme konzultacija (12–14 sati)
  • Zadnji rok:  ponedjeljak, 16. veljače 2015., u 14 sati.


• Kodeks ponašanja ili ``pravila igre'': pogledati kraj slajdova za 1. predavanje.

Popis zadataka po područjima

• Problemi pretraživanja
  1. Misionari i kanibali, ili ljubomorni muževi, generalizacije
     • Wikipedia (pogledajte varijacije),  jedna varijanta zadatka.
  2. Lisica, guska i grah (vuk, koza i kupus), generalizacije
     • Wikipedia (pogledajte varijacije).
  3. Most i baklja
     • Wikipedia (pogledajte varijacije).
  4. Lovac na blago (otvoreni minesweeper)
     • Zadatak s primjerima i rješenjima.
  5. Keramičar — slagalica s pločicama
     • Zadatak s primjerima i rješenjima.
  6. Sudoku
     • Wikipedia (pogledajte varijacije),  primjeri i rješenja.
  7. KenKen — modernija varijanta Sudoku slagalica
     • Wikipedia,  knjiga: Kulkarni, D. Enjoying Math: Learning Problem Solving With KenKen Puzzles.
  8. Str8ts — kombinacija Sudokua i pokerske skale
     • Wikipedia.
  9. Kakuro
     • Wikipedia (pogledajte varijacije),  primjeri i rješenja.
  10. 8 kraljica, 32 skakača, i sl., generalizacije
      • Wikipedia (pogledajte varijacije).
  11. Konjićevi skokovi, obilazak ploče, nepresijecanje puteva, generalizacije ploče i figura
      • Wikipedia,  Wikipedia - nepresijecanje (pogledajte generalizacije za figure).
  12. Nema tri točke na pravcu, generalizacije na pravokutnu (ne-kvadratnu) mrežu
      • Wikipedia (pogledajte varijacije).
  13. 15 slagalica, generalizacije (razne veličine)
      • Wikipedia (pogledajte varijacije),  jedna varijanta zadatka.
  14. Klotski slagalica (Sliding block puzzle), generalizacije oblika
      • Wikipedia (pogledajte varijacije),  jedna varijanta zadatka,  razne varijante,  tri varijante,  razne varijante (pogledajte C15 do C45).
  15. Preskakanje čunjića (Peg solitaire), generalizacije oblika
      • Wikipedia (pogledajte varijacije),  jedna varijanta zadatka.
  16. Pentomino, generalizacije oblika, restrikcije komada
      • Wikipedia (pogledajte varijacije),  primjeri i rješenja.
  17. Hanojski tornjevi, generalizacije na više igala, restrikcija poteza
      • Wikipedia (pogledajte varijacije),  jedna varijanta zadatka.
  18. Rubikova kocka
      • Wikipedia,  jedna varijanta zadatka.
  19. Sokoban
      • Wikipedia (pogledajte linkove),  primjeri nekoliko nivoa,  on-line igranje.
  20. Žabe i krastače — ovaj problem se može promatrati i kao igra dva igrača (v. RN, zadatak 5.8, str. 197)
      • Wikipedia,  jedna varijanta zadatka.


• Igranje igara
  21. Hexapawn — igra pješaka na šahovskoj ploči
      • Wikipedia.
  22. Šah dama — pojednostavljena dama na šahovskoj ploči
      • Opis igre.
  23. Grundyjeva igra
      • Wikipedia,  jedna varijanta zadatka.
  24. Mastermind
      • Wikipedia (pogledajte varijacije).
  25. Reversi (Othello), generalizacije na razne ploče (na pr., na manje)
      • Wikipedia,  osnovna varijanta zadatka.
  26. Točke i kvadrati (Dots-and-Boxes)
      • Wikipedia (pogledajte varijacije),  osnovna varijanta zadatka.
  27. Qubic — križić-kružić (tic-tac-toe) u tri dimenzije
      • Wikipedia,  osnovna varijanta zadatka.
  28. Kvantni križić-kružić
      • Wikipedia,  osnovna varijanta zadatka.
  29. Backgammon — igra s bacanjem kocaka (ExpectiMiniMax)
      • Wikipedia,  osnovna varijanta zadatka.

• Zahvale:
  • Ideje i materijali za većinu zadataka: Matko Bošnjak, Goranka Nogo i Renata Svedrec.
  • Priprema i sređivanje dodatnih materijala: Sanja Singer.