CS105
Fundamentals of Artificial Intelligence
Group-project for Tangram Piece Matching and Recognition
Tangram is one of the most popular games to play with. You put figures of 7 pieces together (five triangles, one square and one parallelogram). You must use all pieces. They must touch but not overlap.
There are 32 half squares or 16 squares altogether.
We could take the half triangle as the basic form, because the square built of all seven tangram pieces has the simple length 4.
There are only 13 convex figures that you can build from tangram pieces.
In this project, you are required to use AI search methods (uninformed search methods such as Breadth First search, Depth First search, Iterative Deepening and Uniform Cost search) and (Informed or heuristic search methods such as Greedy search, A* algorithm and Iterative Deepening version of A* : IDA*) to perform pattern matching and recognition. For some figures, there are more than one goal states that could be reached. You are given all these 13 figures with no lines drawn inside each figure, i.e., they are figures with boundaries only (black box figures). You jobs are given as follows:
1. Divide each figure into 32 half-square (triangle) areas.
2. Group these 32 areas into 7 larger areas: five triangles, one square and one parallelogram. The
area ratios should be 8:8:4:2:2:4:4 =4:4:2:1:1:2:2 =LT:LT:MT:ST:ST:SQ:PA
3. Setup problem formulation that is most suitable for solving this problem.
All seven tangram pieces consist of half square with this shape:
4. Use uninformed and informed search methods to solve this problem.
5. Implement these search methods in a computer system so that analyses of these methods could
be done.
6. Analyze the properties of these search methods in terms of completeness, optimality, time and
space complexity to solve this problem.
7. You are required to form groups or team yourself. Each group should have 3-4 students. You are
advised to include in your team/group at least ONE student who knows how to do programming,
any programming languages, Matlab, etc. could be used. .
8. Submit to me names of your team members NEXT WEEK (week 5 in the class).
9. A user friendly interface should be provided. A system name/title is given, e.g, “A Pattern
Matching and Recognition System”.
10. A presentation and demonstration is a MUST in weeks 13 and 14.
11.Each group or team is required to have a 10-minute presentation which includes the
introduction, description of your method(s), problems you have solved, your contributions,
what have achieved in your system and a demonstration of your project.
12. A clear, succinct, easy to understand user manual/guide on how to INSTALL and EXECUTE the
software (freeware or others) and your DEVELOPED system should be submitted in hardcopy.
13. You are also required to submit a full report of your system in hardcopy. The report should
include the following information.
All your team members’ name, ID number and team number (to be assigned later).
The problems you have solved.
Which uninformed or informed search methods you have used and why?
What evaluation function you have used to guide you in branching (expanding) nodes?
How and why such functions or changes are introduced? What are the reasons behind
introducing such changes?
A figure showing the problem formulation of your system should be included.
A comparison of properties of different adopted or implemented search methods in terms
of Completeness, Optimality, Time and Space complexity need to be done.
The results you have obtained.
14. You are required to submit a USB which contains the source codes of your developed system, shareware or freeware used, user manual/guide on how to INSTALL and EXECUTE your system, and your FULL report mentioned in 13. i.e., you have to store in a USB all the information mentioned in points 12 and 13 and submit them in week 13.