Intelligent Systems Techniques (MSc) and Knowledge and Reasoning (UG)

Chris Thornton

Introduction

The course teaches concepts, methods and issues of artificial intelligence. Basic techniques are introduced for creating AI applications in Java.

Instructions for lab sessions

Assessment is based on one programming assignment and an unseen exam. Most of the syllabus material is in the online lecture notes (below), but note-taking and additional reading is strongly advised.

The first meeting for the course will be the first scheduled lecture.

The first lab will be the first uncancelled lab session. Depending on how lab and lecture times interact, I will have to cancel one or more of the initial sessions.

Lectures

Week 1
. Introduction to the field (pdf)
. Braitenberg Vehicles (pdf)
Week 2
. BugWorks tutorial.
. Route finding (pdf)
Week 3
. Problem Solving (pdf)
. Knowledge test (pdf)
Week 4
. Heuristic Search (pdf)
. Game Playing (pdf)
Week 5
. Knowledge Test (pdf)
. Debates briefing
Week 6
. Route finding in Java (pdf)
. Problem Solving in Java (pdf)
Week 7
. Heuristic Search in Java (pdf)
. Game Playing in Java (pdf)
Week 8
. Debate 1
. Epistemology (pdf)
Week 9
. Reasoning (pdf)
. First-order Logic (pdf)
Week 10
. Knowledge Test (pdf)
. Bayesian Reasoning (pdf)
Week 11
. Bayesian Networks (pdf)
. Debate 2
Week 12
. Revision

Assessment

Assessment is a programming assignment and an unseen exam, with a 50/50 credit split between the two. For the assignment due date, see Sussex Direct

The task is to construct a checkers (draughts) game in Java. The program 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 lectures in the first half of the term.

You can start work on this assignment as soon as you like but bear in mind that the lectures on minimax and alpha-beta pruning are given around the middle of term. Normally it will make sense to commence work after the lecture on minimax in Java. This still leaves you plenty of time to complete the assignment.

There are 25, equally-weighted assessment criteria. In developing your program, you should try to satisfy as many of these as you can.

1. Interactive checkers gameplay (user v. AI) of some sort
2. Valid state representation
3. Successfor function of some sort
4. Valid successor function
5. Use of successor function for validating user moves
6. Use of successor function for generating AI moves
7. Rejection of invalid user moves, with explanation
8. Valid board display
9. Valid AI moves
10. Valid GUI board display
11. Interactive GUI display
12. Drag-and-drop user moves
13. Elements of minimax evaluation
14. Valid minimax evaluation
15. Forcing of takes
16. GUI shows completion of user move (with no pause)
17. King conversions
18. Multi-step user moves
19. Multi-step AI moves
20. GUI pauses to show intermediate states in multi-step moves
21. Minimax evaluation uses pruning of some sort
22. Minimax evaluation uses valid alpha-beta pruning
23. Variable level of AI (eg. a difficulty slider)
24. System accessible from web page (eg. applet)
25. Interactive tutorial guidance (eg. help button)

I use the lab sessions in the final two weeks of term to interactively assess your work. So you need to be ready from the second to last week to give me a short (3-4 minute) demo. I'll use this to establish which criteria you've met, and also to confirm that the code you demo is your own work.

If it's not possible for me to see all the demos in lab time, I'll arrange extra sessions as needed. The demo is mainly to enable me to assess your work. However, students in the same lab session are invited to watch demos too.

As well as providing the demo, you should submit the text of your code (all source and class files) electronically through Study Direct. The source code you submit online will be used to resolve any ambiguities concerning which criteria you've met. Note the code you submit must be the code used for your demo. All university rules on plagiarism apply.

Extra feedback

If you would like further feedback on the way in which you've coded the checkers game (beyond the feedback sheet on Study Direct), you are invited to come to see me on a 1-to-1 basis on the first day of the following term. (My office is C1-101, internal phone 8856). Email me for an appointment or turn up sometime on the first day of term. Remember to print out your code and bring it with you when you come.

Course texts

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

Russell and Norvig, `Artificial Intelligence: A Modern Approach.' (There are many copies in the main library and one in the department 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 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 involves programming so if you're having troubles in this area, it's a good idea to take action earlier rather than later. The key rule is to make yourself do all the lab exercises (even the ones that seem trivial).

I don't require you to follow any particular programming genre or style, i.e., it doesn't have to be pure `OOP'. However, you do need to be consistent, and follow the general principles of good programming. These are as follows.

  1. modularity: modular programs are made up from small, independent components (typically methods) that can be tested and debugged independently 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 like `black boxes' which, once validated, can be ignored. Modular programs make little or no use of class variables for communication information from one part of the program to another. Writing your program in a modular way is a divide-and-conquer strategy.

  2. simplicity: don't introduce complications unless there is a real need. 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 get rid of the redundancy. You'll probably need to create a new method or class which can be used in different situations.

  3. transparency: choose your variable and method names so as to make the code self-explanatory, as far as possible. The name of a variable or method needs to describe the role it plays. Resort to inline comments when you are unable to find a way of making the code `tell its story'. If you do use inline comments, keep them short, and format them so as to minimise disruption to the visual structure of the code. Don't let line-wrapping obscure indentation.

  4. presentation: the program should be presented neatly and clearly, using consistent conventions for use of blank-lines etc. Indentation should be consistently used to show the logical structure of the program, particularly the presence of constructs like `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.

Debate arrangements

Historically, there have been two huge debates in AI: one focussing on John Searle's `chinese room', the other focussing on Rodney Brooks' `knowledge bottleneck'. We will use a couple of sessions to have a go at resolving these.

The basic arrangements are as follows.

At the debate briefing, students will be divided up into four groups (A, B, C and D). Group A will be delegated to argue the pro-Searle cawse, and group B to argue the anti-Searle case. Group C will be delegated to be pro-Brooks, and group D anti-Brooks.

The first debate is around week 8. The second is whenever I finish the material, e.g., week 11. In the weeks running up to the debates, students read up on relevant sources and prepare notes to enable them to argue their case as strongly as possible.

At each debate, we randomly select one person from the two relevant groups to make a five-minute opening statement. After these have been made, the debate is opened up to the whole group. At the end of the session, we take a vote to decide which side has won.

First debate

The chinese room

Motion

The original publication is Searle's BBS article, which includes multiple commentaries.

There are hundreds publications of relevance here, and a huge number of web articles and videos which you can google. An easy-to-read article summarizing Searle's main argument is here. In putting forward the chinese-room argument, Searle was reacting to natural-language systems such as SHRDLU, see this).

Readings largely in favour

Readings largely against

Below are some alternative sources for the readings above. Note that any book which contains Searle's paper is very likely to contain other articles of relevance.

Second debate

Motion

The key article for this debate is Brooks' paper `Intelligence without Representation'.

For information on the subsumption architectures and the information bottleneck see

There's also a nice powerpoint presentation on Brooks' views: here.

Again, you'll find a huge number of web articles and videos offering all shades of opinion. But beware that where stuff is not peer-reviewed, there is no guarantee of valiidity.

Readings largely in favour

Readings largely against

Readings with various viewpoints

Misc.

The bottleneck diagram