alpha-beta pruning

step-by-step explanation: http://www.cs.ucla.edu/~rosen/161/notes/alphabeta.html

tutorial and java applet: http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html

java applet animation: http://wolfey.110mb.com/GameVisual/launch.php

The 8-Puzzle: Assignment

Warm up first, and then assignment.  Submit Assignment on Thursday 23rd December.

Warm-up

Go to Brian's 8-Puzzle Solver - launch the Java application and use this input: 3 2 0 8 7 4 5 1 6

Now ask the Solver to find a solution with "Number of paths to try" set at 100, and 1000, and 10000.

(Note that he uses A* as the name of his best-first algorithm.)

How many moves away is the final solution from the initial state?

How long was the time it took?

Use breadth-first search instead of A* (best-first) and see how many paths breadth-first needs before it finds the solution to the same puzzle.  Can it solve the puzzle within the 100,000 limit that the programmer has set?  How slow is it by comparison to best-first?

Try different inputs.  What is the worst number number of moves you have found?

Try the Enhanced A*.  See the author's notes as to why it is faster.

In Enhanced A*, what type of modifications to A* has Brian done: (choose one)
1- improved the heuristic evaluation function
2- improved the best-first search algorithm
3- improved the data structures

---

Assignment 1


For an 8-puzzle problem solver (assume that it uses depth-first search, but it doesn't matter), answer these questions:

1. What is the number of possible states of the board?
2. What is the average number of possible moves from a given position of the board?
3. Estimate how many moves might be required for an optimal (minimum number of moves) solution to a ``worst-case'' problem (maximum distance between starting and goal states). Explain how you made your estimate.
4. Assuming the answer to question #2 is the ``average branching factor'' and a depth as in the answer to question #3, estimate the number of nodes that would have to be examined to find an answer by brute force (blind) depth-first search.
5. Assuming that your computer can examine one move per microsecond, how long would such a blind-search solution to the problem require?
6. Should a depth-first search program for this problem check for duplicated states and consider a duplicated state to be a failure node? Calculate the effect such a test would have on the answers to questions #4 and #5.
7. The ``worst'' example problem given below is actually one of the easiest for humans to solve. Why do you think that is the case? What lessons for AI programs are suggested by this difference between human performance and performance of your search program?

Goal:        Easy:        Medium:        Hard:        Worst:

1 2 3        1 3 4        2 8 1          2 8 1        5 6 7
8   4        8 6 2          4 3          4 6 3        4   8
7 6 5        7   5        7 6 5            7 5        3 2 1

Taken from http://www.cs.utexas.edu/~novak/asg-8p.html

Final exam prep - part I

The author of the textbook provides some notes on and solutions of the exercises of Chapter 3 and Chapter 4.

The final exam will include this type of questions.  Start studying.

Lecture slides: Heuristic Search

Chapter Four's Slides.

Feedback on the Research Paper Presentations

-----------------------------------

Artificial Life and Real Robot

reviewed by Nada Alaa and Niveen Ali

The pdf of the paper is not included, plus it seems to be a conference paper (not a journal paper).

I liked that each slide had only one point.  No copying-and-pasting of a lot of text, here - which is great.  I also liked that in slides 2 and 3 you showed your authorial voice ("the paper inquired into … and then it got into details of …").  You are conveying to me the general picture of the paper.

Unfortunately for you, the paper got into genetic programming, something about which you know little, and so your slides seem lost by the end.

Choice of Journal Paper and Students' Comprehension of it: 3.5

Summarising Research Paper Content and Structuring of Presentation: 4

-----------------------------------

Untitled

reviewed by Mostafa Hany and Ahmed Alaa

No reference to the paper you based on the presentation on.  No title of presentation.  I don't think the paper was a journal paper.

Only four slides.  The slides were all titled with a question - interesting, why?

Text of slides was obviously copy-and-paste from the paper.  Too much text on each slide.  No conclusions.

Overall, I thought the slides useful and I learnt something from them.  Your choice of content was interesting: combining AI and Games.  But much more work needed to be done.

Choice of Journal Paper and Students' Comprehension of it: 3.5

Summarising Research Paper Content and Structuring of Presentation: 3

-----------------------------------

Intelligence Without Representation

reviewed by Nathalie Amir and Mina Karam

What role does the Word document play?  I found that it was mostly copy-and-paste from various sources.  


There are too many slides.  It would have been impossible for you to present these in ten minutes.  It is clear that the slides copy-and-paste from online sources.  Therefore you must make it clear that you are copying, otherwise you are plagiarising, which is a serious offence.

The choice of journal paper was excellent and I could see that you tried to review the paper well.  Maybe it was a little too much for you, because of all the concepts and because the author is presenting an untraditional approach to AI.  You probably would have made a better job with a paper that had a narrower focus.

Whereas I liked that you tried to find out what other people are saying about the paper, so that you can build on their thoughts, I am not sure this has helped you in the end, because you now give the impression of people who copied-and-pasted from as many sources as they could find.  Also, it opens up the question of whether you chose the paper because you found someone else had already reviewed it, so you could steal their work, not because you read and liked the paper.

Choice of Journal Paper and Students' Comprehension of it: 3.5

Summarising Research Paper Content and Structuring of Presentation: 3.5

-----------------------------------

Games, Computers and AI

reviewed by Sarah Sameh and Ola Mokhtar

The slide design is very attractive.  Each slide has just about enough text, not too much.

My main criticism of this presentation is that the text is clearly copied from the paper's text.  I am not sure you were able to understand the content of the paper.

Choice of Journal Paper and Students' Comprehension of it: 3.5

Summarising Research Paper Content and Structuring of Presentation: 4.5

-----------------------------------

Is Holography the Future of Multimedia Storage

reviewed by Ahmed Aly and Omar Said

The slides have excellent design and each slide has not too much text.  

The pdf of the paper is not included, nor is any reference made to it.  The paper seems a conference paper.  I am not sure this relates to AI.

Choice of Journal Paper and Students' Comprehension of it: 2.5

Summarising Research Paper Content and Structuring of Presentation: 4.5

-----------------------------------

Adaptive Constraint Satisfaction

reviewed by Mohammed Ezzat and Ahmed Mostafa

The text tended to be too much per slide.

This is obviously a copy-and-paste job from the text of the paper.  Constraint Satisfaction is not a topic you are "prepared for" and so your choice of paper was not good.

Choice of Journal Paper and Students' Comprehension of it: 3

Summarising Research Paper Content and Structuring of Presentation: 4

-----------------------------------

Smart Meeting Rooms

reviewed by Mina Nicola and Ahmed Ayman

I liked this presentation and the topic is nice.

The text tended to be too much per slide.  I liked that you included images to illustrate the text.

You did not pick a good paper to demonstrate your efforts.  The paper covers a wide range and so you had to summarise lots of concepts.

Choice of Journal Paper and Students' Comprehension of it: 4.5

Summarising Research Paper Content and Structuring of Presentation: 4.5

-----------------------------------

Robotic Surgery

reviewed by Ahmed Al Ayat and Sherif El Behairy

Great topic.  No paper included in zip file.  Full reference not provided either.  


I think this would have made an excellent presentation.

Choice of Journal Paper and Students' Comprehension of it: 4.5

Summarising Research Paper Content and Structuring of Presentation: 4.5

-----------------------------------

Turing Test: First 50 Years

reviewed by Marian Moheb and Salma Sameh

Good topic, nice presentation.  Would have liked to see you present it.

Where is the pdf of the paper?

Choice of Journal Paper and Students' Comprehension of it: 4.5

Summarising Research Paper Content and Structuring of Presentation: 4.5

-----------------------------------

If not Turing's Test, then What
reviewed by Maria Nichola and Lina Nabil

Where is the pdf of the paper? Where is the full reference to it?

The presentation was very well-illustrated and I felt that the text was probably all yours (you didn't plagiarise a lot).  But I don't think you did a good job in summarising the paper so as to explain its content.

Choice of Journal Paper and Students' Comprehension of it: 3.5

Summarising Research Paper Content and Structuring of Presentation: 4.5

-----------------------------------

Tests of Machine Intelligence

reviewed by Shrouk Moataz and Kholoud Raafat

The title of the paper starts with Tests, but your presentation's title starts with Test!

What is the full reference to the paper?  Is it a journal paper?

I enjoyed this presentation, I would have liked to see you present it.  It lacked pictures and examples.

Choice of Journal Paper and Students' Comprehension of it: 4.5

Summarising Research Paper Content and Structuring of Presentation: 4.5

-----------------------------------

AI presentations

Your presentations have all been received, thank you boys and girls.  Well done for all your work.

You did well on Graphics, but your AI marks are shameful - madbaha!

Anyway, enjoy the short break before we return for three weeks, and then the final.

I'm listening to  Say Ahh by Trey Songz to celebrate.  What are you listening to?  

Research Presentations update

No presentations this Thursday - university says.  (I hate!)

So, instead, mail me at ahmed.ismail@miuegypt.edu.eg your presentations, before 12 noon Thursday.  Send anything, even if one slide.

Deadline is very strict.

Ahmed