Automated Reasoning and AI Programming - Spring Term

Chris Thornton

Introduction

The Spring term component of the ARAIP course introduces AI programming and automated reasoning. The main topics are game playing, knowledge representation, Bayesian reasoning and learning. Basic techniques are introduced for creating AI applications in Java.

The Summer term component will focus on use of AI packages. See also the full course description at http://www.sussex.ac.uk/informatics/syllabus/current/31224.html

Lectures

There are two lectures per week (see Sussex Direct for times). Most of the material (approx 90%) is covered in the online lecture notes. (The syllabus is defined by the section headers.) I find it hard to lecture to a wall of laptops so I'm always grateful if people keep them shut. Lectures are compulsory and I'll be doing regular sign-up sheets. Use the lectures and the labs (rather than email) to ask questions and make comments.

Week 1
Lecture 1 - Introduction to the field pr sl
Lecture 2 - Route finding pr sl

Week 2
Lecture 3 - Route finding in Java pr sl
Lecture 4 - Problem solving pr sl

Week 3
Lecture 5 - Problem solving in Java pr sl
Lecture 6 - Heuristic search pr sl

Week 4
Lecture 7 - Heuristic search in Java pr sl
Lecture 8 - Game playing pr sl

Week 5
Lecture 9 - Game playing in Java pr sl
Lecture 10 - Catch up

Week 6
Lecture 11 - Reasoning pr sl
Lecture 12 - Knowledge representation pr sl

Week 7
Lecture 13 - Bayesian reasoning pr sl
Lecture 14 - Bayesian networks pr sl

Week 8
Lecture 15 - Machine Learning pr sl
Lecture 16 - Machine Learning in Java pr sl

Week 9
Demo/assessment/revision sessions

Labs

From week 2 on, we have one lab session every week. Assessment and feedback for lab work will be through individual sessions; i.e., me coming up behind you and asking you to take me through the work you've completed.

Week 2

Adapt the CampusSearch program for use with data derived from the toy map of Brighton. Check that the program produces valid routes for that map. Then modify the program so that it produces only the shortest route between two locations.

Week 3

Modify the WaterJugs program so that it implements an iterative-deepening search strategy.

Week 4

Turn the EightPuzzleSearch program into a 5-puzzle solver, i.e., modify it so as to use a board with three columns and two rows. Then modify the h2 definition so that it uses the Euclidean distance rather than the City-block distance as a basis for evaluation. (Use Wikipedia to get the formula for Euclidean distance if necessary)

Week 5

Modify the NoughtsAndCrossesSearch program so as to implement alpha-beta pruning.

Week 6

Represent as much information from the UoS main web page as you can using FOL.

Week 7 and 8

Work on main assignment.

Week 9

Presentations.

Assessment

Assessment for the course is based on two coursework assignents and one exam, with a 50/50 split of credit between exam and coursework. So the programming task for the Spring term component is worth 25% of the total marks.

Remember that the expected standard of work is higher in the second year than it is in the first. You will need to raise your game in order to achieve the same results you achieved last year.

The programming assignment for the Spring term component is due Thursday of week 8 (normally 2pm). The task is to construct a draughts (checkers) game game in Java. The program's GUI should present an interactive draughts board that allows pieces to be moved around as per the rules of the game. (See http://www.indepthinfo.com/checkers/play.shtml if you're unsure what these are.) It should be able to produce legal gameplay at different levels of difficulty, making use of minimax and alpha-beta pruning, as explained in the lecture on `game playing'.

You can start work on this assignment as soon as you like but the lecture on relevant methods (minimax and alpha-beta pruning) takes place at the end of week 4. Normally it will make sense to commence work around that time. This gives you three weeks to complete the assignment. The sequence thus looks like this.

Week 4: Lecture on game playing/minimax; commence work on the task.

Weeks 5-8: Work in progress; I'll use lab sessions to give feedback on your work.

Week 8: Submit your work to the department office as a paper document. The report should explain and illustrate (using figures where needed) what you have achieved with regard to each of the assessment criteria below. That means it should have one section (of approx. two paragraphs) for each criterion. The code should be included as an appendix. Normal rules on plagiarism apply.

Week 9 and 10: all lecture and lab sessions will be used for demos, peer assessment and revision groups. At one of these sessions you will have to give your peer assessors a short demo of your implementation so as to enable them to evaluate it on the first six of the 10 criteria below. This will involve showing some code samples as well as demoing the program. You'll also need to attend and peer-mark demos by your assessees.

To summarise, you present your submission as a paper document to the office at the end of week 8. All sessions from then on (lectures and labs) run as labs. At some time during one of these, you'll give the demo of your work to your group of peer assessors. You'll also use this time to see the demos of those students that you are a peer assessor for.

Each peer-assessment group will contain four people. That means you'll have four people in your assessment group and you'll be part of the assessment groups for four other students. As far as possible, arrangements will be made so that students do not end up assessing other students in their own assessment group.

Peer assessors should score submissions on the first six criteria below. Give marks out of 10 for each criterion. I'll make paper forms available during the session. When you assess your own work (in the report), give yourself a mark and comments for the the first nine criteria (i.e., everything except `Quality of marking').

The 10 Assessment criteria:

Quality of board display (clear display with the right squares and pieces? proper interactivity? easy to make moves? do pieces disappear after being taken?)
Quality of basic gameplay (is turn-taking implemented? does the system make legal moves? does it trap illegal moves and give sensible information and instructions? are jump effects sensibly visualized?)
Quality of basic AI (is search used to select moves? are multiple jumps properly implemented)
Quality of advanced AI (is minimax search and alpha-beta pruning used?)
Extra functionality (are there any additional features? tutorial system? multiplayer? tournament?)
Quality of code (clearly layed out and easy to read? short, helpful comments? minimal loop embedding? sensible classes and small, easily understood methods with proper input/output parameters?)

Report completeness (does it include all the information required to assess the work on all 10 criteria?)
Report clarity (clear writing and presentation? good use of figures and execution traces?)
Course awareness (reference to lecture material and discussions. integration of indirectly related lecture material)
Quality of self-marking (reasonable marks awarded? detailed, constructive evaluation and criticism?}.

The mark you get for these criteria will be based on the material in your paper report so you need to make sure that the report justifies the marks you award yourself.

Feedback

I will return your paper submission to you together with a mark for each of the 10 criteria. These marks will show you how well you did on each of the criteria. Taking into account all the information on the website, it should be clear why you got the marks you did, and what you need to do to improve performance.

If you want further clarification of the marks you received, please come to my special feedback session between 11 and 1 on the first monday of the Summer term. Bring along the paper copy of your submission and the marks awarded and be prepared to re-do your demo.

Demos and peer-marking arrangements

An important part of the assignment is the demo. This is an approx. 7 minute presentation of your system given to a group of 4 peer assessors, i.e., other students in the group.

Demos will take place in the lab session in week 9. It is your responsibility to make sure that (a) your demo is seen by all your peer markers and (b) that you get to see the demos of all students you are peer marking.

I will print out copies of the peer assessment sheet for people to fill in during the sessions. After you've filled these in, you can either give them to the student directly or leave them with me to pass on.

I will be at the demo sessions and will oversee the process. However, I will not be watching demos myself. The mark that I award for your submission will be based on my evaluation of your paper submission, so make sure that you provide all the evidence needed for me to evaluate your work on the 10 criteria. My marks are not affected by the peer marks you get for your demo. These are just for your information.

Demo marking sessions for ARAIP 2010

  - Session 1 at 10 minutes past
      Peer group for Jamey-Holden
         Chris-Franklin
         Andrew-Friend
         James-Ongley
         David-Callender
      Peer group for Chris-Skilton
         Zack-Bleach
         Alexander-Hosford
         Mauro-Melo
         Daniel-Worrall
      Peer group for Nathan-Clarke
         Jack-Pady
         James-Maxwell
         Jonathan-Baker
         Peter-Amor
      Peer group for Steven-Cambers
         Barbara-Franca
         Miles-Bilham-Ware
         Nyaradzo-Muzira
         Christopher-Dykes

  - Session 1 at 20 minutes past
      Peer group for David-Callender
         Jamey-Holden
         Chris-Skilton
         Nathan-Clarke
         Steven-Cambers
      Peer group for Zack-Bleach
         Andrei-Pop
         Douglas-Hoyal-Cuthill
         Mark-Jefferis
         Steven-Muggeridge
      Peer group for Alexander-Hosford
         Miroslav-Batchkarov
         Jack-Pay
         Caroline-Wilgar
         Matti-Lyra
      Peer group for Mauro-Melo
         Ben-Campion
         Chris-Franklin
         Andrew-Friend
         James-Ongley

  - Session 1 at 30 minutes past
      Peer group for Chris-Franklin
         David-Callender
         Zack-Bleach
         Alexander-Hosford
         Mauro-Melo
      Peer group for Andrew-Friend
         Daniel-Worrall
         Jack-Pady
         James-Maxwell
         Jonathan-Baker
      Peer group for James-Ongley
         Peter-Amor
         Barbara-Franca
         Miles-Bilham-Ware
         Nyaradzo-Muzira
      Peer group for Andrei-Pop
         Christopher-Dykes
         Jamey-Holden
         Chris-Skilton
         Nathan-Clarke

  - Session 1 at 40 minutes past
      Peer group for Daniel-Worrall
         Steven-Cambers
         Andrei-Pop
         Douglas-Hoyal-Cuthill
         Mark-Jefferis
      Peer group for Jack-Pady
         Steven-Muggeridge
         Miroslav-Batchkarov
         Jack-Pay
         Caroline-Wilgar
      Peer group for James-Maxwell
         Matti-Lyra
         Ben-Campion
         Chris-Franklin
         Andrew-Friend
      Peer group for Jonathan-Baker
         James-Ongley
         David-Callender
         Zack-Bleach
         Alexander-Hosford

  - Session 1 at 50 minutes past
      Peer group for Mark-Jefferis
         Mauro-Melo
         Daniel-Worrall
         Jack-Pady
         James-Maxwell
      Peer group for Steven-Muggeridge
         Jonathan-Baker
         Peter-Amor
         Barbara-Franca
         Miles-Bilham-Ware
      Peer group for Miroslav-Batchkarov
         Nyaradzo-Muzira
         Christopher-Dykes
         Jamey-Holden
         Chris-Skilton
      Peer group for Jack-Pay
         Nathan-Clarke
         Steven-Cambers
         Andrei-Pop
         Douglas-Hoyal-Cuthill

  - Session 2 at 10 minutes past
      Peer group for Peter-Amor
         Mark-Jefferis
         Steven-Muggeridge
         Miroslav-Batchkarov
         Jack-Pay
      Peer group for Barbara-Franca
         Caroline-Wilgar
         Matti-Lyra
         Ben-Campion
         Chris-Franklin
      Peer group for Miles-Bilham-Ware
         Andrew-Friend
         James-Ongley
         David-Callender
         Zack-Bleach
      Peer group for Nyaradzo-Muzira
         Alexander-Hosford
         Mauro-Melo
         Daniel-Worrall
         Jack-Pady

  - Session 2 at 20 minutes past
      Peer group for Caroline-Wilgar
         James-Maxwell
         Jonathan-Baker
         Peter-Amor
         Barbara-Franca
      Peer group for Matti-Lyra
         Miles-Bilham-Ware
         Nyaradzo-Muzira
         Christopher-Dykes
         Jamey-Holden
      Peer group for Ben-Campion
         Chris-Skilton
         Nathan-Clarke
         Steven-Cambers
         Andrei-Pop

    - Session 2 at 30 minutes past
        Peer group for Christopher-Dykes
           Jack-Pay
           Caroline-Wilgar
           Matti-Lyra
           Ben-Campion

Course texts

The back-up text for the course is the encyclopedic book by Russell and Norvig, now in second edition.

Russell and Norvig, `Artificial Intelligence: A Modern Approach.' (as used by Foundations of AI. There are many copies in the main library and one in the COGS library.)

Also of interest is this AI-in-Java text:

Bigus and Bigus, `Constructing Intelligent Agents in Java.' (6 copies in the library including one in reserve section. I also hope to arrange for the COGS library to buy a copy.)

For something a little lighter, try

`Hal's Legacy' edited by David G. Stork. This provides a light-hearted overview of the state-of-the-art in AI.

Programming issues

The assignment for the Spring part of ARAIP involves programming so if you've fallen behind with this part of your work it's a good idea to take action at the start of the course. Let me know early on that you have problems. Make sure you do all the lab exercises. If they are too hard, get me to suggest easier exercises you can use for target practice.

In doing your programming, I don't require that you follow any particular genre or style (it doesn't have to be pure `OOP'). However, you do need to be consistent and you need to follow the general principles of good programming.

I take the general requirements to be:

modularity: modular programs are made up from small, independent components (typically methods) that can be tested and debugged in isolation from the rest of the program. Such components get their data via formal input parameters. They only affect the rest of the program via the formal outputs (results) they return. They are, in effect, `black boxes'. Once validated, they can be eliminated from the debugging process. Modular programs make little or no use of variables for purposes of communication information from one part of the program to another. Writing your program in a modular way exploits the divide-and-conquer strategy.
simplicity: don't introduce additional complications unless there is a real need. Follow the KISS principle (Keep It Simple Stupid). Don't start experimenting with advanced features of Java (e.g. final variables and inner classes) without good reason. If you find you are writing the same (or almost the same) code more than once, look for a way to eliminate the redundancy. You'll probably need to create a new method or class which can be used in different situations.
transparency: choose your variable and method names so as to make the code self-explanatory. (This will only be possible if your code is modular.) The name of a variable (or method) needs to show what role is being played. Resort to inline comments when you are unable to find a way of making the code tell its own story. If you do use inline comments, keep them as short as possible and format them so as to minimise disruption to the visual structure of the code. Don't let line-wrap problems obscure indentation.
presentation: the program should be presented neatly and clearly, using consistent conventions for use of blank-lines etc. Indentation should be carefully used to delineate the logical structure of the program, particularly the presence of contingencies (i.e., `if' statements) and loops. Programs should be commented in the standard `javadoc' style but please note that the javadoc listing should NOT be included with your submission.

Page created on: Mon Feb 22 11:25:58 GMT 2010
Feedback to Chris Thornton