Saturday, 18 December 2010

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

    Friday, 17 December 2010

    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.

    Friday, 3 December 2010

    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


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

    Thursday, 2 December 2010

    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?  

    Tuesday, 30 November 2010

    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

    Tuesday, 16 November 2010

    5th Week Results

    No bonus marks here.

    ahmed alaa 3
    ahmed aly 3
    ahmed ayman 4
    ahmed farouk 3.5
    ahmed mostafa 3
    ahmed omar 3.5
    hisham rabie 1
    ibrahim galal 2.5
    kholoud raafat 3.5
    lina nabil 3.5
    maria nicola 2.5
    marian moheb 4
    menna fathy 2.5
    mina karam 2.5
    mina nicola 4
    mo ezzat 3.5
    mostafa hany 3.5
    nada alaa 4
    nathalie amir 3.5
    neveen ali 4
    ola mokhtar 3
    omar khaled 3
    omar said 4
    rafik farid 3
    salma sameh 3.5
    sarah sameh 4.5
    sherif ahmed 3
    shrouk moataz 4


    Some general notes on people's performance:

    - In explaining the chat dialogues a lot of you would say things like "the computer said 'I think' and a computer cannot think, therefore it's not a computer". This is not sufficient. You need to find better reasons and explain your reasoning more.

    A good example to follow came from Mina Karam:

    "I don't think you're serious, by winter's day ..."
    B understands that what A said has a literal meaning and another meaning (tashbeeh) [analogy or metaphor]; a computer wouldn't understand this.


    A bad example is that of Rafik Farid:

    B is not a computer because of the sentence "I don't think".


    Rafik, you must explain more.

    - In the question about finding two errors in the predicate logic statement concerning rents in Alex and Cairo, many of you were very unclear.

    Ahmed Mostafa wrote a predicate logic statement without putting arrows, or anything, to show what corrections he made. Not good.

    Mina Nicola wrote out the parts with the errors, and then made a point of listing each correction separately. Well done.

    Shrouk Moataz put arrows on the corrections and labelled them "error" - good enough.

    - Going back to the dialogue question, many of you accepted the hypothesis and started to explain on that basis. E.g., "Q is programmed so that when it finds that P is not sure, it asks him 'why are you not sure?'" Here, the student assumed that Q is a computer already. But the question asks you to show evidence that Q is a computer.  Many of you started with the hypothesis as if it is already proven. Say something like: it is likely that when Q replied to P's 'might' with 'why are you not sure', Q had not understood, or chosen to ignore, the content of P's statement. Such behaviour is typical of an automaton, unless if Q is an uncooperative human being.

    - Also in the dialogue question, many of you said things like "a computer cannot feel", "a computer cannot think", but computers can be programmed to say I feel, I think, so go deeper.

    - I was very disappointed to find that many of you thought this was an example of inductive reasoning. Wrong!

    Premise: All philosophy majors are quiet.
    Premise: Nageeba is a philosophy major.
    Conclusion: Nageeba is quiet.

    - Please improve your grammar.

    Sunday, 14 November 2010

    5th Week Exams

    Here are the 5th Week exams: v1 and v2.

    Research Presentation

    I found that I have access to many ScienceDirect papers, so if you are interested in a particular paper, and cannot find it through an author's homepage, I can get it for you (probably). Make sure to read the abstract to make sure the paper is suitable for you.

    Wednesday, 3 November 2010

    5th Week Prep

    Here is the work you did earlier this afternoon.

    Tuesday, 2 November 2010

    Wednesday, 27 October 2010

    Sunday, 24 October 2010

    Turing Test bots

    Check http://www.botspot.com/. Programs here were designed to carry on a conversation just like a person. A big goal would be to replace humans in chat-based technical support, or telephone call-centres.

    Check also the Turing Test Loebner Prize and see the winners of past years.

    Look through youtube for Turing Test-related videos, and post the interesting ones here.

    Sunday, 10 October 2010

    Self-Driving Cars - a bit of history

    Many geeks got excited by Google's announcement of the self-driving car, but there is also a bit of history.  This is what a newspaper reported in 1985:

    Google's Artificial-Intelligence Software Drives a Car

    The internet is alive with commentary on Google's Intelligent Car, a car driven by cameras and robot, that they have been testing for months.

    Hello, world!

    I shall be using this blog to update you with links, comments and various follow-ups from the lectures.

    I encourage you all to comment and interact with me, and each other, via this blog.  (Click 'comment'.)