Hill Climbing (Steepest Ascent)

I believe that my previous blog has provided you a little hint about how the AI works.
In this blog, I will be discussing another heuristic algorithm which has slightly
better performance than Simple Hill Climbing. This algorithm is known as Hill
Climbing (Steepest Ascent).

It is better than the Simple Hill Climbing in a way that it chooses the better node
out of all the nodes and then proceeds, unlike Simple Hill Climbing in which it
chooses the first better node it encounters and then proceeds. Thereby missing the
next nodes which may have higher heuristic values than the current node and leading
to the wrong selection and falling into local maxima.

The algorithm is as follows:

1. Evaluate the initial state. If it also a goal state return it and quit. Otherwise
    continue with the initial state as current state.
2. Loop until a solution is found or until a complete iteration produces no change
    to the current state:
    a) Let SUCC be a state such that any possible successor of current state is
        better than SUCC.
    b) For each operator that applies to the current state do-
        i) Apply the operator and generate a new state.
       ii) Evaluate the new state, if it be a goal state then return it & quit.
            Else if it is better than SUCC then set SUCC to this state else retain
            SUCC as it was.
    c) If SUCC is better than the current state then  set current state to SUCC.

This gif image will clear the concept:

But, even this algorithm has the same disadvantage as Simple Hill Climbing.
It cannot backtrack to its parent node. If it gets trapped in the local
maxima, then nothing can help it to get out of that situation.

As this algorithm involves very slight change, that's why I am not providing
the example code this time. My previous blog will serve as a reference. Take
this as a challenge and try to implement it. When you implement it yourself,
you will start to get the essence of AI. So best of luck with that.
I hope you find my blogs helpful and keep following me.
Stay tuned and keep coding.
this algorithm.

Simple Hill Climbing

In this blog, I will be introducing you to the first heuristic algorithm Simple Hill Climbing.
It is relatively simple to implement, making it a popular first choice. Although more advanced
algorithms may give better results, in some situations hill climbing works well.

The algorithm is as follows :

Step 1: Evaluate the initial state. It is also a goal state, then return it and quit.
            Otherwise continue with the initial state as the current state.
Step 2: Loop until a solution is found or until there are no new operators left to be
            applied in the current state :
            (a) Select an operator that has not yet been applied to the current state and
            apply it to produce a new state.
            (b) Evaluate the new state.
                (i)    If it is a goal state, then return it and quit .
                (ii)   If it is not a goal state, but it is better than the
                        current state, then make it the current state.
                (iii)  If it is not better than the current state, then continue
                        in the loop.

Here "evaluate" denotes the heuristic function. It measures the heuristic value of the
node.

This algorithm does not evaluate all the successive nodes at once. The first node that
has the higher heuristic value than the current node is set as the current node.

This picture will clear your doubts.

But, there is a big disadvantage of this algorithm. It cannot traverse back to its
parent and gets stuck at an intermediate node. This intermediate node is known as Local
Maximum.

There are three types of situation which prevents the algorithm to reach the Global
Maximum :

Local Maximum : A local maximum is a state that is better than all its neighbours but
is not better than some other states farther away.

Plateau: A Plateau is a flat area of the search space in which a whole set of
neighbouring states have the same value.

Ridge : A ridge is a special kind of local maximum. It is an area of the search space
that is higher than surrounding areas and that itself has a slope.

To get a clear understanding, I have implemented Simple Hill Climbing algorithm
in the Four Queens Problem. The Four Queens Problem is a problem where four
queens are to be placed in such a way that no queens attack each other in
the 4 x 4 chessboard.

Here is the C# code :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Windows.UI;
using Windows.UI.Xaml.Controls;
using Windows.UI.Xaml.Media;
using Windows.UI.Xaml.Media.Imaging;
using Windows.UI.Xaml.Shapes;
namespace Win81AppSimpleHillClimbing4Queens
{
    public class FourQueensProblem
    {
        private int NumberOfQueensPlaced;
        private bool IsAttacked, IsPlaced;
        private Rectangle[,] Queens, Rects;
        private string Result;
        public FourQueensProblem(Rectangle[,] Queens, Rectangle[,] Rects)
        {
            this.Queens = Queens;
            this.Rects = Rects;
        }
        private void SetIndicatorYellow(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 255, 0));
        }
        private void SetIndicatorGreen(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 0, 255, 0));
        }
        private void SetIndicatorRed(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 255, 0, 0));
        }
        private void SetIndicatorNormal(int i, int j)
        {
            Rects[i, j].Stroke = new SolidColorBrush(Color.FromArgb(255, 9, 93, 240));
        }
        private bool CheckUpperLeftDiagonalCells(int i, int j)
        {
            bool culdc = false;
            int t;
            if (i == j)
                t = i;
            else if (i < j)
                t = i;
            else
                t = j;
            for (int x = 0; x < t; x++)
            {
                --i;
                --j;
                if (IsQueenPresent(i, j) == true)
                {
                    culdc = true;
                    break;
                }
                else
                    culdc = false;
            }
            return culdc;
        }
        private bool CheckUpperRightDiagonalCells(int i, int j)
        {
            bool curdc = false;
           
            for (int x = 0; x < 3; x++)
            {
                --i;
                ++j;
                if (i >= 0 && j < 4)
                {
                    if (IsQueenPresent(i, j) == true)
                    {
                        curdc = true;
                        break;
                    }
                    else
                        curdc = false;
                }
                else
                {
                    break;
                }
            }
            return curdc;
        }
        private bool CheckUpperTopCells(int i, int j)
        {
            bool cutc = false;
            int t = i;
            for (int x = 0; x < t; x++)
            {
                --i;
                if (IsQueenPresent(i, j) == true)
                {
                    cutc = true;
                    break;
                }
                else
                    cutc = false;
            }
            return cutc;
        }
        //Simple Hill Climbing
        public async Task Solve(int a, int b)
        {
            NumberOfQueensPlaced = 0;
            IsPlaced = true;
            for (int i = 0; i < 4; i++)
            {
                if(IsPlaced == true)
                {
                    for (int j = 0; j < 4; j++)
                    {
                        if (i == a && j < b)
                            continue;
                        else
                        {
                            SetIndicatorYellow(i, j);
                            await Task.Delay(TimeSpan.FromSeconds(1));
                            if (IsQueenAttacked(i, j) == false) //Evaluate
                            {
                                SetIndicatorGreen(i, j);
                                SetQueen(i, j); //set as current state
                                await Task.Delay(TimeSpan.FromSeconds(1));
                                IsPlaced = true;
                                ++NumberOfQueensPlaced;
                                break;
                            }
                            else
                            {
                                SetIndicatorRed(i, j);
                                await Task.Delay(TimeSpan.FromSeconds(1));
                                SetIndicatorNormal(i, j);
                                IsPlaced = false;
                            }
                        }
                    }
                }
                else
                {
                    break;
                }
            }
            if (NumberOfQueensPlaced == 4)
                Result = "Success";
            else
                Result = "Failure";
        }
        public string GetResult()
        {
            return Result;
        }
        //heuristic function
        private bool IsQueenAttacked(int i, int j)
        {
            IsAttacked = false;
           
            if (i == 0)
                IsAttacked = false;
            else if (CheckUpperLeftDiagonalCells(i, j) == true)
                IsAttacked = true;
            else if (CheckUpperTopCells(i, j) == true)
                IsAttacked = true;
            else if(CheckUpperRightDiagonalCells(i, j) == true)
                IsAttacked = true;
            else
                IsAttacked = false;
            return IsAttacked;
        }
        private void SetQueen(int i, int j)
        {
            ImageBrush ib = new ImageBrush();
            ib.ImageSource = new BitmapImage(new Uri("ms-appx:///Assets/chess_piece_queen2.png"));
            Queens[i, j].Fill = ib;
            Queens[i, j].IsTapEnabled = false;
        }
        private bool IsQueenPresent(int i, int j)
        {
            bool IsPresent = false;
            if (Queens[i, j].IsTapEnabled == false)
                IsPresent = true;
            else
                IsPresent = false;
            return IsPresent;
        }
        public void ResetQueens()
        {
            for (int i = 0; i < 4; i++)
            {
                for (int j = 0; j < 4; j++)
                {
                    SetIndicatorNormal(i, j);
                    Queens[i, j].Fill = null;
                    Queens[i, j].IsTapEnabled = true;
                }
            }
        }
    }
}


Here is the video of how it works :

That's the end of this blog. I hope you find it useful. Keep coding.

Search Classification

AI plays a vital role in searching algorithms. As we already know that AI means a thinking machine,
capable of acting like Humans. Humans have the capability to improvise in the middle of doing a
work. Similarly, machines can also be programmed to improvise while searching. Now we will see
how this can be achieved.

The searching algorithms can be divided into two main categories :
1. Blind / Uninformed
2. Heuristic / Informed

1. Blind / Uninformed searching technique means that search is not aware of its position
in the search space. For example - Breadth First Search, Depth First Search, etc.

2. Heuristic / Informed searching technique means that the search is aware of its position
in the search space. It uses a heuristic function to improvise its searching technique.
It can calculate how much distance it has covered and predict how many calculations
are required to reach its target.
For example - Simple Hill Climbing, Best First Search, A*, AO*, etc.

A heuristic function is a function that maps from the problem
state descriptions to measures of desirability, usually
represented as numbers.

The best example for demonstrating heuristic function is the 8-puzzle problem.
The 8-puzzle is a small board game for a single player; it consists of 8
square tiles numbered 1 through 8 and one blank space on a 3 x 3 board.
Moves of the puzzle are made by sliding an adjacent tile into the position
occupied by the blank space, which has the effect of exchanging the positions
of the tile and blank space. Only tiles that are horizontally or vertically
adjacent (not diagonally adjacent) may be moved into the blank space.
The goal is to set all the numbered tiles in ascending order starting
from the top left corner.

Let the heuristic function be like the total number of numbered tiles that
are exactly in its place. For example, Tile 4 is at the position 4.

From the above picture it is clear that we will select that state which has
higher heuristic value as it leads us to the goal perfectly.

That's an example of heuristic function. There is no hard and fast rule that
a problem will have same heuristic function. It completely depends on the
programmer how to solve the problem. For instance, anyone can make a heuristic
function that counts how tiles are not in places.

Now a formal definition of heuristic search process:
A heuristic is a technique that improves the efficiency of a search process,
possibly by sacrificing claims of completeness.

I will describe the heuristic algorithms in the next blog. Till then, keep coding.

Production System in AI

Okay!!! So before diving into deeper in the forest of AI, let us understand some basic terminologies
like what is problem, problem characteristics, state space, etc. This might seem little boring to
you but we need to discuss about these terminologies to proceed further. So I'll quickly give you
the idea about what they are :

A problem consists of four parts-
1. Initial state(s)
2. Set of actions
3. Goal test function
4. Path cost function

A state space comprised of all feasible state corresponding to the problem.
Solution may be a path from initial state to goal state incorporating various intermediate
states.

The characteristics of problem are :
1. Is the problem decomposable?
2. Can solution steps be ignored or undone ?
3. Is the problem universe predictable?
4. Is a good solution must, without comparing all other solutions ?
5. Is the desired solution a path to a state or simply a state?

Now, the important topic starts from here. Every problem must be solved using a system.
It is one of the very basic necessities of AI to solve a problem.

To build a system that can solve the problem must follow these :
1. Precise problem definition & specification of states
2. Analysis of important features
3. Isolate & represent task-knowledge
4. Choose the best problem solving techniques & apply it.

A system that solves a problem in AI is known as a Production System.
Describing & performing the search process during goal state determination will be done
by the production system. It consists of-
1. A set of rule : A set of do(s) and don't(s).
2. Database/knowledgebase : A collection of data or knowledge.
3. Control strategy : The control flow of the program for the solving the problem.
4. Rule applier : As the name implies, it applies the appropriate rule to the system.

A little more description about Control Strategy :
A good control strategy may ensure a goal state with
comparatively reasonable path cost. Two of its features are vital
1. Dynamic : will ensure newer and newer state only to enhance possibility of obtaining a goal state.
2. Systematic : this feature will drive it into either of the solution paths through least effort.

For simplicity, here we will take the example of Water Jug Problem for the better understanding of Production System.

Water Jug Problem
Two jugs of size 7 and 4 gallons and one liquid source with enough amount can be availed. The
container contains no scaling on them. Container can be filled, emptied or exchange liquid
between themselves. Perform operation in such an way that 7 gallon jug contains 2 gallon of water.

Production Rule :
1. (x,y) -> (x,4) Fill-up the 4-gallon Jug from Water Source.
     if(y<4)
2. (x,y) -> (7,y) Fill-up the 7-gallon Jug from Water Source.
     if(x<7)
3. (7,y) -> (7-(4-y),4) Fill-up the 4-gallon Jug from the 7-gallon Jug.
     if(y<4)
4. (x,4) -> (7,4-(7-x)) Fill-up the 7-gallon Jug from the 4-gallon Jug.
     if(x<7) && (x>2)
etc.

Knowledge Base :
7-gallon Jug
4-gallon Jug
Water Source

Control Strategy :
This problem can be solved in many ways. A small part of the search tree or graph will help you to visualise the different possibilities. But not all the possibilities will be followed. Only the path with the least effort will be taken.

Rule Applier :
x    y    Rule / Operation
0    0    Initial state
7    0    Fill-up the 7 gallon jug from the water source
3    4    Fill 4g jug from 7g jug
3    0    Empty the 4g jug
0    3    Fill 4g jug from 7g jug
7    3    Fill-up the 7g jug from the water source
6    4    Fill 4g jug from 7g jug
6    0    Empty the 4g jug
2    4    Fill 4g jug from 7g jug

In this way, this problem can be solved with the least effort.
Here is a small video for the solution.

Intelligence requires Knowledge

“Every knowledgeable person is not intelligent but every intelligent person is knowledgeable”.

This statement provides a very strong foundation for the above mentioned Title. But first of all, what is knowledge? It is the internal representation of facts. A single fact can vary from person to person’s perspective in terms of knowledge. We will come to its detailed explanation later.

Knowledgeable person may have huge knowledge base but fails to use it when required in real life situation. But an intelligent person knows when and how to use that knowledge base to solve a problem. This intelligence makes human, different and superior from every other thing.

Artificial Intelligence also requires knowledge. But this knowledge can’t be anything. There are some knowledge characteristics:
Desirable property — Indispensability.
Less desirable Property -
1. It is voluminous.
2. It is hard to characterize accurately.
3. It is constantly changing.
4. There is a difference between the way it is organized and it is used.

AI technique is a method that exploits knowledge .
Knowledge should be represented so that -
1. Generalisation. Situation that share same property are grouped together.
2. Data provider must understand it.
3. Can be modified to rectify errors.
4. Can be used, if partially or almost complete but not entirely.

It is not yet over, there is more to it!!

Turing Test for a Thinking Machine

Turing Test is a way to test whether the machine is actually capable of thinking by itself or not. The Turing Test involves the factors like :

1. Knowledge Representation
2. Automated Reasoning
3. Natural Language Processing
4. Machine Learning
5. Computer Vision
6. Robotics

Factors from 1 to 4 are the basic requirements for a machine to be thinking. Hence, it is also known as Partial Turing Test.

Why AI needed?

In earlier days, AI was only used for game playing like Chess, Chinese Checker, Tic Tac Toe, Tower of Hanoi, etc. There was a reason behind this. To code games like Chess or other board games, all possible states had to be calculated & stored in memory if it was done in a deterministic manner. Now suppose a chess match takes 50 moves & 50 countermoves and there are 32 chess pieces(including King, Queen, Knight, Pawns, etc.). Now to calculate & store all the possibilities of this match will require 32¹+32²+……….32⁹⁹+32¹⁰⁰ bits of memory which almost Zetabytes of memory for one single match. So it was never possible to code all the possibilities of chess in deterministic fashion. That’s why AI was needed to deal with non-deterministic ways to play chess. As we have already mentioned in our previous story that AI deals with inexactness, incompleteness, partial knowledge. As this story might bore you if I provide just theoretical concept. So I have included a video of one small Windows Store App(more specifically a game, although I didn’t publish it Windows Store) made by me just to give you a hint on how much it becomes difficult to code this Tic Tac Toe in a deterministic fashion.