Labs for Artificial Intelligence 1 (Winter 2017/18)

This page contains materials for the practice lessons of the Artificial Intelligence 1 (NAIL069) course that is/has been taught during winter term of 2017/2018 at Charles University in Prague, Czech Republic. The course is/was lead by Roman Barták. Labs are/were backed up by Jakub Gemrot (gemrot@gamedev.cuni.cz) and Otakar Trunda.

Permalink to this page: bit.ly/mff-uk-ai1-labs-2017

---

Monday’s labs, 15:40, SU2 (Jakub)

Wednesday’s labs, 17:20, SU2 (Otakar)

---

How to pass the practice

Following text applies ONLY to labs lead by Jakub Gemrot (i.e., Monday’s labs only).

We have a point system here. You can receive points for: homeworks (extra credits for meeting deadlines) and tournaments (as detailed below). Tournament points are not necessary to pass the practice, extra stuff just for fun 😉

You will need to collect 40 points to pass the practice; there are going to be 5 homeworks in total:

1. Mario – 5 pts,
2. Pac-Man – 10 pts,
3. Sokoban – 10pts,
4. Warlight – 20 pts,
5. Minesweeper – 10pts.

To earn those points you either have to implement (Variant 1) the homework or to write an essay (Variant 2) on how you would approach the problem in practice.

Additionally, you can obtain points from bug-reporting (1 point / bug reported and confirmed) and tournaments .

Points are tracked within a google spreadsheet; students may ask for the link (security through obscurity) via email: gemrot@gamedev.cuni.cz

Variant 1 – Implementations

Each homework comes with a small framework (usually hosted on GitHub) that you have to extend at some point (usually a well-defined AI agent interfce). To submit your homework, you have to ZIP your whole workspace and send it as is. So, please zip up the whole project folder (may be except bin/ folder) and send them to me. Never alter any framework code outside the project of the homework entry point class!

When submitting, note that it helps to rename the extension to obfuscate the zip mime … if you submitt .zi_ or .zzz via GMail (into mine and/or from yours) it will not complain about the attachment having executable files.

Implementation Homework	Points	Extra Points Deadline	Repo	Homework Entry Point	Description
Mario	5	28.10.2017 (23:59) 2 extra points	GitHub	MarioAgent class	Create a reflexive agent that can survive simple Mario levels.
Pac-Man	10	26.11.2017 (23:59) 2 extra points	GitHub	E4 class	Implement plethora of graph-search variants of following algos: DFS, BFS, UCS, DLS, IDS, BIS
Sokoban	10	9.12.2017 (23:59) 2 extra points	GitHub	DFSAgent class from the playground project	Implement Sokoban agent! Use IDS instead of DFS, implement a few heuristics.
Warlight	20	14.1.2018 (23:59) 2 extra points	GitHub	ConquestBot class	Implement alpha-beta search for the game; inclusion of ExpectiMiniMax is up to you; heuristics to be used are up to you. You may use SmartBot for opponent modelling as your target is to beat it 😉
Minesweeper	10	14.1.2018 (23:59) 2 extra points	GitHub	SATAgent class	Implement SAT-based agent for the minesweeper.

Variant 2 – Esseys

It is possible to write an “essay” instead of implementing stuff. The essay must describe in detail (and pseudocode) the solution for a given homework.

Each essay should have following sections:

1. Analysis of the homework – classify an environment we are facing, what are the options for solving it (i.e., what algorithms you can pick from) and what cannot be used (and of course why)
2. High-level description of the chosen solution that you tackle the problem with
3. Detailed description of the solution (including pseudocode)
4. Ideas for future work (how the solution can be developed further)

Following table is summarizing what an essay should contain specifically for each homework you will be given.

Essay Homework	Points	Extra Points Deadline	Section 1 – Analysis	Section 2 – Chosen solution	Section 3 – Description	Section 4 – Future work
Mario	5	28.10.2017 (23:59) 2 extra points	Classify the environment	Describe what reflexive agents are about; describe what kind of sensors and actions you will need to implement.	Present a pseudocode of your agent including notes on actions and sensors; comment respective agent rules with notes what kind of behavior they encode.	What can be done better?
Pac-Man	10	26.11.2017 (23:59) 2 extra points	Classify the environment	Describe respective algorithms one can use for graph searches; detail how tree search differs from graph search.	Provide commented pseudocode of respective algorithms; can pseudocode be written in a modular way so you do not have to copy-paste stuff between algos?	N/A
Sokoban	10	9.12.2017 (23:59) 2 extra points	Classify the environment; what algorithms can be used to solve Sokoban?	Detail your chosen solution; what heuristics are you going to implement? What other tricks can you employ?	Provide commented pseudocode; detail how heuristics are used.	What can be done better?
Warlight	20	13.1.2018 (23:59) 2 extra points	Classify the environment; what algorithms can be used to solve Warlight? Estimate size of the game tree.	Detail your chosen solution; what heuristics are you going to implement?	Provide commented pseudocode; detail how heuristics are used.	What can be done better?
Minesweeper	10	13.1.2018 (23:59) 2 extra points	Classify the environment; describe what SAT is about.	Detail how are you going to encode Minesweeper for a SAT solver.	Provide commented description of the SAT encoding.	N/A

Homework submission

Send me an email: gemrot@gamedev.cuni.cz

Subject: AI1 – 2017 – H[homework number] – [homework name]

Please, awasy comply with the subject above, otherwise I might miss your submission!

Note that you always have a chance to submit fixes (for both variants) if I find your solution not good enough 😉

---

Tournaments

There are going to be 3 tournaments organized during the course. Each tournament has a deadline for submission. You do not have to invest extra effort to participate in tournaments. Homework implementations are sufficient (unless you want those extra points right?). You automatically enter the tournament by submitting a homework implementation prior the deadline.

Tournament	Submission deadline	Extra points	Details
Mario	28.10.2017 (23:59)	1st place: 8 2nd place: 6 3rd place: 4 4th-30% (rd) of participants: 2	We will make Mario run through LevelConfig.LEVEL_4_SPIKIES, the best AIs will be awarded with points!Use Evaluate class to evaluate your implementation quickly.
Sokoban	9.12.2017 (23:59)	1st place: 12 2nd place: 8 3rd place: 6 4th-30% (rd) of participants: 4	The best Sokoban AI (solving the most levels) will win! See levels GitHub folder that contains plethora of Sokoban problems.
Warlight	13.1.2018 (23:59)	1st place: 16 2nd place: 12 3rd place: 8 4th-30% (rd) of participants: 4	The best Warlight AI (table tournament; 1v1) will win!

---

Labs

Lab 06 – 10.12.2017 / 17.12.2017

SAT and Prolog agents for Minesweeper framework!

• Homework 05 – “Minesweeper” [10 points]

Lab 05 – 27.11.2017 / 4.12.2017

RISK again! Explaining chance nodes and how to work around non-determinism, showing Monte-Carlo Tree Search algo.

• Homework 04 – “Warlight” [20 points]

Lab 04 – 13.11.2017 / 20.11.2017

Today it’s about RISK! And its game tree … its huge … what to do now?

Slides (PDF)

• “No” homework

Lab 03 – 30.10.2017 / 6.11.2017

Today it’s about informed tree-search for Sokoban, check out its sources from Sokoban GitHub repo.

Slides (PDF)

• Homework 03 – “Sokoban” [10 points]

Lab 02 – 16.10.2017 / 23.10.2017

Today it’s about uninformed graph-search for Pac-Man maze, checkout its sources from Pac-Man GitHub repo.

Slides (PDF)

• Homework 02 – “Pac-Man” [10 points]

Lab 01 – 2.10.2017 / 9.10.2017

We were playing with Super Mario simulator in Java, checkout its sources from Mario GitHub repo.

Slides (PDF)

• Introduction to environment classification
• Homework 01 – “Mario” [5 points]
  • Create AI for Super Mario!
    • AI must be reflexive, no “agent state / agent memory” persistence allowed
  • If you wish to score extra tournament points, try to prepare your Mario for the tough LevelConfig.LEVEL_4_SPIKIES

Java notes (PDF)

• Contains hint how to fight with Eclipse GUI
• The only thing that is not included