Lab codes for Artificial Intelligence Lab of Level 3 Term 2 at BUET CSE undergrad
A* is a well known traversal algorithm in searching based AI systems. It is used to find exact solution paths in large search spaces. The main idea is to do a best-first search: at each node visit the child with best result(minimum cost/maximum profit etc.), where result is estimated using a heuristic appropiate for the problem. An admissible heuristic gurantees that A* search will find exact path from start search node to goal search node.
We were given a classical problem of N-puzzle (ordering number blocks in square grid using least number of moves) and had to solve the problem using two heuristics: number of incorrect blocks and sum of distances from blocks to goals.
Adverserial searches are another important searching paradigm in AI, where competing goals/agents make moves against each other and try to reach a goal in optimal way. Minimax algorithm is a common adverserial search algorithm used in game playing/decision making. Here, two agents play a zero sum game and at each step, each try to exhaust all possible scenarios as far into future moves it can and find optimal move. Thus for a optimization goal, one tries to minimize, other tries to maximize.
In this project, we created a game playing system that uses minimax algorithm with alpha beta pruning (stopping search down paths that will be definitely worse than current best solution) to play the Mancala game. We implemented the algorithm with both normal mode and alpha beta pruning enabled. Then we created a system where the computer can play Mancala against user and also against itself (opposite moves). It was fun to see computer winning games against me!
For our final search algorithm assignment, we experimented on randomized search with greedily created initial solution. The specific algorithm was GRASP (Greedy Randomized Adaptive Search Procedure).
Here, first a tentative solution is created by greedily expanding a randomly/heuristically selected starting solution/solution element. Then a local search is done with the greedy solution as base. This process is repeated many times and the best solution is our answer to the given problem. The random starting solution/solution elements ensure variety, while the greedy initial construction quickly gives a tentative solution in most problems. The local search at the end ensures we reach a local optima or at least move towards it in the search space.
The abstraction aside, the problem we solved was max-cuts in graph (set of edges in weighted graph which joins two disjoint vertice sets and sums to largest weight). Our initial solution elements were largest weighted edges and they were expanded both greedily and semi-greedily (randomly selecting from top additions found greedily). The local search was done by rearranging the found solution of two disjoint vertices.
This was my most favourite assignment. We finally moved out of searching in solution space and put the machine to study :3. We recreated the ID3 algorithm for making decision trees. In simple words, it takes the given dataset and creates a tree by iteratively choosing features that quickly leads to a decision. This is done by choosing features whose values help split the dataset in parts that have uneven composition in terms of decisions. Mathematically this is done by choosing the most information rich features (the ones with highest entropy).
I completed the whole project in C++ using structs and functions. The dataset was well known and well formatted, so I wrote a simple parser for it. I also wrote the ID3 algorithm and applied it on the dataset. I made my solution as modular as possible. I also wrote a text based tree visulalizer to check validity of solution. My implementation achieved the usual score of decision trees in this dataset, over 85%. I used cmake for buiild and used annotated doxygen comments to help development.