## A* Algorithm in Python to solve 8 puzzle problem

My team got this as A* algorithm assignment in Artificial Intelligence class few years ago taught by Mrs. Afiahayati, Ph.D. We should create an implementation of A* algorithm (read: “A” Star) to solve 8 puzzle problem. This puzzle problem is the small version of 15 sliding puzzle game.

## A* Algorithm

In my opinion A* Algorithm (read more about it here) is looks like combination of Breadth First Search (BFS) and Depth First Search (DFS) algorithm (or maybe Dijkstra’s too(?)). It’s using Heuristic scoring to estimate the step from vertex to goal so make the system may running faster, and like Dijkstra’s, it’s a complete search which always finding a best solution. Read this to get better explanation.

My team agreed to use Manhattan distance to estimate distance between the current state and the goal state (h) and count the number of step as exact cost (g).

## Implementation

I wrote the code using Python. And after several hours coding I found python have a “magical” function that make easy to write 🙂 My first implementation was not using any class at all and it made the code hard to read. After I saw this implementation, I realize that code is much prettier than mine, so I rewrite my code using Node class with similar class concept from that code.

See the complete source code on Github

## How Do I Learn Neural Network (and Deep Learning)

First, I am nobody in this topic, please don’t hesitate to give better suggestion. This is actually just a “documentation” about my experience when I work on my undergraduate thesis in 2015. Once again, please don’t hesitate to discuss and give better suggestion about this topic, or.. correct my English if I made some mistakes 🙂

Background

Okay, before I tell you my story, I’ll tell you about my background when I started to learn neural network. I wrote this section only have one intention, to make you easy measure what you need, nothing else.

1. I have familiarity with some of mathematical symbols, like how to read sigma symbol, derivative symbol and many others (but not every symbols).
2. I have familiarity with basic math operation like derivative function, algebra, matrix and vector operation (but only “the basic”).
3. I’ve never coded in python, but I’ve been using C++ around 2-3 years and I used to code  Matlab style programming language in some project before (and thanks, this knowledge is very helpful)
4. I studied the Introduction of Artificial Intelligence at the fourth semester in college, but I won’t said I did it well 🙁

After a month googling randomly, I started to make a list what should I learn, the order of the list below it’s just the best order in my opinion. In my experience I jumped many times over the topic because at that time, I didn’t know what I didn’t know 🙁

If you want to learn about Deep Learning, lets begin with: What is Machine Learning?

Then start to learn about Neural Network

Let’s do some math, Backpropagation?

I suggest you to fully-understand this algorithm in order to give some intuitions to help you in model tuning or error handling when you start implement the neural network

• Easy start : I watched again the neural network demistifyed, and slowly got the intuition how backpropagation work, I followed and tried the math step-by-step
• Watch the 4th week on Coursera Introduction to Machine Learning
• Try the example of how backpropagation works : https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/
• Read carefully the second chapter from http://neuralnetworksanddeeplearning.com/
• And if you start thinking they have different formula / calculation / interpretation, start to prove that you are wrong. I started to compare all the calculations to understand more

Python for machine learning?

So what is Deep Learning?

What is Convolutional Neural Network (I use CNN in my undergraduate thesis)?

Backpropagation in CNN?

I don’t know it is necessary or not, but I learned it. I think if you understand the basic of backpropagation it’s enough. But if you are curious how backpropgation through max pooling or convolution layer, it does not hurt to learn it.

And…great, It’s done, That’s all my references that I used when I did my undergraduate thesis, I hope it will be useful for someone :/ or at least for me in the future 🙂