Announcements and Special Information

CSC447

3/13b – It is VERY UNLIKELY that most - perhaps even all - projects will be able to solve the 26 puzzle problems over 50 moves.  You may even begin to encounter space and time usage problems as early as 15 or 20 moves.
        This is because the branching factor of 4 means that the number of nodes occurring at each level of the search tree is 4 times the number at the previous level.  In other words we are looking at a 4^d space & time usage framework.  And, since Manhattan distance in many cases grossly underestimates, we can wind up with space/time usage closer to breadth-first than to depth-first search.
        One improvement you can make right away is to make sure that you do not go back to the node you just came from.  Then you would immediately reduce your branching factor from 4 to 3, so you are looking at 3^d instead of 4^d.  Another possibility is to look for switched tiles and add a set amount for that.  Even though switched tile configurations are only a small percentage of all possible configurations, suppressing the expansion of even some grossly underestimated nodes may help to narrow the search focus enough to make a difference.
        I will be making some intermediate length problems - specifically with number of moves = 16, 17, 18, 19, 21, 22, 23, & 24.  That way your program will not have to make such a huge jump (from 15 to 20; from 20 to 25).  I will email those, but it will only later this evening.

3/13 – If you are using some of the Python code I gave the class, keep in mind that for most of the problems you will need to either reset the counter or remove it entirely.  It essentially counts the number of nodes expanded.  For the "15 Moves" problem this is well over 1000.
        This also means that time and space usage will go up dramatically.

3/12 – Specs and other info for the project have been posted.  Also, please read this article on the Spatial Semantic Hierarchy and the power point.

3/6 – I just discovered that, for some reason, browsers cannot find Python code (or more precisely .py files).  So, if you tried to access the SemTab prover code, it is there, but I had to change the extension to .txt for the browsers to be able to find it. 

3/3 – In case you want to get a head start, the next homework assignment has been posted.

3/1 – Information on implementing the A* algorithm and seeking a better heuristic has been posted.

2/24 – Study material has been posted.

1/22 – If you are thinking "job market" here's something to keep in mind.

1/17 – Answers to homework problems will be posted here.

1/13 – Welcome to class!  Please check this page regularly for information that will be posted.