1st Assignment at AI
		--------------------------

1) Random-restart hill climbing for the 8-puzzle with min(h1,h2) as heuristic function [RN, 113, 106] ()
2) Random-restart hill climbing for the 8-puzzle with h2 as the heuristic function [RN, 113, 106] ()
3) A* for the 8-puzzle with h2 as the heuristic function, and g(n)= number of moves from the initial state [RN, 97, 106] ()
4) A* for the 8-puzzle with h1 as the heuristic function g(n)= number of moves from the initial state [RN, 97, 106] ()
5) SMA* for the Romania cities graph problem, with a working memory of only 4 nodes [RN 104] ()
6) Depth-first search for the labyrinth problem. ()
7) A* for the labyrinth problem ()
8)  IDA* for the labyrinth problem. ()
9) Breadth-first for the n-queens problem. Maximal n=10 ()
10) Depth-first for the n-queen problem. Maximal n=10 ()
11) A* for the vacuum cleaner problem with 3 cells. ()
12) Iterative deepening for the vacuum cleaner problem with 3 cells. ()
13) RBFS search for the Missionaries-cannibals problem.  ()
14) Dept-first for the 8-puzzle problem. ()
15) Hill climbing for the 8-puzzle ()
16) Hill climbing with side stepping for the 8-puzzle. ()
17) Hill climbing with side stepping for the Romania cities problem. ()
18) A* for the Romania cities problem. ()
19) Depth-first search for the missionaries-cannibals problem. ()
20) RBFS for the vacuum cleaner problem with 4 cells. (AI-3 slide )
21) Uniform cost search for Romania cities problem. ()
22) SMA* for the labyrinth problem ()
23) Alpha Beta pruning for tic-tac-toe ()
24) A* algorithm for tic-tac-toe ()

25) Comparison between A* for Romanian cities problem, using f(n)=a*g(n) + b*h(n) for different values of a and b. 
Try a, b in {0.2 ,ÿ 0.5 , 0.7 , 1 , 1.2 , 1.5 , 2}. 
You will thus have 49 combinations and we are interested in the number of nodes developed (you will count them and save them in a text file in CSV format). 
e.g "0.2 ; 0.7 ; number_of_nodes_developed" and so on, 49 lines in total

26) RBFS for the Romanian cities problem, with keeping just 5 nodes in the memory.
27) Best-First search for the monkey and bananas problem
28) Min-Max search for chance games (Backgammon)
29) Bidirectional Breadth First Search for 8-puzzle problem
30) Bidirectional Breadth First Search for the Romania citities problem
31) AC-3 algorithm for the map colouring problem
32) AC-1 algorithm for the map colouring problem
33) AC-4 algorithm for the map colouring problem
34) AC-7 algorithm for the map colouring problem
35) AC-2001 algorithm for the map colouring problem

36) IDA* for the Romanian cities problem, with keeping just 5 nodes in the memory.
37) Bidirectional A* for the labyrinth problem.
38) Comparison between A* and Uniform Cost search for the labyrinth problem on the same labyrinth of size 20 by 20, then 30 by 30. 
Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited.
There will be a number of labyrinths which have no solution. The output should be written in a text file as CSV values. 
e.g. "AStar; 20; 20; 253.35; 17"  meaning: for A* on 20 by 20 averaged number of moves measured on 50 labyrinths is 253.35 ans 17 unsolvable problems
39) Comparison between A* and Depth-First search for the labyrinth problem on the same labyrinth of size 20 by 20, then 30 by 30. 
Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited.
There will be a number of labyrinths which have no solution. The output should be written in a text file as CSV values. 
e.g. "AStar; 20; 20; 253.35; 17"  meaning: for A* on 20 by 20 averaged number of moves measured on 50 labyrinths is 253.35 ans 17 unsolvable problems
40) Comparison between A* and Breadth-First search for the labyrinth problem on the same labyrinth of size 20 by 20, then 30 by 30. 
Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited.
There will be a number of labyrinths which have no solution. The output should be written in a text file as CSV values. 
e.g. "AStar; 20; 20; 253.35; 17"  meaning: for A* on 20 by 20 averaged number of moves measured on 50 labyrinths is 253.35 ans 17 unsolvable problems
41) Comparison between A* and Best-First search (with h as the objective function) for the labyrinth problem on the same 
labyrinth of size 20 by 20, then 30 by 30. 
Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited.
There will be a number of labyrinths which have no solution. The output should be written in a text file as CSV values. 
e.g. "AStar; 20; 20; 253.35; 17"  meaning: for A* on 20 by 20 averaged number of moves measured on 50 labyrinths is 253.35 ans 17 unsolvable problems
42) Comparison between bidirectional search A* and bidirectional Uniform Cost search for the labyrinth problem on the same labyrinth 
of size 20 by 20, then 30 by 30. 
Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited.
There will be a number of labyrinths which have no solution. The output should be written in a text file as CSV values. 
e.g. "Bidirectional AStar; 20; 20; 253.35; 17"  meaning: for A* on 20 by 20 averaged number of moves measured on 50 labyrinths is 253.35 ans 17 unsolvable problems
43) Comparison of the "Bidirectional Depth-First Search" with "Depth-First Search" for the labyrinth problem on the same labyrinth of size 10 by 10, then 20 by 20. 
Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited.
No backtracking admitted! A lot of the cases are unsolvable because of that! No ploblem with that. Be sure to implement BFS and not Backtracking!
For one problem, try solving it with at least 3 orderings of the moves. E.g. Up,Left,Right,Down and another 2 orderings. 
The move ordering is established at start.
There will be a number of labyrinths which have no solution. The output should be written in a text file as CSV values. 
e.g. "BiDir DFS; 20; 20; 253.35; 17"  meaning: for Bidirectional DFS on 20 by 20 averaged number of moves measured on 50 labyrinths is 253.35 ans 17 
unsolvable problems 
44) Comparison between "Bidirectional Uniform Cost Search" and "Uniform Cost Search" search for the labyrinth problem on the same labyrinth 
of size 20 by 20, then 30 by 30. 
Generate random labyrinths with 5, 10, 20, 25, 30 percents of the space as "walls". You should count the number cells visited.
There will be a number of labyrinths which have no solution. The output should be written in a text file as CSV values. 
e.g. "Bidirectional UCS; 20; 20; 253.35; 17"  meaning: for Bidirectional UCS on 20 by 20 averaged number of moves measured on 50 labyrinths is 253.35 ans 17 unsolvable problems 

Important Notes: 	
---------------
1) RECOMMENDED DUE DATE for the 1st assignment is in weeks 5-7 
2) When can you present your project? At the end of the lab 
OR at the end of the lecture, 
OR at the consultations (Thursdays from 9:40-11:10)
3) The assignment has to be DELIVERED IN PERSON, NO e-mails, because you will be asked questions about it.
4) Direct consequence of 2) and 3) is the in weeks 13 and 14 I can just see a limited number of projects and thus the rest will be 
REJECTED.

5) Any programming language is allowed, 2 stdents can take the same assignment, but they MUST do it in different prohramming languages.
6) For problems 31-35, those algorithms try to improve the standard backtracking algorithm by obtaining network of constraints that 
are "arc-consistent" thus eliminating some of the possible values that the variables implied in constrains can take. 
Thus less values=> faster backtracking. The problem proposed is a very simple one for which backtracking would run fast even 
without optimization. My purpose is to see you implement exactly that optimization, in order to see if you understood the algorithms. 
If you do not implement the correct algorithm, then the project is probably graded with zero. Eventually you can ask what you hadn't 
understood at consultations, or at the laboratory.
7) After presenting the project at class, you will be required to send it by e-mail with the following Subject "ASSGN1 AI". See points 2) and 3) also.

Bibliography (for 31-35):
1) Roman Bartak - Consistency Techniques, 1998,   http://kti.mff.cuni.cz/~bartak/constraints/consistent.html
2) Handbook of Constraint Programming, 2006 Elsevier, Chapter 3 C. Besiere - Costraint Propagation,   https://books.google.ro/books?id=Kjap9ZWcKOoC&pg=PA47&lpg=PA47&dq=ac-2001&source=bl&ots=QCCnBR1UQc&sig=tYGj6XXVILqndHgfvguBF3RXPnA&hl=ro&sa=X&ved=0ahUKEwiV64G1qJfQAhVEtRQKHYy6CMQQ6AEIWTAM#v=onepage&q=ac-2001&f=false

Bibliograpy for the rest:
1) Russel and Norvig ? Artifficial Intelligence, A Modern Approach, 2nd Edition
2) (AI-n slide m) means the lecture notes written by me. In the example, lecture ?n? silde ?m?